A comparison of list schedules for parallel processing systems

Communications of the ACMPublished 1 December 1974Open access

Thomas L. Adam, K. Mani Chandy, J. R. Dickson

DOI10.1145/361604.361619

Source URL

Citations613

SJR quartileQ1

SJR score1.15

SNIP3.34

View PDF

TL;DR

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks and a dynamic programming solution for the case in which execution times are random variables is presented.

Abstract

The problem of scheduling two or more processors to minimize the execution time of a program which consists of a set of partially ordered tasks is studied. Cases where task execution times are deterministic and others in which execution times are random variables are analyzed. It is shown that different algorithms suggested in the literature vary significantly in execution time and that the B-schedule of Coffman and Graham is near-optimal. A dynamic programming solution for the case in which execution times are random variables is presented.

Keywords

Computer ScienceEngineering

Bell System Technical JournalBounds for Certain Multiprocessing Anomalies

1,617 Citations1966Ronald Graham

Acta InformaticaOptimal scheduling for two-processor systems

610 Citations1972E. G. Coffman, Ronald Graham

It is proved that the algorithm gives optimal solutions and its application to preemptive scheduling disciplines is discussed.

IEEE Transactions on ComputersOptimal Scheduling Strategies in a Multiprocessor System

209 Citations1972C. V. Ramamoorthy, K. Mani Chandy +1 more

A set of techniques that can be used to optimally schedule a sequence of interrelated computational tasks on a multiprocessor computer system using a directed graph model to represent a computational process are described.

IEEE Transactions on ComputersBounds on the Number of Processors and Time for Multiprocessor Optimal Schedules

172 Citations1973Eduardo B. Fernández, B. Bussell

A unified formulation for lower bounds on the minimum number of processors and on time is presented and these lower bounds are sharper than previously known values and provide a general framework that gives insight for deriving simplified expressions.

Journal of the ACMProduction and Stabilization of Real-Time Task Schedules

87 Citations1967Glenn K. Manacher

A coherent theory of task-list control is developed, in which the nature of peculiarities of this control scheme is brought under systematic study and a number of potentially useful results are derived.

View PDF

A survey of techniques for recognizing parallel processable streams in computer programs

79 Citations1969C. V. Ramamoorthy, Mercedes González

State-of-the-art advances---in particular, anticipated advances generated by LSI---have given fresh impetus to research in the area of parallel processing, with motives for parallel processing including real-time urgency and reduction of turnaround time of high priority jobs.

View PDF

IEEE Transactions on Electronic ComputersExperiments on Models of Computations and Systems

39 Citations1967David F. Martin, Gerald Estrin

Effectiveness of parallel processing, convergence properties of the successive approximation assignment and sequencing procedure, sensitivity to input parameter variation, the cost in computer time of the graph analysis, and comparison with more conventional SIMSCRIPT simulation are presented.