Comparison of general approaches to multiprocessor scheduling

Jing Chiou Liou, Michael A. Palis

Research output: Contribution to journalConference articlepeer-review

74 Scopus citations

Abstract

This paper demonstrates the effectiveness of the two-phase method of scheduling, in which task clustering is performed prior to the actual scheduling process. Task clustering determines the optimal or near-optimal number of processors on which to schedule the task graph. In other words, there is never a need to use more processors (even though they are available) than the number of clusters produced by the task clustering algorithm. The paper also indicates that when task clustering is performed prior to scheduling, load balancing (LB) is the preferred approach for cluster merging. LB is fast, easy to implement, and produces significantly better final schedules than communication traffic minimizing (CTM). In summary, the two-phase method consisting of task clustering and load balancing is a simple yet highly effective strategy for scheduling task graphs on distributed memory parallel architectures.

Original languageEnglish
Pages (from-to)152-156
Number of pages5
JournalProceedings of the International Parallel Processing Symposium, IPPS
StatePublished - 1997
EventProceedings of the 1997 11th International Parallel Processing Symposium, IPPS 97 - Geneva, Switz
Duration: 1 Apr 19975 Apr 1997

Fingerprint

Dive into the research topics of 'Comparison of general approaches to multiprocessor scheduling'. Together they form a unique fingerprint.

Cite this