×

A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors. (English) Zbl 0797.68021

Summary: Clustering of task graphs have been used as an intermediate step toward scheduling parallel architectures. 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) [T. Yang and A. Gerasoulis, Proc. Supercomputing 91, 633-642 (1991)] and the algorithms of S. J. Kim and J. C. Browne [Int. Conf. on Parallel Processing, Vol. 3, 1-8 (1988)], V. Sarkar [Partitioning and scheduling parallel programs for execution on multiprocessors (MIT Press, 1989; Zbl 0679.68056)], and M. Y. Wu and D. Gajski [J. Supercomput. 2, 349-372 (1988)]. 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.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68M10 Network design and communication in computer systems
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 0679.68056
PDFBibTeX XMLCite
Full Text: DOI