Benchmarking and comparison of the task graph scheduling algorithms

The problem of scheduling a parallel program represented by a weighted dire cted acyclic graph (DAG) to a set of homogeneous processors for minimizing the completion time of the program has been extensively studied. The NP-com pleteness of the problem has stimulated researchers to propose a myriad of heuristic algorithms. While most of these algorithms are reported to be eff icient, it is not clear how they compare against each other. A meaningful p erformance evaluation and comparison of these algorithms is a complex task and it must take into account a number of issues. First, most scheduling al gorithms are based upon diverse assumptions, making the performance compari son rather meaningless. Second, there does not exist a standard set of benc hmarks to examine these algorithms. Third, most algorithms are evaluated us ing small problem sizes, and, therefore, their scalability is unknown. In t his paper, we first provide a taxonomy for classifying various algorithms i nto distinct categories according to their assumptions and functionalities. We then propose a set of benchmarks that are based on diverse structures a nd are not biased toward a particular scheduling technique. We have impleme nted 15 scheduling algorithms and compared them on a common platform by usi ng the proposed benchmarks, as well as by varying important problem paramet ers. We interpret the results based upon the design philosophies and princi ples behind these algorithms, drawing inferences why some algorithms perfor m better than others. We also propose a performance measure called scheduli ng scalability (SS) that captures the collective effectiveness of a schedul ing algorithm in terms of its solution quality. the number of processors us ed and the running time. (C) 1999 Academic Press.