Architecture & Design Analysis

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

Source: Narayanan, D.; Santhanam, K.; Kazhamiaka, F.; Phanishayee, A.; Zaharia, M. 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI '20), November 4-6, 2020, pp. 481-498. ISBN: 978-1-939133-19-9 Affiliations: Stanford University (Narayanan, Santhanam, Kazhamiaka, Zaharia); Microsoft Research (Phanishayee). Narayanan and Santhanam did part of the work as interns at Microsoft Research. Code: https://github.com/stanford-futuredata/gavel Reader: Direct PDF text extraction (pdftotext -layout), cross-read against a delegated PDF-reader pass. Analyst: Vishwakarma Date: 2026-09-01

Filename note. The local file is 0067_Gravel.pdf, but the paper itself is titled Gavel throughout (system name, code repository, and all in-text references). "Gravel" appears nowhere in the document. This analysis uses the paper's own spelling.

Figure-reference convention. Fig N with a ^ caption refers to a diagram drawn in this document. Figure N / paper Fig. N always refers to a figure in the Gavel paper itself.

Table of Contents

1. System Architecture (the scheduler)
2. Cluster & Workload Architecture (the system under test)
3. Design-Space Diagram (axes swept, axes held fixed)
4. Algorithm & Control-Flow Diagrams (key procedures)
5. Quantitative Results — Empirical Findings by Regime
6. Configuration-Regime Trade-off Tables
7. Bottlenecks & Insights Surfaced by the Measurements
8. Limitations of the Methodology
9. Note on NCCL Tuning
10. Analogy

1. System Architecture (the scheduler)

Gavel is a cluster scheduler for DNN training jobs on a pool of heterogeneous accelerators. Its central architectural bet is a decoupling: scheduling policy is a mathematical optimization problem whose output is an allocation matrix, and a separate, policy-agnostic mechanism realizes that matrix on physical hardware. §3.4 states the scope explicitly — Gavel proposes no new scheduling policies and no new performance optimizations, only a framework that makes existing policies heterogeneity-, colocation-, and placement-aware.

+------------------------------------------------------------------+
|                          G A V E L                               |
|                                                                  |
|  +--------------------+   jobs written in PyTorch / TensorFlow   |
|  | Training jobs      |                                          |
|  +---------+----------+                                          |
|            |  (measurements supplied by user, if available)      |
|            v                                                     |
|  +--------------------+         +--------------------------+     |
|  | Throughput         |== T ===>| Policy                   |     |
|  | Estimator          | tensor  | (optimization problem    |     |
|  | (profiling +       |<--------+  over allocation X)      |     |
|  |  matrix completion)|         +------------+-------------+     |
|  +--------------------+                      |                   |
|            ^                       X (allocation matrix)         |
|            |                                 v                   |
|            |                    +--------------------------+     |
|            |                    | Scheduling Mechanism     |     |
|            |                    | (round-based, priority-  |     |
|            |                    |  driven, policy-agnostic)|     |
|            |                    +------------+-------------+     |
|            |                       per-round placement           |
|            |                                 v                   |
|            |   +------------------------------------------+      |
|            |   | Accelerator pool: ..V100 ..P100 ..K80    |      |
|            |   +------------------------------------------+      |
|            +====== observed throughputs =====+                   |
+------------------------------------------------------------------+
^ Fig 1: Gavel overview, redrawn from Figure 2. The user supplies an
  objective; the policy emits X; the mechanism turns X into per-round
  placements. The feedback edge from the pool back to the estimator
  closes the loop.

The interface between the three boxes is deliberately narrow: the policy consumes T and emits X, the mechanism consumes X and emits placements, and neither knows the other's internals. The paper states the payoff directly — "Gavel's scheduling mechanism is decoupled from its policies, ensuring that the same scheduling mechanism can be used for many different policies" — and this is precisely what it claims prior schedulers (Tiresias, Themis, AlloX, Gandiva-fair) lack, because their mechanisms are "strongly coupled with the target policy."

1.1 Where Gavel sits in the stack

+------------------------------------------------+
| User objective (fairness / makespan / cost)     |  <- declarative
+------------------------------------------------+
| Policy layer: LP / LP-sequence / MILP (cvxpy)   |
|   Table 1 policies, all over throughput(m, X)   |
+------------------------------------------------+
| Allocation matrix X   (the narrow waist)        |  <- the contract
+------------------------------------------------+
| Scheduling mechanism: rounds, priorities,       |
|   greedy conflict-free selection (Algorithm 1)  |
+------------------------------------------------+
| Scheduler <-> application API (gRPC control)    |
|   GavelIterator, lease renewal, checkpoints     |
+------------------------------------------------+
| DNN framework (PyTorch; TensorFlow future work) |
+------------------------------------------------+
| Accelerators: V100 / P100 / K80                 |
+------------------------------------------------+
^ Fig 2: Layered view. X is the narrow waist: everything above is
  declarative optimization, everything below imperative placement.
  Only two things cross it -- X downward, measured throughputs up.

The narrow waist is what lets the paper claim generality across the nine policies in Table 1: adding a policy means writing one new objective function over throughput(m, X), and touching neither the mechanism, the API, nor the estimator.

1.2 The allocation matrix and effective throughput

The allocation matrix X gives, for each job m and accelerator type j, the fraction of wall-clock time job m should spend on type j between allocation recomputation events. The paper's worked example:

                       V100   P100   K80
                     +-----------------------+
   X_example =       | 0.60   0.40   0.00 |  job 0
                     | 0.20   0.60   0.20 |  job 1
                     | 0.20   0.00   0.80 |  job 2
                     +-----------------------+

Effective throughput is the time-weighted average of a job's throughput across the accelerator types it is allocated:

     throughput(m, X) =    SUM      T_mj * X_mj
                       j in accel.
                            types

Constraints (equations 1-3 of the paper):

   (1)  0 <= X_mj <= 1                                    for all (m,j)
   (2)  SUM_j X_mj <= 1                                   for all m
   (3)  SUM_m X_mj * scale_factor_m <= num_workers_j      for all j

Equation 1 keeps entries valid fractions, equation 2 stops a job from exceeding 100% of wall-clock time, and equation 3 stops an accelerator type from being oversubscribed. T_mj is set to -inf when job m cannot run on type j (for example, due to memory constraints).

  +----------------+                         +-----------------+
  | Throughput     |  == T (m x j matrix) ==> | Policy solver   |
  | matrix T       |    iterations/second     | (cvxpy)         |
  |  T_mj = -inf   |                          |                 |
  |  if infeasible |  <== profiling requests ==|                |
  +----------------+                          +--------+--------+
                                                       |
                                        X (m x j allocation matrix)
                                                       |
                                                       v
  +-----------------------------------------------------------+
  |  throughput(m, X) = SUM_j  T_mj * X_mj                    |
  |    -- the single scalar every Table 1 policy optimizes    |
  +-----------------------------------------------------------+
^ Fig 3: Data flow around the effective-throughput abstraction.
  Every policy in Table 1 is a different objective function over
  this one scalar. That uniformity is what makes the framework
  generalize.

1.3 Three optional extensions to the matrix

The same matrix formalism absorbs two performance optimizations and one placement concern, without changing the mechanism:

Space sharing (SS). Rows are added for job combinations, and T carries per-combination throughputs. The paper's example:

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

Entries of T are limited to combinations of at most 2 jobs; the paper states they "found empirically that larger combinations rarely increase net throughput." The throughput expression generalizes to throughput(m, X) = SUM_j SUM_{k in C_m} T_kjm * X_kjm, where C_m is the set of all job combinations containing job m. Constraints become 0 <= X_kj <= 1, SUM_{k in C_m} SUM_j X_kj <= 1, and SUM_k X_kj * scale_factor_m <= num_workers_j.

Placement sensitivity. Rather than a new mechanism, Gavel adds two worker types — consolidated (as many accelerators on the same server as possible) and unconsolidated (accelerators on independent servers) — each with its own rows in T and X, described as "extreme points in the placement space" and "upper and lower bounds on performance." The stated reason placement matters is communication: "some models have compact weight representations and can scale well even when workers are not on the same server, while other models scale poorly when workers are spread over many servers." The paper also notes that "slower workers are less likely to be communication-bound," so consolidation is less effective on slower accelerator types.

Multi-resource jobs. scale_factor_m enters both constraint 3 and the fairness objectives, because multi-resource jobs occupy a larger share of the cluster per unit time. The LAS objective becomes

   Maximize_X  min_m  (1/w_m) * ------------------------------- * scale_factor_m
                                 throughput(m, X)
                                 throughput(m, X_m^equal)

2. Cluster & Workload Architecture (the system under test)

Gavel is evaluated on two clusters — one physical, one simulated — and the paper explicitly validates the simulator against the hardware.

+--------------------- PHYSICAL CLUSTER (§7.1, §7.2) ---------------+
|                                                                   |
|   +-------------+   +-------------+   +-------------+             |
|   |  8 x V100   |   | 16 x P100   |   | 24 x K80    |             |
|   |  (fastest)  |   |  (middle)   |   |  (slowest)  |             |
|   +-------------+   +-------------+   +-------------+             |
|                    total: 48 GPUs                                 |
|                                                                   |
|   Traces: "static"     -> 100 jobs, all present at t=0            |
|           "continuous" -> Poisson arrivals, span 1 day, 100 jobs  |
+-------------------------------------------------------------------+

+--------------------- SIMULATED CLUSTER (§7.1, §7.3) --------------+
|                                                                   |
|   +-------------+   +-------------+   +-------------+             |
|   | 36 x V100   |   | 36 x P100   |   | 36 x K80    |             |
|   +-------------+   +-------------+   +-------------+             |
|                    total: 108 GPUs                                |
|                                                                   |
|   Traces: >= 5000 jobs, spanning 20-30 days                       |
|           steady-state window = jobs with ID 4000 to 5000         |
|           3 random seeds per arrival rate lambda                  |
+-------------------------------------------------------------------+

+--------------- SMALL CLUSTERS USED FOR SPECIFIC FIGURES ----------+
|  Hierarchical-policy study (Figs 12, 13): 3 V100, 3 P100, 3 K80   |
|  Throughput-estimation study (paper Fig. 16): heterogeneous, 12 GPU|
+-------------------------------------------------------------------+
^ Fig 4: The three cluster configurations named in the paper. The
  physical cluster is deliberately *asymmetric* (8/16/24), while the
  simulated cluster is symmetric (36/36/36).

The physical cluster's asymmetry is worth flagging: there are three times as many K80s as V100s. That composition is itself a source of heterogeneity pressure — the scarce resource is also the fast one.

2.1 Workload table

Table 2 of the paper defines 26 distinct job (or model) types, drawn as the Cartesian product of seven models and their listed batch sizes:

Job types are sampled uniformly from this table. The spread of batch sizes across five orders of magnitude (1 for CycleGAN up to 8192 for Recoder) is what generates the throughput heterogeneity the policies must exploit.

2.2 Trace generation model

  +-------------------------------------------------------------+
  | JOB DURATION SAMPLING (matches the process used by Gandiva) |
  |                                                             |
  |   duration on V100 = 10^x minutes                           |
  |     x ~ Uniform[1.5, 3.0]   with probability 80%            |
  |     x ~ Uniform[3.0, 4.0]   with probability 20%            |
  |                                                             |
  |   num_steps  = observed V100 throughput (steps/s) x duration|
  +-------------------------------------------------------------+
  +-------------------------------------------------------------+
  | SCALE-FACTOR DISTRIBUTION (two simulated regimes)           |
  |                                                             |
  |   "continuous-single":    100% of jobs request 1 worker     |
  |                                                             |
  |   "continuous-multiple":   70% request 1 worker             |
  |                            25% request 2-4 workers          |
  |                             5% request 8 workers            |
  |     (as observed in published Microsoft Philly traces)      |
  +-------------------------------------------------------------+
^ Fig 5: Trace synthesis. The heavy-tailed duration mixture (20%
  of jobs drawn from a decade further out) is what makes the
  makespan and JCT tails interesting; the scale-factor split is
  what makes the distributed-job regime distinguishable from the
  single-worker regime.

2.3 Implementation stack

+------------------------------------------------+
| Gavel scheduler: ~9,000 LOC Python             |
| Gavel simulator: ~500 LOC                      |
+------------------------------------------------+
| cvxpy  -- policy solving (LP / LP-sequence)    |
| gRPC   -- scheduler <-> worker control msgs    |
+------------------------------------------------+
| GavelIterator (Python library, wraps the       |
|   framework data iterator)                     |
|   args: train_loader, load_checkpoint,         |
|         save_checkpoint, config                |
|   user code change: < 5 LOC                    |
+------------------------------------------------+
| PyTorch  (TensorFlow support = future work)    |
+------------------------------------------------+
^ Fig 6: Implementation. The entire user-facing burden is under
  five lines of code -- a wrapper around the data iterator plus
  two checkpoint callbacks. This narrowness is what makes the
  "transparent" claim credible.

3. Design-Space Diagram (axes swept, axes held fixed)

+-------------------------------------------------------------------+
|                       DESIGN SPACE                                |
|                                                                   |
|  Axis 1: SCHEDULING POLICY (Table 1, 9 entries)                    |
|    [Makespan] [LAS] [LAS w/ weights] [Finish Time Fairness]        |
|    [FIFO] [Shortest Job First] [Minimize cost]                     |
|    [Minimize cost w/ SLOs] [Hierarchical (multi-level)]            |
|                                                                   |
|  Axis 2: HETEROGENEITY AWARENESS (2 levels)                        |
|    [heterogeneity-agnostic baseline]  [Gavel heterogeneity-aware]  |
|                                                                   |
|  Axis 3: SPACE SHARING (3 levels)                                  |
|    [off]  [Gandiva-style ad-hoc SS]  [Gavel principled SS]         |
|                                                                   |
|  Axis 4: TRACE TYPE (3 levels)                                     |
|    [static]  [continuous-single]  [continuous-multiple]            |
|                                                                   |
|  Axis 5: INPUT JOB RATE lambda (Poisson)                           |
|    continuous-single  figures sweep up to ~8 jobs/hr               |
|    continuous-multiple figures sweep up to ~3.5 jobs/hr            |
|    (high-load reference points named in text: 5.6 and 2.6 jobs/hr) |
|                                                                   |
|  Axis 6: ROUND LENGTH (4 levels, paper Fig. 15a)                   |
|    [360 s]  [720 s]  [1440 s]  [2880 s]                            |
|                                                                   |
|  Axis 7: NUMBER OF ACTIVE JOBS (4 levels, paper Fig. 14)           |
|    [32]  [128]  [512]  [2048]                                      |
|    (cluster size scaled up together with job count)                |
|                                                                   |
|  Axis 8: THROUGHPUT SOURCE (2 levels, paper Fig. 16)               |
|    [oracle throughputs]  [estimated via matrix completion]         |
|                                                                   |
|  Axis 9: EXECUTION VENUE (2 levels)                                |
|    [physical cluster]  [simulator]                                 |
|                                                                   |
|  ---------------------------------------------------------------  |
|  HELD FIXED                                                        |
|    - Accelerator types: exactly 3 (V100, P100, K80)                |
|    - Max job-combination size for SS: 2                            |
|    - Placement model: 2 extreme points only                        |
|        (fully consolidated / fully unconsolidated)                 |
|    - Round duration in all end-to-end runs: 6 minutes              |
|    - Framework: PyTorch only                                       |
|    - Job-type pool: 26 types (Table 2), uniformly sampled          |
|    - Seeds per lambda in simulation: 3                             |
|    - Steady-state measurement window: job IDs 4000-5000            |
|    - Interconnect / network fabric: not specified, not swept       |
|    - Collective-communication library and its configuration:       |
|        not specified, not swept                                    |
+-------------------------------------------------------------------+
^ Fig 7: Nine swept axes and the held-fixed set. The single most
  consequential fixed choice is the placement model: only two
  extreme points, no intermediate spreads.

Two absences shape what the paper can and cannot claim. First, the accelerator dimension has exactly three levels, all NVIDIA GPUs of successive generations. The introduction motivates the work with TPUs, FPGAs and custom ASICs, but the evaluation never leaves the V100/P100/K80 family. Second, the placement axis is discretized to two extremes. The paper is explicit that consolidated and unconsolidated are "upper and lower bounds on performance," which is a sound modeling choice for an LP but leaves the interior of the placement space — 2-of-8-on-one-server, 4-and-4, rack-local-but-not-server-local — unmodeled.

4. Algorithm & Control-Flow Diagrams

4.1 Top-level control flow: when does the policy re-run?

  START
    |
    v
 (1) [Jobs arrive, written in PyTorch, wrapped in GavelIterator]
    |
    v
 (2) [Throughput matrix T available?]
    |
    +-- yes, user-provided ------------------+
    |                                        |
    +-- no --> (2a) [Throughput Estimator]   |
    |            profile on dedicated        |
    |            profiling workers +         |
    |            matrix completion           |
    |                                        |
    v                                        v
 (3) [Policy solves optimization problem -> X_opt]
    |
    v
 (4) [Scheduling mechanism runs rounds of 6 minutes]
    |     each round: compute priorities, pick conflict-free
    |     highest-priority job combinations, place them
    |
    v
 (5) [Reset event?]
    |
    +-- job arrives -----> back to (3)
    +-- job completes ---> back to (3)
    +-- worker fails ----> back to (3)
    +-- periodic timer --> back to (3)
    +-- none ------------> back to (4)
^ Fig 8: Top-level control flow. Allocations are "intended to be
  respected only between allocation recomputation events." Policy
  recomputation is triggered either by a reset event (arrival,
  completion, worker failure) or on a periodic timer.

The paper is careful to note that policy recomputation is asynchronous with respect to round execution: "allocations do not need to be recomputed every scheduling round -- however, the longer the policy takes to run, the longer it takes for the new allocation to be acted upon (jobs can still be given heterogeneity-agnostic allocations in the interim)." That fallback is the graceful-degradation path: a slow solver degrades you to the baseline scheduler, not to no scheduler.

4.2 Priority computation and the round loop

The mechanism maintains t_mj, the cumulative time job (or combination) m has spent on accelerator type j. From it:

      f_mj  =  t_mj  /  SUM_{m'} t_{m'j}          (realized fraction)

      priorities  =  X_opt  /  f            (element-wise division)

The paper's Figure 5 walks a concrete three-job example:

   rounds_received_n           priorities_n
    V100 P100 K80               V100 P100 K80
   +---------------+           +----------------+
   |  3    1    0  | job 0     | 0.2   0.4  0   | job 0
   |  1    3    0  | job 1     | 0.2   0.2  inf | job 1
   |  0    0    4  | job 2     | inf   0    0.2 | job 2
   +---------------+           +----------------+
                                     |
              place jobs where their priority is highest
                                     |
                                     v
   rounds_received_{n+1}
    V100 P100 K80
   +---------------+
   |  3    2    0  | job 0    <- job 0 gained a P100 round (0.4 highest)
   |  1    3    1  | job 1    <- job 1 gained a K80 round (inf)
   |  1    0    4  | job 2    <- job 2 gained a V100 round (inf)
   +---------------+
^ Fig 9: One priority update, redrawn from Figure 5 of the paper.
  An `inf` priority means the job has received zero rounds on that
  type while X_opt allocates it a nonzero share -- so it is placed
  first. This is the anti-starvation guarantee.

The paper distinguishes this from Tiresias's priority discretization on three counts, all of which follow from the extra degrees of freedom Gavel carries: (a) Gavel must decide which accelerator type a job runs on, not merely which job is active; (b) Gavel must respect an arbitrary allocation returned by an arbitrary policy, rather than one hard-coded objective; and (c) Gavel must prevent two job combinations that share a constituent job from running in the same round, a conflict Tiresias never faces because it has no notion of job combinations.

The inf entries are the mechanism's starvation cure. The paper states the invariant directly: "A job (combination) not run in a particular round will have increased priority in subsequent rounds until it receives accelerator time, while a job that runs in a particular round will have decreased priority. This ensures that jobs do not suffer from starvation if they have a non-zero optimal allocation."

4.3 Algorithm 1 — greedy conflict-free selection

The exact problem ("pick the highest-priority set of job combinations that fits the worker budget, with no job appearing twice") is, as the paper notes, similar to a multiple-choice knapsack problem and therefore NP-hard. Gavel solves it greedily and relies on subsequent rounds to correct errors.

  ALGORITHM 1: SCHEDULE_JOBS
    |
    v
  active_combinations <- all active job combinations
  num_workers_rem     <- number of total workers
    |
    v
  +--> while num_workers_rem > 0:
  |      |
  |      v
  |    (a) j <- job combination with highest priority
  |      |
  |      v
  |    (b) remove j from active_combinations
  |      |
  |      v
  |    (c) does j.scale_factor exceed num_workers_rem?
  |          |
  |          +-- yes --> continue (skip j this round)
  |          |
  |          +-- no --> (d) remove every j' that conflicts with j
  |                          (i.e. shares any constituent job k)
  |                     (e) num_workers_rem -= j.scale_factor
  |      |
  +------+
    |
    v
  PLACEMENT PHASE
    place jobs in decreasing order of requested workers;
    prefer accelerators on the same physical server
    (to minimize fragmentation)
    |
    v
  END of round
^ Fig 10: Algorithm 1. Step (d) is the correctness-critical step:
  it enforces "each distinct job can have <= 1 job combination
  running in a given round to prevent work duplication."

The design rationale for accepting a greedy approximation is stated plainly: "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: our goal is to ensure that the average allocation each job receives over multiple rounds resemble the computed allocation."

4.4 Why rounds at all

The paper motivates rounds with a concrete dilemma: an 8-accelerator cluster with 4 accelerators free and one 8-accelerator job queued. Either wait for all 8, leaving 4 idle (under-utilization), or hand the 4 to a smaller job — but "this situation can repeat itself, leading to starvation." Rounds cut between the horns: they "limit resource under-utilization, simplify scheduling logic, and ensure that jobs with large scale factors do not experience prolonged starvation." The work handed to a worker in one round is called a micro-task.

4.5 Water filling for hierarchical policies

Hierarchical policies (weighted fairness across entities, then a per-entity policy such as fairness or FIFO) cannot be expressed as a single LP. Gavel solves them with a water-filling procedure adapted from max-min fair link allocation in networks. Entity s has weight w_s, and per-job weights satisfy SUM_{m in s} w^job_m = w_s.

  ITERATION k:
    |
    v
  (1) LP:  Maximize_X  min_{m : w^job_m > 0}
             (1/w^job_m) * [ throughput(m,X)/throughput(m,X_m^equal) - t_m ]
           s.t. throughput(m,X) >= throughput(m,X_prev)  for all m
           ( t_m = normalized eff. throughput from iter k-1; 0 at k=1 )
    |
    v
  (2) MILP: identify BOTTLENECKED jobs -- jobs whose effective
            throughput cannot rise without lowering another's
    |
    v
  (3) Bottlenecked jobs -> priority 0, dropped from later iterations
    |
    v
  (4) Redistribute their weight per the ENTITY'S OWN policy:
        fairness entity -> split equally among siblings
        FIFO entity     -> hand entirely to the next job in queue
    |
    v
  (5) All jobs bottlenecked? -- no --> back to (1)   -- yes --> DONE
^ Fig 11: Water-filling loop. Alternating an LP (allocate) with an
  MILP (detect saturation) is what lets one framework satisfy the
  inter-entity and intra-entity policies simultaneously.

Worked example: four identical jobs, four identical GPUs, job 1 weighted 3.0 and jobs 2-4 weighted 1.0. Iteration 1 gives job 1 throughput 1.0 and jobs 2-4 throughput 0.33 apiece; job 1 is then a bottleneck; iteration 2 gives jobs 2-4 full-GPU allocations. Gavel supports fairness at upper levels and fairness or FIFO at lower levels, matching the Hadoop scheduler; extending to other policy sets (e.g., finish-time fairness) is named as future work.

4.6 Throughput estimator

  OFFLINE                          ONLINE
  +---------------------+          +----------------------+
  | Reference job set   |          | New job i            |
  |  ref job 1 .. job r |          |  few measured entries|
  |  densely profiled   |          |  (green); rest missing|
  |  -> matrix R        |          |  (black)             |
  +----------+----------+          +----------+-----------+
             |                                |
             +============ R ================>v
                                   +----------------------+
                                   | MATRIX COMPLETION    |
                                   | sparse low-rank      |
                                   | reconstruction ->    |
                                   | fingerprint of job i |
                                   +----------+-----------+
                                              |
                                   +----------v-----------+
                                   | Find closest         |
                                   | reference job; use   |
                                   | its throughputs as   |
                                   | the initial estimate |
                                   +----------+-----------+
                                              |
                                              v
                                      policy's T matrix
^ Fig 12: Throughput estimator, redrawn from Figure 8. This path is
  needed only for *colocated* throughputs; for individual jobs the
  paper notes throughputs "can be estimated on the fly as jobs run
  on different resource types."

The technique is explicitly borrowed from Quasar: "a mix of profiling and matrix completion to compute a 'fingerprint' against a set of reference models profiled offline. In this work, we show that the techniques used by Quasar can be successfully applied to this new setting."

4.7 The scheduler-application contract: lease renewal

                round nearing its end
   [RUNNING] ------------------------------> [CHECK LEASE]
       ^                                           |
       |  lease renewed (same job, same worker)    |
       +-------------------------------------------+
                                                   |
                                      lease NOT renewed
                                                   v
                                        [SAVE_CHECKPOINT]
                                                   |
                                                   v
                                        [WORKER RELEASED] --+
                                                            |
                            scheduler launches another job  |
                                                            v
   [RUNNING] <---------------------------- [LOAD_CHECKPOINT] (later)
^ Fig 13: GavelIterator lease-renewal state machine. The iterator
  asks the scheduler near round end whether the same job runs again
  on the same worker; this one optimization is what collapses
  preemption overhead (Table 4).

GavelIterator also "ensures that each task in a distributed job runs for the same number of iterations, and synchronizes the conclusion of rounds between the scheduler and workers" — a barrier necessary because the round boundary must be globally consistent across all workers of a distributed job.

5. Quantitative Results — Empirical Findings by Regime

Reading note on figures. Figures 1 and 4 carry explicit per-bar and per-cell numeric labels in the PDF's text layer, and those values are reproduced verbatim below; the row/column assignment was confirmed against the glyph coordinates, not merely against reading order. Figures 9-16 are line plots and CDFs that carry only axis tick labels — no data-point labels. For those figures, only numbers stated in the body text, the captions, or Tables 2-4 are reproduced. Where a figure's shape is informative but its values are not stated, the shape is described qualitatively and marked as such. No curve values are estimated from plot geometry anywhere in this document.

5.1 Motivating heterogeneity measurement (§1, Figure 1)

Body text, verbatim in substance:

• A ResNet-50 model sees a nearly 10x speedup from an NVIDIA V100 compared to a K80.
• An A3C Deep RL model sees only a 2x speedup over the same pair.
• On a dollar-normalized basis (throughput divided by the relevant GCP on-demand price), the V100 is "no longer the optimal choice for all models" — "for many models, the older P100 GPU is competitive or cheaper on a per-dollar basis."

Figure 1 labels each bar with its value. Five models appear (LSTM and Recoder are absent from this figure), all normalized to K80 = 1.0.

Figure 1a — Throughput (w.r.t. K80):

Figure 1b — Dollar-normalized throughput (w.r.t. K80), computed by dividing throughput by the relevant GCP on-demand price:

Three features of these tables do all the work. The speedup spread: ResNet-50 gains 9.6x from a V100 while A3C gains 2.2x — if every model gained the same factor, the optimal allocation would be trivially uniform and heterogeneity awareness worthless. The Transformer plateau: Transformer scores 3.3 on both P100 and V100, gaining nothing from the newest generation, so a scheduler assuming "newer is faster" wastes every V100 it hands to a Transformer job. The dollar-normalized inversion: in Figure 1b the V100 is worse than a K80 for Transformer (0.6) and worse than a P100 for A3C, while still best for ResNet-50 (1.8) and CycleGAN (1.7). The accelerator ranking does not merely vary by model — it reverses between the throughput and cost objectives. No single scalar ordering over the three GPU types exists, which is exactly why the policy must be an optimization problem rather than a sort.

5.2 Colocation measurement (§3.1, Figure 4)

Figure 4 is a 6x6 upper-triangular heatmap of normalized throughput (iterations/second) for pairs of models co-located on a single P100 GPU, each normalized against that model's isolated throughput. Every cell holds an ordered pair — the row model's retained throughput and the column model's retained throughput. Black squares mark pairs that cannot co-locate due to memory constraints. Values below are the figure's own cell labels; nan marks cells the figure leaves empty (the matrix is symmetric, so only the upper triangle is drawn).

The paper's stated conclusion is qualitative — "different pairs of DNN applications in practice have vastly different performance when colocated together, based on the resources they consume" — but the cell values make the structure legible:

• A3C is a near-free rider. Its row retains 0.92-1.00 against every partner except ResNet-50, and costs its partners only 0.80-0.87. It is the Deep RL job with batch size 4; it barely occupies the device.
• ResNet-50 is a monopolist. In every feasible pair it retains 1.00 while driving its partner to 0.64 (A3C), 0.36 (Transformer), 0.26 (LSTM), or 0.23 (ResNet-18).
• Two cells are (0.00, 0.00) — ResNet-50 with itself, and CycleGAN with ResNet-50. These are the black squares: memory-infeasible pairs, the T_mj = -inf entries of the formalism.
• Self-colocation is not free. CycleGAN+CycleGAN is (0.59, 0.59) and ResNet-18+ResNet-18 is (0.59, 0.60) — combined 1.18-1.19x, so packing two copies of the same model gains under 20%.

Summed pair throughput ranges from 1.82 (A3C+Transformer) down to 1.19 (two ResNet-18s) and 0.00 for the infeasible pairs. That is the quantitative case against Gandiva's random exploration: the payoff surface has hard-zero regions, near-flat regions, and a few sharp peaks, with no smoothness for a random walk to exploit. (The 1.82 and 1.19 sums are my own arithmetic on the figure's cell labels, not paper-stated figures.)

5.3 Physical cluster vs. simulation (Table 3, verbatim)

For the continuous trace the metric is the average JCT of 25 jobs in a steady-state cluster; for the static trace it is the total time to complete 100 jobs submitted at the start of the run. The paper's headline claims from this table: heterogeneity-aware policies improved average job completion time by 1.5x and makespan by 1.2x on the physical cluster, and the physical-vs-simulated discrepancy is < 8%, "indicating that our simulator has high fidelity."

5.4 Preemption overhead (Table 4, verbatim)

Round duration = 6 minutes.

The paper's framing: "Allocations and worker assignments can be computed asynchronously. The only synchronous overhead is the loading and saving of checkpoints, which is dependent on the size of the model." Overhead is "< 3%" even without lease renewals and with a short round duration. The paper separately reports that "the time needed to load and save checkpoints for our target models is < 5 seconds."

5.5 Simulated end-to-end results by policy

All simulation results use a 6-minute round duration. The paper notes speedups are larger in simulation than on hardware "since the simulated traces show job behavior over weeks, while the physical cluster traces are only a day long; consequently, queue buildups are less extreme."

Qualifying detail the numbers alone do not carry:

LAS vs. AlloX. Heterogeneity-aware LAS supports higher load than AlloX, because AlloX "can give short jobs preferential treatment in the interest of optimizing average JCT, leading to long jobs experiencing starvation (long tail in JCT CDF)." At moderate load AlloX is a best-case scenario since it explicitly optimizes average JCT on a heterogeneous cluster, and "Gavel is able to essentially match this best case scenario, while also supporting other objectives."

FTF direction. Lower FTF is better — it is the ratio of time to finish a job under the given allocation to time to finish under an isolated 1/n-of-cluster allocation. The Figure 11 CDF is at 2.6 jobs/hr.

Cost / SLO mechanism. The pure cost policy "prioritizes cheaper but slower GPUs; in particular, the A3C jobs are scheduled on K80 GPUs which results in violations for tight SLOs." The SLO-constrained policy fixes this "by ensuring that A3C jobs with tight SLOs are run on instances with V100 GPUs" — consistent with Figure 1b, where ResNet-50's best cost-normalized throughput is on the V100 (1.8) and A3C's is on the K80 (1.0 vs 0.4 on both newer parts). Job durations were drawn from {0.5, 1, 2, 4, 8} days and SLOs from {1.2x, 2x, 10x} the duration.

Hierarchical setup. Figures 12 and 13 use 3 V100 + 3 P100 + 3 K80, adding a job every 4 timesteps: the first 6 jobs to entity 0 (w0 = 1), the next 6 to entity 1 (w1 = 2), the last 6 to entity 2 (w2 = 3). Figure 13 (fairness over FIFO) shows "later jobs in each entity 0 do not receive any GPU time to respect the per-entity FIFO policy."

5.6 Scalability of policy computation (§7.4, Figure 14)

The cluster size is increased as the number of active jobs is increased (equal numbers of V100, P100, K80). The paper's tolerance argument: "We believe latencies of < 30 minutes for large clusters are still preferable to non-preemptive schedulers where jobs experience large queuing delays, or preemptive schedulers with heterogeneity-agnostic policies which lead to worse objective values."

5.7 Mechanism fidelity (§7.5, Figure 15)

Round lengths swept: 360 s, 720 s, 1440 s, 2880 s. The paper states the direction of the effect without giving numbers: "A smaller round length gives Gavel's scheduling mechanism more rounds to course correct, allowing the true allocation and computed optimal allocation to more closely match." Combined with the < 5-second checkpoint cost, "a round length of 6 minutes gives a good tradeoff between fidelity with the optimal allocation and preemption overhead."

Against an ideal baseline that allocates exactly according to the computed allocation, "Gavel's scheduling mechanism with a round duration of 6 minutes behaves almost identically to this ideal baseline with a single-GPU trace (behavior with a multi-GPU trace is similar)." The paper notes the ideal baseline "is impractical to use in practice, since jobs with different scale factors can complete at different times (leading to starvation), and preemptions can be often since allocations for some (job, accelerator type) pairs are small, leading to high overhead."

5.8 Throughput-estimation ablation (§7.6, Figure 16)

On a heterogeneous 12-GPU cluster, the space-sharing-aware LAS policy is run with (a) oracle throughputs and (b) estimated throughputs, and both are compared against LAS without space sharing. The stated result: "The throughput estimator is able to determine missing throughputs in an online fashion accurately enough to observe a very small decrease in average JCT at high load." No numeric gap is quoted in the text.

5.9 Allocation-quality micro-example (§4.1)

The paper works a three-job, two-accelerator example with w_m = 1 and a cluster of 1 V100 and 1 K80:

                    V100    K80                  V100    K80
                  +-------------+              +--------------+
        T =       | 40.0   10.0 | job 0        | 0.45   0.00 | job 0
                  | 12.0    4.0 | job 1  ==>   | 0.45   0.09 | job 1
                  |100.0   50.0 | job 2        | 0.09   0.91 | job 2
                  +-------------+              +--------------+
                                                     X_het.

Result: "Jobs receive about 10% higher throughput compared to an allocation where every user is given 1/n of the time on each accelerator (here, n = 3), also called an isolated allocation."

6. Configuration-Regime Trade-off Tables

6.1 Heterogeneity awareness: on or off

The homogeneous-cluster equivalence is a genuine design property, not an empirical result: §4.4 states that with one accelerator type throughput(m, X) = X_m * T_m, so the heterogeneity-aware optimization problem "reduces to the original optimization problem." Gavel is a strict generalization — it can never be worse than the policy it wraps on a uniform cluster.

6.2 Space sharing: off / ad-hoc / principled

Gavel's choice: principled SS wherever the policy solve fits the time budget, off otherwise. The clean statement of the limit is the scalability result — space sharing squares the row count of T, which drops the tractable job count from 2048 to 512 at the same 10-minute solve budget. The paper mitigates this by noting "in practice we only need to consider combinations that actually perform well," but does not quantify the resulting sparsity.

6.3 Round length

Gavel's choice: 360 s (6 minutes). The paper's justification is the ratio of the < 5-second checkpoint cost to the round length: at 6 minutes the worst measured overhead is 2.91% without lease renewals and 0.47% with them. Directionality of the fidelity axis is stated in the text; the figure's numeric values are not, so only the direction is recorded here.

6.4 Scale-factor regime (single-worker vs. distributed)

Gavel's choice: neither — both regimes are reported. The interesting asymmetry is that every one of Gavel's advantages shrinks in the distributed regime. Distributed jobs occupy more of the cluster per unit time (scale_factor_m in constraint 3), leave less slack for packing, and are the only jobs for which the placement axis exists at all.

6.5 Cost policy variants

Gavel's choice: cost subject to SLOs. The paper's own framing is that the SLO variant "eliminates all violations for a small increase in cost." The 1.4x-to-1.2x delta is the price of the guarantee.

6.6 Policy expressiveness comparison against prior schedulers

This table is assembled from the paper's §8 characterizations of each prior system; the column values are the paper's claims about those systems, not independent measurements.

7. Bottlenecks & Insights Surfaced by the Measurements

7.1 The system rests on one empirical asymmetry, and one headroom figure

ResNet-50 gains 9.6x from a V100 over a K80; A3C gains 2.2x; Transformer gains 3.3x from a P100 and the same 3.3x from a V100. Were these equal, the optimal allocation would be trivially uniform and Gavel would reduce to its own baseline; the ~4.4x spread between ResNet-50 and A3C is the entire exploitable signal. The complementary figure is the one the paper cites from prior work: average GPU utilization (percentage of Streaming Multiprocessors active over time) as low as 52% on a Microsoft cluster. That is the budget space sharing tries to reclaim, and Figure 4 bounds how much is actually recoverable.

7.2 Dollar-normalization inverts the accelerator ranking

The V100 is fastest for every model in Figure 1a but not best per dollar for every model in Figure 1b — it is worse than a K80 for Transformer (0.6). The cost policy and the throughput policy therefore actively disagree about placement: ResNet-50's best cost-normalized throughput is on the V100, A3C's is on the K80. A scheduler with a single hard-coded notion of "better accelerator" cannot represent this inversion at all.

7.3 Space sharing is a packing problem, not a search problem

Gandiva's random exploration loses to Gavel's LP-based packing by 2.2x on average JCT at high load, on both traces. Colocation performance is pair-specific and contains hard infeasibilities (the black squares). Random search over a landscape with infeasible regions, flat regions, and a few sharp peaks is exactly the case where an explicit model wins.

7.4 Space sharing's benefit collapses for distributed jobs

1.4x for single-worker jobs falls to 1.1x once distributed jobs are present. Distributed jobs already consume multiple accelerators, leaving less unused capacity per device to pack into, and every combination must satisfy the conflict-free constraint across all constituent workers. The optimization that helps most in the easy regime helps least in the hard one.

7.5 The greedy mechanism is not the bottleneck — the LP is

Greedy Algorithm 1 tracks the ideal baseline "almost identically" at a 6-minute round, while the policy solve walls out at 2048 jobs without space sharing and 512 with, on a 10-minute budget. The architecture puts the approximation in the cheap layer and the exactness in the expensive one; the measurements say the approximation costs almost nothing and the exactness costs minutes. Asynchrony is the escape hatch: because policy recomputation is decoupled from round execution, a slow solve does not stall the cluster — jobs continue under heterogeneity-agnostic allocations in the interim, so the worst case of a slow policy is the baseline scheduler's behaviour rather than a stalled cluster. This is the single most valuable consequence of the policy/mechanism split, and the paper states it only in passing.

7.6 Preemption is nearly free once lease renewal exists

Table 4 overheads fall by roughly 4x-6x across all six models once lease renewals are enabled (2.91% -> 0.47% for LSTM; 1.58% -> 0.25% for ResNet-50; 0.22% -> 0% for A3C). The mechanism is just "don't checkpoint if you are about to run again on the same worker" — most of the theoretical cost of fine-grained preemption is avoidable by not paying it when nothing changes.

7.7 AlloX marks the ceiling, and Gavel reaches it

The paper positions AlloX as "a best-case scenario" at moderate load because it directly optimizes the reported metric, and states Gavel "essentially match[es] this best case scenario, while also supporting other objectives." At high load Gavel exceeds it, because AlloX's preference for short jobs starves long ones. This is the clearest statement of the value proposition: generality at no measured cost against a specialist.

7.8 Fairness properties are asserted, and one is disclaimed

§4.4 claims sharing incentive for all policies (the isolated 1/n allocation is always feasible, so Gavel's optimum is at least as good), Pareto efficiency for max-min fairness with water filling, and that colocation solutions are always at least as good as non-colocation ones. It explicitly does not claim strategy proofness, citing Sun et al.'s impossibility result that no fair-sharing policy can simultaneously satisfy Pareto efficiency, sharing incentive, and strategy proofness with interchangeable resources. Users who misreport throughputs can obtain larger shares.

8. Limitations of the Methodology

The most structurally consequential of these is the pairing of the last two rows in the "communication" group. Placement sensitivity is introduced because distributed jobs are communication-bound, and the paper even reasons about it correctly ("slower workers are less likely to be communication-bound"). But the interconnect is never characterized, the collective library is never named, and the throughput values for consolidated and unconsolidated placements are treated as given. Gavel therefore consumes communication performance as an input without ever modeling it — which is a clean layering decision, but it means the paper cannot say anything about why a particular model is placement sensitive, only that it is.

9. Note on NCCL Tuning

Gavel's throughput estimator solves a problem that recurs whenever a runtime must choose among configurations it has not measured: the job x accelerator-type table is large, sparse, and expensive to fill by direct profiling, so Gavel profiles a dense reference set offline, takes a handful of live measurements to build a fingerprint, completes the sparse row with matrix completion, and then borrows the nearest reference row's values as its estimate. The same shape appears in collective-library tuning, where the (collective, message size, rank count, algorithm, protocol, channel count) table is far too large to sweep exhaustively on every cluster, and most cells will never be visited. Gavel's contribution here is the demonstration that a low-rank assumption over such a table is strong enough in practice: it reports "a very small decrease in average JCT" relative to oracle throughputs. The complementary lesson is architectural rather than statistical — Gavel keeps the estimator, the optimizer, and the executor as three separately replaceable components communicating only through a matrix and an allocation, so an estimator that degrades gracefully never blocks the executor.

10. Analogy

Gavel is a scheduler for a hospital that owns three grades of surgical suite — one fully robotic, one conventional, one old but serviceable. Every procedure runs in every suite, but the speedup from the robotic theatre is procedure-specific: a complex reconstruction (ResNet-50) finishes 9.6x faster there, a short diagnostic (A3C) only 2.2x, and one procedure (Transformer) gains nothing over the conventional suite at all. A scheduler that treats "an operating room is an operating room" hands the robot to whoever is next in line — the heterogeneity-agnostic baseline.

The administrator (the policy) never assigns rooms. They publish a timetable of proportions: "the reconstruction team gets 60% robotic and 40% conventional this week." That timetable is the allocation matrix X, computed by solving whatever objective the board declared this quarter — shortest average wait, earliest finish for a batch, lowest cost, or a department-by-department fairness split.

The charge nurse (the mechanism) never reads the board's objective. Every six minutes they consult a ledger of who has actually received how much theatre time versus what the timetable promised, and send in whoever is furthest behind. A team promised time in a theatre it has never entered gets infinite priority — the anti-starvation rule. Occasionally the nurse makes a locally poor call because two procedures wanted the same room; it does not matter, because the ledger corrects it in later slots.

Space sharing is two short procedures sharing one theatre: some pairs work beautifully, some interfere badly, and some cannot share at all because the equipment does not fit. Gandiva tries random pairings until one seems to work; Gavel keeps a compatibility table and folds it into the timetable computation, which is why it wins by 2.2x. Placement sensitivity is whether a team's members are in adjacent rooms or on different floors — it matters only for procedures needing many staff at once, which is exactly why the packing benefit falls from 1.4x to 1.1x once multi-room cases enter the mix.

And the throughput estimator is the resident who has never performed this exact procedure. Rather than block the schedule, they compare the case against a catalogue of previously-timed reference procedures, match the closest, and hand up a provisional duration — good enough that the timetable barely degrades. The architectural point is that the administrator, the nurse, and the resident communicate through exactly two artifacts: a table of expected durations going up, and a timetable of proportions coming down. Replace any one of the three and the other two never notice.