Scheduling Multi-Server Jobs With Sublinear Regrets via Online Learning
IEEE Transactions on Services Computing · 2024-05 · 17 (3) · 1168-1180
DOI: 10.1109/tsc.2023.3303344 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Services Computing, 2024-05. Verfasst von Hailiang Zhao und 6 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 45 Literaturangaben. Gefördert von: Key Research Project of Zhejiang Province, National Natural Science Foundation of China.
Abstract (Originalsprache)
Multi-server jobs that request multiple computing resources and hold onto them during their execution dominate modern computing clusters. When allocating the multi-type resources to several co-located multi-server jobs simultaneously in online settings, it is difficult to make the tradeoff between the parallel computation gain and the internal communication overhead, apart from the resource contention between jobs. To study the computation-communication tradeoff, we model the computation gain as the speedup on the job completion time when it is executed in parallelism on multiple computing instances, and fit it with utilities of different concavities. Meanwhile, we take the dominant communication overhead as the penalty to be subtracted. To achieve a better gain-overhead tradeoff, we formulate an cumulative reward maximization program and design an online algorithm, named OgaSched, to schedule multi-server jobs. OgaSched allocates the multi-type resources to each arrived job in the ascending direction of the reward gradients. It has several parallel sub-procedures to accelerate its computation, which greatly reduces the complexity. We proved that it has a sublinear regret with general concave rewards. We also conduct extensive trace-driven simulations to validate the performance of OgaSched. The results demonstrate that OgaSched outperforms widely used heuristics by 11.33%, 7.75%, 13.89%, and 13.44%, respectively.
Förderung
- Key Research Project of Zhejiang Province
- National Natural Science Foundation of China
Zitieren
APA
Zhao, H., Deng, S., Xiang, Z., Yan, X., Yin, J., Dustdar, S., & Zomaya, A. Y. (2024). Scheduling Multi-Server Jobs With Sublinear Regrets via Online Learning. IEEE Transactions on Services Computing, 17(3), 1168-1180. https://doi.org/10.1109/tsc.2023.3303344
Vancouver
Zhao H, Deng S, Xiang Z, Yan X, Yin J, Dustdar S, et al. Scheduling Multi-Server Jobs With Sublinear Regrets via Online Learning. IEEE Transactions on Services Computing. 2024;17(3):1168-1180. doi:10.1109/tsc.2023.3303344
BibTeX
@article{Zhao2024,
author = {Zhao, Hailiang and Deng, Shuiguang and Xiang, Zhengzhe and Yan, Xueqiang and Yin, Jianwei and Dustdar, Schahram and Zomaya, Albert Y.},
title = {Scheduling Multi-Server Jobs With Sublinear Regrets via Online Learning},
journal = {IEEE Transactions on Services Computing},
year = {2024},
volume = {17},
number = {3},
pages = {1168--1180},
doi = {10.1109/tsc.2023.3303344}
}
EUVIMED