Sia: Heterogeneity-aware, goodput-optimized ML-cluster scheduling

Suhas Jayaram Subramanya, Daiyaan Arfeen, Shouxu Lin, Aurick Qiao, Zhihao Jia, Gregory R. Ganger | Carnegie Mellon University / Cornell University / Petuum Inc. | SOSP '23, Koblenz, Germany, October 23–26, 2023 | DOI: 10.1145/3600006.3613175

Problem

Shared DL clusters increasingly contain a mix of GPU types, because clusters are grown incrementally and the most cost-effective hardware is bought at each purchase. Existing schedulers cover only one of the two relevant degrees of freedom. Heterogeneity-aware schedulers (Gavel being the state of the art) explicitly model GPU-type differences but only accommodate rigid jobs — jobs that must run with a user-specified GPU count, cannot scale elastically, and do not adapt to the resources they receive. Adaptivity-aware schedulers (Pollux being the state of the art) model how non-rigid jobs adapt their batch size and GPU count, but assume every GPU in the cluster is identical. When both degrees of freedom are present, the paper reports 40–70% lower average JCTs are left on the table, and the gap grows with load because Gavel scales poorly with contention and Pollux scales poorly with cluster size. Naively extending either system does not work: expanding Gavel's (job_id, GPU_type) throughput matrix to (job_id, GPU_type, num_GPUs, minibatch_size) requires extensive per-job profiling and yields an optimization program too large to solve quickly, while Pollux enumerates every placement for each (job, GPU_count) pair, making its search space exponential in nodes and GPUs-per-node — its genetic algorithm takes tens of minutes to terminate on 1000+ GPU clusters.

Core Insight

Restricting the allocation search to a small, structurally-constrained configuration set — powers of two within a node, whole nodes across nodes — shrinks the per-job space from Pollux's O(N^R) to (N + log₂ R) without measurably hurting job runtimes, which makes the combined heterogeneity-plus-adaptivity problem expressible as a single ILP over a row-normalized goodput matrix, and per-job per-GPU-type throughput models can be bootstrapped from one-GPU profiles alone rather than profiled exhaustively.

Method

Sia is a pre-emptive, round-based scheduler that each round considers every possible assignment of GPU number and type to current jobs, estimates aggregate goodput including resizing costs, and picks the best cluster-wide assignment. Goodput, borrowed from Pollux, combines sample-processing throughput with statistical efficiency.

 (1) submit ──► Profiler ──(2) profile 1 GPU of each type, ~10 batchsizes──┐
                                                                           │
                                                        (3) bootstrap models
                                                                           ▼
      Queue (4) ──────────────► Policy ──(5) allocation: (n, m, type)──► Placer
                                  ▲                                        │
                                  │ (8) refreshed goodput estimates        │ (6) physical GPUs
                                  │                                        ▼
                          Goodput Estimator ◄──(7) grad + xput stats── Adaptive
                          (Sia throughput model                        Executors
                           + Pollux stat-efficiency model)             (30 s reporting)

Key mechanisms:

• Decoupled allocation and placement. Allocation decides number and type; Placement decides exact physical GPUs. Placer rules: partial-node allocations must not straddle nodes; whole-node allocations take whole nodes; otherwise evict and retry (rare, usually fewer than 3 evictions at once). Combined with the restricted configuration set, the Submesh Shape Covering theorem guarantees a placement in which no two distributed jobs share a node, which eliminates NIC contention.
• Configuration set. C = {(1,2⁰,X) … (1,R,X)} ∪ {(2,2R,X) … (N,N·R,X)}, of size (N + log₂ R) versus Pollux's O(N^R).
• Normalized goodput matrix. G_ij ← N_i^min · G_ij / min_j G_ij, making utilities comparable across jobs as well as within a job.
• ILP objective. max_A Σ_i Σ_j A_ij·G_ij + λ(1 − ‖A_i‖₁), subject to at most one configuration per job and per-GPU-type capacity. With the fairness exponent: max_A Σ_i Σ_j A_ij·(r_i·G_ij)^p + λ(1 − ‖A_i‖₁). Solved as a MILP with GLPK_MI via CVXPY.
• Restart factor. r_i = (T_i − N_i·S_i)/(T_i + S_i) discounts only those entries requiring a restart, so Sia restarts a job only when not doing so causes a big objective loss. Restart cost is 25–250 s for the evaluated models.
• Bootstrapped throughput models. Profile one GPU of each type over ~10 batchsizes (< 20 GPU-seconds per GPU type). Compute time is independent of GPU count under data-parallel all-reduce, so only communication time must be predicted. Two-GPU throughput is initially assumed to be exactly 2× one-GPU throughput; once a job runs multi-GPU on type A, throughput on an unprofiled type B is estimated as est-xput_B(N) = (xput_B(1)/xput_A(1)) · xput_A(N), and this crude model is discarded once the job actually runs multi-GPU on B.
• Scaling policy. Start each job at 1 GPU; scale up by at most 2× per round; scale down no lower than min_ngpus.
• Limited adaptivity. Strong-scaling jobs fix batch size (Sia substitutes throughput for goodput); rigid jobs fix batch size and GPU count, optimized over GPU type only via a separate objective term.
• Hybrid parallelism. A PMP job on P GPUs with N data-parallel replicas uses N × P GPUs and is scaled by replicating the submitter-fixed configuration.

Implementation replaces the scheduler and data-loader of the open-source AdaptDL framework; Sia Policy runs as a Kubernetes service. Preemption checkpoints weights, data-loader state, and optimizer state only after the current minibatch completes, so no communication is in flight.

Experimental Setup

Headline Quantitative Results

Physical 44-GPU cluster (3-hour, 30-job trace, 4 runs): Sia gave lower average JCT than Gavel by 50% and than Pollux by 35–50%. The simulator showed less than 5% error in average JCT and makespan for both Sia and Gavel.

Heterogeneous 64-GPU setting (Table 3):

Aggregate: 30–93% lower average JCT, 28–95% lower p99 JCT, 12–60% fewer GPU hours per job. (The abstract states 12–55% for GPU hours; the Introduction and Section 5.2 state 12–60%. The Introduction additionally states 38–65% lower makespan, 64% lower worst-case FTF, and 99% lower unfair job fraction; the Conclusion states 22–31% reductions in unfair job fraction.)

Homogeneous 64-GPU setting, Philly traces (Table 4):

Sia matches Pollux in Pollux's own target domain and slightly exceeds it because its ILP guarantees a global optimum where Pollux's genetic algorithm does not. Sia averaged 2.6 restarts/job vs. Pollux's 5.1. Sia and Pollux both show a 50–70% improvement over the inelastic baselines on all metrics.

Rigid-jobs-only setting: with adaptivity disabled for everyone, Sia still beats Gavel by about 25%, because Sia maximizes goodput while Gavel maximizes cluster throughput.

Isolating the two axes (Figure 11): optimizing GPU count in addition to GPU type improves average JCT by 56%; additionally optimizing batch size improves it by a further 13%.

Contention and workload intensity: Sia consistently outperforms Pollux by 50–65% across arrival rates on Helios. On the 48-hour newTrace, Gavel sees about 7× more contention than Sia, versus under 2× on the 8-hour traces.

Finish-time fairness (Helios, heterogeneous):

Policy runtime (64 GPUs, Helios): Sia median 96 ms / p95 426 ms; Pollux 2.2 s / 4.8 s; Gavel 13 ms / 28 ms. Scaling to 2048 GPUs, Sia stays at single-second policy optimization while Pollux's genetic algorithm runs about 100× slower than Sia's ILP.

Profiling overhead: Bootstrap costs ≈ 0.1 GPU hrs per job and performs 30% better than no profiling and only 8% worse than an Oracle that would require 1–10 GPU hrs/job. With 20 GPU types, bootstrapping adds < 5% overhead to a job's execution.

Parameter sensitivity: raising the round duration from 60 s to 300 s increased Sia's average JCT by 333 s (12%); a 30 s round worsened it via excess re-allocation. p = −0.5 performed best across avg JCT, makespan, and fairness.

Hybrid parallel (2.8B GPT, GPipe, 2 stages on a100 / 8 on rtx, 48 microbatches of size 1 per replica): throughput scales linearly with GPU count because computation dominates communication; Sia scaled the job down around the 1-hour mark and back up around the 4-hour mark in response to congestion.

Limitations

• Most results come from the Pollux discrete-time simulator rather than hardware; the physical evaluation covers only a 44-GPU, 3-GPU-type cluster with a single 3-hour, 30-job trace run four times.
• Pollux performed significantly worse on the physical cluster than the simulator predicted, which the authors attribute in part to their own simulator modifications advantaging Pollux for single-job heterogeneous scheduling.
• The heuristic collapsing Pollux's mixed-GPU placements to a single type (most-GPUs-wins, tie broken by a100 > quad > rtx > t4) is acknowledged as imperfect; designing a better one is explicitly out of scope.
• The configuration set admits only power-of-two within-node and whole-node multi-node allocations; nodes whose GPU count is not a power of two must be modeled as several virtual nodes.
• Hybrid-parallel jobs are scaled only by replicating a submitter-fixed PMP/TMP configuration data-parallel-style; the non-data-parallel degrees stay fixed.
• The GPU-hours result is not uniformly favorable: YOLOv3 and DeepSpeech2 consume about 5% more GPU hours under Sia than under heterogeneity-unaware Pollux on Helios traces.
• The bootstrap estimator rests on stated simplifying assumptions — perfect 2× scaling with zero communication time, and equal compute:communication scaling across GPU types — justified only empirically by the 8% Bootstrap-vs-Oracle gap.
• Applicability beyond DL training (batch inference, latency-sensitive inference) is sketched as a belief with proposed goodput estimators, not evaluated.

Open Problems

1. Efficient elastic scaling without fixing non-data-parallel degrees, which the authors leave as future work because existing hybrid-parallel optimizers are time-consuming.
2. Additional adaptation dimensions for pipeline-model-parallel jobs, explicitly deferred in Section 5.3.
3. Principled handling of mixed-GPU-type placement rather than the most-GPUs-wins heuristic used to make Pollux comparable.
4. Goodput estimators for non-training workloads — the paper proposes throughput-as-goodput for batch inference and a 0/1 latency-feasibility goodput for latency-sensitive inference, but does not evaluate either.