Optimal online scheduling of parallel jobs with dependencies

Anja Feldmann, Ming Yang Kao, Jiri Sgall, Shang Hua Teng

Research output: Chapter in Book/Report/Conference proceedingConference contribution

33 Scopus citations

Abstract

We study the following general online scheduling problem. Parallel jobs arrive dynamically according to the dependencies between them. Each job requests a certain number of processors with a specific communication configuration, but its running time is not known until it is completed. We present optimal online algorithms for PRAMs, hypercubes and one-dimensional meshes, and obtain optimal tradeoffs between the competitive ratio and the largest number of processors requested by any job. Our work shows that for efficient online scheduling it is necessary to use virtuahza-Tion, i.e., to schedule parallel jobs on fewer processors than requested while preserving the work. Assume that the largest number of processors requested by a job is λN, where 0 < λ < 1 and N is the number of processors of a machine. With visualization, our algorithm for PRAMs has a competitive ratio of 2+ √4λ2+1-1/2λ. Our lower bound shows that this ratio is optimal. As A goes from 0 to 1, the ratio changes from 2 to 2 + <?, where <f> ss 0.618 is the golden ratio. For hypercubes and one- dimensional meshes we present ⊖( logN/loglogN )-competitive algorithms as well as matching lower bounds. Without vir-Tualization, no online scheduling algorithm can achieve a competitive ratio smaller than N for λ = 1. For λ < 1, the lower bound is 1 + 1/1-λ and our algorithm for PRAMs achieves this competitive ratio. We prove that tree constraints are complete for the scheduling problem, i.e., any algorithm that solves the scheduling problem if the dependency graph is a tree can be converted to solve the general problem equally efficiently.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993
PublisherAssociation for Computing Machinery
Pages642-651
Number of pages10
ISBN (Electronic)0897915917
DOIs
StatePublished - Jun 1 1993
Event25th Annual ACM Symposium on Theory of Computing, STOC 1993 - San Diego, United States
Duration: May 16 1993May 18 1993

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129585
ISSN (Print)0737-8017

Other

Other25th Annual ACM Symposium on Theory of Computing, STOC 1993
CountryUnited States
CitySan Diego
Period5/16/935/18/93

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Optimal online scheduling of parallel jobs with dependencies'. Together they form a unique fingerprint.

Cite this