A comparative study of multiprocessor list scheduling heuristics

Many multiprocessor list scheduling heuristics that account for interprocessor communication delay have been proposed in recent years. However, no uniform comparative study of published heuristics has been performed in almost 20 years. This paper presents the results of a large quantitative study using random, but program-like input graphs. We found differences in the performance of the various heuristics related to the amount of parallelism in the input graph. As well, we found that no single heuristic consistently produces the best schedules under call program structures and multiprocessor configurations. Finally we propose enhancements to existing heuristics as well as our own heuristic, DS, which strikes a good balance between performance and scheduling (i.e. compile) time.<>