Abstract
Recent years have witnessed a rapid growth of distributed machine learning (ML) frameworks, which exploit the massive parallelism of computing clusters to expedite ML training. However, the proliferation of distributed ML frameworks also introduces many unique technical challenges in computing system design and optimization. In a networked computing cluster that supports a large number of training jobs, a key question is how to design efficient scheduling algorithms to allocate workers and parameter servers across different machines to minimize the overall training time. Toward this end, in this paper, we develop an online scheduling algorithm that jointly optimizes resource allocation and locality decisions. Our main contributions are three-fold: i) We develop a new analytical model that considers both resource allocation and locality; ii) Based on an equivalent reformulation and observations on the worker-parameter server locality configurations, we transform the problem into a mixed packing and covering integer program, which enables approximation algorithm design; iii) We propose a meticulously designed approximation algorithm based on randomized rounding and rigorously analyze its performance. Collectively, our results contribute to the state of the art of distributed ML system optimization and algorithm design.
Introduction
Training modern deep neural networks (DNNs) requires significant computational power, often necessitating the use of distributed systems. The most prevalent architecture for this is the Parameter Server (PS) model, where the workload is divided between "workers" that compute gradients and "servers" that aggregate these gradients to update model parameters. While this approach enables massive parallelism, it introduces significant communication overhead, particularly in shared cluster environments where multiple jobs compete for resources.
The Challenges of Locality and Online Scheduling
Two major hurdles complicate the optimization of distributed ML training:
- The Locality Challenge: Network communication is frequently the primary bottleneck. When a worker and its corresponding parameter server are co-located on the same physical machine, they can communicate via internal memory, which is significantly faster than network-based communication. However, incorporating this "locality" into scheduling decisions makes the problem non-deterministic and mathematically complex.
- The Online Challenge: In production environments, jobs arrive unpredictably. Schedulers must make real-time decisions without knowledge of future job arrivals. Existing solutions often rely on simple heuristics like First-In-First-Out (FIFO) or Dominant Resource Fairness (DRF), which fail to provide theoretical performance guarantees or adequately account for locality.
Methodology: The PD-ORS Algorithm
To address these challenges, we propose PD-ORS, an online scheduling algorithm that jointly optimizes resource allocation and locality. The approach consists of three key components:
- Mathematical Reformulation: We transform the complex scheduling problem—which is inherently non-linear due to the "slowest-worker" bottleneck in Bulk Synchronous Parallel (BSP) training—into a structured Integer Linear Program (ILP).
- Primal-Dual Framework: To handle online job arrivals, we employ a primal-dual approach. Cluster resources (GPU, CPU, RAM) are assigned dynamic "prices" that increase exponentially as utilization grows. A job is scheduled only if its utility exceeds the current marginal cost of the resources it requires.
- Dynamic Programming and Randomized Rounding: For each arriving job, we use dynamic programming to determine the optimal allocation of workers and servers over time. To convert fractional theoretical results into practical integer allocations, we apply a randomized rounding scheme that preserves a tight approximation of the optimal solution.
Evaluation and Key Results
We evaluated PD-ORS using both synthetic data and real-world traces from Google cluster data. Our results demonstrate that PD-ORS significantly outperforms traditional schedulers:
- Higher System Utility: PD-ORS consistently achieved greater total utility compared to FIFO, DRF, and Dorm.
- Locality Advantage: By explicitly exploiting co-location, PD-ORS significantly outperformed OASiS, a state-of-the-art scheduler that separates workers and servers.
- Provable Performance: Theoretically, PD-ORS maintains a competitive ratio within a logarithmic factor of the offline optimal. In practice, the performance ratio was observed to be between 1.0 and 1.4.
- Computational Efficiency: The algorithm operates in polynomial time, making it practical for real-time deployment in large-scale clusters.
Conclusion
PD-ORS represents a significant step forward in distributed ML system optimization. By bridging the gap between theoretical guarantees and practical locality-aware scheduling, it offers a robust framework for managing high-performance computing clusters. Future work will focus on refining parameter estimation and validating the algorithm in live production environments like Kubernetes.
Summary updated