TASK CLUSTERING AND SCHEDULING FOR DISTRIBUTED-MEMORY PARALLEL ARCHITECTURES

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.