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.
17231470
Dynamic scheduling of parallel computations
Structures of parallel programs are usually represented by task graphs in the scheduling literature. Such graphs are sometimes obtained at compile time. In many other cases, however, they can be determined only at run time. In this paper, we consider the scheduling of parallel computations whose task graphs are generated at run time. We analyze the case where the task graph is a random out-tree. When the number of offspring of a task has a geometric distribution whose parameter is decreasing and convex in the level, then the breadth-first policy stochastically minimizes the makespan. If, however, this parameter is increasing and concave, then the depth-first policy stochastically minimizes the makespan.
17293889
Complexity of Task Graph Scheduling with Fixed Communication Capacity
Consider a scheduling problem of parallel computations in multiprocessor systems. Let a parallel program be modeled by a task graph, where vertices represent tasks and arcs the communications between tasks. An interprocessor communication time incurs when two tasks assigned to two different processors have to communicate. Such a scheduling problem has recently been studied in the literature, mostly for the case where interprocessor communication times are fully determined. In this paper, we consider the scheduling problem with communication resource constraints. More specifically, we consider the case where all interprocessor communications take place on a network of bounded capacity. We consider two variants of the problem: communications with independent-data semantics and common-data semantics. We show that even for very specific subproblems, viz. scheduling of general graphs on two processors and scheduling of binary trees on an infinite number of processors, the minimization of the makespan of parallel programs in such a multiprocessor system is strongly -hard. We first establish the results for the case of capacity 1, referred to as the single-bus system. We then extend the results to the more general case of fixed communication capacities. As a consequence, the general scheduling problem of parallel programs with communication resource constraints is strongly -hard. These results are to be contrasted with the corresponding scheduling problems without contraint on the communication capacity, where the two-processor case has unknown time complexity and the infinite-processor case is polynomial. Our results are also extended to the case of broadcasting communications, and can be applied to multiprocessor systems with shared memory.
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.
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.
7929531
Closed-Form Deterministic End-to-End Performance Bounds for the Generalized Processor Sharing Scheduling Discipline
The Generalized Processor Sharing (GPS) schedulingdiscipline is an important scheduling mechanism that can support both class isolation and bandwidth sharing among different service classes, thus making itan appealing choice for networks providing multiple services with Quality-of-Service guarantees. In this paper, we study a broad classof GPS networks known as Consistent Relative Session Treatment}(CRST) GPS networks and establish closed-form end-to-end performance boundsfor CRST GPS networks. This result generalizes the results of Parekhand Gallager (1994) where simple, closed-form end-to-end performancebounds are derived for a special sub-class of CRST GPS networks, theso-called Rate Proportional Processor Sharing (RPPS) GPS networks, but performance bounds for the general CRST GPS networks do not haveclosed-form. Our result is obtained through the notion of CRSTpartition, which in fact yields a broader class of CRST GPS networksthan the one originally defined in (Parekh and Gallager, 1993). Moreover,our approach is quite general. It not only applies to the deterministicanalysis of GPS networks, but can also be employed in the study of GPSnetworks in a stochastic setting.
11711500
Verification of schedulability for real-time programs
Assume that a real-time programPT consisting of a number of parallel processes is executed on a system having a setPr of processors which are shared between the processes by a real-time schedulerST. Assume that PT must meet some timing deadlines. We show that such an implementation ofPT can be represented as a transformationL(PT) and that the deadlines ofPT will be met if they are satisfied by the timing properties of the transformed program. The condition for feasibility of a real-time program executed under a scheduler is formalized and rules are provided for verification. The schedulerST can be specifiedgenerically and applied to different programs, making it unnecessary to introduce low-level operations such as scheduling primitives into the programming language. Thus real-time program specification and Schedulability can be considered in the same framework and the timing properties of a program can be determined at the specification level. By separating the specification of the scheduler from that of the program, the feasibility of an implementation can be proved by considering a scheduling policy rather than its implementation details.
11468499
Secure Information Flow in Mobile Bootstrapping Process
The security of bootstrapping is very important for mobile computing. In this paper, we present the bootstrapping process of the Cherubim security system which uses a smartcard to allow a mobile Cherubim client to universally access remote standard services. In order to prevent any leakage of sensitive information, we apply a type system for secure flows to the bootstrapping source codes. The type system guarantees that well-typed programs satisfy a noninterference security property. This means that the program does not ``leak'''' sensitive data. The type system also produces principal types for type-correct programs that characterize how programs can be called securely. The analysis demonstrates that the type system can ensure secure flow enforcement.
3756850
Clustering algorithms for content-based publication-subscription systems
We consider efficient communication schemes based on both network-supported and application-level multicast techniques for content-based publication-subscription systems. We show that the communication costs depend heavily on the network configurations, distribution of publications and subscriptions. We devise new algorithms and adapt existing partitional data clustering algorithms. These algorithms can be used to determine multicast groups with as much commonality as possible, based on the totality of subscribers' interests. They perform well in the context of highly heterogeneous subscriptions, and they also scale well. An efficiency of 60% to 80% with respect to the ideal solution can be achieved with a small number of multicast groups (less than 100 in our experiments). Some of these same concepts can be applied to match publications to subscribers in real-time, and also to determine dynamically whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We demonstrate the quality of our algorithms via simulation experiments.
8433230
A biologically inspired congestion control routing algorithm for MANETs
This paper presents EARA-CG, an improved version of a swarm-intelligence ad hoc routing algorithm EARA introduced in the work of Z. Liu et al. (2004). Based on the understanding of the evolutionary cooperation in the biological swarm, we use the principle of swarm intelligence to reinforce good quality routes with only local communication. The concept of stigmergy is adopted to reduce the amount of control traffic. By locally monitoring the network transmission queue and other MAC layer information, this algorithm can forward data traffic through paths that avoid network hotspots. The data traffic influences routing table updates at each node. We also discuss an evaluation methodology to simulate ad hoc networks, and the simulation results show that this novel routing algorithm scales well to a variety of network conditions.
16465387
Rapid modeling of animated faces from video
Generating realistic 3D human face models and facial animations has been a persistent challenge in computer graphics. We have developed a system that constructs textured 3Dface models from videos with minimal user interaction. Our system takes images andvideo sequences of a face with an ordinary video camera. After five manual clicks ontwo images to tell the system where the eye corners, nose top and mouth corners are, thesystem automatically generates a realistic looking 3D human head model and the constructed model can be animated immediately. A user with a PC and an ordinary camera can use our system to generate his/her face model in a few minutes. Copyright © 2001 John Wiley & Sons, Ltd.