OASiS: Maximizing ML Cluster Utility via Dynamic Primal-Dual Scheduling

Executive Summary

TL;DR: OASiS is a novel online algorithm designed for shared distributed machine learning clusters. Unlike static schedulers, OASiS dynamically adjusts the number of workers and parameter servers for each job during its execution. By leveraging a primal-dual framework, it makes real-time admission decisions and optimizes resource allocation to maximize the total utility of all jobs relative to their completion deadlines.

Background: Within the landscape of ML infrastructure, this work bridges the gap between theoretical online optimization and practical cluster management. It moves beyond simple "fairness" (like DRF) or "order" (like FIFO) to a "value-driven" approach, specifically optimized for the Parameter Server architecture common in frameworks like MXNet and TensorFlow.

The Core Challenge: Static Resources in a Dynamic World

Training Deep Neural Networks (DNNs) is incredibly resource-intensive, often requiring hours or days on expensive GPU clusters. Most current production schedulers (Borg, YARN, Kubernetes) suffer from a major limitation: Static Allocation.

When a user submits a job, they specify a fixed number of workers. However:

1. Resource Fragmentation: Fixed slots lead to "holes" in cluster utilization.
2. Diminishing Returns: Adding the 100th worker provides less speedup than the 2nd, but current schedulers don't account for this efficiency curve.
3. Time Sensitivity: Not all jobs are equal. A production model update is more critical than a researcher's exploratory experiment.

Methodology: The OASiS Approach

OASiS (Online Algorithm for Scheduling ML Jobs) treats cluster resources as commodities with fluctuating prices.

1. Dual Pricing Mechanism

The algorithm maintains a "dual price" for every resource (CPU, GPU, Memory, Bandwidth) across every time slot. As a resource becomes scarce, its price increases exponentially.

• Initial State: Low prices allow for high job admission.
• Saturation: As servers fill up, prices hit a ceiling, ensuring only high-priority/high-utility jobs are admitted.

2. The Decision Engine (Primal-Dual)

When a new job arrives, OASiS calculates the "Payoff": $Payoff=Utility(CompletionTime)-\sum (ResourceUsageimesDualPrice)$ If the payoff is positive, the job is admitted.

3. Dynamic Programming Subroutine

To find the best schedule (the $l^{\ast }$ that maximizes the payoff), OASiS uses a sophisticated DP approach to distribute the workload ($E_i{N}_i$ data chunks) across potential future time slots.

Figure 1: The architecture of the managed ML cluster with separate worker and parameter server pools.

Experimental Validation

The authors implemented OASiS as a custom scheduler for Kubernetes managing MXNet jobs.

SOTA Comparison

In simulations using Google cluster traces, OASiS consistently outperformed FIFO and DRF. While DRF focuses on giving everyone a "fair share," OASiS focuses on the utility—ensuring that time-critical jobs get more resources when they need them to meet deadlines.

Figure 2: Total job utility comparison showing OASiS providing a clear lead over traditional scheduling policies as the number of jobs increases.

Key Findings

• Lower Tail Latency: As shown in Fig. 8 of the paper, OASiS manages to keep job completion times much closer to their targets compared to RRH or FIFO.
• Theoretical Robustness: The algorithm maintains a competitive ratio of $2\alpha$, meaning its performance is mathematically bounded relative to an offline oracle that knows all future job arrivals.

Critical Insight & Future Work

The brilliance of OASiS lies in its recognition that ML training is elastic. Unlike a web server that needs a specific amount of RAM to function, an ML job can run on 2 GPUs or 20 GPUs—it just changes the completion time. By modeling this elasticity through a utility-cost trade-off, OASiS achieves a level of efficiency static schedulers cannot match.

Limitations:

• The algorithm assumes a symmetric bandwidth model and constant training time per mini-batch, which might fluctuate in highly congested networks.
• The "cold start" problem (estimating initial price parameters $U$ and $L$) requires historical data.

Conclusion: OASiS provides a rigorous framework for the next generation of AI infrastructure, where "Efficiency" is defined not just by utilization percentages, but by the business value (utility) delivered per GPU-hour.