HYBRID DEEP REINFORCEMENT LEARNING AND INTEGER OPTIMIZATION FOR RESOURCE SCHEDULING IN HETEROGENEOUS AI COMPUTING CLUSTERS
Keywords:
GPU cluster scheduling, Deep reinforcement learning, Mixed-integer programming, Heterogeneous computing, Multi-resource allocation, AI infrastructureAbstract
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.