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

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 | *work done in part as interns at Microsoft Research

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

Per-section summary organized by the paper's own headings, with paragraph-level bullets and exact quantitative results where the paper provides them. Values appearing only inside un-labeled figure bars or heatmap cells are not reconstructed; only numbers stated in text, tables, or inline matrices are reported.

Abstract

• Specialized accelerators (GPUs, TPUs, FPGAs, custom ASICs) are increasingly deployed to train deep learning models, and they exhibit heterogeneous performance behavior across model architectures.

• Existing schedulers for accelerator clusters optimize multi-job, multi-user objectives such as fairness and makespan, but largely do not consider performance heterogeneity.

• The paper proposes Gavel, a heterogeneity-aware scheduler that systematically generalizes a wide range of existing scheduling policies.

  "Gavel expresses these policies as optimization problems and then systematically transforms these problems into heterogeneity-aware versions using an abstraction we call effective throughput."

• Gavel uses a round-based scheduling mechanism to ensure jobs receive their ideal allocation given the target policy.

• Headline claim: heterogeneity-aware policies let a heterogeneous cluster sustain higher input load and improve end objectives such as makespan and average JCT by 1.4× and 3.5× versus heterogeneity-agnostic policies. (§9 states average JCT 3.5×, makespan 2.5×, cost 1.4×.)

1 Introduction

• As Moore's law ends, specialized accelerators have emerged as an alternative to general-purpose CPUs and have been deployed to great effect to train state-of-the-art DNN models for language, image, and video.
• Users must choose among many accelerators: cloud users rent several generations of NVIDIA GPUs and Google TPUs; private clusters accumulate types over time — the authors note their own group's cluster holds NVIDIA Titan V, Titan X, and P100 GPUs. Multi-tenant resources are arbitrated by schedulers such as Themis, Tiresias, AlloX, and Gandiva, which implement cluster-wide policies optimizing fairness or makespan. Choosing the best accelerator type is hard for three reasons.

Reason 1 — Performance Heterogeneity.

• Models show heterogeneous behavior across accelerator types due to architectural differences.

  "Figure 1a shows that a ResNet-50 model sees a nearly 10× speedup from an NVIDIA V100 GPU compared to a K80 GPU, while an A3C Deep Reinforcement Learning model only sees a 2× speedup."

• Figure 1b: once dollar-normalized throughput is considered (throughput ÷ relevant GCP on-demand price), the V100 is no longer optimal for all models — for many models the older P100 is competitive or cheaper per dollar.

• Some policies benefit from splitting a job across resource types: minimizing cost subject to a latency SLO (e.g. finish in 10 hours) might mean starting on a cheaper accelerator and switching to a faster, more expensive device to meet the SLO.

• Thus even single-job accelerator choice is non-trivial and depends on both job and policy; multi-job settings are harder, since granting every job its preferred accelerator may be impossible. Gandiva, Tiresias, and Themis do not consider this behavior.

Reason 2 — Generality across Policies.

• Operators want different policies for different business goals: makespan for batch sets, fairness for ad-hoc jobs, or hierarchical policies dividing resources among high-level entities (e.g. departments) with one policy and among individual jobs with another. Data-analytics clusters (Hadoop, Spark, YARN Capacity Scheduler) already support hierarchical allocation.
• The two heterogeneity-aware GPU schedulers, AlloX and Gandiva_fair, optimize a single objective and tightly couple their mechanism to it (e.g. max-min fairness), so they cannot easily support the more sophisticated policies used in practice.

Reason 3 — Colocation and Placement Optimizations.

• Existing schedulers deploy space sharing (Gandiva — multiple jobs concurrently on one accelerator) and placement sensitivity (Themis, Tiresias — careful task placement in distributed jobs). Their benefits should be considered explicitly while optimizing global objectives, since they are more effective when deployed in a heterogeneity-aware way.
• Quantified: explicit modeling for space sharing improves objectives by 2.2× versus Gandiva's ad-hoc approach.

The proposal and key observation.

• Gavel targets DNN training in on-premise and cloud deployments, incorporating heterogeneity in both hardware and workloads, and provides heterogeneity-aware versions of: fair sharing / least attained service, FIFO, minimum makespan, minimum cost subject to SLOs, finish-time fairness, shortest job first, and hierarchical policies.

  "Gavel's key observation is that many widely used scheduling policies, including hierarchical ones, can be expressed as optimization problems whose objective is a function of the jobs' achieved throughputs."

• LAS is equivalent to maximizing the minimum scaled throughput; makespan is equivalent to minimizing the maximum duration (iterations ÷ achieved throughput); and so on.

• Given a policy's optimization problem, Gavel applies a general transformation making it heterogeneity-, colocation-, and placement-aware: it searches over a heterogeneous allocation per job — the fraction of time spent in various resource configurations (e.g. 60% alone on a V100 and 40% space-sharing an A100 with another job) — and replaces throughput terms with effective throughput, the average throughput over the mix of resources in the allocation. Extra constraints ensure validity.

• The transformed problems are efficient even for clusters with hundreds of GPUs and jobs, and many are solvable as a sequence of one or more linear programs.

From allocation to schedule.

• Allocations must be mapped to actual placement decisions; Gavel uses a preemptive round-based mechanism so jobs receive resources in fractions similar to the target allocation. The mechanism must handle both distributed jobs (multiple accelerators at once) and combinations of jobs concurrently on one accelerator under space sharing.
• Gavel schedules transparently: a scheduler–application API lets PyTorch and TensorFlow jobs move between resources with minimal code changes, and a Quasar-like mechanism estimates colocated-job performance when not available a priori.

Results preview and contributions.

• On a smaller physical cluster, average JCT improves 1.5×. On a larger simulated cluster, Gavel increases the maximum supportable input load while improving average JCT by 3.5×, makespan by 2.5×, and cost by 1.4×.
• Contributions: (1) a systematic method to convert existing policies into heterogeneity- and colocation-aware equivalents that remain practical for current DNN clusters; (2) a round-based scheduling mechanism realizing those allocations; (3) generalizations of many existing policies that improve the corresponding objectives.

2 Background

2.1 Deep Neural Network (DNN) Training

• Training proceeds in iterations; each processes a minibatch and updates parameters from its gradients. Minibatches are of similar size, so throughput can be measured with short profiling runs (order of minutes) — the fact Gavel's throughput estimator leverages. Jobs are long-running (hours to days) and can be distributed over many workers.
• Modern schedulers exploit iterative training to suspend and resume at iteration boundaries, time-multiplexing jobs over physical resources; parameters must be checkpointed to stable storage on suspension so progress is not lost. This work shows how time sharing should be deployed to optimize various single- and multi-job objectives.

2.2 Performance Optimizations

• Prior work shows GPUs can be severely under-utilized in multi-tenant clusters: average GPU utilization (percentage of GPU Streaming Multiprocessors active over time) was as low as 52% on a Microsoft cluster. Task placement for distributed jobs also has significant performance impact. Gavel can deploy these optimizations systematically.
• Space Sharing. Smaller models often do not use a modern GPU's full capacity; concurrently executing multiple models on one GPU via NVIDIA's Multi-Process Service (MPS) or CUDA streams can improve utilization.
• Placement Sensitivity. Models differ in distributed scaling behavior depending on the size of tensors exchanged between workers: some have compact weight representations and scale well even when workers are not co-located, while others scale poorly when spread across servers. Existing schedulers like Tiresias use heuristics for placement sensitivity.

3 System Overview

• Gavel arbitrates accelerators of different types among resident jobs while optimizing the desired objective, in a two-step process.
• Step 1: a heterogeneity-aware policy computes the fraction of time jobs (and combinations) should run on each accelerator type. Policies need per-job, per-accelerator throughputs, either user-provided or measured on the fly by the throughput estimator.
• Allocations are respected only between recomputation events: e.g. if job 1 is much longer than job 2, the allocation is recomputed once job 2 completes. Recomputation is triggered by a reset event (job arrives/completes, worker fails) or at periodic intervals.
• Step 2: the scheduling mechanism grants jobs time on resources and moves jobs between workers so the true fraction of time each job spends on each resource closely resembles the optimal allocation.
• Figure 2 workflow: jobs written in PyTorch/TensorFlow → throughput estimator (optionally seeded by user-supplied measurements) → policy (allocation optimizing a user-specified objective) → scheduling mechanism (per-round placement faithfully mimicking the allocation) → workers (V100, P100, …), with throughput measurements from runs fed back into the estimator.

3.1 Heterogeneity-Aware Policies

• Policies are optimization problems; allocations are matrices giving the fraction of wall-clock time a job spends on each accelerator type between recomputations. A matrix X covers the homogeneous case, the heterogeneous case, and other optimizations:

                 V100   P100   K80
              ┌                      ┐
X_example  =  │  0.6    0.4    0.0   │  job 0
              │  0.2    0.6    0.2   │  job 1
              │  0.2    0.0    0.8   │  job 2
              └                      ┘

• Job 0 spends 60% of the time this allocation is valid on a V100 and the remaining 40% on a P100. Figure 3 visualizes cumulative time per accelerator type between allocation_n and allocation_{n+1}.
• Constructing the problem requires a throughput matrix T, each job's throughput in training iterations per second on each accelerator. T_mj = −∞ if job m cannot run on accelerator j (e.g. memory constraints).
• Given T and X, the effective throughput of model m is the time-weighted average throughput across accelerators and jobs, throughput_T(m, X) (abbreviated throughput(m, X)):

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

• A hypothetical policy maximizing total effective throughput: Maximize_X Σ_{m ∈ jobs} throughput(m, X).
• Validity constraints (Equations 1–3) ensure each job-worker allocation is in [0,1], a job's total allocation does not exceed 1, and workers are not oversubscribed:

(1)   0 ≤ X_mj ≤ 1                                    ∀(m, j)
(2)   Σ_j X_mj ≤ 1                                    ∀m
(3)   Σ_m X_mj · scale_factor_m ≤ num_workers_j       ∀j

Space Sharing (SS).

• Previous work used greedy algorithms; the authors found different pairs of DNN applications have vastly different performance when colocated, based on the resources they consume (Figure 4).
• Figure 4 reports, for several DNN models run concurrently on a single P100 GPU, the normalized throughput (iterations/second) of colocated models i and j, normalized against each model's isolated throughput. Black squares mark pairs that cannot colocate due to memory constraints.
• With SS, X needs rows for each viable job combination and T needs combination throughputs:

                    V100        P100    K80
              ┌                              ┐
T  =          │   40.0         20.0    10.0  │  job 0
              │   15.0         10.0     5.0  │  job 1
              │ (20.0, 7.5)     0.0     0.0  │  jobs (0, 1)
              └                              ┘

• Gavel limits T entries to combinations of at most 2 jobs — larger combinations were found empirically to rarely increase net throughput. Although |T| grows quadratically in the number of jobs even at size 2, in practice only well-performing combinations need to be considered (scaling is evaluated in §7.4).
• Objectives are unchanged in form, but throughput(m, X) is recomputed to include colocated jobs, and constraints are modified, where C_m is the set of all combinations containing job m:

throughput(m, X)  =   Σ_{ j ∈ accel. types }  Σ_{ k ∈ C_m }   T_kjm · X_kjm

0 ≤ X_kj ≤ 1                                     ∀(k, j)
Σ_{k ∈ C_m} Σ_j X_kj ≤ 1                         ∀m
Σ_k X_kj · scale_factor_m ≤ num_workers_j        ∀j

Placement Sensitivity.

• Observed throughput for distributed jobs depends on task location, model, and accelerator type — "slower workers are less likely to be communication-bound, which means consolidation of tasks is less effective."
• Gavel models the two extreme points of the placement space: a consolidated setting with as many accelerators on the same server as possible (e.g. 8 GPUs per server on 8-GPU servers), and an unconsolidated setting with accelerators on independent servers. These are upper and lower bounds on performance, modeled as two different worker types with corresponding values in T and X.

3.2 Round-based Scheduling Mechanism

• After computing the optimal allocation, Gavel must assign jobs (or combinations) to accelerator types matching it as closely as possible — during the period where jobs 0, 1, 2 are the only runnable jobs, they should receive resources according to their computed optimal time fractions.
• The scheduler computes a priority score per (job, accelerator type) that is high when a job has received a smaller time fraction than its optimal allocation. Each round, jobs are run in decreasing priority order while ensuring a job is not scheduled on multiple workers in a given round.
• Figure 5 computes priorities_n = X / rounds_received_n (element-wise division), moving the received allocation toward X_example; per-job rows across the V100 / P100 / K80 columns:

• Priorities are updated as rounds complete. Empirically, round durations of around 6 minutes let Gavel effectively approximate the ideal allocation (§7.5).

3.3 Throughput Estimator

• To estimate throughputs of concurrent jobs (e.g. for SS), Gavel employs a throughput estimator similar to Quasar: it maps a new job to a set of pre-profiled reference jobs and uses the closest reference job's throughputs as the initial estimate for the new job's combinations.
• For individual jobs the estimator is not needed, since throughputs can be estimated on the fly as jobs run on different resource types.

3.4 Limitations and Non-Goals

"While Gavel exposes a flexible API that supports a variety of policies and objectives, we do not propose new scheduling policies or performance optimizations in this work."

• Gavel's goal is to determine how best to share resources among many users and jobs in a heterogeneity-aware way while supporting many existing cluster-wide objectives, via: a policy framework making policies heterogeneity-, colocation-, and placement-aware (§4); a reusable scheduling mechanism (§5); and a narrow scheduler API requiring minimal user code changes (§6).

4 Scheduling Policies

4.1 Max-Min Fairness as an Optimization Problem

• Classical Least Attained Service (LAS), used by Tiresias, implements max-min fairness across active users by round-robining resources according to total accelerator-hours consumed; it extends to weighted max-min fairness with per-user weights w_m.
• On a homogeneous cluster, if job m with weight w_m receives scalar fraction X_m: Maximize_X min_m (1 / w_m) · X_m, with the added constraint Σ_m X_m ≤ 1 (cluster not overprovisioned).
• Vanilla LAS is not fair in a heterogeneous setting: jobs might see unequal throughput reductions due to performance variation across types. Giving one job a K80 and another a V100 equalizes their number of resources but could give very low performance to the K80 job.
• The fix is max-min fairness over weighted normalized effective throughputs. Let X_m^equal be the allocation for job m assuming an equal time share on each worker (for a cluster with 1 V100 and 1 K80, X_m^equal = [0.5, 0.5]); it scales effective throughputs to be comparable across jobs:

Maximize_X   min_m   (1 / w_m) ·  throughput(m, X) / throughput(m, X_m^equal)

• Worked heterogeneous example (3 jobs, 1 V100 + 1 K80, w_m = 1):

            V100     K80                           V100     K80
      ┌                    ┐                ┌                    ┐
T  =  │  40.0     10.0     │  job 0         │  0.45     0.0      │  job 0
      │  12.0      4.0     │  job 1    →    │  0.45     0.09     │  job 1   = X_het.
      │ 100.0     50.0     │  job 2         │  0.09     0.91     │  job 2
      └                    ┘                └                    ┘

• Result: jobs receive about 10% higher throughput than under an allocation giving each user 1/n of the time on each accelerator (here n = 3), also called an isolated allocation.
• Fairness objectives must account for jobs with scale_factor_m > 1, which occupy a larger share of the cluster per unit time; an easy way is to multiply the max-min objective by scale_factor_m:

Maximize_X  min_m  (1 / w_m) · [ throughput(m, X) / throughput(m, X_m^equal) ] · scale_factor_m

4.2 Other Policies as Optimization Problems

• Many common policies can be expressed using throughput(m, X). Most need a single linear program; the exception is the cost policies, formulated as a linear-fractional program reducible to a sequence of LPs. Optimal allocations can be computed with off-the-shelf solvers.

Table 1: Policies that can be expressed in Gavel

• Minimize Makespan completes all active jobs as soon as possible; Gandiva uses a version of this for higher-level tasks such as hyperparameter tuning and AutoML, which train many model variants. With num_steps_m iterations remaining for model m: Minimize_X max_m num_steps_m / throughput(m, X).
• Minimize Finish-Time Fairness (Themis). Themis proposes finish-time fairness ρ, the ratio of the time to finish a job under a given allocation to the time under 1/n of the cluster (X^isolated), assuming n users. With t_m the time elapsed since training started for model m and t_m^isolated the hypothetical elapsed time under 1/n of the cluster:

                   t_m + num_steps_m / throughput(m, X)
ρ_T(m, X)  =  ────────────────────────────────────────────────────
              t_m^isolated + num_steps_m / throughput(m, X^isolated)

Minimize_X   max_m   ρ_T(m, X)

• FIFO schedules jobs in arrival order; in a heterogeneous regime jobs should be placed on the fastest available accelerator type, i.e. maximize throughput relative to throughput(m, X^fastest). With jobs enumerated in arrival order and M the total number of jobs: Maximize_X Σ_m [ throughput(m, X) / throughput(m, X^fastest) ] · (M − m).
• Shortest Job First minimizes the duration of the shortest job: Minimize_X min_m num_steps_m / throughput(m, X).
• Minimizing Total Cost and Cost subject to SLOs. For elastic public-cloud deployments, since VMs are charged per unit time, policies can explicitly optimize total cost, speed, or both. The simple total-throughput policy is written in the paper as Minimize_X Σ_m throughput(m, X) (transcribed as printed; §3.1 states the same total-throughput policy with Maximize_X). The cost-adjusted objective, with cost_j the cost of accelerator type j:

Maximize_X    [ Σ_m throughput(m, X) ]  /  [ Σ_m ( Σ_j cost_j · X_mj ) ]

The numerator is time-averaged effective throughput, the denominator time-averaged cost. Under space sharing, care must be taken not to double-count the cost of instances running job combinations (all jobs in a combination derive value as some throughput).

• Jobs can have time SLOs (e.g. certain high-priority jobs must complete every 12 hours). Given SLO_m per model (SLO_m = ∞ for models without SLOs), add: throughput(m, X) ≥ num_steps_m / SLO_m.

4.3 Hierarchical Scheduling Policies

• Hierarchical policies are common: an organization shares one cluster among entities using a fairness policy, and each entity shares resources among jobs using a distinct per-entity policy such as per-user fairness or FIFO.
• Figure 6: a research team and a product team share a cluster under weighted fairness (w_1, w_2); the research team runs ad-hoc experiments in FIFO order (jobs 4, 5), while the product team needs fairness across its jobs (jobs 1, 2, 3).
• Gavel supports fairness in the upper levels and fairness or FIFO in the lower levels, matching the hierarchical policies supported by the Hadoop scheduler. Extending to other hierarchical policy sets (e.g. with finish-time fairness) is future work.
• Gavel solves hierarchical objectives with water filling, used in other max-min fairness problems such as link allocation in networks: increase all parties' allocations at an equal rate until a party saturates, remove the saturated party, and repeat until all commodities are saturated.
• Gavel adapts this by iterating two problems: an LP computing a fair allocation across entities while respecting each entity's internal policy, and an MILP identifying bottlenecked jobs — jobs whose effective throughputs cannot be improved without lowering others'.
• Each entity s has weight w_s; its jobs receive a total cluster share proportional to w_s. w_m^job is job m's weight, set so Σ_{m ∈ s} w_m^job = w_s. Priorities follow the entity's policy: a fairness policy assigns each job a weight proportional to its individual weight within the entity, while under FIFO the first job in the queue initially receives the entity's entire weight.
• Each iteration solves the modified LP below (assuming scale_factor_m = 1 for simplicity), where t_m is job m's normalized effective throughput in the previous iteration (t_m := 0 initially); the objective can be modified for scale_factor_m > 1:

Maximize_X   min_{ m : w_m^job > 0 }   (1 / w_m^job) · [ throughput(m, X) / throughput(m, X_m^equal) − t_m ]

• Bottlenecked jobs get priority 0 and are excluded from future iterations; priorities are redistributed among non-bottlenecked jobs per the entity's policy. In Figure 6, if job 4 is bottlenecked its weight is reassigned to job 5 per FIFO; if job 2 is bottlenecked its weight is split equally between jobs 1 and 3 per the entity's fairness policy.
• The LP solves max-min on remaining resources while ensuring no job's throughput drops versus the previous allocation X^prev: throughput(m, X) ≥ throughput(m, X^prev) for all m. Iterations continue until all jobs are bottlenecked.
• Concrete example: 4 identical jobs on 4 identical GPUs, job 1 with weight 3.0 and jobs 2–4 with weight 1.0. In iteration 1, job 1 gets throughput 1.0 and jobs 2–4 get 0.33, respecting weights; job 1 is a bottleneck while the others can still improve, so in iteration 2 jobs 2–4 get full-GPU allocations.
• The final allocation satisfies both inter-entity and intra-entity policies. Water filling can also be used for single-level fairness policies (§4.1) to improve non-bottlenecked jobs' throughput.

4.4 Properties of Gavel's Policies

• Existing schemes are analyzed via sharing incentive, Pareto efficiency, and strategy proofness; the paper formalizes Gavel's policies in this context.
• Homogeneous Clusters. Gavel's heterogeneity-aware policies are equivalent to the baseline policies (throughput(m, X) = X_m · T_m), since the problems reduce to the originals with one type.
• Sharing Incentive. On heterogeneous clusters the policy's objective metric (least job share in LAS, first job's completion time in FIFO, or makespan) is at least as good as under a policy that naïvely splits resources equally, because the 1/n-of-each-resource allocation is a feasible solution to Gavel's problem. All Gavel policies have sharing incentive, encouraging users to use the shared cluster rather than a static private share.
• Colocation. Solutions with colocation are always at least as good as without.
• Pareto Efficiency. Max-min fairness allocations with water filling are Pareto efficient: no job's allocation can be increased without decreasing another's.
• Not strategy-proof. Sun et al. showed no fair-sharing policy can simultaneously satisfy Pareto efficiency, sharing incentive, and strategy proofness with interchangeable resources. If users manipulate their throughputs they can possibly obtain larger cluster shares (e.g. placement on a faster accelerator type) for certain objectives. Making the policies strategy-proof is future work.

5 Scheduling Mechanism

• The mechanism schedules training iterations of runnable jobs on available workers so that, for each schedulable job (or combination), the fraction of wall-clock time on each accelerator type is approximately equal to the computed optimal allocation X^opt between recomputation events.

• Two challenges: (1) jobs can run on multiple accelerators, and since distributed training can be communication intensive, jobs should be placed on accelerators "close" to each other (same server, or servers in the same rack); (2) combinations of up to two jobs can run on a set of accelerators for space sharing, and each distinct job can have ≤ 1 combination running per round to prevent work duplication.

• Round-based scheduling is similar in spirit to Tiresias's priority discretization, but differs in three ways: Gavel must schedule jobs on different accelerator types (deciding both which job is active and which type it uses); it must respect an arbitrary allocation returned by the policy; and it must ensure multiple job combinations sharing a job do not run in the same round (Tiresias does not consider combinations).

• Gavel places work on all available workers for a configurable duration — 6 minutes in the experiments — and calls the work handed to each worker in a round a micro-task.

• Without rounds, jobs requesting many accelerators can starve. With 8 total accelerators and 4 available and an 8-accelerator job waiting, the scheduler could (a) wait for 8 to free, leaving 4 unused, or (b) keep the job queued and give the 4 to a smaller job — but this can repeat, causing starvation. Rounds therefore limit under-utilization, simplify scheduling logic, and ensure jobs with large scale factors do not experience prolonged starvation.

• Since active schedulable jobs may far exceed workers, Gavel first picks which combinations run next round. It maintains t_mj, time spent by job (or combination) m on accelerator type j, updated each round, and computes the fraction of total wall-clock time f_mj = t_mj / ( Σ_{m'} t_{m'j} ). The priority matrix is the element-wise division of X^opt by f.

• Each round the goal is to move f_mj closer to X^opt_mj by giving high-priority jobs time on type j. This is solvable exactly if jobs request single accelerators and SS is off (find the num_workers_j highest-priority jobs, e.g. with a heap), but with distributed jobs and SS the exact problem resembles a multiple-choice knapsack problem, which is NP-hard.

  "we observe that it is acceptable to make greedy sub-optimal scheduling decisions occasionally in any given round, since we can recover from these sub-optimal decisions in subsequent rounds"

• The goal is that the average allocation over multiple rounds resembles the computed allocation (§7.5 studies this design choice). A job not run in a round has increased priority subsequently until it receives accelerator time; a job that runs has decreased priority, so jobs with a non-zero optimal allocation do not starve.

• Gavel greedily picks the highest-priority combinations fitting the resource budget: it maintains eligible_job_combinations, adds highest-priority ones to job_combinations_to_schedule, and removes all conflicting combinations (sharing a job) so no job runs twice in a round; combinations that cannot fit due to space limits are also removed.

Algorithm 1 (as printed):

 1: function SCHEDULE_JOBS
 2:     active_combinations ← all active job combinations
 3:     num_workers_rem. ← number of total workers
 4:     while num_workers_rem. > 0 do
 5:         j ← job combination with highest priority
 6:         Remove j from active_combinations
 7:         if j.scale_factor > num_workers_rem. then
 8:             continue
 9:         for all j' that conflict (share a job k) with j do
10:             Remove j' from active_combinations
11:         num_workers_rem. −= j.scale_factor

• The mechanism is decoupled from the policies, so the same mechanism serves many policies. Figure 7 shows it achieving X^{het.+SS} — the V100 column runs the space-shared 0+1 combination every round while P100 and K80 alternate jobs 2 and 3:

                 V100   P100   K80
              ┌                      ┐
X^{het.+SS} = │  1.0    0.0    0.0   │  jobs 0+1   (space-shared pair)
              │  0.0    0.5    0.5   │  job 2
              │  0.0    0.5    0.5   │  job 3
              └                      ┘

• Placement. Once the round's jobs are chosen, Gavel places them in decreasing order of requested workers and tries to give jobs accelerators on the same physical server to minimize fragmentation.

6 Implementation

• Prototype in approximately 9000 lines of Python, with a simulator in about 500 LOC; cvxpy implements the heterogeneity-aware policies and gRPC carries control messages between scheduler and workers.
• Interface. Gavel currently supports PyTorch; TensorFlow support is left for future work. A Python library provides GavelIterator, a wrapper around framework-provided data iterators that ensures each task in a distributed job runs the same number of iterations and synchronizes round conclusions between scheduler and workers.
• GavelIterator takes train_loader (base data loader), load_checkpoint, save_checkpoint, and a configuration object; load_checkpoint loads all necessary parameters and metadata at round start and save_checkpoint creates a checkpoint at round end, each needing < 5 LOC of framework calls.
• Near a round's end GavelIterator contacts the scheduler to see if the same job will run next round on the same worker — a lease renewal. If not renewed, it calls save_checkpoint at round end and the scheduler launches another job on the worker.
• Throughput Estimation. Gavel uses a Quasar-like technique for colocated throughputs when not available a priori, mixing profiling with matrix completion. Matrix completion reconstructs sparse low-rank matrices with low error, letting Gavel extrapolate measurements from separate workers dedicated to profiling and identify the most similar pre-profiled reference job, whose throughputs become the initial estimate.
• Figure 8: an offline reference matrix R (rows = reference jobs 1…r; green entries measured, black entries not) plus a new job i goes through matrix completion to produce R^est whose hashed entries estimate the missing black entries; the completed row is job i's fingerprint, used to find the closest reference job.

7 Evaluation

Questions: do the heterogeneity-aware policies improve objectives on a physical cluster (§7.2) and in simulations of larger clusters (§7.3)? How do the policies scale (§7.4)? How well does the mechanism realize the allocations (§7.5)? Can Gavel accurately estimate colocated throughputs (§7.6)?

7.1 Experiment Setup

• Physical cluster: 8 V100s, 16 P100s, 24 K80s. Simulated cluster: 36 GPUs of each type.
• Two trace types: static (all jobs available at the start, none added later) and continuous (jobs continuously added). Continuous arrivals follow a Poisson process with inter-arrival rate λ; in simulation λ is varied to show the extra load each policy sustains in steady state, with 3 seeds per λ and standard deviations shown. Physical experiments use a single λ keeping the cluster well utilized.
• Simulated online traces have at least 5000 jobs spanning 20–30 days; completion times of jobs with ID 4000 to 5000 are measured for steady-state behavior (new jobs keep arriving until the jobs of interest complete). Job types are uniformly sampled from a table of 26 distinct job (model) types (Table 2). Physical online traces span a day with 100 jobs.
• Job duration model (matching Gandiva's process): duration on a V100 is sampled from an exponential distribution — jobs have duration 10^x minutes, x drawn uniformly from [1.5, 3] with 80% probability and from [3, 4] with 20% probability; the number of training steps is inferred by multiplying V100 throughput (steps/sec) by duration.
• Two simulated regimes: continuous-single (all jobs use one worker) and continuous-multiple (70% of jobs request 1 worker, 25% request 2–4 workers, 5% request 8 workers — as observed in published Microsoft traces).

Table 2: Models used in the evaluation

• Metrics. For fairness and FIFO policies: average JCT of steady-state jobs (the metric used by related work). Finish time fairness (FTF) is also shown for policies optimizing it. For makespan policies: time to complete a job batch. For cost policies: cost in dollars and the percentage of jobs violating time SLOs.

7.2 End-to-End Results on Physical Cluster

• Physical runs compare a heterogeneity-aware vs. heterogeneity-agnostic fairness policy on a continuous trace, and a heterogeneity-aware makespan policy against a baseline using Gandiva's ad-hoc space sharing on a static trace.
• Gavel improved average JCT by 1.5× and makespan by 1.2×. For the makespan objective Gavel was not run with space sharing; in theory space sharing would additionally reduce makespan.
• Simulation and physical metrics differ by < 8%, indicating high simulator fidelity.

Table 3: End objective, physical experiment vs. simulation

(Continuous trace: average JCT of 25 jobs in a steady-state cluster. Static trace: total time to complete 100 jobs submitted at the start of the run.)

• Allocations and worker assignments can be computed asynchronously; the only synchronous overhead is loading and saving checkpoints, dependent on model size. Lease renewals reduce this by letting jobs run on the same worker for extra rounds. Preemption overhead, even without lease renewals and with a short round duration, is low (< 3%).

Table 4: Overhead of preemptive scheduling (round duration = 6 minutes)

7.3 End-to-End Results in Simulation

• A larger simulated cluster evaluates the policies across objectives against heterogeneity-agnostic versions from previous work, using a 6-minute round duration, plus baselines such as AlloX.
• Speedup magnitudes are higher in simulation than on the physical cluster because simulated traces span weeks while physical traces span a day, so queue buildups are less extreme in the latter.

Least Attained Service (LAS) (Figures 9, 10). Baselines: vanilla LAS; LAS with Gandiva's ad-hoc space sharing; and AlloX, which explicitly optimizes average JCT but only for single-worker jobs.

• First, heterogeneity-aware policies support higher load on the same cluster and reduce average JCT by 3.5× for continuous-single and 2.2× for continuous-multiple at high load (5.6 jobs/hr and 2.6 jobs/hr respectively); the graph is read by comparing average JCT at a given input job rate, or by x-intercept.
• Second, heterogeneity-aware LAS supports higher load than AlloX, since AlloX gives short jobs preferential treatment to optimize average JCT, causing long jobs to starve (a long tail in the JCT CDF). At moderate load AlloX is a best case since it explicitly optimizes average JCT on a heterogeneous cluster; Gavel essentially matches it while also supporting other objectives.
• Third, Gandiva-style packing — randomly exploring job combinations until one improves performance — is ineffective versus Gavel's principled packing: 2.2× better average JCT on both traces at high load.

Finish Time Fairness (FTF) (Figure 11, continuous-multiple).

• The heterogeneity-aware policy reduces average JCTs by 3× and improves average FTF by 2.8× versus its heterogeneity-agnostic counterpart. FTF is the ratio of the time to finish a job under a given allocation to the time under 1/n of the cluster (X^isolated) assuming n users; lower FTF means jobs take less time under the provided allocation.

Makespan.

• Gavel's heterogeneity-aware makespan policy reduces makespan by 2.5× versus a FIFO baseline and by 1.4× versus a baseline using Gandiva's ad-hoc space sharing. Makespan is reduced by a further 8% when the number of jobs in the trace is high, when using space sharing.

FIFO.

• Heterogeneity-aware FIFO lets the cluster support higher average input job rate. At high load, the version without space sharing reduces average JCT by 2.7× and the version with space sharing by 3.8×. Space sharing is less effective for distributed jobs: it reduces average JCT by 1.1× with distributed jobs versus 1.4× for continuous-single.

LAS with priorities.

• With 20% of jobs at higher priority, at high load Gavel reduces the average JCT of high-priority jobs by 1.5× and of low-priority jobs by 2.7×.

Cost.

• Simulated on a 500-job workload of ResNet-50 and A3C jobs. Per Figure 1b, ResNet-50 has the best cost-normalized throughput on the V100 and A3C on the K80. Each job's duration is chosen from {0.5, 1, 2, 4, 8} days and each SLO from {1.2×, 2×, 10×} its duration.
• The minimize-cost policy reduces total cost versus the maximize-throughput policy by roughly 1.4×, but approximately 35% of jobs violate their SLO, since it prioritizes cheaper but slower GPUs — in particular A3C jobs land on K80s, causing violations for tight SLOs.
• The cost-with-SLO policy eliminates all violations for a small increase in cost (a cost reduction of 1.2× versus the baseline policy), by ensuring A3C jobs with tight SLOs run on V100 instances.

Multi-level Hierarchical Policies (Figures 12, 13).

• Setup: 3 V100, 3 P100, 3 K80 GPUs; jobs added every 4 timesteps; the first 6 jobs belong to entity 0 (w_0 = 1), the next 6 to entity 1 (w_1 = 2), the last 6 to entity 2 (w_2 = 3).
• Figure 12a: resources respect both higher- and lower-level policies — fairness is enforced within and across entities, visible as the widths of the colored bands (cross-entity fairness) and the widths of bands within a color (fairness across jobs within an entity); allocations adjust as new jobs arrive.
• Figure 13: under a fairness + FIFO policy (weighted fairness on top, FIFO below), later jobs in entity 0 receive no GPU time, respecting the per-entity FIFO policy.
• The multi-level fairness policy can also be implemented heterogeneity-agnostically by statically partitioning resources across users while respecting per-entity and per-user weights. That is also fair, but total effective throughput is about 17% lower (Figure 12b).

7.4 Scalability of Heterogeneity-Aware Policies

• Figure 14 shows scaling of heterogeneity-aware LAS and multi-level fairness (hierarchical) policies with and without space sharing, on a cluster with equal numbers of V100, P100, and K80 GPUs, cluster size growing with active job count (x-axis 32 to 2048 jobs, y-axis 0.125 s to 512 s).
• Even with 2048 active jobs the hierarchical policy without space sharing runs in < 10 minutes; with space sharing it runs with 512 jobs in < 10 minutes. The single-level LAS policy is much cheaper to compute.
• Allocations need not be recomputed every scheduling round, but the longer the policy takes, the longer before the new allocation is acted upon (jobs can still receive heterogeneity-agnostic allocations, and hence resource time, in the interim).
• The authors argue latencies of < 30 minutes for large clusters are preferable to non-preemptive schedulers with large queuing delays, or preemptive schedulers with heterogeneity-agnostic policies that give worse objective values.

7.5 Efficacy of Scheduling Mechanism

• Figure 15a: effect of round length on average JCT for heterogeneity-aware LAS with a single-GPU trace, comparing 360 s, 720 s, 1440 s, 2880 s; similar behavior was seen on multi-GPU traces and other policies. A smaller round length gives more rounds to course correct, bringing the true and computed optimal allocations closer.
• Checkpoint load/save for the target models takes < 5 seconds, so a 6-minute round gives a good tradeoff between allocation fidelity and preemption overhead (Table 4).
• Figure 15b: Gavel's mechanism at 6-minute rounds behaves almost identically to an ideal baseline that allocates resources exactly per the computed allocation, with a single-GPU trace (multi-GPU is similar). The ideal baseline is impractical: jobs with different scale factors complete at different times (causing starvation), and preemptions can be frequent since some (job, accelerator type) allocations are small, driving high overhead.

7.6 Impact of Throughput Estimation

• Figure 16 compares the SS-aware LAS policy with estimated throughputs against the same policy with oracle throughputs and against LAS without space sharing, on a heterogeneous 12-GPU cluster.
• The estimator determines missing throughputs online accurately enough that only a very small decrease in average JCT at high load is observed relative to the oracle.

8 Related Work and Discussion

Existing DNN Training Schedulers.

• Gandiva uses time and space sharing to cut queuing delay and improve utilization but does not specify an explicit scheduling policy and does not support configurable objectives; its profiling-based colocation decision does not incorporate model performance data (isolated or co-located) into its policy, instead using random exploration of job combinations until one improves performance.
• Tiresias and Themis use different objectives for multi-job fairness but do not incorporate jobs' affinities for different accelerator types, and their mechanisms are strongly coupled with the target policy, making sophisticated policies like multi-level fairness hard to support.
• AlloX and Gandiva_fair consider worker and model heterogeneity but only for single policies (average JCT for AlloX, max-min fairness for Gandiva_fair). Gandiva_fair uses a second-price auction to improve a heterogeneity-agnostic max-min fairness scheme but gives no optimality guarantee. Gavel formalizes each policy as an optimization problem, can guarantee the returned solution is "optimal" per the provided objective, and supports multi-level fairness.

Traditional Cluster Schedulers. Mesos, Borg, TetriSched, YARN support fixed heterogeneous resource requests but do not reason about jobs' diverse performance across accelerators, nor about interchangeable resource types that run the same computation: Mesos's DRF allocates distinct resource types (RAM vs. CPUs) but assumes each job declared which resources it needs and in what ratio. The multi-interchangeable resource allocation (MIRA) problem introduces a similar notion of effective throughput but does not show how to specify policies as optimization problems, ignores space sharing and placement sensitivity, and does not discuss realizing allocations on physical resources. Omega, Apollo, Hydra handle heterogeneity in task number and duration, but tasks largely take the same time on different CPUs and memory heterogeneity only affects how many/large tasks fit on a server; in Gavel's setting the compute devices themselves are interchangeable with sometimes large performance differences, and policies decide time fractions while optimizing end objectives.

Dynamic Performance Estimation. Gavel uses Quasar's approach to estimate co-located performance online, mixing profiling and matrix completion to compute a "fingerprint" against offline-profiled reference models; the contribution is showing Quasar's techniques apply to this new setting.

Applicability to Other Settings. The authors believe Gavel can serve non-DNN GPU workloads such as simulations (given performance estimates), and that the main insight — formulating diverse scheduling policies as optimization problems — is broadly applicable, usable on homogeneous deep learning clusters and on CPU clusters.

9 Conclusion

• Gavel is a heterogeneity-aware cluster scheduler optimizing high-level metrics such as fairness, makespan, and cost; it shows how existing policies can be expressed as optimization problems, extends them to be heterogeneity-aware, and uses a decoupled round-based scheduling mechanism to realize the computed optimal allocation.
• Gavel's policies improve end objectives on both physical and simulated clusters, supporting a higher average input job rate while improving average job completion time by 3.5×, makespan by 2.5×, and cost by 1.4×.

A Artifact Appendix

• Open-sourced at https://github.com/stanford-futuredata/gavel (MIT License), including the heterogeneity-aware policies, the round-based mechanism, GavelIterator, baselines such as AlloX, a simulator, and code to reproduce the paper's graphs. Simulation runs on any multicore server with Ubuntu 16.04 (the authors used a 56-core server); physical experiments need NVIDIA GPUs (other framework-supported accelerators also work).
• Disk space: ~100 GB for simulated-experiment logfiles, ~10 GB for physical-experiment model checkpoints, ~150 GB for datasets. Run time: days to a week for full simulated experiments; hours to a day scaled down (via smaller cluster, fewer traces, smaller traces, or a smaller set of jobs of interest). Experiments can be run with different seeds via the sweep scripts.
• Workflow: a driver script instantiates the scheduler and adds jobs from a pre-defined trace or on-the-fly distributions; the scheduler computes the optimal allocation per active job and assigns resources via the round-based mechanism. In simulation, oracle throughputs estimate job progress; for makespan policies jobs are added once at the start and then drain from the cluster. On physical clusters the structure is the same but jobs run on real accelerators for the specified number of steps.

Cross-Cutting Quantitative Summary

Limitations

Sourcing note: items under Stated by the paper are limitations, non-goals, or future work the paper itself declares. Items under Observed by this reviewer are my own framing of facts the paper reports; the paper does not present them as limitations.

Stated by the paper

• Gavel proposes no new scheduling policies or performance optimizations (§3.4, an explicit non-goal); the contribution is the transformation and the mechanism, so policy quality is inherited.
• Not strategy-proof (§4.4): users who manipulate their reported throughputs can possibly obtain larger cluster shares for certain objectives; making the policies strategy-proof is future work. This matters because the throughput matrix T can be user-provided.
• Hierarchical coverage is partial: only fairness at the upper levels and fairness or FIFO at the lower levels, matching the Hadoop scheduler; extending to other sets (e.g. finish-time fairness) is future work.
• Placement sensitivity is modeled only at two extreme points — fully consolidated and fully unconsolidated — described by the paper as upper and lower bounds rather than a full placement model.
• Space sharing is capped at combinations of 2 jobs, justified empirically ("larger combinations rarely increase net throughput"); |T| still grows quadratically in the number of jobs.
• Policy computation 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 for large clusters, during which jobs receive heterogeneity-agnostic allocations.
• The scheduling mechanism is deliberately greedy and sub-optimal per round (the exact problem is NP-hard), so fidelity to X^opt is only achieved on average over multiple rounds.
• Framework support is limited to PyTorch; TensorFlow support is left for future work.

Observed by this reviewer

• Round duration is bounded below by checkpoint cost (< 5 s for the target models); models with larger checkpoints would raise preemption overhead and force longer rounds, degrading allocation fidelity.
• Simulation carries most of the headline numbers: the physical cluster (8 V100 + 16 P100 + 24 K80, one-day traces, 100 jobs) yields 1.5× / 1.2×, while 3.5× / 2.5× / 1.4× come from simulated 20–30-day traces; the paper attributes the gap to queue-buildup differences.
• Job durations and arrivals are synthetic — Poisson arrivals and a 10^x-minute duration distribution borrowed from Gandiva — rather than replayed from a production trace.
• The evaluated heterogeneity is one vendor and three GPU generations (V100 / P100 / K80); the TPUs, FPGAs, and ASICs that motivate the paper are not evaluated, and the cost policies are exercised on a narrow two-model workload (ResNet-50 and A3C) chosen because the two have opposite cost-normalized optima.
• Space sharing is much less effective for distributed jobs (1.1× vs. 1.4×), limiting the benefit of principled packing in exactly the multi-GPU regime that large-model training occupies.