A new heuristic for scheduling parallel programs on multiprocessor

Jing Chiou Liou, Michael A. Palis

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

15 Scopus citations

Abstract

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).

Original languageEnglish
Title of host publicationProceedings - 1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages358-365
Number of pages8
ISBN (Electronic)0818685913
DOIs
StatePublished - 1998
Event1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998 - Paris, France
Duration: 12 Oct 199818 Oct 1998

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
ISSN (Print)1089-795X

Conference

Conference1998 International Conference on Parallel Architectures and Compilation Techniques, PACT 1998
Country/TerritoryFrance
CityParis
Period12/10/9818/10/98

Fingerprint

Dive into the research topics of 'A new heuristic for scheduling parallel programs on multiprocessor'. Together they form a unique fingerprint.

Cite this