TY - GEN
T1 - Scheduling Out-Trees Online to Optimize Maximum Flow
AU - Agrawal, Kunal
AU - Moseley, Benjamin
AU - Newman, Heather
AU - Pruhs, Kirk
N1 - Publisher Copyright:
© 2024 Owner/Author.
PY - 2024/6/17
Y1 - 2024/6/17
N2 - We consider online scheduling. on m identical processors. Jobs are parallel programs constructed using dynamic multithreading (also called fork-join parallelism). Jobs arrive over time online and the goal is to optimize maximum flow. Essentially all prior work on this problem has used a relaxed form of analysis where the algorithm has faster speed processors than the optimum and this paper seeks to understand the problem without this strong assumption. We show that the most natural algorithm, First-In-First-Out (FIFO), is Ømega(łog m)-competitive for jobs that are out-trees. For this challenging class where jobs are out-trees, we give new clairvoyant algorithm that is O(1)-competitive. We then give some circumstantial evidence that FIFO is O(łog m)-competitive, even on arbitrary jobs.
AB - We consider online scheduling. on m identical processors. Jobs are parallel programs constructed using dynamic multithreading (also called fork-join parallelism). Jobs arrive over time online and the goal is to optimize maximum flow. Essentially all prior work on this problem has used a relaxed form of analysis where the algorithm has faster speed processors than the optimum and this paper seeks to understand the problem without this strong assumption. We show that the most natural algorithm, First-In-First-Out (FIFO), is Ømega(łog m)-competitive for jobs that are out-trees. For this challenging class where jobs are out-trees, we give new clairvoyant algorithm that is O(1)-competitive. We then give some circumstantial evidence that FIFO is O(łog m)-competitive, even on arbitrary jobs.
KW - dynamic multithreaded jobs
KW - maximum flow
UR - http://www.scopus.com/inward/record.url?scp=85197429530&partnerID=8YFLogxK
U2 - 10.1145/3626183.3659955
DO - 10.1145/3626183.3659955
M3 - Conference contribution
AN - SCOPUS:85197429530
T3 - Annual ACM Symposium on Parallelism in Algorithms and Architectures
SP - 77
EP - 88
BT - SPAA 2024 - Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures
PB - Association for Computing Machinery
T2 - 36th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2024
Y2 - 17 June 2024 through 21 June 2024
ER -