Static scheduling algorithms for allocating directed task graphs to multiprocessors

Static scheduling of a program represented by a directed task graph on a mu ltiprocessor system to minimize the program completion time is a well-known problem in parallel processing. Since finding an optimal schedule is an NP -complete problem in general, researchers have resorted to devising efficie nt heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, se arching, graph-theory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling alg orithms and their functionalities in a contrasting fashion as well as exami ne their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their fu nctionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categor ies. We consider 27 scheduling algorithms, with each algorithm explained th rough an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promis ing optimization approaches and current research trends in the area. Finall y, we give an overview of the software tools that provide scheduling/mappin g functionalities.