Abstract
A simple greedy algorithm is presented for task clustering with duplication (or recomputation) which, for a task graph with arbitrary granularity, produces a schedule whose makespan is at most twice optimal. Furthermore, the quality of the schedule improves as the granularity of the task graph increases. 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, the algorithm runs in O(n(n lg n + e)) time, which is n times faster than the currently best known algorithm for this problem. Similar algorithms are developed that produce: (1) optimal schedules for coarse grain graphs; (2) 2-optimal schedules for trees with no task duplication; and (3) optimal schedules for coarse grain trees with no task duplication.
| Original language | English |
|---|---|
| Pages | 398-405 |
| Number of pages | 8 |
| State | Published - 1994 |
| Event | Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN) - Kanazawa, Jpn Duration: 14 Dec 1994 → 16 Dec 1994 |
Conference
| Conference | Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN) |
|---|---|
| City | Kanazawa, Jpn |
| Period | 14/12/94 → 16/12/94 |