© 1990 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Scheduling of Precedence-Constrained Tasks on Multiprocessors*
1 Department of Computer Science, Stephen F. Austin State University, Nacogdoches, Texas 75962, USA, 2 Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California 91109, USA
A major factor in the intelligent utilization of multiprocessor systems is the determination of how to assign computational tasks among processors and to schedule their execution. To this end, we consider a set of precedence – constrained tasks, with arbitrary communication among them, in a network of identical processors. We investigate several approaches to statically assign and schedule the tasks in order to achieve maximum parallelism and minimum communication overhead in both fully-connected and hypercube multiprocessor ensembles. Three simple heuristic techniques and an adaptation of simulated annealing are described. Results of computational experimentation provide a comparative analysis of the performance of these heuristic approaches, and give insight into the appropriate application of each method for scheduling distributed task systems.
Received May 1988. revised February 1990.
* This paper presents research results carried out in part at the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administration (NASA). Funding was provided by NASA's Office of Aeronautics and Space Technology, Computer Science and Information Systems Branch.
Department of Computer Science, Stephen F. Austin State University, Nacogdoches, Texas 75962, USA.
¶ Jet Propulsion Laboratory, California Institute of Technology, Pasadena, California 91109, USA.
To whom correspondence should be addressed.