Gandiva: Introspective Cluster Scheduling for Deep Learning

Wencong Xiao, Romil Bhardwaj, Ramachandran Ramjee, Muthian Sivathanu, Nipun Kwatra, Zhenhua Han, Pratyush Patel, Xuan Peng, Hanyu Zhao, Quanlu Zhang, Fan Yang, Lidong Zhou | Beihang University / Microsoft Research / The University of Hong Kong / Huazhong University of Science and Technology / Peking University | OSDI '18, October 8–10, 2018, Carlsbad, CA, pp. 595–608

Problem

Deep learning training (DLT) jobs are scheduled today by big-data schedulers such as Kubernetes and YARN, which treat a DLT job as just another MapReduce-style job: it is allocated a fixed set of GPUs at startup and holds exclusive access until completion. This is a poor fit for two workload realities.

First, deep learning is feedback-driven exploration. Users submit a set of configurations — a multi-job — and rely on early accuracy feedback to prioritize or kill subsets. Hyper-parameter search methods such as HyperOpt and Hyperband depend on this: Hyperband might spawn 128 jobs and, every 100 mini-batch iterations, kill half of them. A scheduler that runs a subset to completion while queueing the rest cannot deliver the simultaneous early feedback these methods require. Meanwhile jobs that have already fixed their hyper-parameters run for several hours to days, producing head-of-line blocking and pushing users toward reserved GPUs or over-provisioning.

Second, DLT jobs are heterogeneous, so best-fit placement cannot be computed a priori. Jobs differ widely in memory usage, GPU core utilization, sensitivity to interconnect bandwidth, and sensitivity to interference. The paper measures this directly: VGG16 on two P100 GPUs in different CPU sockets reaches only 60% of its same-PCIe-switch throughput, while ResNet-50 is unaffected; two co-located Language Model jobs each slow down 19%, while ResNet-50 co-located with LM does not suffer; and across two servers on 40G InfiniBand, split 2-GPU jobs cost ResNet-50 47%, InceptionV3 30%, and DeepSpeech only 5%. A prior production study reports average GPU utilization of only around 52%, and GPU VMs in the cloud cost nearly 10x a regular VM.

Core Insight

DLT jobs possess intra-job predictability — they are millions of near-identical, clearly separated mini-batch iterations whose GPU memory usage follows a cyclic pattern with a large max/min swing (77x, 23 GB to 0.3 GB, for ResNet-50 on ImageNet). Suspending at the minimum of that cycle makes suspend-resume and migration an order of magnitude more efficient than a naïve implementation, and comparing mini-batch progress rate before and after a placement decision turns the scheduler into an introspective, stateful trial-and-error system rather than one that must analytically model job performance and interference.

Method

Gandiva removes GPU exclusivity and fixed assignment through three mechanisms, all supported by continuous profiling, and exposes five primitives to any DLT scheduling policy: efficient suspend-resume/time-slicing, low-latency migration, fine-grained profiling, dynamic intra-job elasticity, and dynamic prioritization. The enabling idea is a co-design approach spanning both the scheduler layer and the DLT toolkit layer (PyTorch, TensorFlow), which gives the scheduler visibility into the job while retaining generality.

Suspend-resume and packing. On suspend, the toolkit waits for the memory-cycle minimum, copies GPU-resident objects to CPU, frees all GPU allocations including cache, then invokes classic CPU suspend; resume reverses this. In PyTorch the mini-batch boundary is detected by tracking cycle minima inside THCCachingAllocator; in TensorFlow it is the end of session.run(). Signals are SIGTSTP / SIGCONT, and GPU object addresses are patched on resume. Packing — running multiple jobs simultaneously on one GPU — is the alternative, but it helps only when combined resources fit and the jobs do not interfere, so Gandiva packs only after profiling and unpacks back to time-slicing if throughput degrades.

Migration. Two paths. The generic path uses CRIU, but since CRIU cannot migrate GPU-using processes, Gandiva first checkpoints GPU objects and strips GPU state; because CRIU snapshots the entire process memory this yields GB-scale checkpoints. The fast path is checkpoint-aware: tf.Saver is called at a mini-batch boundary, the destination Migration Helper warms up the TF session in advance, only necessary training state moves, the checkpoint lives in Ramdisk (written to the remote Ramdisk over NFS for cross-server moves), the meta-graph is excluded and reconstructed from user code, and under data parallelism only one GPU's copy of the model is saved regardless of GPU count.

Grow-shrink. Opt-in jobs grow their GPU count opportunistically when the cluster is idle and shrink immediately when load returns, bounded by the maximum GPUs in a single server, with growth gated behind an idle timeout to avoid thrashing.

Scheduling policy. The scheduler runs in two concurrent modes. Reactive mode places arriving jobs via Algorithm 1, preferring same-affinity nodes at minimum load, then un-affinitized nodes, then any node with free GPUs (accepting fragmentation, since migration can defragment), then same-affinity nodes with suspend-resume, and only queueing as a last resort. Introspective mode continuously re-optimizes: a greedy packing heuristic sorts jobs by GPU utilization and tries the lowest-utilization job on the lowest-utilization GPU, keeping a packing only when packed throughput exceeds time-sliced throughput; migration improves locality on job departure and defragments in the background until every non-idle server has fewer than 3 of 4 GPUs free.

Key definitions: height of a server = ⌈M/N⌉ for M allocated and N total GPUs (suspend/resume engages only above height one); height of a cluster = max server height; overload ⟺ cluster height > 1; mini_batch_time = time between two consecutive minima of the GPU memory cycle. GPU requests are assumed to be powers of two, and a dedicated GPU cluster is assumed. Cluster-level fairness is explicitly out of scope — only per-server round-robin fairness is provided.

Experimental Setup

Headline Quantitative Results

Cluster efficiency and early feedback (180 GPUs, 1,000 jobs over two hours, time-slicing + packing only):

Trace replay against YARN capacity scheduler (100 GPUs):

Gandiva initiated migration 470 times during this run — approximately once every 20 minutes.

Packing gains vary enormously by GPU utilization (Table 1, P40, mb/s = minibatches/s):

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

AutoML on a ResNet-like network, by target accuracy (minutes, Table 4):

At a 90% target the qualified model found reaches 92.62% validation accuracy; at a 70% target Gandiva shows no benefit because a qualified model appears early and single-run completion time dominates.

Mechanism overheads:

Other headline numbers: Gandiva explores ~10x the hyper-parameter configurations of the baseline at both 4 and 16 GPUs; in a shared 100-GPU cluster two multi-jobs complete 13.6x and 12.9x faster than under the capacity scheduler (baseline 1,215.74 and 1,110.62 mins), of which time-slicing alone accounts for 7x and the remainder is attributed to improved locality from migration. Migration save/restore time is almost constant regardless of GPU count because only one model copy is saved, and parallel per-GPU checkpoint loading does not saturate PCIe bandwidth.

Limitations

• Cluster-level fairness is explicitly not a design goal. Only per-server round-robin fairness via suspend-resume is provided; long-term cluster-level fairness is believed feasible with Gandiva's mechanisms but left to future work.
• The scheduler is centralized. All GPUs are controlled by a single scheduler; the authors note that "a hierarchical approach may be needed if scalability becomes a concern."
• Grow-shrink is narrow. It is opt-in only — because users may need to retune learning rate and batch size when GPU count changes — and jobs grow only up to one server's maximum GPU count.
• Packing is not analytically modeled. "Analytically modeling performance of packing is a challenging problem given the heterogeneity of DLT jobs"; a greedy trial-and-error heuristic substitutes, and prediction is hard even for jobs of the same type.
• MPS could not be used. NVIDIA MPS added significant overhead on the P40/P100 hardware, so packing results exclude it; V100 hardware MPS may improve packing further, but this is untested.
• Trace fidelity is indirect. The real production job code and data were unavailable due to security and privacy regulations, so a synthesized trace of 10 public GitHub models with matched category ratios and runtime distribution was used instead.
• Scope restrictions. Only data parallelism with synchronous updates is evaluated; GPU request counts are assumed to be powers of two; a dedicated GPU cluster for DLT jobs is assumed.
• The CRIU migration path is heavyweight — GB-scale checkpoints and 8-10 s single-GPU migration — which is what motivated the checkpoint-aware TensorFlow path.
• No generality claim: "Gandiva does not claim generality of the proposed techniques to other application domains."
• Communication is characterized, not optimized. The paper measures PCIe-affinity and NIC-interference penalties and uses migration to improve locality, but contains no discussion of NCCL, MPI, ring all-reduce, gradient compression, or parameter-server topology; NVLink is never mentioned and the evaluation network explicitly runs without RDMA.

Open Problems

1. AutoML/scheduler co-design. The authors state directly that "detailed analysis of when and how many configurations to generate and/or how to best allocate priority among the various running configurations to utilize Gandiva features optimally is an open problem that we leave for future work."
2. Cluster-level fairness under over-subscription, time-slicing and migration — asserted to be feasible with these mechanisms but not designed or evaluated.
3. Predicting packing outcomes. Gains span +412% to −16% and are hard to predict even between jobs of the same type; an analytical or learned model of GPU co-location interference (caches, memory bandwidth) would replace the greedy undo-and-retry loop.
4. Hierarchical scheduling to remove the single central scheduler as a scalability limit.
5. Packing on newer hardware. Whether V100-class hardware MPS support changes the packing calculus is raised but left unmeasured.