[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, Vol.14 No.1, pp.7-26 (March 1998)
On the Effectiveness of Compiler-Time Scheduling
Approaches for Distributed Memory Multiprocessor

Jing-Chiou Liou and Michael A. Palis*
AT&T Laboratories
Middletown, NJ 07748-4801, USA
* Department of Computer Science
Rutgers University
Camden, NJ 08102, USA

This paper demonstrates the effectiveness of the two-phase method of compiler-time multiprocessor 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. This paper also shows 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 does 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.

Keywords: task graph, clustering, scheduling, load balancing, parallel compiler

Received March 5, 1997; revised November 29, 1997.
Communicated by PeiZong Lee.