Architecture & Measurement-Design Analysis

Gandiva: Introspective Cluster Scheduling for Deep Learning

Source: Xiao, W.; Bhardwaj, R.; Ramjee, R.; Sivathanu, M.; Kwatra, N.; Han, Z.; Patel, P.; Peng, X.; Zhao, H.; Zhang, Q.; Yang, F.; Zhou, L. 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI '18), October 8-10, 2018, Carlsbad, CA, USA, pp. 595-610. ISBN 978-1-939133-08-3. URL: https://www.usenix.org/conference/osdi18/presentation/xiao Affiliations: Microsoft Research; Beihang University; The University of Hong Kong; Huazhong University of Science and Technology; Peking University. (Xiao and Bhardwaj contributed equally.) Reader: pdftotext extraction of the full 16-page proceedings PDF (gemini-reader delegated in parallel; local extraction used as the authoritative source for exact table values) Analyst: Vishwakarma Date: 2026-08-31

Table of Contents

1. System Architecture (the co-designed scheduler stack)
2. System-Under-Test Architecture (the 180-GPU testbed and the trace)
3. Design-Space Diagram (mechanisms x models x cluster regimes)
4. Mechanism Architecture — the Five Primitives
5. Algorithm & Control-Flow Diagrams (placement, introspection, suspend)
6. Quantitative Results — Empirical Findings by Regime
7. Configuration-Regime Trade-off Tables
8. Bottlenecks & Insights Surfaced by the Measurements
9. Limitations of the Methodology
10. Note on NCCL Tuning
11. Analogy

1. System Architecture (the co-designed scheduler stack)

Gandiva is not a scheduler bolted onto an opaque runtime. Its central commitment is vertical co-design: scheduler and deep-learning toolkit are modified together so the scheduler gains visibility into, and control over, a structure that would otherwise be invisible — the mini-batch boundary. Every efficiency claim in the paper traces back to that one piece of shared knowledge crossing the layer boundary.

+---------------------------------------------------------------------+
|                      Gandiva Cluster (45 servers)                    |
|                                                                      |
|  +--------------------------------------------------------------+   |
|  | Kubernetes                                                    |   |
|  |   - overall cluster management, node/container inventory      |   |
|  |   - does NOT decide GPU assignment for DLT jobs               |   |
|  +--------------------------+-----------------------------------+   |
|                             | Kubernetes API                        |
|                             | (node info, container events)         |
|                             v                                        |
|  +--------------------------------------------------------------+   |
|  | Gandiva Central Scheduler   (itself a K8s-managed container)  |   |
|  |                                                               |   |
|  |   Reactive mode      : arrivals / departures / failures       |   |
|  |   Introspective mode : continuous packing, migration,         |   |
|  |                        grow-shrink, time-slice re-balance     |   |
|  |                                                               |   |
|  |   State: per-server height, per-server affinity,              |   |
|  |          per-job GPU util / mem / mini_batch_time,            |   |
|  |          per-job priority, grow-shrink capability flag        |   |
|  +---+------------------------------------------+---------------+   |
|      |                                          |                    |
|      | poll / command                           | migrate cmd        |
|      | (suspend, resume, migrate, prioritize)   |                    |
|      v                                          v                    |
|  +--------------------------------+   +--------------------------+  |
|  | DLT Job Container (Docker)     |   | Migration Helper         |  |
|  |                                |   | (one per server, 200+    |  |
|  |  +--------------------------+  |   |  lines)                  |  |
|  |  | Gandiva Client           |  |   |                          |  |
|  |  |  - polls scheduler for   |  |   |  - warms up destination  |  |
|  |  |    assigned GPU IDs      |  |   |  - triggers checkpoint   |  |
|  |  |  - sends SIGTSTP/SIGCONT |  |   |  - moves ckpt via NFS    |  |
|  |  |  - in-memory file flags  |  |   |    to remote Ramdisk     |  |
|  |  |    "resume on new GPU"   |  |   |  - resumes session       |  |
|  |  +------------+-------------+  |   +--------------------------+  |
|  |               |                |                                 |
|  |               v                |                                 |
|  |  +--------------------------+  |                                 |
|  |  | Modified DL Toolkit      |  |                                 |
|  |  |   PyTorch 0.3  (8 models)|  |                                 |
|  |  |   TensorFlow 1.4 (10)    |  |                                 |
|  |  |                          |  |                                 |
|  |  |   mini-batch boundary    |  |  <-- THE shared abstraction     |
|  |  |   detector:              |  |                                 |
|  |  |    TF  = end session.run |  |                                 |
|  |  |    PT  = mem-cycle min   |  |                                 |
|  |  |          in THCCaching-  |  |                                 |
|  |  |          Allocator       |  |                                 |
|  |  +--------------------------+  |                                 |
|  +--------------------------------+                                 |
|                                                                      |
|  +--------------------------------------------------------------+   |
|  | GlusterFS (2-way replication over server SSDs)                |   |
|  +--------------------------------------------------------------+   |
+----------------------------------------------------------------------+
^ Fig 1: Gandiva's three-tier structure. Kubernetes retains cluster
  management but surrenders GPU placement to the Gandiva scheduler.
  The Gandiva client is the per-container agent; the toolkit patch is
  what makes suspend/migrate cheap. Note that the mini-batch boundary
  detector is the only piece of domain knowledge crossing the layers,
  and every mechanism in Section 4 depends on it.

The design choice worth naming is that the scheduler is centralized and the intelligence is decentralized to the toolkit. The scheduler issues coarse verbs (suspend, resume, migrate, set-priority); the toolkit decides when to honour them — always at a mini-batch boundary, never mid-iteration. The command is advisory in timing and mandatory in outcome, so a suspend may be delayed by up to one mini-batch interval (a few seconds or less for all 18 evaluated models), and the scheduler must track that delay and compensate the quantum for fairness. Bounded latency is traded for an order-of-magnitude cut in state-transfer cost.

The paper is explicit that the API surface, not the specific policy, is the contribution. The five primitives exposed to any DLT scheduling policy are:

Gandiva is a middle layer: it replaces neither the cluster manager nor the training framework, but sits between them and rewires the resource binding that both previously treated as fixed.

+------------------------------------------------+
| AutoML / hyper-parameter search (Hyperopt,      |  <- generates multi-jobs
| Hyperband, curve-fitting evaluator)             |
+------------------------------------------------+
| DLT job (model + hyper-parameter config)        |
+------------------------------------------------+
| Modified DL toolkit (PyTorch 0.3 / TF 1.4)      |  <- mini-batch boundary,
|   + Gandiva client                              |     GPU-object checkpoint
+------------------------------------------------+
| Gandiva scheduler (reactive + introspective)    |  <- the insertion point
+------------------------------------------------+
| Kubernetes + Docker                             |
+------------------------------------------------+
| Servers: 4x P100 or 4x P40, 2x 40 Gbps (no RDMA)|
+------------------------------------------------+
^ Fig 2: Software stack. Gandiva's novelty is that it reaches UP into the
  toolkit (patching PyTorch/TF) while sitting BELOW it in the control
  hierarchy — a deliberate layering violation traded for cheap primitives.

2. System-Under-Test Architecture (the 180-GPU testbed and the trace)

Three distinct experimental substrates appear in the paper, and they are not interchangeable. Conflating them is the easiest way to misread the results.

+-- A: micro-benchmarks ----------------------------------------------+
|  1 server x 4 P100 (time-slicing, grow-shrink); 1 P40 (packing,     |
|  Table 1); 8 P100 (migration breakdown); 4x K80 and 1x K80 for the  |
|  GPU memory-cycle traces.                                           |
+---------------------------------------------------------------------+
+-- B: 180-GPU cluster (Sec. 6.3) ------------------------------------+
|  45 servers x 4 GPUs, roughly equal mix P100 / P40.                 |
|  Time-slicing + packing ON;  migration OFF;  grow-shrink OFF.       |
+---------------------------------------------------------------------+
+-- C: 100-GPU trace replay (Sec. 6.4) -------------------------------+
|  100 GPUs (50 P100 + 50 P40), replayed against YARN capacity sched. |
|  Time-slicing + migration ON;  grow-shrink OFF (cluster at load).   |
+---------------------------------------------------------------------+
^ Fig 3: Three substrates. The headline "26% utilization improvement"
  comes from Substrate B with migration OFF; the "26.8% JCT / 17.8%
  makespan" numbers come from Substrate C with migration ON. They are
  different experiments that happen to share a leading digit.

The per-server hardware is uniform and, by 2018 standards, deliberately modest on the network side:

+-------------------- One Gandiva server ---------------------+
|                                                             |
|   +---------------------------------------------------+     |
|   | 2x Intel Xeon E5-2690 @ 2.60 GHz (12 cores total) |     |
|   | 448 GB RAM        Ubuntu 16.04                    |     |
|   +----------------+-----------------+----------------+     |
|                    |                 |                      |
|              CPU socket 0      CPU socket 1                 |
|                    |                 |                      |
|              +-----+-----+     +-----+-----+                |
|              | PCIe sw   |     | PCIe sw   |                |
|              +--+-----+--+     +--+-----+--+                |
|                 |     |           |     |                   |
|              +--+-+ +-+--+     +--+-+ +-+--+                |
|              |GPU0| |GPU1|     |GPU2| |GPU3|                |
|              +----+ +----+     +----+ +----+                |
|              (4x P100  OR  4x P40 -- never mixed in a node) |
|                                                             |
|   Network: 2x 40 Gbps links, NO RDMA                        |
|   Storage: GlusterFS, 2-way replication on server SSDs      |
+-------------------------------------------------------------+
^ Fig 4: Server topology. The three affinity classes measured in Fig. 1
  of the paper map directly onto this picture: SamePCIeSw (GPU0-GPU1),
  SameSocket (across PCIe switches within a socket), DiffSocket
  (GPU0-GPU2). Locality is a property of *which pair of slots* a job
  lands on, which is precisely what migration can change.

The absence of RDMA on the 2x 40 Gbps links is architecturally significant: inter-server gradient exchange goes through the host TCP/IP stack, so the intra-server / inter-server bandwidth gap on the scheduling testbed is wide, which is what makes migration-for-locality pay off there.

One fabric distinction matters and is easy to misread. The Section 3 motivating measurements — inter-server locality (4x1-GPU vs 2x2-GPU vs local-4) and NIC interference (the 47% / 30% / 5% numbers) — were taken on a separate two-server setup interconnected with 40G InfiniBand, not on the 45-server non-RDMA cluster used for the scheduling experiments. The paper never runs the scheduler itself on InfiniBand. Read the Section 3 numbers as evidence that locality sensitivity is real and model-specific, not as calibration of the Section 6 cluster results.

The workload trace is synthesized, not replayed literally:

The 10 substitute models, with the checkpoint sizes read off the Fig. 13 x-axis labels (these sizes are the direct determinant of migration cost):

3. Design-Space Diagram (mechanisms x models x cluster regimes)

Gandiva's evaluation sweeps four axes and pins several others. The pinned axes are where the paper's generality claims are weakest, so they are worth setting out as explicitly as the swept ones.

+---------------------------------------------------------------------+
|                    DESIGN SPACE (swept axes)                        |
|                                                                     |
|  Axis 1: MECHANISM (5 levels, evaluated independently)              |
|    [time-slicing] [packing] [migration] [grow-shrink] [priority]    |
|                                                                     |
|  Axis 2: MODEL / GPU-UTILIZATION CLASS (Table 1, 8 PyTorch models)  |
|    low  util (8.7% - 14.1%)  : VAE, SuperResolution                 |
|    mid  util (61.6% - 76.2%) : RHN, SCRNN, MI-LSTM                  |
|    high util (87.2% - 98.9%) : LSTM, ResNet-50, ResNext-50          |
|                                                                     |
|  Axis 3: CLUSTER SCALE / REGIME                                     |
|    [1 GPU] [4 GPU] [8 GPU] [16 GPU] [100 GPU] [180 GPU]             |
|    load regime: under-utilized (grow-shrink) vs overloaded          |
|                 (time-slice + pack)                                 |
|                                                                     |
|  Axis 4: BASELINE SCHEDULER                                         |
|    [bin-packing, no over-subscription]  (Sec. 6.3)                  |
|    [Hadoop YARN capacity scheduler]     (Sec. 6.4)                  |
|    [FIFO queue]                         (Sec. 6.2 AutoML)           |
|                                                                     |
|  HELD FIXED (no sweep):                                             |
|    - Parallelism: DATA parallelism only; synchronous updates only   |
|    - GPU request size: assumed a power of two                       |
|    - Cluster tenancy: dedicated single-tenant GPU cluster           |
|    - Batch size: framework defaults from each model's reference     |
|    - Time-slicing quantum: 60 s, everywhere                         |
|    - NVIDIA MPS: DISABLED (measured as harmful on P40/P100)         |
|    - Fairness: per-server only; cluster-wide fairness out of scope  |
|    - Grow-shrink target: capped at one server's GPU count           |
|    - Interconnect: 2x 40 Gbps, no RDMA (single configuration)       |
|    - Collective/communication library configuration: never varied   |
+---------------------------------------------------------------------+
^ Fig 5: 4 swept axes over a large set of pinned ones. The two most
  consequential pins are "data parallelism, synchronous only" (which
  makes the mini-batch boundary a clean global barrier) and "MPS
  disabled" (which caps how well packing can possibly do).

The mechanism axis is swept one mechanism at a time and only partially recombined at cluster scale: Sec. 6.3 runs time-slicing + packing with migration off; Sec. 6.4 runs time-slicing + migration with grow-shrink off. No experiment enables all five simultaneously — a deliberate ablation structure that makes each number attributable but never reports the combined ceiling. The GPU-utilization axis matters most because it is the axis along which packing flips sign; the paper's own framing is that predicting packing performance is hard "even with jobs of the same type, let alone when jobs of different types are packed together," which is why the design abandons analytical modelling entirely.

4. Mechanism Architecture — the Five Primitives

The entire mechanism layer rests on one measured property: GPU memory usage during training is cyclic and aligned with mini-batch boundaries.

  GPU memory (GB)              ResNet-50 / ImageNet, 4x K80, batch 128
  23 +      /\        /\        /\        /\
     |     /  \      /  \      /  \      /  \
     |    /    \    /    \    /    \    /    \
     |   /      \  /      \  /      \  /      \
 0.3 +--/--------\/--------\/--------\/--------\----> time
     |<-- ~1.5s -->|
        forward = memory rises,  backward = memory falls
        max 23 GB  /  min 0.3 GB   ==>  77x ratio

  GNMT / WMT'14 En-De, 1x K80, batch 16, model 0.4 GB
        same cyclic shape, but only a 3x max/min ratio
        (larger model, smaller batch, define-by-run dynamic graph)
^ Fig 6: The memory cycle. The suspend point is the cycle MINIMUM.
  Choosing that instant rather than an arbitrary one is what turns a
  23 GB GPU-to-CPU copy into a 0.3 GB copy -- the single measurement
  that makes every other mechanism affordable.

4.1 Suspend-Resume

  Scheduler            Gandiva Client          Modified Toolkit
      |                      |                       |
  (1) |-- suspend(job) ----->|-- SIGTSTP ----------->|
      |                      |-- in-mem file: ------>| (2) set suspend flag
      |                      |   "resume on new GPU?"|
      |                      |                       | (3) KEEP RUNNING to the
      |                      |                       |     mini-batch boundary
      |                      |                       |     (mem-cycle minimum)
      |                      |                       | (4) copy GPU objects
      |                      |                       |     -> CPU DRAM
      |                      |                       | (5) free ALL GPU allocs
      |                      |                       |     incl. toolkit cache
      |                      |                       | (6) classic CPU suspend
      |                      |                       |
      |     [ if GPU changes: cudaDeviceReset + CudaInit, 5-10 s,
      |       run in BACKGROUND while the job is suspended ]
      |                      |                       |
  (7) |-- resume(job) ------>|-- SIGCONT ----------->| (8) allocate GPU mem
      |                      |                       | (9) copy objects back
      |                      |                       |(10) patch GPU object
      |                      |                       |     pointers to the new
      |                      |                       |     device addresses
      |                      |                       |(11) resume training
^ Fig 7: Suspend-resume sequence. Steps (3) and (10) carry the domain
  knowledge: wait for the cycle minimum, and rewrite device addresses so
  the job does not care which physical GPU it lands on.

Measured cost: under 100 ms for typical image-classification jobs, up to 1 s for large language-translation jobs. Against a 60 s time-slicing quantum that is an overhead of 2% or less.

4.2 Packing

Packing runs two or more jobs simultaneously on one GPU and lets the GPU hardware interleave them, as opposed to time-slicing which gives one job the whole GPU for a quantum. It is only admissible when combined memory fits in GPU memory; otherwise CPU-memory paging costs dominate. Whether it is profitable above that constraint is unpredictable a priori, so Gandiva measures.

4.3 Migration — two competing implementations

  APPROACH A: generic process migration (CRIU)
  +--------------------------------------------------------------+
  | 1. checkpoint GPU objects, strip ALL GPU state from process   |
  | 2. invoke CRIU  --> checkpoints the ENTIRE process memory     |
  | 3. checkpoint size: order of GBs for PyTorch DLT jobs         |
  |    ==> migration overhead 8-10 s for 1-GPU jobs, more for     |
  |        multi-GPU                                              |
  +--------------------------------------------------------------+

  APPROACH B: checkpoint-aware DLT job (Gandiva's choice)
  +--------------------------------------------------------------+
  | 1. destination Migration Helper WARMS UP a TF session first   |
  |    (reconstruct meta-graph, create Executor, run a warm-up op |
  |     so initialization is not deferred lazily)                 |
  | 2. source Helper asks TF to tf.Saver at a mini-batch boundary |
  | 3. checkpoint holds the model from ONE GPU only, regardless   |
  |    of job GPU count (data parallelism => replicas identical)  |
  | 4. meta-graph EXCLUDED from checkpoint (rebuilt from usercode)|
  | 5. checkpoint kept in Ramdisk; cross-server writes go direct  |
  |    to the remote Ramdisk over NFS                             |
  | 6. resume: parallel per-GPU load of the in-memory checkpoint  |
  |    ==> migration overhead as little as 1-2 s                  |
  +--------------------------------------------------------------+
^ Fig 8: The two migration designs. Approach A is application-agnostic
  and pays 8-10 s because it moves everything; Approach B is
  application-aware and pays 1-2 s because it moves only the training
  state and overlaps the rest. This is a ~5-8x gap bought entirely
  with domain knowledge.

Implementation cost of Approach B: 400+ lines of Python/C++ in TensorFlow, plus 200+ lines for the per-server Migration Helper.

4.4 Grow-Shrink

Opt-in only: a job must declare itself grow-shrink-capable, because changing GPU count changes effective batch size and may require retuning the learning rate. Growth is capped at one server's GPU count and triggers only after an idle timeout (anti-thrashing); shrink executes immediately when a new job needs the GPUs — deliberately asymmetric hysteresis.

4.5 Profiling / Introspection

   mini_batch_time(job) := time between two consecutive minima
                           of the GPU memory usage cycle

   Used as the universal effectiveness oracle:

     decision D  -->  measure mini_batch_time before D
                 -->  apply D
                 -->  measure mini_batch_time after D
                 -->  if worse, UNDO D

   Applied to: packing (throughput of packed pair vs time-slicing),
               migration (locality gain), grow-shrink (progress rate
               used to apportion spare GPUs across candidate jobs).
^ Fig 9: The introspection contract. One scalar, measured the same way
  for every model and every mechanism, is the entire feedback signal.

This is the paper's cleanest architectural idea. Rather than build a performance model per (model, GPU, co-tenant) triple — intractable given cache, memory-bandwidth and PCIe interference — Gandiva makes every scheduling decision reversible and measures the outcome. Mini-batch predictability is what makes that measurement cheap and low-variance enough to trust.

5. Algorithm & Control-Flow Diagrams

5.1 Definitions used by the scheduler

Suspend-resume is used only when a server's height exceeds one. Below that, Gandiva behaves like a conventional exclusive-allocation scheduler.

5.2 Reactive mode — node placement (Algorithm 1, getNodes)

  JOB ARRIVES
      |
      v
  nodes0 <- findNodes(job.gpu, affinity = job.gpu)  // same-class servers
  nodes1 <- minLoadNodes(nodes0)                    // least loaded of those
  nodes2 <- findNodes(job.gpu, affinity = 0)        // untouched servers
  nodes3 <- findNodes(job.gpu)                      // any server w/ free GPUs
      |
      v
  (1) nodes1 AND height(nodes1) < 1 ?  --yes--> PLACE on nodes1
      | no                                      "same affinity, free GPUs"
      v
  (2) nodes2 AND numGPUs(nodes2) >= job.gpu ? --yes--> PLACE on nodes2
      | no                                             "pristine server"
      v
  (3) nodes3 non-empty ?               --yes--> PLACE on nodes3
      | no                                      "affinity relaxed; the
      |                                          defragmenter will repair"
      v
  (4) nodes1 non-empty ?               --yes--> PLACE on nodes1 with
      | no                                      OVER-SUBSCRIPTION
      v                                         (suspend-resume kicks in)
   ENQUEUE  (job waits -- last resort)
^ Fig 10: Algorithm 1 as a decision cascade. The ordering encodes a
  strict preference lattice: same-affinity-with-space > pristine server
  > any-space-anywhere > over-subscribe > queue. Queueing is the LAST
  resort, the exact inversion of a conventional scheduler where queueing
  is the FIRST response to overload.

The affinity heuristic is what produces the segregation visible in the paper's 16-GPU worked example: 1-GPU jobs cluster onto servers dedicated to 1-GPU jobs (six per 4-GPU server, i.e. height 2), 2-GPU jobs onto their own server, 4-GPU jobs onto theirs. Grouping like-sized jobs keeps fragmentation from stranding a 2-GPU request behind two scattered singletons.

  Server A (affinity 1)        Server B (affinity 1)
  +----+----+----+----+        +----+----+----+----+
  |J6  |J5  |J12 |J11 |        |    |    |    |    |   <- second "layer"
  |J1  |J2  |J3  |J4  |        |J7  |J8  |J9  |J10 |   <- first layer
  +----+----+----+----+        +----+----+----+----+
   GPU0 GPU1 GPU2 GPU3          GPU0 GPU1 GPU2 GPU3
   height = ceil(6/4) = 2       height = ceil(6/4) = 2

  Server C (affinity 2)        Server D (affinity 4)
  +---------+---------+        +-------------------+
  |  J15    |   J17   |        |       J16         |
  |  J13    |   J14   |        |                   |
  +---------+---------+        +-------------------+
   GPU0 GPU1 GPU2 GPU3          GPU0 GPU1 GPU2 GPU3
^ Fig 11: The 16-GPU placement example. Over-subscription load is
  balanced (six 1-GPU jobs on each of the two affinity-1 servers)
  rather than piled onto one server, so time-slicing degradation is
  spread evenly.

5.3 Introspective mode — the continuous optimization loop

  +---------------------------------------------------------------+
  |                  INTROSPECTIVE LOOP (continuous)               |
  |                                                                |
  |  (1) PROFILE every job: GPU util, GPU memory, mini_batch_time  |
  |      (jobs run EXCLUSIVE first, to get a clean baseline)       |
  |                    |                                           |
  |                    v                                           |
  |  (2) OVERLOADED?                                               |
  |     yes -> PACKING BRANCH            no -> GROW BRANCH         |
  |       |                                     |                  |
  |       v                                     v                  |
  |   sort jobs by GPU util ASC            cluster idle AND job    |
  |   pick LOWEST-util job + GPU           has growshrink flag?    |
  |   combined mem <= GPU mem ?            wait out idle timeout,  |
  |     no  -> try next GPU                grow (cap = GPUs on one |
  |     yes -> PACK, keep profiling        server), split spares   |
  |       |                                by profiled progress    |
  |       v                                     |                  |
  |   throughput(packed) > time-sliced ?        | new job arrives  |
  |     yes -> KEEP, recurse to next            v                  |
  |            lowest-util job              SHRINK IMMEDIATELY     |
  |     no  -> UNDO, try next GPU                                  |
  |                    |                                           |
  |                    v                                           |
  |  (3) MIGRATION BRANCH (event- and background-driven)           |
  |      a: job departs -> can cluster height drop? move a         |
  |         suspended job onto the vacated GPUs                    |
  |      b: job departs -> can locality improve? move non-         |
  |         colocated jobs into colocated slots                    |
  |      c: background defrag -> take the non-idle server with the |
  |         MOST free GPUs, push its jobs onto servers with FEWER  |
  |         free GPUs while loss is negligible; stop when every    |
  |         non-idle server has < 3 of 4 free, or nobody benefits  |
  |      d: low-priority job stuck behind higher-priority jobs     |
  |         -> migrate it off that server                          |
  |                    |                                           |
  |                    v                                           |
  |  (4) TIME-SLICE: weighted round-robin per server, quantum 60 s,|
  |      adjusted for the suspend delay from Fig 7 step (3).       |
  |      Higher-priority jobs are NEVER suspended for lower ones.  |
  +---------------------------------------------------------------+
^ Fig 12: The introspective loop. Every branch is a greedy heuristic
  guarded by a measured revert condition -- there is no global optimizer
  and no analytical performance model anywhere in this diagram.

5.4 Migration for locality — the worked cluster example

  Before (multi-job of four 2-GPU jobs, poor affinity):

  Server0   Server1   Server2   Server3   Server4   Server5   Server6
  +-----+   +-----+   +-----+   +-----+   +-----+   +-----+   +-----+
  | J0  |   | J0  |   | J1  |   | J1  |   | J2  |   | J2  |   | J3  |
  |     |   |  D  |   |     |   |  D  |   |  D  |   |     |   | J3  |
  +-----+   +-----+   +-----+   +-----+   +-----+   +-----+   +-----+
   only J0 is colocated;  D = one of the 8 GPUs freed when a background
   DeepSpeech job finished 3 minutes in (3 of the 8, on servers 1/3/4,
   are useful here).  Gandiva migrates J1, J2, J3 onto colocated pairs,
   so the 2-GPU VGG-like model's gradient exchange stays on PCIe rather
   than crossing the non-RDMA 40 Gbps network.
^ Fig 13: Locality repair by migration. The trigger is exogenous -- an
  unrelated job finished -- which is exactly the case that a one-shot
  placement decision at job-arrival time can never exploit.

6. Quantitative Results — Empirical Findings by Regime

6.1 Time-slicing (Substrate A: six 1-GPU jobs on 4x P100)

Workload: six 1-GPU ResNet-50 / Cifar10 jobs, PyTorch, on one 4-GPU P100 server. Ideal share is 4 minutes of GPU time out of every 6.

6.2 Packing (Substrate A: single P40, PyTorch) — Table 1 verbatim

The sign flip happens between 76.2% and 87.2% GPU utilization. Below it, packing recovers idle SM cycles; above it, packing merely adds contention. Two facts make this table hard to turn into a rule: it is measured without NVIDIA MPS (the authors found MPS imposes significant overhead on P40/P100 and speculate that V100's hardware MPS support could raise packing gains), and the utilization ordering is not perfectly monotone in gain (LSTM at 87.2% loses 16%, worse than ResNext-50 at 98.9% which loses 11%).

6.3 Migration (Substrate A: 8x P100, TensorFlow)

Fig. 13 reports max, min and average over 3 runs of a 1-GPU job, separately for intra-server and inter-server migration, across the 10 trace models — so the sub-second figure covers cross-machine moves, not just GPU-to-GPU hops.

The Fig. 12 breakdown separates cost into eliminated and irreducible components:

  Components ELIMINATED or HIDDEN by Gandiva:
    - pre-initialization              (moved to destination warm-up)
    - CUDA lazy initialization        (forced early by warm-up op)
    - TensorFlow lazy initialization  (forced early by warm-up op)
    - saving the meta-graph           (rebuilt from user code instead)
    - saving extra replicas           (only one GPU's model is saved)

  Components that REMAIN (the true migration time):
    - saving the checkpoint      } roughly CONSTANT in GPU count,
    - restoring the checkpoint   } because only one replica moves and
                                   per-GPU loads run in parallel
                                   without saturating PCIe
^ Fig 14: Migration cost decomposition. The scaling property is the
  headline: migration time is flat in job GPU count, so migrating an
  8-GPU job costs about what migrating a 1-GPU job costs.

6.4 Grow-Shrink (Substrate A: 4x P100, ResNet-50 / PyTorch)

6.5 AutoML / multi-job (Substrate A: 4 and 16 P40)

Setup: LeNet-like CNN on Cifar10, 12 hyper-parameter dimensions (learning rate, dropout rate, layer count, optimizer choice, ...), Hyperopt generator, learning- curve extrapolation evaluator run every 1,000 mini-batches (3% of total), jobs predicted below 30% accuracy are killed early. AutoML schedules 2 (4-GPU case) or 8 (16-GPU case) additional jobs every 1,000 mini-batches. Baseline is a FIFO queue on the same GPUs.

Table 3 verbatim — time to find a qualified configuration (minutes):

The monotone rise in speedup with position is the key trend: the deeper in the search the good configuration hides, the more Gandiva wins — and the authors argue that deep is the realistic case, since early-stopped jobs are what guide the generator toward good regions.

Table 4 verbatim — model searching in a ResNet-like network (minutes):

Setup: official Keras ResNet example for Cifar10, Hyperopt, 100 configurations, search space spans architecture and hyper-parameters, 16 P40 GPUs, 1 GPU per job, learning-curve prediction every 3% of mini-batches.

At a 90% target the qualifying model actually reached 92.62% validation accuracy. The 70% row is the paper's own honest null result: when a qualified model appears at position 15, the total search time is dominated by the runtime of a single qualifying job, and scheduling cleverness contributes nothing.

6.6 Cluster experiment — time-slicing + packing (Substrate B, 180 GPUs)

Workload: the 8 models of Table 1, sampled so mean GPU utilization is ~50% (matching a published production-cluster study) — jobs 1-2 (low util) at p=0.3, jobs 3-5 (mid) at p=0.25, jobs 6-8 (high) at p=0.45; jobs 7-8 request 2 or 4 GPUs, the rest request 1. Mini-batch counts give each job 30-45 minutes of isolated P40 time. 1,000 jobs arrive uniformly at random over two hours. Baseline is bin-packing with no over-subscription; migration and grow-shrink off.

The paper notes that the cumulative count of successful packings rises almost monotonically over the run, with only small occasional dips corresponding to packings that had to be undone — direct evidence that the greedy measure-then-revert heuristic rarely mispredicts badly.

6.7 Cluster experiment — trace replay (Substrate C, 100 GPUs)

Fast-forwarding: to replay 9 days in reasonable wall-clock, the scheduler instructs jobs to skip mini-batches whenever no scheduling event (arrival, departure, migration) is pending, computing skipped time from the measured steady-state mini-batch rate. Validated against a full 3-hour trace: average JCT and makespan differed by less than 1% for both schedulers.

Table 5 verbatim — full trace with fast-forwarding:

Migration activity over the whole replay: 470 migrations, roughly one every 20 minutes. The JCT CDF shows Gandiva's advantage concentrated in jobs completing in under roughly 100 minutes — the short-job tail, which is exactly what head-of-line blocking punishes hardest.

6.8 Multi-job inside a loaded shared cluster (Substrate C)

Setup: the synthesized trace runs as background load on the same 100 GPUs. At minute 5,607 (mid-trace), two AutoML multi-jobs launch, 8 GPUs each, allowed to preempt background jobs for fair comparison. Model is a 2-GPU VGG-like network chosen because it is large and locality-sensitive. 40 configurations tuning learning rate, 100,000 mini-batches per job, learning curve reported every 3,000 mini-batches (3%), early stopping enabled. Completion criterion: 99.5% training accuracy, corresponding to 91.3% validation accuracy. Top M = 2 jobs (4 GPUs) run exclusively; the rest time-slice.

Attribution: a companion micro-benchmark showed time-slicing alone yields ~7x for this AutoML workload, so the remaining ~2x is attributed to improved locality from migration. This is the paper's only clean decomposition of a combined-mechanism result.

6.9 Motivating sensitivity measurements (Substrate A)

7. Configuration-Regime Trade-off Tables

7.1 Time-slicing vs packing (the same GPU, two ways to share it)

Gandiva's resolution is not to choose but to default to time-slicing and promote to packing only on evidence. Every job starts exclusive so a clean baseline exists; packing is attempted lowest-utilization-first; the pairing is retained only if aggregate throughput beats time-slicing. The design cost is a transient period of measurably-bad performance every time a wrong pairing is tried, which the utilization curve shows as small dips.

7.2 Migration implementation: application-agnostic vs application-aware

7.3 Scheduler philosophy: conventional vs introspective

8. Bottlenecks & Insights Surfaced by the Measurements

8.1 The bottleneck was never compute — it was exclusivity

The production numbers that motivate the paper (about 52% average GPU utilization, queueing times from minutes to hundreds of minutes, against hardware where "a GPU VM in the cloud costs nearly 10x that of a regular VM") are not a throughput problem but an allocation-policy problem. A job holding four GPUs at 8.7% utilization for six hours is not slow, it is a lock held too long. Every Gandiva mechanism breaks that lock along a different dimension: suspend-resume in time, packing in space, migration in place, grow-shrink in size. Framing utilization as lock-holding rather than inefficiency is what makes OS primitives the natural vocabulary.

8.2 Periodicity converts an expensive operation into a cheap one — 77x

The single most leveraged measurement in the paper is that ResNet-50 on ImageNet swings between 23 GB and 0.3 GB of GPU memory every ~1.5 s. Suspending at an arbitrary instant means copying up to 23 GB across PCIe; suspending at the cycle minimum means copying 0.3 GB. The mechanism is not novel — CPU suspend-resume is decades old — but knowing when to fire it is worth two orders of magnitude. The corollary is the risk: models whose min/max ratio is small get much less benefit. GNMT's ratio is only 3x, because its model is large (0.4 GB) and its batch is small (16), and it is precisely the language-translation class that the paper reports takes up to 1 s to suspend rather than under 100 ms. The downstream payoff is visible in the aggregate: time-slicing six jobs across four GPUs costs under 2% throughput purely because the switching cost (100 ms to 1 s) is negligible against the 60 s quantum — a naive 23 GB copy per switch would have inverted that conclusion.

8.3 Packing profitability is not analytically predictable

Table 1 is a refutation of model-based scheduling for co-location. Gains span +412% to -16% across eight PyTorch models on identical hardware, and the ordering is not even monotone in GPU utilization. The paper's stated reason is that a predictive model would need to capture cache interference, memory-bandwidth contention, and PCIe contention jointly — and would then need to generalize to pairs of heterogeneous jobs. The design response is to make the decision cheap to reverse rather than accurate to predict. When the cost of being wrong is one profiling interval, exploration beats modelling.

8.4 Migration cost is flat in job size, which changes what is schedulable

Because only one model replica is checkpointed (data-parallel replicas are identical) and per-GPU restores run in parallel without saturating PCIe, the irreducible migration time is roughly constant in GPU count — 98% of a 35 s overhead eliminated for an 8-GPU ResNet-50 job. A scheduler whose migration cost grew with job size would rationally migrate only small jobs, which is exactly backwards: the large multi-GPU jobs are the locality-sensitive ones. Flattening this curve is what makes locality-driven defragmentation viable.

8.5 Locality sensitivity is model-specific, so static topology rules fail

VGG16 drops to 60% of peak when its two GPUs sit in different sockets; ResNet-50 in the same configuration is unaffected. ResNet-50 loses up to 47% when split across servers while DeepSpeech loses 5%. There is no single "good placement" rule — placement quality is a joint function of the model's communication volume and the fabric segment it lands on. This is why Gandiva measures mini_batch_time before and after a migration rather than consulting a topology score.

8.6 The value of scheduling is concentrated in the deep tail of a search

Table 3's speedups rise monotonically with the position of the qualifying configuration (5.51x at the 25th percentile, 7.04x at the 98th), and Table 4's rise with the target accuracy (1.00x at 70%, 5.66x at 90%). Both say the same thing: when the answer is easy to find, scheduling is irrelevant; when the answer is buried, the ability to keep many candidates alive simultaneously dominates. Early feedback is not a convenience feature — it is the mechanism by which the search algorithm's pruning signal arrives in time to be useful. The paper's framing example is Hyperband, which "might initially spawn 128 DLT jobs and, in each round (e.g., 100 mini-batch iterations), kill half of the jobs with the lowest accuracy" — an algorithm that is simply incoherent on a scheduler that can only run as many jobs concurrently as it has GPUs.

9. Limitations of the Methodology

The most consequential limitation is the framework-modification requirement. Every efficiency number depends on the toolkit exposing a mini-batch boundary and cooperating in checkpointing; a scheduler that cannot patch the framework gets the CRIU numbers (8-10 s migration, no cheap suspend), not the Gandiva numbers (1-2 s migration, sub-100 ms suspend). The co-design is not an implementation detail, it is the entire delta. Second: the three headline improvements come from three different substrates with different mechanisms enabled, so no single experiment demonstrates the full system of Section 4 running at once.

10. Note on NCCL Tuning

Gandiva's mechanisms make a running job's interconnect topology mutable at runtime, and that is the non-obvious consequence for collective-library configuration. A 4-GPU job placed as 4x1-GPU across four servers, then migrated by the defragmenter into a single node, has moved from a TCP-over-40GbE gradient-exchange path to an intra-node PCIe path — a regime change that a communicator configuration chosen once at initialization cannot reflect. The paper's own measurements show the size of the prize: 40% for VGG16 between the worst and best intra-node GPU pairing, up to 47% for ResNet-50 between colocated and split-across-servers. Gandiva also supplies the feedback signal a configuration selector would need — mini_batch_time measured between GPU memory-cycle minima is a per-iteration, per-job, framework-level latency metric that can be compared before and after any change, which is precisely the before/after protocol it already uses to accept or revert a packing decision. The gap the paper leaves open is that migration rebinds the GPUs but nothing rebinds the collective configuration to match the new topology.

11. Analogy

Gandiva is an air-traffic controller who is allowed to talk to the pilots.

A conventional cluster scheduler works from a radar screen alone: it sees that an aircraft occupies a runway, holds everyone else in a stack until that runway clears, and has no idea what is happening inside the cockpit. A runway (a GPU) is assigned to one aircraft (a job) for the whole operation. That is head-of-line blocking, and it is why queueing runs to hundreds of minutes while runways sit at 52% duty.

Gandiva adds a radio channel to the cockpit, and the crucial discovery is that every flight in this airspace flies the same repeating holding pattern — the mini-batch loop. Because the controller knows the pattern, it knows the exact moment when the aircraft is lightest: fuel burned down, cargo stowed, the 23 GB / 0.3 GB memory minimum. Instructing an aircraft to divert at that instant costs almost nothing, whereas the same instruction at the heaviest moment would mean offloading twenty-three tonnes. That is suspend-resume: the periodicity is what turns "land and refuel" into a 100-millisecond operation.

The rest follows from having the radio. Packing puts two light aircraft on one wide runway at once — brilliant for two Cessnas (VAE, +412%), dangerous for two 747s (ResNext-50, -11%) — and since no flight-dynamics model predicts which pairs work, the controller tries it, watches the approach, and waves one off if spacing degrades. Migration reroutes an aircraft to a better gate after a neighbouring flight departs: the passengers (model state) transfer, not the airframe, and because only one copy of the manifest moves, rerouting a 400-seat flight costs what rerouting a 4-seat one costs. Grow-shrink opens extra runways overnight to crews who declared themselves qualified, and closes them the instant a scheduled flight appears. Introspection is the controller listening for one number from every cockpit — time since the last circuit — and undoing any decision that lengthens it.

The analogy also exposes the cost. This controller works only because the airline installed the radio and trained the pilots: 400 lines inside TensorFlow, 200 in a helper, a memory-cycle detector wired into PyTorch's allocator. An airline that will not modify its cockpits gets the radar-only controller and the eight-to-ten-second diversions. And the controller is deliberately not fair — it optimizes for how fast the tower learns which flights are worth continuing, not for equal airtime — which is why it finds a good configuration 13.6x faster in a busy sky, and exactly 1.00x faster when the first aircraft down was already the right one.