heSRPT: optimal scheduling of parallel jobs with known sizes

Benjamin Berg; Rein Vesilo; Mor Harchol-Balter

doi:10.1145/3374888.3374896

heSRPT: optimal scheduling of parallel jobs with known sizes

Benjamin Berg, Rein Vesilo, Mor Harchol-Balter

School of Engineering

Research output: Contribution to journal › Conference paper › peer-review

3 Citations (Scopus)

Abstract

Nearly all modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to share a fixed number of servers between many parallelizable jobs. In this paper, we provide the first closed form expression for the optimal allocation of servers to jobs. Specifically, we specify the number of servers that should be allocated to each job at every moment in time. Our solution is a combination of favoring small jobs (as in SRPT scheduling) while still ensuring high system efficiency. We call our scheduling policy high-efficiency SRPT (heSRPT).

Original language	English
Pages (from-to)	18-20
Number of pages	3
Journal	Performance Evaluation Review
Volume	47
Issue number	2
DOIs	https://doi.org/10.1145/3374888.3374896
Publication status	Published - Sept 2019
Event	Workshop on MAthematical performance Modeling and Analysis (21st : 2019) - Phoenix, United States Duration: 28 Jun 2019 → 28 Jun 2019

Access to Document

10.1145/3374888.3374896

Cite this

@article{fbdedf01b6ae4160b47310177f546073,

title = "heSRPT: optimal scheduling of parallel jobs with known sizes",

abstract = "Nearly all modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to share a fixed number of servers between many parallelizable jobs. In this paper, we provide the first closed form expression for the optimal allocation of servers to jobs. Specifically, we specify the number of servers that should be allocated to each job at every moment in time. Our solution is a combination of favoring small jobs (as in SRPT scheduling) while still ensuring high system efficiency. We call our scheduling policy high-efficiency SRPT (heSRPT).",

author = "Benjamin Berg and Rein Vesilo and Mor Harchol-Balter",

year = "2019",

month = sep,

doi = "10.1145/3374888.3374896",

language = "English",

volume = "47",

pages = "18--20",

journal = "Performance Evaluation Review",

issn = "0163-5999",

publisher = "Association for Computing Machinery",

number = "2",

note = "Workshop on MAthematical performance Modeling and Analysis (21st : 2019), MAMA 2019 ; Conference date: 28-06-2019 Through 28-06-2019",

}

TY - JOUR

T1 - heSRPT

T2 - Workshop on MAthematical performance Modeling and Analysis (21st : 2019)

AU - Berg, Benjamin

AU - Vesilo, Rein

AU - Harchol-Balter, Mor

PY - 2019/9

Y1 - 2019/9

N2 - Nearly all modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to share a fixed number of servers between many parallelizable jobs. In this paper, we provide the first closed form expression for the optimal allocation of servers to jobs. Specifically, we specify the number of servers that should be allocated to each job at every moment in time. Our solution is a combination of favoring small jobs (as in SRPT scheduling) while still ensuring high system efficiency. We call our scheduling policy high-efficiency SRPT (heSRPT).

AB - Nearly all modern data centers serve workloads which are capable of exploiting parallelism. When a job parallelizes across multiple servers it will complete more quickly, but jobs receive diminishing returns from being allocated additional servers. Because allocating multiple servers to a single job is inefficient, it is unclear how best to share a fixed number of servers between many parallelizable jobs. In this paper, we provide the first closed form expression for the optimal allocation of servers to jobs. Specifically, we specify the number of servers that should be allocated to each job at every moment in time. Our solution is a combination of favoring small jobs (as in SRPT scheduling) while still ensuring high system efficiency. We call our scheduling policy high-efficiency SRPT (heSRPT).

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

U2 - 10.1145/3374888.3374896

DO - 10.1145/3374888.3374896

M3 - Conference paper

AN - SCOPUS:85077746752

SN - 0163-5999

VL - 47

SP - 18

EP - 20

JO - Performance Evaluation Review

JF - Performance Evaluation Review

IS - 2

Y2 - 28 June 2019 through 28 June 2019

ER -

heSRPT: optimal scheduling of parallel jobs with known sizes

Abstract

Access to Document

Other files and links

Fingerprint

Cite this