Ma. Palis et al., TASK CLUSTERING AND SCHEDULING FOR DISTRIBUTED-MEMORY PARALLEL ARCHITECTURES, IEEE transactions on parallel and distributed systems, 7(1), 1996, pp. 46-55
Citations number
19
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
This paper addresses the problem of scheduling parallel programs repre
sented as directed acyclic task graphs for execution on distributed me
mory parallel architectures. Because of the high communication overhea
d in existing parallel machines, a crucial step in scheduling is task
clustering, the process of coalescing fine grain tasks into single coa
rser ones so that the overall execution time is minimized. The task cl
ustering problem is NP-hard, even when the number of processors is unb
ounded and task duplication is allowed. A simple greedy algorithm is p
resented for this problem which, for a task graph with arbitrary granu
larity, produces a schedule whose makespan is at most twice optimal. I
ndeed, the quality of the schedule improves as the granularity of the
task graph becomes larger. For example, if the granularity is at least
1/2, the makespan of the schedule is at most 5/3 times optimal. For a
task graph with n tasks and e inter-task communication constraints, t
he algorithm runs in O(n(n lg n + e)) time, which is n times faster th
an the currently best known algorithm for this problem. Similar algori
thms are developed that produce: (1) optimal schedules for coarse grai
n graphs; (2) 2-optimal schedules for trees with no task duplication;
and (3) optimal schedules for coarse grain trees with no task duplicat
ion.