DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors

Research output: Contribution to journalArticlepeer-review

457 Scopus citations

Abstract

We present a low-complexity heuristic, named the, dominant sequence clustering algorithm (DSC), for scheduling parallel tasks on an unbounded number of completely connected processors. The performance of DSC is, on average, comparable to, or even better than, other higher-complexity algorithms. We assume no task duplication and nonzero communication overhead between processors. Finding the optimum solution for arbitrary directed acyclic task graphs (DAG’s) is NP-complete. DSC finds optimal schedules for special classes of DAG’s, such as fork, join, coarse-grain trees, and some fine-grain trees. It guarantees a performance within a factor of 2 of the optimum for general coarse-grain DAG’s. We compare DSC with three higher-complexity general scheduling algorithms: the ETF by Hwang, Chow, Anger, and Lee; Sarkar’s clustering algorithm; and the MD by Wu and Gajski. We also give a sample of important practical applications where DSC has been found useful.

Original languageEnglish (US)
Pages (from-to)951-967
Number of pages17
JournalIEEE Transactions on Parallel and Distributed Systems
Volume5
Issue number9
DOIs
StatePublished - Sep 1994

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Keywords

  • Clustering
  • directed acyclic graph
  • heuristic algorithm
  • optimality
  • parallel processing
  • scheduling
  • task precedence

Fingerprint

Dive into the research topics of 'DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors'. Together they form a unique fingerprint.

Cite this