Task clustering and scheduling for distributed memory parallel architectures

Michael A. Palis, Jing Chiou Liou, David S.L. Wei

Research output: Contribution to journalArticlepeer-review

155 Scopus citations

Abstract

This paper addresses the problem of scheduling parallel programs represented as directed acyclic task graphs for execution on distributed memory parallel architectures. Because of the high communication overhead in existing parallel machines, a crucial step in scheduling is task clustering, the process of coalescing fine grain tasks into single coarser ones so that the overall execution time is minimized. The task clustering problem is NP-hard, even when the number of processors is unbounded and task duplication is allowed. A simple greedy algorithm is presented for this problem which, for a task graph with arbitrary granularity, produces a schedule whose makespan is at most twice optimal. Indeed, 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, 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 languageEnglish
Pages (from-to)46-55
Number of pages10
JournalIEEE Transactions on Parallel and Distributed Systems
Volume7
Issue number1
DOIs
StatePublished - 1996

Keywords

  • Approximation algorithms
  • Distributed memory architectures
  • Program task graph
  • Task granularity
  • Task scheduling

Fingerprint

Dive into the research topics of 'Task clustering and scheduling for distributed memory parallel architectures'. Together they form a unique fingerprint.

Cite this