TY - GEN
T1 - Scheduling parallel DAG jobs online to minimize average flow time
AU - Agrawal, Kunal
AU - Li, Jing
AU - Lu, Kefu
AU - Moseley, Benjamin
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2016
Y1 - 2016
N2 - In this work, we study the problem of scheduling parallelizable jobs online with an objective of minimizing average flow time. Each parallel job is modeled as a DAG where each node is a sequential task and each edge represents dependence between tasks. Previous work has focused on a model of parallelizability known as the arbitrary speed-up curves setting where a scalable algorithm is known. However, the DAG model is more widely used by practitioners, since many jobs generated from parallel programming languages and libraries can be represented in this model. However, little is known for this model in the online setting with multiple jobs. The DAG model and the speed-up curve models are incomparable and algorithmic results from one do not immediately imply results for the other. Previous work has left open the question of whether an online algorithm can be O(1)-competitive with O(1)-speed for average flow time in the DAG setting. In this work, we answer this question positively by giving a scalable algorithm which is (1 + ϵ)-speed O(1/3ϵ)-competitive for any ϵ > 0. We further introduce the first greedy algorithm for scheduling parallelizable jobs - our algorithm is a generalization of the shortest jobs first algorithm. Greedy algorithms are among the most useful in practice due to their simplicity. We show that this algorithm is (2 + ϵ)-speed O(1/ϵ4) - competitive for any ϵ > 0.
AB - In this work, we study the problem of scheduling parallelizable jobs online with an objective of minimizing average flow time. Each parallel job is modeled as a DAG where each node is a sequential task and each edge represents dependence between tasks. Previous work has focused on a model of parallelizability known as the arbitrary speed-up curves setting where a scalable algorithm is known. However, the DAG model is more widely used by practitioners, since many jobs generated from parallel programming languages and libraries can be represented in this model. However, little is known for this model in the online setting with multiple jobs. The DAG model and the speed-up curve models are incomparable and algorithmic results from one do not immediately imply results for the other. Previous work has left open the question of whether an online algorithm can be O(1)-competitive with O(1)-speed for average flow time in the DAG setting. In this work, we answer this question positively by giving a scalable algorithm which is (1 + ϵ)-speed O(1/3ϵ)-competitive for any ϵ > 0. We further introduce the first greedy algorithm for scheduling parallelizable jobs - our algorithm is a generalization of the shortest jobs first algorithm. Greedy algorithms are among the most useful in practice due to their simplicity. We show that this algorithm is (2 + ϵ)-speed O(1/ϵ4) - competitive for any ϵ > 0.
UR - http://www.scopus.com/inward/record.url?scp=84962867375&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84962867375&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974331.ch14
DO - 10.1137/1.9781611974331.ch14
M3 - Conference contribution
AN - SCOPUS:84962867375
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 176
EP - 189
BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
A2 - Krauthgamer, Robert
PB - Association for Computing Machinery
T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Y2 - 10 January 2016 through 12 January 2016
ER -