Optimal On-Line Scheduling of Parallel Jobs with Dependencies

Anja Feldmann*, Ming Yang Kao, Jiří Sgall, Shang Hua Teng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

We study the following general on-line scheduling problem. Parallel jobs arrive on a parallel machine dynamically according to the dependencies between them. Each job requests a certain number of processors in a specific communication configuration, but its running time is not known until it is completed. We present optimal on-line algorithms for PRAMs and one-dimensional meshes, and efficient algorithms for hypercubes and general meshes. For PRAMs we obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested by any job. Our results demonstrate that on-line scheduling with dependencies differs from scheduling without dependencies in several crucial aspects. First, it is essential to use virtualization, i.e., to schedule parallel jobs on fewer processors than requested. Second, the maximal number of processors requested by a job has significant influence on the performance. Third, the geometric structure of the network topology is an even more important factor than in the absence of dependencies.

Original languageEnglish (US)
Pages (from-to)393-411
Number of pages19
JournalJournal of Combinatorial Optimization
Volume1
Issue number4
DOIs
StatePublished - 1998

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Optimal On-Line Scheduling of Parallel Jobs with Dependencies'. Together they form a unique fingerprint.

Cite this