List-Scheduling versus Cluster-Scheduling

Abstract

In scheduling theory and parallel computing practice, programs are often represented as directed acyclic graphs. Finding a makespan-minimising schedule for such a graph on a given number of homogenous processors (PIprec; cijICmax) is an NP-hard optimisation problem. Among the many proposed heuristics, the two dominant approaches are list-scheduling and cluster-scheduling (based on clustering), whereby clustering targets an unlimited number of processors at its core. Given their heuristic nature, many experimental comparisons exist. However, their overwhelming majority compares algorithms within but not across categories. Hence it is not clear how cluster-scheduling, for a limited number of processors, performs relative to list-scheduling or how list-scheduling, for an unlimited number of processors, performs against clustering. This study addresses these open questions by comparing a large set of representative algorithms from the two approaches in an extensive experimental evaluation. The algorithms are discussed and studied in a modular nature, categorizing algorithms into components. Some of the included algorithms are previously unpublished combinations of these techniques. This approach also permits to study the separate merit of techniques like task insertion or lookahead. The results show that simple low-complexity algorithms are surprisingly competitive and that more sophisticated algorithms only exhibit their strengths under certain conditions.