TY - GEN
T1 - Scheduling parallelizable jobs online to minimize the maximum flow time
AU - Agrawal, Kunal
AU - Li, Jing
AU - Lu, Kefu
AU - Moseley, Benjamin
N1 - Publisher Copyright:
© 2016 ACM.
PY - 2016/7/11
Y1 - 2016/7/11
N2 - In this paper we study the problem of scheduling a set of dynamic multithreaded jobs with the objective of minimizing the maximum latency experienced by any job. We assume that jobs arrive online and the scheduler has no information about the arrival rate, arrival time or work distribution of the jobs. The scheduling goal is to minimize the maximum amount of time between the arrival of a job and its completion - this goal is referred to in scheduling literature as maximum flow time. While theoretical online scheduling of parallel jobs has been studied extensively, most prior work has focussed on a highly stylized model of parallel jobs called the "speedup curves model." We model parallel jobs as directed acyclic graphs, which is a more realistic way to model dynamic multithreaded jobs. In this context, we prove that a simple First-In-First-Out scheduler is (1 + ϵ)-speed O(1/ϵ-)-competitive for any e > 0. We then develop a more practical work-stealing scheduler and show that it has a maximum flow time of O(1/2ϵ max{OPT, ln(n)}) for n jobs, with (1 + ϵ)-speed. This result is essentially tight as we also provide a lower bound of Ω(log(n)) for work stealing. In addition, for the case where jobs have weights (typically representing priorities) and the objective is minimizing the maximum weighted flow time, we show a non-clairvoyant algorithm is (1 + ϵ)-speed O(1/2ϵ)-competitive for any ϵ > 0, which is essentially the best positive result that can be shown in the online setting for the weighted case due to strong lower bounds without resource augmentation. After establishing theoretical results, we perform an empirical study of work-stealing. Our results indicate that, on both real world and synthetic workloads, work-stealing performs almost as well as an optimal scheduler.
AB - In this paper we study the problem of scheduling a set of dynamic multithreaded jobs with the objective of minimizing the maximum latency experienced by any job. We assume that jobs arrive online and the scheduler has no information about the arrival rate, arrival time or work distribution of the jobs. The scheduling goal is to minimize the maximum amount of time between the arrival of a job and its completion - this goal is referred to in scheduling literature as maximum flow time. While theoretical online scheduling of parallel jobs has been studied extensively, most prior work has focussed on a highly stylized model of parallel jobs called the "speedup curves model." We model parallel jobs as directed acyclic graphs, which is a more realistic way to model dynamic multithreaded jobs. In this context, we prove that a simple First-In-First-Out scheduler is (1 + ϵ)-speed O(1/ϵ-)-competitive for any e > 0. We then develop a more practical work-stealing scheduler and show that it has a maximum flow time of O(1/2ϵ max{OPT, ln(n)}) for n jobs, with (1 + ϵ)-speed. This result is essentially tight as we also provide a lower bound of Ω(log(n)) for work stealing. In addition, for the case where jobs have weights (typically representing priorities) and the objective is minimizing the maximum weighted flow time, we show a non-clairvoyant algorithm is (1 + ϵ)-speed O(1/2ϵ)-competitive for any ϵ > 0, which is essentially the best positive result that can be shown in the online setting for the weighted case due to strong lower bounds without resource augmentation. After establishing theoretical results, we perform an empirical study of work-stealing. Our results indicate that, on both real world and synthetic workloads, work-stealing performs almost as well as an optimal scheduler.
UR - http://www.scopus.com/inward/record.url?scp=84979783624&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84979783624&partnerID=8YFLogxK
U2 - 10.1145/2935764.2935782
DO - 10.1145/2935764.2935782
M3 - Conference contribution
AN - SCOPUS:84979783624
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 195
EP - 205
BT - SPAA 2016 - Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2016
Y2 - 11 July 2016 through 13 July 2016
ER -