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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

49 Scopus citations

Abstract

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

Original languageEnglish (US)
Title of host publicationProc Supercomput 91
PublisherPubl by IEEE
Pages633-642
Number of pages10
ISBN (Print)0818621583
StatePublished - Dec 1 1991
EventProceedings of Supercomputing '91 - Albuquerque, NM, USA
Duration: Nov 18 1991Nov 22 1991

Publication series

NameProc Supercomput 91

Other

OtherProceedings of Supercomputing '91
CityAlbuquerque, NM, USA
Period11/18/9111/22/91

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'A fast static scheduling algorithm for DAGs on an unbounded number of processors'. Together they form a unique fingerprint.

  • Cite this

    Yang, T., & Gerasoulis, A. (1991). A fast static scheduling algorithm for DAGs on an unbounded number of processors. In Proc Supercomput 91 (pp. 633-642). (Proc Supercomput 91). Publ by IEEE.