PARALLEL DATA LAB 

PDL Abstract

BOA Constrictor: Squeezing Performance out of GPUs in the Cloud via Budget-Optimal Allocation

arXiv:2602.01404v2 [cs.DC] 26 Jul 2026.

Zhouzi Li, Cindy Zhu, Arpan Mukhopadhyay*, Mor Harchol-Balter, Benjamin Berg^

Carnegie Mellon University
* University of Warwick
^ UNC Chapel Hill

http://www.pdl.cmu.edu/

The past decade has seen a dramatic increase in demand for GPUs to train Machine Learning (ML) models. Because it is prohibitively expensive for most organizations to build and maintain a large GPU cluster, organizations instead rent GPUs from cloud providers. A cloud customer must decide (i) how many GPUs to rent at every moment in time to process a stream of training jobs and (ii) how to allocate the rented GPUs among the currently active jobs. While allocating more GPUs to a single training job helps the job complete more quickly, the customer pays for each GPU-hour they use. Because training jobs often receive a diminishing marginal benefit from running on additional GPUs, allocating too many GPUs to a single job can dramatically increase the cost the customer pays. This gives rise to a cost-performance tradeoff when training models in the cloud.

To balance the cost-performance tradeoff,we develop BOA Constrictor, a new scheduler for ML training jobs that uses a Budget-Optimal Allocation (BOA) policy to squeeze the most performance out of a cloud-based GPU cluster given a fixed budget. While prior approaches focus on fixed-sized clusters and heuristic approaches for balancing cost and performance, we formalize the problem as a budget-constrained scheduling problem. Given a monetary budget that the customer is willing to spend on GPUs, we derive the BOA policy that minimizes the average job completion time (JCT) of a stream of arriving jobs. Our BOA policy can be computed efficiently for any budget level, providing users with the optimal tradeoff between cost and performance. For a given budget level, BOA Constrictor can reduce average JCT by 1.6× in small-scale implementation experiments and by 2× in detailed, large-scale simulations compared to state-of-the-art schedulers. BOA Constrictor also reduces the budget needed to achieve a given average JCT by up to 2×.

FULL PAPER: pdf