Which Cluster Meets My Deadline: a Budget-Aware Scheduler for Distributed Training Jobs in Heterogeneous Environments

Training deep learning (DL) models demands substantial computational resources, often relying on expensive GPUs in a distributed manner. To meet this demand, cloud providers deploy GPU clusters worldwide to offer users compute instance rental services. These GPU clusters are typically heterogeneous, comprising multiple GPU types with varying computational capabilities, and their prices vary significantly across both GPU instance types and geographic regions. Meanwhile, users often have specific deadlines for training their models. Most existing works focus solely on performance, overlooking price heterogeneity and failing to optimize costs effectively. Given the high cost and time demands of model training, focusing on performance alone is insufficient. In this paper, we aim to balance performance and cost through a DL broker service that maximizes the number of jobs completed within their deadlines under a given budget. We propose CADDS, which jointly optimizes cluster placement and dynamically adjusts GPU type and quantity during training to reduce rental costs. We formulate the scheduling problem as an integer nonlinear programming problem and propose an efficient online approach combining greedy and dynamic programming. Experimental results demonstrate that CADDS significantly outperforms existing approaches, improving the deadline satisfactory ratio within budget limits by <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{5 9. 4 \%}$</tex> to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathbf{8 0. 2 \%}$</tex>.