Online Job Scheduling in Distributed Machine Learning Clusters

Yixin Bao, Yanghua Peng, Chuan Wu, Zongpeng Li

Introduction

Training deep learning models is a resource-intensive process that increasingly relies on large-scale clusters of GPUs. In production environments, such as those operated by Google or Tencent, these clusters are shared among numerous users and jobs. However, traditional cluster schedulers like Borg, YARN, or Mesos typically employ static resource allocation. When a job is submitted, it is assigned a fixed number of workers that remains constant until completion.

This static approach leads to significant inefficiencies. A job might finish much faster by utilizing idle resources during low-load periods, or it might need to scale down to accommodate high-priority tasks during peak demand. To address this, we present OASiS (Online Algorithm for Scheduling ML Jobs), a framework designed for online job scheduling with dynamic scaling to maximize total cluster utility.

The OASiS Framework

OASiS treats the scheduling problem as a combinatorial optimization task. Unlike traditional schedulers that prioritize order (FIFO) or fairness (DRF), OASiS focuses on maximizing the "utility" or value of completed jobs. It achieves this through several key mechanisms:

  • Primal-Dual Framework with Exponential Pricing: OASiS maintains "dual prices" for cluster resources (CPU, GPU, memory, and bandwidth). As resource utilization increases, the price rises exponentially. This pricing serves as a natural buffer, effectively "saving" resources for high-utility jobs that may arrive in the future without requiring complex forecasting.
  • Job Admission and Payoff Calculation: Upon job arrival, OASiS calculates a potential payoff by subtracting the total resource cost (based on current dual prices) from the job's utility. Jobs are only admitted if they provide a positive payoff.
  • Dynamic Programming for Optimal Scaling: The algorithm uses a dynamic programming subroutine to determine the optimal number of workers and parameter servers to deploy at each time step, ensuring the job maximizes its utility within the constraints of the current cluster state.

Distributed Architecture and Communication

The system specifically targets the parameter server (PS) architecture common in distributed machine learning. In this model, workers compute gradients while parameter servers aggregate them and update model weights.

The interaction between workers and parameter servers involves frequent exchanges of gradients and parameters, which OASiS manages to prevent communication bottlenecks.

OASiS recognizes that workers and parameter servers have distinct resource bottlenecks—typically GPUs for workers and network bandwidth for servers. By decoupling these entities in the scheduling logic, OASiS ensures a balanced ratio that prevents communication overhead from stalling the training process.

Evaluation and Key Results

The performance of OASiS was evaluated using simulations driven by Google Cluster Data traces and a physical testbed consisting of a 9-node MXNet cluster running on Kubernetes. The evaluation included standard deep learning models such as ResNet, AlexNet, and VGG.

OASiS significantly outperforms traditional schedulers in both total utility achieved and the ability to meet job deadlines.

Performance Highlights:

  • Superior Utility: In scenarios with up to 400 jobs, OASiS consistently achieved higher total utility than FIFO, DRF, and complex heuristics like the Risk-Reward Heuristic (RRH).
  • Deadline Adherence: For time-critical jobs, OASiS kept completion times remarkably close to target deadlines. In contrast, competing schedulers often saw actual completion times drift significantly beyond the targets.
  • Elasticity Benefits: The ability to dynamically adjust the number of workers creates "breathing room" in the cluster, increasing overall throughput and efficiency, especially under high-load conditions.

Conclusion and Future Directions

OASiS demonstrates that moving from static to elastic resource allocation can significantly improve the productivity of shared ML clusters. By using a primal-dual approach with exponential pricing, it provides a mathematically grounded way to handle the uncertainty of online job arrivals.

Future work may explore the application of OASiS to synchronous training environments, where worker coordination is more rigid, and further investigate the overhead associated with frequent container re-scaling in massive-scale deployments.

Summary updated

Abstract

Nowadays large-scale distributed machine learning systems have been deployed to support various analytics and intelligence services in IT firms. To train a large dataset and derive the prediction/inference model, e.g., a deep neural network, multiple workers are run in parallel to train partitions of the input dataset, and update shared model parameters. In a shared cluster handling multiple training jobs, a fundamental issue is how to efficiently schedule jobs and set the number of concurrent workers to run for each job, such that server resources are maximally utilized and model training can be completed in time. Targeting a distributed machine learning system using the parameter server framework, w e design an online algorithm for scheduling the arriving jobs and deciding the adjusted numbers of concurrent workers and parameter servers for each job over its course, to maximize overall utility of all jobs, contingent on their completion times. Our online algorithm design utilizes a primal-dual framework coupled with efficient dual subroutines, achieving good long-term performance guarantees with polynomial time complexity. Practical effectiveness of the online algorithm is evaluated using trace-driven simulation and testbed experiments, which demonstrate its outperformance as compared to commonly adopted scheduling algorithms in today's cloud systems.
BibTeX
@inproceedings{bao2018online,
  author = {Yixin Bao and Yanghua Peng and Chuan Wu and Zongpeng Li},
  title = {{Online Job Scheduling in Distributed Machine Learning Clusters}},
  booktitle = {INFOCOM},
  year = {2018},
  url = {https://openreview.net/forum?id=51GT6tRS0r},
}
Figure