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.
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.
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