Static scheduling algorithms for allocating directed task graphs to multiprocessors
Yu‐Kwong Ricky Kwok, Ishfaq Ahmad · ACM Computing Surveys · 1999
Static scheduling of a program represented by a directed task graph on a multiprocessor 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 efficient heuristics. A plethora of heuristics have been proposed based on a wide spectrum of techniques, including branch-and-bound, integer-programming, searching, graph-theory, randomization, genetic algorithms, and evolutionary methods. The objective of this survey is to describe various scheduling algorithms and their functionalities in a contrasting fashion as well as examine their relative merits in terms of performance and time-complexity. Since these algorithms are based on diverse assumptions, they differ in their functionalities, and hence are difficult to describe in a unified context. We propose a taxonomy that classifies these algorithms into different categories. We consider 27 scheduling algorithms, with each algorithm explained through an easy-to-understand description followed by an illustrative example to demonstrate its operation. We also outline some of the novel and promising optimization approaches and current research trends in the area. Finally, we give an overview of the software tools that provide scheduling/mapping functionalities.
Cited by 1,314 works. doi:10.1145/344588.344618 Open-access PDF
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Genetic algorithms in search, optimization, and machine learning
- Adaptation in Natural and Artificial Systems
- Lecture Notes in Computer Science 1205
- Genetic Algorithms in Search, Optimization and Machine Learning
- Handbook of Genetic Algorithms
- Genetic Algorithms in Search
- Combinatorial Optimization: Algorithms and Complexity.
- Randomized Algorithms
- Bounds for Certain Multiprocessing Anomalies