TY - JOUR
T1 - A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors
AU - Gerasoulis, Apostolos
AU - Yang, Tao
N1 - Funding Information:
We thank Sesh Venugopal for several useful discussions on this work and Ajay Bakre and the referees for reading the manuscript and suggesting improvements in the presentation. This work was in part supported by Grant DMS-8706122 from NSF.
PY - 1992/12
Y1 - 1992/12
N2 - Clustering of task graphs has been used as an intermediate step toward scheduling parallel architectures. In this paper, we identify important characteristics of clustering algorithms and propose a general framework for analyzing and evaluating such algorithms. Using this framework, we present an analytic performance comparison of four algorithms: Dominant Sequence Clustering (DSC) (Yang and Gerasoulis, Proc. Supercomputing '91, 1991, pp. 633-642) and the algorithms of Kim and Browne (Int. Conf. on Parallel Processing, 1988, Vol. 3, pp. 1-8) Sarkar (Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors, MIT Press, 1989), and Wu and Gajski (J. Super-comput. 2 (1988), 349-372). We identify the common features and differences of these algorithms and explain why DSC is superior to other algorithms. Finally, we present some experiments to verify our analysis.
AB - Clustering of task graphs has been used as an intermediate step toward scheduling parallel architectures. In this paper, we identify important characteristics of clustering algorithms and propose a general framework for analyzing and evaluating such algorithms. Using this framework, we present an analytic performance comparison of four algorithms: Dominant Sequence Clustering (DSC) (Yang and Gerasoulis, Proc. Supercomputing '91, 1991, pp. 633-642) and the algorithms of Kim and Browne (Int. Conf. on Parallel Processing, 1988, Vol. 3, pp. 1-8) Sarkar (Partitioning and Scheduling Parallel Programs for Execution on Multiprocessors, MIT Press, 1989), and Wu and Gajski (J. Super-comput. 2 (1988), 349-372). We identify the common features and differences of these algorithms and explain why DSC is superior to other algorithms. Finally, we present some experiments to verify our analysis.
UR - http://www.scopus.com/inward/record.url?scp=44049113422&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=44049113422&partnerID=8YFLogxK
U2 - 10.1016/0743-7315(92)90012-C
DO - 10.1016/0743-7315(92)90012-C
M3 - Article
AN - SCOPUS:44049113422
SN - 0743-7315
VL - 16
SP - 276
EP - 291
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 4
ER -