Creator of Knowledge
Information Resources Management Association
Advancing the Concepts & Practices of Information Resources Management in Modern Organizations

Optimal Scheduling of Parallel Jobs With Unknown Service Requirements

Optimal Scheduling of Parallel Jobs With Unknown Service Requirements
View Sample PDF
Author(s): Benjamin Berg (Carnegie Mellon University, USA) and Mor Harchol-Balter (Carnegie Mellon University, USA)
Copyright: 2021
Pages: 23
Source title: Handbook of Research on Methodologies and Applications of Supercomputing
Source Author(s)/Editor(s): Veljko Milutinović (Indiana University, Bloomington, USA) and Miloš Kotlar (University of Belgrade, Serbia)
DOI: 10.4018/978-1-7998-7156-9.ch003


View Optimal Scheduling of Parallel Jobs With Unknown Service Requirements on the publisher's website for pricing and purchasing information.


Large data centers composed of many servers provide the opportunity to improve performance by parallelizing jobs. However, effectively exploiting parallelism is non-trivial. For each arriving job, one must decide the number of servers on which the job is run. The goal is to determine the optimal allocation of servers to jobs that minimizes the mean response time across jobs – the average time from when a job arrives until it completes. Parallelizing a job across multiple servers reduces the response time of that individual job. However, jobs receive diminishing returns from being allocated additional servers, so allocating too many servers to a single job leads to low system efficiency. The authors consider the case where the remaining sizes of jobs are unknown to the system at every moment in time. They prove that, if all jobs follow the same speedup function, the optimal policy is EQUI, which divides servers equally among jobs. When jobs follow different speedup functions, EQUI is no longer optimal and they provide an alternate policy, GREEDY*, which performs within 1% of optimal in simulation.

Related Content

Miloš Kotlar. © 2021. 4 pages.
Ivan Ratković, Miljan Djordjevic. © 2021. 13 pages.
Benjamin Berg, Mor Harchol-Balter. © 2021. 23 pages.
Bryan Donyanavard, Amir M. Rahmani, Axel Jantsch, Onur Mutlu, Nikil Dutt. © 2021. 33 pages.
Assefaw Gebremedhin, Mostofa Patwary, Fredrik Manne. © 2021. 22 pages.
Nenad Korolija, Jovan Popović, Miroslav M. Bojović. © 2021. 10 pages.
Christina Pacher. © 2021. 8 pages.
Body Bottom