Gavel: Heterogeneity-Aware Cluster Scheduling Policies for Deep Learning Workloads

Deepak Narayanan, Keshav Santhanam, Fiodar Kazhamiaka (Stanford University); Amar Phanishayee (Microsoft Research); Matei Zaharia (Stanford University) | 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20), November 4–6 2020 | ISBN 978-1-939133-19-9

Filing note: the local file is 0067_Gravel.pdf; the system's name in the paper is Gavel. Artifact: https://github.com/stanford-futuredata/gavel (MIT License).

Problem

Specialized accelerators — GPUs, TPUs, FPGAs, custom ASICs — are increasingly deployed for DNN training, and they exhibit heterogeneous performance behavior across model architectures. ResNet-50 sees a nearly 10× speedup moving from a K80 to a V100, while an A3C deep-RL model sees only 2×; once throughput is dollar-normalized against GCP on-demand prices, the V100 is no longer optimal for all models and the older P100 is competitive or cheaper per dollar for many. Existing GPU cluster schedulers — Gandiva, Tiresias, Themis — arbitrate these expensive resources across users while optimizing fairness or makespan, but do not consider this heterogeneity at all. The two schedulers that do, AlloX and Gandiva_fair, each optimize a single objective and tightly couple their scheduling mechanism to it, so they cannot express the hierarchical and cost/SLO policies operators actually want. Utilization optimizations such as space sharing and placement sensitivity are likewise deployed ad hoc rather than being folded into the global objective.

Core Insight

Many widely used scheduling policies — including hierarchical ones — can be written as optimization problems whose objective is a function of the jobs' achieved throughputs; replacing those throughput terms with effective throughput (the time-weighted average throughput of a job over a mix of resource configurations) mechanically converts any such policy into a heterogeneity-, colocation-, and placement-aware version, which a decoupled round-based mechanism can then realize on real hardware.

Method

Gavel operates in two decoupled steps.

Step 1 — Policy as an optimization problem. Allocations are matrices X giving the fraction of wall-clock time each job spends on each accelerator type between recomputations; a throughput matrix T gives each job's throughput in iterations/second per accelerator (T_mj = −∞ if the job cannot run there, e.g. memory limits). Effective throughput is

throughput(m, X)  =   Σ_{ j ∈ accelerator types }   T_mj · X_mj

subject to 0 ≤ X_mj ≤ 1, Σ_j X_mj ≤ 1, and Σ_m X_mj · scale_factor_m ≤ num_workers_j. Substituting this into an existing policy yields its heterogeneity-aware form — e.g. heterogeneity-aware LAS maximizes min_m (1/w_m) · throughput(m, X) / throughput(m, X_m^equal). Table 1 of the paper lists nine expressible policies: Makespan, LAS, LAS with weights, Finish Time Fairness, FIFO, Shortest Job First, Minimize cost, Minimize cost with SLOs, and Hierarchical. Most are a single linear program; the cost policies are linear-fractional programs reduced to a sequence of LPs; hierarchical policies iterate an LP (fair allocation respecting per-entity policies) with an MILP (identify bottlenecked jobs) under water filling. Space sharing adds rows for job combinations, capped at 2 jobs per combination. Placement sensitivity is modeled as two worker types, consolidated and unconsolidated.

Step 2 — Round-based scheduling mechanism. Gavel tracks t_mj, the time job (or combination) m has spent on accelerator type j, computes f_mj = t_mj / (Σ_{m'} t_{m'j}), and forms a priority matrix as the element-wise division of X^opt by f. Each round (6 minutes in the experiments) it greedily selects the highest-priority non-conflicting combinations that fit the worker budget (Algorithm 1); the exact problem is a multiple-choice knapsack and NP-hard, so occasional greedy sub-optimality is accepted and corrected in later rounds. Jobs are placed in decreasing order of requested workers, preferring accelerators on the same physical server.

Supporting components. A throughput estimator (Quasar-style) mixes profiling on dedicated workers with matrix completion to fingerprint a new job against pre-profiled reference jobs when colocated throughputs are unknown. GavelIterator wraps framework data iterators, equalizes iteration counts across distributed tasks, synchronizes round boundaries, and performs lease renewal to avoid unnecessary checkpointing. Implementation: ~9000 LOC Python plus a ~500 LOC simulator, using cvxpy and gRPC; user code changes are < 5 LOC.

Experimental Setup

Models: ResNet-50 (ImageNet), ResNet-18 (CIFAR-10), A3C (Pong), LSTM (Wikitext-2), Transformer (Multi30k de-en), CycleGAN (monet2photo), Recoder autoencoder (ML-20M).

Headline Quantitative Results

Physical cluster (Table 3):

Average JCT improves 1.5× and makespan 1.2×; simulation tracks the physical cluster to within < 8%.

Preemption overhead (Table 4, 6-minute rounds): < 3% without lease renewals (worst case 2.91% for LSTM, best 0.22% for A3C); ≤ 0.47% with lease renewals. Checkpoint load/save is < 5 seconds.

Simulation (larger cluster, longer traces):

Gavel essentially matches AlloX — the best-case average-JCT-optimizing baseline — while supporting other objectives, and supports higher load than AlloX because AlloX starves long jobs.

Other measurements: heterogeneity-aware allocation gives ~10% higher throughput than an isolated (1/n) allocation in the 3-job worked example; explicit space-sharing modeling improves objectives 2.2× over Gandiva's ad-hoc approach; the hierarchical policy solves 2048 jobs in < 10 minutes without space sharing and 512 jobs in < 10 minutes with it; average GPU SM utilization on a Microsoft cluster is as low as 52%.

Limitations

Stated by the paper:

• Gavel proposes no new scheduling policies or performance optimizations (§3.4 explicit non-goal); policy quality is inherited from prior work.
• Not strategy-proof: users who manipulate reported throughputs can obtain larger cluster shares for some objectives — significant because T can be user-provided.
• Hierarchical coverage is partial: fairness at upper levels, fairness or FIFO at lower levels only, matching the Hadoop scheduler.
• Placement sensitivity is modeled at only two extreme points (fully consolidated, fully unconsolidated), which the paper calls upper and lower bounds rather than a full placement model.
• Space sharing is capped at 2-job combinations, justified empirically; |T| still grows quadratically in the number of jobs.
• Policy latency grows with scale: with space sharing the hierarchical policy stays under 10 minutes only up to 512 jobs, and the authors defend latencies up to 30 minutes, during which jobs get heterogeneity-agnostic allocations.
• The mechanism is deliberately greedy per round (exact problem is NP-hard), so fidelity to X^opt holds only on average over rounds.
• Framework support is PyTorch only.

Observed by this reviewer (facts the paper reports, framed as limitations here):

• Round duration is bounded below by checkpoint cost (< 5 s for these models); larger checkpoints would force longer rounds and degrade fidelity.
• Simulation carries most of the headline numbers — the physical cluster yields 1.5× / 1.2×, while 3.5× / 2.5× / 1.4× come from simulated 20–30-day traces.
• Job durations and arrivals are synthetic (Poisson arrivals, Gandiva's 10^x-minute duration distribution) rather than a replayed production trace.
• Evaluated heterogeneity is one vendor and three GPU generations; the TPUs, FPGAs, and ASICs that motivate the paper are not evaluated, and cost policies use only a two-model workload.
• Space sharing is much less effective for distributed jobs (1.1× vs. 1.4×) — exactly the multi-GPU regime large-model training occupies.

Open Problems

1. Strategy-proofness. Sun et al. showed no fair-sharing policy can simultaneously satisfy Pareto efficiency, sharing incentive, and strategy proofness with interchangeable resources; making Gavel's policies strategy-proof is called out as future work.
2. Richer hierarchical policy sets. Extending beyond fairness-over- {fairness, FIFO} — for example, hierarchies using finish-time fairness — is left open.
3. TensorFlow (and broader framework) support for the scheduler API.
4. Non-DNN and CPU settings. The authors believe the effective-throughput formulation applies to other GPU-amenable workloads such as simulations, to homogeneous DL clusters, and to CPU clusters — but performance estimates for those applications would first be needed.