a new heuristic for scheduling parallel programs on multiprocessor
In this paper, we present an efficient algorithm, called CASS-II, for task clustering without task duplication. Unlike the DSC algorithm, which is empirically the best known algorithm to date in terms of both speed and solution quality, CASS-II uses only limited ``global'' information and does not recompute the critical path in each refinement step. Therefore, the algorithm runs in $O(|E| + |V| lg |V|)$ which is faster than $O((|V|+|E|)lg |V|)$ of the DSC algorithm. Indeed, our experimental results show that CASS-II is between 3 to 5 times faster than DSC. (It is worth pointing out that we used the C code for DSC developed by the authors of the DSC algorithm. The C code for CASS-II was developed by the authors of this paper.) With respect to solution quality, experimental results show that CASS-II is virtually as good as DSC and, in fact, even outperforms DSC for very fine grain DAGs (granularity less than 0.6).
heuristics scheduling parallel programming multiprocessor paper efficiency algorithm task clustering quality informal critic refine experimentation point code author compiler resource management distributed memory multiprocessor