A fast static scheduling algorithm for DAGs on an unbounded number of processors

Abstract

Scheduling parallel tasks on an unbounded number of completely connected processors when communication overhead is taken into account ig NP-complete. Assuming that task duplication is not allowed, we propose a fast heuristic algorithm, called the dominant sequence clustering algorithm (DSC), for this scheduling problem. The DSC algorithm is superior to several other algorithms from the literature in terms of both computational comptezity and parallel time. We present experimental results for scheduling general directed acyclic ta8k graph8 (DA Gs) and compare the performance of several algorithms. Moreover, we show that DSC is optimum for special classes of DA Gs such as join, fork and coarse grain tree graphs. 1