Scheduling Parallel Computations
Raymond Reiter · Journal of the ACM · 1968
A model for parallel computations is given as a directed graph in which nodes represent elementary operations, and branches, data channels. The problem considered is the determination of an admissible schedule for such a computation; i.e. for each node determine a sequence of times at which the node initiates its operation. These times must be such that each node, upon initiation, is assured of having the necessary data upon which to operate. Necessary and sufficient conditions that a schedule be admissible are given. The computation rate of a given admissible schedule is defined and is shown to have a limiting value 1/π where π is a parameter dependent upon the cycles in the graph. Thus, the computation cannot proceed at a rate exceeding 1/π. For γ ≥ π, the class of all periodic admissible schedules with period γ is characterized by the solution space of a certain system of linear inequalities. In particular, then, the maximum computation rate of 1/π is attainable under a periodic admissible schedule with period π. A class of all-integer admissible schedules is given. Finally, an algorithm is given for the determination of the number of initiations of each node in the graph defining a parallel computation. An example for a system of difference equations is given in detail.
Cited by 229 works. doi:10.1145/321479.321485 Open-access PDF
Authors
References
- Sequencing Aspects of Multiprogramming
- Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing
- Parallel Processing in a Restructurable Computer System
- FINDING A CYCLE IN A GRAPH WITH MINIMUM COST TO TIME RATIO WITH APPLICATION TO A SHIP ROUTING PROBLEM
- A Study Of A Model For Parallel Computations.
- An Automatic Sequencing Procedure with Application to Parallel Programming