HYBRID DEEP REINFORCEMENT LEARNING AND INTEGER OPTIMIZATION FOR RESOURCE SCHEDULING IN HETEROGENEOUS AI COMPUTING CLUSTERS

Authors

  • PengFei Li (Corresponding Author) Duke University, Durham, NC, USA.
  • EnMiao Feng Duke University, Durham, NC, USA.
  • GaiKe Wang New York University, New York, NY, USA.
  • TianJun Mo Duke University, Durham, NC, USA.

Keywords:

GPU cluster scheduling, Deep reinforcement learning, Mixed-integer programming, Heterogeneous computing, Multi-resource allocation, AI infrastructure

Abstract

AI computing clusters increasingly combine several generations of GPUs with CPU-only servers and host a mix of long-running training jobs and short, latency-sensitive inference or interactive jobs whose demands span GPUs, CPU cores and memory. Scheduling such clusters is a sequential, multi-objective combinatorial problem: heuristic and myopic optimization-based schedulers ignore how current placements constrain future arrivals, whereas pure deep reinforcement learning (DRL) schedulers face an exploding action space and offer no feasibility guarantee. This paper presents HyRIS, a hybrid scheduler that couples DRL with mixed-integer programming (MIP). At each decision epoch, a permutation-equivariant Transformer policy trained by proximal policy optimization emits state-dependent weights of the job-utility function and per-accelerator shadow prices, and a compact MIP converts them into a gang-, multi-resource- and heterogeneity-aware placement that satisfies all capacity constraints by construction. Zero-initialized residual heads anchor the policy to a hand-tuned MIP so that learning starts from a strong and safe operating point, and a reward derived from Little’s law jointly accounts for job completion time, monetary cost and service-level-objective (SLO) violations. Trace-driven experiments on the Alibaba PAI GPU cluster trace with V100, P100, T4, legacy GPUs and CPU-only nodes show that, under heavy load, HyRIS reduces the composite scheduling objective by 13.0–23.9% relative to FIFO, fragmentation-aware, multi-resource packing, heterogeneity-aware LP and pure DRL schedulers and remains within 1.9% of the best baseline (Static-MIP), while keeping the SLO-violation rate of latency-sensitive jobs at 11.9% (shortest-job-first: 10.8%). Each MIP is solved in 2.6 ms on average, making HyRIS practical for online use.

References

[1] Jeon M, Venkataraman S, Phanishayee A, et al. Analysis of large-scale multi-tenant GPU clusters for DNN training workloads. In: Proceedings of the USENIX Annual Technical Conference (ATC), 2019.

[2] Hu Q, Sun P, Yan S, et al. Characterization and prediction of deep learning workloads in large-scale GPU datacenters. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC), 2021.

[3] Weng Q, Xiao W, Yu Y, et al. MLaaS in the wild: Workload analysis and scheduling in large-scale heterogeneous GPU clusters. In: Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2022.

[4] Narayanan D, Santhanam K, Kazhamiaka F, et al. Heterogeneity-aware cluster scheduling policies for deep learning workloads. In: Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2020.

[5] Mohan J, Phanishayee A, Kulkarni J, et al. Looking beyond GPUs for DNN scheduling on multi-tenant clusters. In: Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2022.

[6] Weng Q, Yang L, Yu Y, et al. Beware of fragmentation: Scheduling GPU-sharing workloads with fragmentation gradient descent. In: Proceedings of the USENIX Annual Technical Conference (ATC), 2023.

[7] Li J, Xu H, Zhu Y, et al. Lyra: Elastic scheduling for deep learning clusters. In: Proceedings of the European Conference on Computer Systems (EuroSys), 2023: 835-850. DOI: 10.1145/3552326.3587445.

[8] Grandl R, Ananthanarayanan G, Kandula S, et al. Multi-resource packing for cluster schedulers. In: Proceedings of the ACM SIGCOMM Conference on Data Communication (SIGCOMM), 2014.

[9] Jayaram Subramanya S, Arfeen D, Lin S, et al. Sia: Heterogeneity-aware, goodput-optimized ML-cluster scheduling. SOSP '23: Proceedings of the 29th Symposium on Operating Systems Principles, 2023: 642-657. DOI: 10.1145/3600006.3613175.

[10] Mao H, Alizadeh M, Menache I, et al. Resource management with deep reinforcement learning. In: Proceedings of ACM Workshop on Hot Topics in Networks (HotNets), 2016.

[11] Mao H, Schwarzkopf M, Venkatakrishnan S B, et al. Learning scheduling algorithms for data processing clusters. In: Proceedings of the ACM SIGCOMM Conference on Data Communication (SIGCOMM), 2019.

[12] Peng Y, Bao Y, Chen Y, et al. DL2: A deep learning-driven scheduler for deep learning clusters. IEEE Transactions on Parallel and Distributed Systems, 2021, 32(8): 1947-1960. DOI: 10.1109/TPDS.2021.3052895.

[13] Vaswani A, Shazeer N, Parmar N, et al. Attention is all you need. 31st Conference on Neural Information Processing Systems (NIPS 2017), Long Beach, CA, USA, 2017.

[14] Huangfu Q, Hall J A J. Parallelizing the dual revised simplex method. Mathematical Programming Computation, 2018, 10(1): 119-142.

[15] Schulman J, Wolski F, Dhariwal P, et al. Proximal policy optimization algorithms. arXiv:1707.06347, 2017. DOI: 10.48550/arXiv.1707.06347.

[16] Xiao W, Bhardwaj R, Ramjee R, et al. Gandiva: Introspective cluster scheduling for deep learning. In: Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2018.

[17] Gu J, Chowdhury M, Shin K G, et al. Tiresias: A GPU cluster manager for distributed deep learning. In: Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2019.

[18] Peng Y, Bao Y, Chen Y, et al. Optimus: An efficient dynamic resource scheduler for deep learning clusters. In: Proceedings of the European Conference on Computer Systems (EuroSys), 2018.

[19] Mahajan K, Balasubramanian A, Singhvi A, et al. Themis: Fair and efficient GPU cluster scheduling. In: Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2020.

[20] Zhao H, Han Z, Yang Z, et al. HiveD: Sharing a GPU cluster for deep learning with guarantees. In: Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2020.

[21] Xiao W, Ren S, Li Y, et al. AntMan: Dynamic scaling on GPU clusters for deep learning. In: Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2020.

[22] Qiao A, Choe S K, Jayaram Subramanya S, et al. Pollux: Co-adaptive cluster scheduling for goodput-optimized deep learning. In: Proceedings of the USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2021.

[23] Hu Q, Zhang M, Sun P, et al. Lucid: A non-intrusive, scalable and interpretable scheduler for deep learning training jobs. In: Proceedings of the ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2023.

[24] Bengio Y, Lodi A, Prouvost A. Machine learning for combinatorial optimization: A methodological tour d’horizon. European Journal of Operational Research, 2021, 290(2): 405-421.

[25] Gasse M, Chételat D, Ferroni N, et al. Exact combinatorial optimization with graph convolutional neural networks. In: Advances in Neural Information Processing Systems (NeurIPS), 2019.

[26] Tang Y, Agrawal S, Faenza Y. Reinforcement learning for integer programming: Learning to cut. In: Proceedings of the International Conference on Machine Learning (ICML), 2020.

[27] Kool W, van Hoof H, Welling M. Attention, learn to solve routing problems! In: Proceedings of the International Conference on Learning Representations (ICLR), 2019.

[28] Delarue A, Anderson R, Tjandraatmadja C. Reinforcement learning with combinatorial actions: An application to vehicle routing. In: Advances in Neural Information Processing Systems (NeurIPS), 2020.

[29] Silver T, Allen K, Tenenbaum J, et al. Residual policy learning. arXiv:1812.06298, 2018.

[30] Schulman J, Moritz P, Levine S, et al. High-dimensional continuous control using generalized advantage estimation. In: Proceedings of the International Conference on Learning Representations (ICLR), 2016.

Downloads

Published

2024-06-04

Issue

Section

Research Article

DOI:

How to Cite

PengFei Li, EnMiao Feng, GaiKe Wang, TianJun Mo. Hybrid Deep Reinforcement Learning And Integer Optimization For Resource Scheduling In Heterogeneous Ai Computing Clusters. Innovation and Technology Studies. 2024, 1(1): 48-56. DOI: https://doi.org/10.61784/its4028.