FKST-OOSPJD-92
Anja Feldmann, Ming-Yang Kao, Jiri Sgall, Shang-Hua Teng. Optimal online scheduling of parallel jobs with dependencies. Research Report Carnegie Mellon University, No. CMU-CS-92-189, 1992.
Download [help]
Download paper:
Postscript (ps) 
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Note on this paper
No. CMU-CS-92-189
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 virtualization, 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 lambda N, where 0< lambda <= 1 and N is the number of processors of a machine. With virtualization, our algorithm for PRAMs has a competitive ratio of 2 + (sqrt{4 lambda^2+1}-1) / (2 lambda). Our lower bound shows that this ratio is optimal. As lambda goes from 0 to 1, the ratio changes from 2 to 2+phi, where phi (approx. 0.618) is the golden ratio. For hypercubes and one-dimensional meshes we present Theta(log N / loglog N)-competitive algorithms as well as matching lower bounds. Without virtualization, no online scheduling algorithm can achieve a competitive ratio smaller than N for lambda=1. For lambda<1, the lower bound is 1 + 1 / (1-lambda) 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. This shows that the structure of a dependency graph is not as important for online scheduling as it is for offline scheduling, although even simple dependencies make the problem much harder than scheduling independent jobs.
Keyword
[ Ca ]
Contact
BibTex Reference
@TechReport{FKST-OOSPJD-92,
Author = {Feldmann, Anja and Kao, Ming-Yang and Sgall, Jiri and Teng, Shang-Hua},
Title = {Optimal online scheduling of parallel jobs with dependencies},
Institution = {Carnegie Mellon University},
Year = {1992}
}
EndNote Reference [help]
Get EndNote Reference (.ref)
It has been automatically generated using the bib2html program.