© 1996 by British Computer Society
A Compile-Time Scheduling Heuristic for Multiprocessor Architectures
*
i *Faculty of Electronic Engineering, University of Nis, Beogradska 14, P.O. Box 73, 18000 Nis, Serbia, Yugoslavia. Email: gdjordjevic{at}europa.elfak.ni.ac.yu
The multiprocessor scheduling problem can be stated as finding a schedule for a task graph to be executed on a multiprocessor architecture so that the execution time can be minimized. Since this problem is known to be NP-hard, in all but a few very restricted cases, the main research efforts in this area are focused on heuristic methods for obtaining near-optimal solutions in a reasonable amount of time. A new compile-time single-pass multiprocessor scheduling technique, called chaining, has been developed and is presented in this paper. Chaining can be used to schedule task graphs onto multiprocessor architectures that contain an arbitrary number of processors connected in an irregular fashion, taking into account the expected execution and communication requirements of the task graph on the given multiprocess architecture. This technique can be viewed as a generalization of the list scheduling technique, that does not impose any preconditions about the ordering according to which tasks are selected for scheduling. Varying the selection criteria, implemented in this technique, we have generated a new class of scheduling algorithms. An evaluation of this class was made on 360 randomly generated examples, and the estimated performances were compared with two list scheduling algorithms, the dynamic level scheduler proposed by Sih and Lee, and the earliest task first algorithm proposed by Hwang et al.
Received June 28, 1995. revised July 25, 1996.
* Faculty of Electronic Engineering, University of Nis, Beogradska 14, P.O. Box 73, 18000 Nis, Serbia, Yugoslavia Email: gdjordjevic{at}europa.elfak.ni.ac.yu