Modern data centers and cloud computing clusters are increasingly running workloads composed of malleable jobs. A malleable job can be parallelized across any number of cores, yet the job typically exhibits diminishing marginal returns for each additional core on which it runs. Examples of malleable jobs include machine learning tasks, parallelized across multiple GPUs, and large-scale database queries, parallelized across multiple servers. Given the prevalence of malleable jobs, theoretical works have posed the problem of how to allocate a fixed number of cores across a stream of arriving malleable jobs so as to minimize the mean response time across jobs. We refer to this as the Core Allocation to Malleable jobs (CAM) problem. Although quite a few recent papers have been written on CAM, the problem remains challenging to solve optimally. In particular, prior theoretical work has only solved the CAM problem in very constrained cases. This paper takes a new approach to CAM, looking at the problem in the mean field asymptotic regime. In this regime, we are able to optimally solve a much more general instance of CAM. We derive two distinct mean field optimal policies, FW-CAM and GLAM. FW-CAM demonstrates a new intuition: in the mean field regime, individual job sizes are not relevant in finding an optimal policy. GLAM (Gittins-Like Allocation for Malleable jobs) is asymptotically optimal under certain common assumptions, and also serves as a good heuristic outside of the asymptotic regime by adapting dynamically to the current number of jobs in the system. Notably, none of the policies previously proposed in the literature are mean field optimal when jobs follow different speedup functions.
Zhouzi Li, Cindy Zhu, Arpan Mukhopadhyay, Mor Harchol-Balter, Benjamin Berg
原文摘要
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 choose to rent GPUs from cloud providers. The customer is responsible for devising a policy for (i) deciding how many GPUs to rent at every moment in time to process a stream of ML training jobs and (ii) allocating the rented GPUs among the currently active jobs in the system. Because ML training jobs can be parallelized across different numbers of GPUs, the customer generally has many options for how many GPUs to use for each job. Allocating more GPUs to a single training job will cause the job to complete more quickly. However, the customer pays for each GPU-hour they use, and a training job receives a diminishing marginal benefit from running on additional GPUs. Hence, allocating too many GPUs to a single training job can dramatically increase the overall cost that the customer pays to the cloud provider. This gives rise to a cost-performance tradeoff that customers must balance when running training jobs in the cloud. To balance the cost-performance tradeoff, we develop BOA Constrictor, a new scheduler for ML training jobs which uses a Budget-Optimal Allocation (BOA) policy to squeeze the highest level of performance out of a cloud-deployed GPU cluster given a fixed budget constraint. We explicitly formulate the problem as a budget-constrained scheduling problem and derive the BOA policy which minimizes the average job completion time (JCT) of a stream of arriving jobs subject to the user's budget. For a given budget level, we demonstrate that BOA Constrictor can reduce average JCT by 1.6 times in small-scale implementation experiments and by 2 times in detailed, large-scale simulations compared to state-of-the-art heuristic based schedulers.