TY - GEN

T1 - Optimal online scheduling of parallel jobs with dependencies

AU - Feldmann, Anja

AU - Kao, Ming Yang

AU - Sgall, Jiri

AU - Teng, Shang Hua

N1 - Funding Information:
*School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213. t Department of Computer Science, Duke Universit y, Durham, NC 27706. Supported in part by NSF Grant CCR-9101385. t School of Computer Science, Czu-negie Mellon University, Pittsburgh, PA 15213. On leave from Mathematical Institute, AV dR, ~itrvi 25, 11567 Praha 1, Czech Republic $Department of Mathematics, Massachusetts Institute Technology, Cambridge, MA 02139. Supported in part by AFOSR F49620-92-J-0125 and Darpa NOO01492-J-1799. Part of the work was done at Xerox Palo Alto Research Center.
Publisher Copyright:
© 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - 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 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.

AB - 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 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.

UR - http://www.scopus.com/inward/record.url?scp=0027150659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027150659&partnerID=8YFLogxK

U2 - 10.1145/167088.167254

DO - 10.1145/167088.167254

M3 - Conference contribution

AN - SCOPUS:0027150659

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 642

EP - 651

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

Y2 - 16 May 1993 through 18 May 1993

ER -