Gerasoulis, Apostolos; Yang, Tao A comparison of clustering heuristics for scheduling directed acyclic graphs on multiprocessors. (English) Zbl 0797.68021 J. Parallel Distrib. Comput. 16, No. 4, 276-291 (1992). 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. Cited in 19 Documents 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 Keywords:clustering of task graphs; dominant sequence clustering; scheduling; parallel architectures; performance comparison Citations:Zbl 0679.68056 PDFBibTeX XMLCite \textit{A. Gerasoulis} and \textit{T. Yang}, J. Parallel Distrib. Comput. 16, No. 4, 276--291 (1992; Zbl 0797.68021) Full Text: DOI