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.
16029762
Preemptive Scheduling with Variable Profile, Precedence Constraints and Due Dates
Abstract This paper is concerned with the problem of scheduling preemptive tasks subject to precedence constraints in order to minimize the maximum lateness and the makespan. The number of available parallel processors is allowed to vary in time. It is shown that when an earliest due date first algorithm provides an optimal nonpreemptive schedule for unit-execution-time (UET) tasks, the preemptive priority scheduling algorithm, referred to as smallest laxity first, provides an optimal preemptive schedule for real-execution-time (RET) tasks. When the objective is to minimize the makespan, we get the same kind of result between highest level first schedules solving nonpreemptive tasks with UET and the longest remaining path first schedule for the corresponding preemptive scheduling problem with RET tasks. These results are applied to four specific profile scheduling problems and new optimality results are obtained.
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.
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.
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.
14189544
Verification, refinement and scheduling of real-time programs
Abstract A real-time program can be developed by refining a specification into program code. Verification of the timing properties of the program is then usually done at two levels: verification of the ordering of timed actions in the program and proof that execution of the program on a specific system will meet its timing requirements. Refinement is done within a formal model but the second step requires a different framework in which scheduling theory analysis is used and actual program execution times can be taken into account. The implementation of a program on a system is said to be feasible or schedulable if it will meet all the timing deadlines. This paper shows how the feasibility of scheduling a real-time program can also be proved as a step in the refinement of the program from its specification. Verification of this step of refinement makes use of methods from scheduling theory within a formal system development framework.
3399031
On 2-factors in claw-free graphs
Abstract A graph is said claw-free if it contains no induced subgraph isomorphic to K 1,3 . We prove that if G is a claw-free graph with minimum degree δ ⩾4, then G contains a 2-factor with at most 6 n /( δ +2)−1 components. Moreover, together with a theorem of Choudoum and Paulraj (J. Graph Theory 15 (1991) 259–265) and one of Anstee (J. Algorithms 6 (1985) 112–131), it is polynomial (in O( n 3 )) to construct such a 2-factor.
13004956
Consistency checking of UML requirements
This paper discusses how to check consistency of UML requirements model which consists of a use case model and a conceptual class model with system constraints. Based on a given semantics, the requirements consistency can be defined and checked formally. The consistency among use cases and constraints are classified into five types. A system operation of interaction between actor and system is formally defined as a pair of pre and post conditions. An atomic use case is described as one system operation, and a composed use case may be defined as several system operations described by an activity diagram. Thus, each use case can also be modelled as a pair of pre and post conditions by composing the pre and post conditions of system operations by introducing a sequence composition operation. Requirement consistency can be logically checked based on the semantics. A simple library system is used as a case study to illustrate the feasibility of the method.
9219349
Flexible Secure Multicasting in Active Networks
In this paper we describe an alternative, flexible approach to multicast security in active networks. Traditional schemes for securing multicast communication have key management and scalability problems for many typical applications. In addition, traditional mechanisms are not capable of expressing flexible, situational security policies for multicast sessions and participants. Our scheme exploits the computational power of active networks to provide dynamic, flexible security for multicast applications. One of the main advantages of our scheme is the low communication and key distribution overhead associated with multicast group management. Our approach is based on the Seraphim security architecture implementation, which uses active capabilities for access control. Seraphim is an extensible, reconfigurable security architecture that is flexible and accommodates a wide variety of security policies and mechanisms. It also provides applications and users the ability to create dynamically and enforce highly customized and situational policies. Using these policies we have developed several secure multicast applications that demonstrate the flexible nature and low overheads associated with our architecture.
18394118
Formalizing Real-Time Scheduling as Program Refinement
This paper shows how the feasibility of scheduling a realtime program consisting of a number of parallel processes (tasks) can be proved as a step in the refinement of the program from its specification. Verification of this step of refinement makes formal use of methods and results from real-time scheduling theory.