252821
Performance Analysis of Stochastic Timed Petri Nets Using Linear Programming Approach
Stochastic timed Petri nets are a useful tool in the performance analysis of concurrent systems such as parallel computers, communication networks and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for practical problems due to their sizes. In this paper, we provide a method to efficiently compute upper and lower bounds for the throughputs and mean token numbers for a large class of stochastic timed Petri nets. Our approach is based on uniformization technique and linear programming.
14587701
Routing and Transmitting Problems in de Bruijn Networks
De Bruijn graphs, both directed and undirected, have received considerable attention as architecture for interconnection networks. In this paper, we focus on undirected de Bruijn networks of radix d and dimension 0, denoted by UB(d, 0). We first discuss the shortest-path routing problem. We present properties of the shortest paths between any two vertices of UB(d, 0) and propose two shortest-path routing algorithms, one of which has linear time complexity. Secondly, we study the transmitting problem. We establish a lower bound for the optimal transmitting time which implies in particular that the optimal transmitting problem is trivial for UB(d, 0) when d/spl ges/5. We present a transmitting scheme on undirected binary de Bruijn networks UB(2, n) with transmitting time n-1 for n/spl ges/5, and conjecture that the optimal transmitting time is n-1 for UB(2, n), and n for U8(3, n) and UB(4, n).
12816052
Worst-Case Analysis of Scheduling Heuristics of Parallel Systems
Abstract It is well-known that most scheduling problems arising from parallel systems are NP -hard, even under very special assumptions. Thus, various suboptimal algorithms, in particular heuristics, were proposed in the literature. Worst-case error bounds are established in this paper for heuristics of makespan minimization of parallel computations. Different parallel computation models are investigated, including interprocessor communication, task duplication, multiprocessor tasks and parallel tasks. Due to the heterogeneity of these systems, scheduling heuristics can be far away from the optimal solutions. These bounds provide insights to the design of scheduling heuristics in order to obtain good performance guarantee than arbitrary heuristics. Moreover, the performance guarantee of these special heuristics is independent of model parameters such as the maximal duplication degree, processor requirement and parallelization degree.
29521719
Improving the Stability Characteristics of Asynchronous Traffic in FDDI Token Ring
The Fiber Distributed Data Interface (FDDI) token ring protocol supports two classes of traffic : synchronous and asynchronous. The time constraint mechanism of FDDI garantees the transmission delay of synchronous traffic. A Target Token Rotation Time (TTRT) being fixed, the FDDI protocol ensures that the token rotation time is always bounded above by twice TTRT. In this paper, we consider the stability issues of the asynchronous traffic in the FDDI protocol. We obtain sufficient and necessary stability conditions which indicates how the choice of TTRT affects the stability of the system. We suggest an improvement of the FDDI protocol for which the token rotation time is also bounded by twice TTRT. We show that the stability conditions of the new protocol are weaker (and thus it enables to transmit more asynchronous packets). This protocol is also easier to implement.
3758350
An Analytical Approach to the Performance Evaluation of Master-Slave Computational Models
Abstract Many stochastic models and analysis techniques have been proposed in the literature during the last two decades for the performance evaluation of parallel and distributed systems. However, few of them are directly applicable to practical systems which are generally too complex. In this paper, we analyze performances of the master–slave computational model, one of the most commonly used models in parallel and distributed computations. We propose a hybrid analytical approach by using techniques from the theories of both stochastic task graphs and queueing networks. We apply this method to the analysis of a computational chemistry application running on a Transputer based system. The proposed method turns out to be not only very efficient in time for large systems but also very accurate compared to measuring.
774892
Single Machine Scheduling Subject To Precedence Delays
Abstract A single-machine scheduling problem with precedence delays is analyzed. A set of n tasks is to be scheduled on the machine in such a way that the makespan is minimized. The executions of the tasks are constrained by precedence delays, i.e., a task can start its execution only after any of its predecessors has completed and the delay between the two tasks has elapsed. In the case of unit execution times and integer lengths of delays, the problem is shown to be NP-hard in the strong sense. In the case of integer execution times and unit length of delays, the problem is polynomial, and an O(n2) optimal algorithm is provided. Both preemptive and non-preemptive cases are considered.
28594120
Pattern recognition using Markov random field models
In this paper, we propose Markov random field models for pattern recognition, which provide a flexible and natural framework for modelling the interactions between spatially related random variables in their neighbourhood systems. The proposed approach is superior to conventional approaches in many aspects. This paper introduces the concept of states into Markov random filed models, presents a theoretic analysis of the approach, discusses issues of designing neighbourhood system and cliques, and analyses properties of the models. We have applied our method to the recognition of unconstrained handwritten numerals. The experimental results show that the proposed approach can achieve high performance.
31153136
An Adaptive Scheduling Algorithm for Molecule Docking Design on Grid
Grid provides a promising platform for the efficient execution of drug molecular docking design. Scheduling such applications is challenging for the heterogeneity, autonomy, and dynamic adaptability of grid resources. Assuming resource owners have a preemptive priority, we propose an adaptive algorithm of jobs scheduling based on time balancing strategy, which solves parallel molecular docking task by using the idle resources in the Grid. A mathematical model is developed to predict performance, which also considers systems with heterogeneous machine utilization and heterogeneous service distribution. According to the time balancing policy, ligands are partitioned into several subtasks and scheduled. The expected value of molecular docking completion time is predicted with performance model. To get better parallel computing performance, an optimal subset of heterogeneous resources with the shortest parallel executing time of tasks can be selected with the algorithm.
12789585
A Secure Agent Architecture for Sensor Networks
Advances in sensor and wireless technologies will enable thousands, or even millions of small but smart sensors to be deployed for a wide range of monitoring applications. The sensor networks must be dynamically configurable and adaptive in order to response actively to events. Security must also be built into sensor networks at the very initial design stage to prevent any potential threats. This paper presents a design of a generic software architecture based on tiny active agents for sensor networks. The architecture has built-in security components. This architecture will significantly benefit the dynamic and secure deployment and configuration tasks of large sensor networks for various applications.
16274304
Face detection and tracking in video using dynamic programming
Face detection and tracking are important in video content analysis since the most important objects in most video are human beings. This paper proposes a new approach for combined face detection and tracking in video. The face detection algorithm is a fast template matching procedure using iterative dynamic programming (DP). Although the face detection algorithm is designed for frontal face, the same mechanism can also be applied to track non-frontal faces with online adapted face models. Due to the essence of template matching, the algorithm is capable of comparing the similarity among different faces, which makes it suitable for tracking the same face that occur at disjointed temporal locations in video. While the proposed face detection method provides comparable accuracy as the neural network based approach, it is much faster.
3730862
Distributed Resource Allocation in Stream Processing Systems
Distributed stream processing architecture has emerged as appealing solution to coping with the analysis of large amount of data from dispersed sources. A fundamental problem in such stream processing systems is how to best utilize the available resources so that the overall system performance is optimized. We consider a distributed stream processing system that consists of a network of cooperating servers, collectively providing processing services for multiple data streams. Each stream is required to complete a series of operations on various servers. We assume all servers have finite computing resources and all communication links have finite available bandwidth. The problem is to find distributed schemes to allocate the limited computing resources as well as the communication bandwidth in the system so as to achieve a maximum concurrent throughput for all output streams. We present a generalized multicommodity flow model for the above problem. We develop a distributed resource allocation algorithm that guarantees the optimality. We also provide detailed analysis on the complexity of the algorithm and demonstrate the performance using numerical experiments.