Gandiva: Introspective Cluster Scheduling for Deep Learning — Detailed Summary

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 | ISBN 978-1-939133-08-3

Per-section summary organized by the paper's heading structure. Each section includes paragraph-level bullet points and exact quantitative results where the paper provides them. The first two authors contributed equally; Xiao, Han, Peng and Zhao performed the work as interns at Microsoft Research. Shepherd: KyoungSoo Park.

Abstract

• Gandiva is a cluster scheduling framework that uses domain-specific knowledge of deep learning to improve both latency and efficiency of training DL models on a GPU cluster.
• First characteristic exploited — feedback-driven exploration. A user runs a set of jobs (a multi-job) toward one mission and uses early accuracy feedback to dynamically prioritize or kill a subset; simultaneous early feedback on the entire multi-job is critical.
• Second characteristic — heterogeneity. DL jobs differ widely in resource usage, so a scheduler cannot achieve best-fit a priori.
• Third characteristic (the enabler) — intra-job predictability. A job is millions of repetitive mini-batch iterations. Gandiva exploits this to time-slice GPUs efficiently (low latency) and to introspect job performance and dynamically migrate jobs to better-fit GPUs (high efficiency).
• Headline claims: hyper-parameter search sped up by up to an order of magnitude; on a real workload in a 180-GPU cluster, aggregate cluster utilization improves by 26%.

"We show via a prototype implementation and micro-benchmarks that Gandiva can speed up hyper-parameter searches during deep learning by up to an order of magnitude, and achieves better utilization by transparently migrating and time-slicing jobs to achieve better job-to-resource fit."

1. Introduction

Epigraph: "All men schedulers make mistakes; only the wise learn from their mistakes." — Winston Churchill (with "men" struck through and replaced by "schedulers").

• Deep learning has become an increasingly popular computing trend, already impacting personal products for voice and image recognition, and is likely to be a vital and growing workload in cloud data centers.
• DL is compute-intensive and reliant on expensive GPUs: a GPU VM in the cloud costs nearly 10x a regular VM. Cloud operators and large companies manage clusters of tens of thousands of GPUs and depend on schedulers for efficiency.
• Common practice today schedules DLT (deep learning training) jobs with a traditional big-data scheduler — Kubernetes or YARN — designed for MapReduce-style workloads. A DLT job is treated as just another big-data job: allocated GPUs at startup and holding exclusive access until completion.
• Gandiva's thesis: significant cluster-efficiency gains come from tailoring the scheduling framework itself to the unique characteristics of the DL workload.

Characteristic 1 — feedback-driven exploration.

• Because DL experimentation is inherently trial-and-error, users submit several configurations of a job (a multi-job) and use early feedback to prioritize or kill subsets. This conditional exploration, hyper-parameter search, may be manual or automated (HyperOpt, Hyperband). Traditional schedulers run a subset of jobs to completion while queueing the rest — a direct misfit for multi-jobs that need simultaneous early feedback on all constituents.
• Jobs that have already found their hyper-parameters run for several hours to days, causing head-of-line blocking: long jobs hold GPUs exclusively while multi-jobs wait. Long queueing pushes users toward reserved GPUs or cluster over-provisioning, which reduces efficiency.

Characteristic 2 — heterogeneity.

• DLT jobs come from diverse application domains and differ widely in memory usage, GPU core utilization, sensitivity to interconnect bandwidth, and sensitivity to interference. Some multi-GPU jobs perform much better with affinitized GPUs; others are affinity-insensitive. A black-box scheduler therefore achieves sub-optimal efficiency.

Characteristic 3 — intra-job predictability (the enabler).

• A job is millions of similar, clearly separated mini-batch iterations. GPU RAM usage follows a cyclic pattern aligned with mini-batch boundaries, usually with more than 10x difference in GPU RAM usage within a mini-batch.
• Gandiva exploits this to implement application-aware time-slicing, redefining the atom of scheduling from a job to automatically-partitioned micro-tasks. This lets the cluster over-subscribe DLT jobs and give early feedback to every job, including every job in a multi-job.
• Predictability also enables profile-driven introspection: mini-batch progress rate is used to continuously introspect scheduling decisions. Gandiva packs jobs on one GPU only when memory and GPU utilization are low, migrates communication-intensive jobs to more affinitized GPUs, and opportunistically grows a job's parallelism when resources are spare (shrinking when they are not). The implemented policy is a stateful trial-and-error policy, feasible only because of predictability plus a limited state space of options.

Framework contribution — five APIs.

• Beyond the specific policy evaluated, Gandiva exposes five primitives any DLT scheduling policy can use: (a) efficient suspend-resume / time-slicing, (b) low-latency migration, (c) fine-grained profiling, (d) dynamic intra-job elasticity, (e) dynamic prioritization.
• The key to making these efficient is a co-design approach spanning both the scheduler layer and the DLT toolkit layer (TensorFlow, PyTorch). Traditional schedulers treat jobs as black boxes for good reason; Gandiva exploits the dedicated nature of GPU clusters to give the scheduler visibility and control into the job while retaining generality across arbitrary DLT jobs.

Implementation and results preview.

• Implemented by modifying PyTorch and TensorFlow to expose new primitives, plus a scheduling policy manager over Kubernetes and Docker containers.
• On a cluster of 180 heterogeneous GPUs: (i) cluster scheduling efficiency improves by up to 26%; (ii) Gandiva is reactive enough to time-slice multiple jobs on one GPU, reducing time to early feedback by as much as 77%. For a popular hyper-parameter search technique, overall search completion time improves by up to an order of magnitude while using the same resources.

Stated contributions.

1. Illustrate the unique characteristics of the DL workflow and map them to specific cluster-scheduling requirements.
2. Identify generic primitives usable by a DLT scheduling policy, and make time-slicing and migration an order of magnitude more efficient — and therefore practical — by leveraging intra-job periodicity.
3. Propose and evaluate an introspective scheduling framework that continuously refines its decisions, improving early-feedback time and cluster efficiency.

2. Background

• DL is representation learning that automatically infers features from raw data (image classification, language translation); supervised (labeled) or unsupervised (unlabeled). The representation is a deep neural network whose parameters, the weights, are arranged in layers and typically number in the millions.
• Training operates on a mini-batch at a time: a forward pass computes scores from the weights; an objective function measures error against desired scores; a backward pass computes a gradient per weight and applies the negative gradient scaled by the learning rate. Both passes involve billions of floating point operations, hence GPUs. One forward-backward pair is a mini-batch iteration, and millions of iterations are typically performed on large datasets.
• Feedback-driven exploration. A prerequisite for accuracy is model selection. Discovering models such as ResNet or Inception is largely trial-and-error today, though automating it is an active research area.
• Beyond model structure, a set of hyper-parameters must be specified — number of layers/weights, mini-batch size, learning rate — chosen from domain knowledge and trial-and-error, and they can cause early training failure. Hence early feedback is critical, especially in the initial training stages.
• Multi-job. Once a model is fixed, the user runs hyper-parameter search, generating a multi-job where each job trains fully under one configuration. Users typically explore hundreds of configurations, so this is computationally expensive. Sophisticated methods exist: HyperOpt and Hyperband — e.g., Hyperband might initially spawn 128 DLT jobs and, in each round (e.g., 100 mini-batch iterations), kill half the jobs with the lowest accuracy.
• For these algorithms, early feedback on the entire set of jobs is crucial; without it they cannot make effective training decisions.

3. DLT Job Characteristics

3.1 Sensitivity to locality

• Multi-GPU DLT job performance depends on the affinity of allocated GPUs, and jobs differ in sensitivity. Even within one server, asymmetric architecture produces three affinity classes: GPUs in different CPU sockets (DiffSocket), in the same socket but different PCIe switches (SameSocket), or on the same PCIe switch (SamePCIeSw).
• Figure 1 (VGG16 and ResNet-50, two P100 GPUs, TensorFlow): VGG16 with the worst locality (two GPUs in different CPU sockets) achieves only 60% of the best-locality (same PCIe switch) configuration; ResNet-50 is unaffected. The cause is that VGG16 is a larger model, so per-mini-batch model synchronization imposes a higher communication load on the underlying PCIe bus.
• Figure 2 (4-GPU TensorFlow job, ResNet-50 and InceptionV3): the same trend holds across servers. Even over a 40G InfiniBand network, throughput clearly degrades across local 4-GPU → 2x2-GPU → 4x1-GPU, though the two models' sensitivities differ in magnitude.
• Conclusion: a DLT scheduler must account for a job's locality sensitivity when allocating GPUs.

3.2 Sensitivity to interference

• In a shared execution environment, DLT jobs interfere through resource contention, and the degree varies by job.
• Figure 3 — intra-server interference (single-GPU jobs under the same PCIe switch, co-located with a Language Model job): two LMs running together each suffer a 19% slowdown; ResNet-50 does not suffer from co-location with LM; GNMT shows a modest degree of interference. Similar variation is seen for multi-GPU training across model types (omitted for space).
• Figure 4 — inter-server / NIC interference (two 4-GPU servers over 40G InfiniBand, multiple 2-GPU jobs each split across servers): ResNet-50 shows up to 47% slowdown, InceptionV3 30%, while DeepSpeech shows only 5%.
• Summary: popular models across vision, language and speech show different levels of sensitivity to both locality and interference — motivating the predictability-based approach that follows.

3.3 Intra-job predictability

• Figure 5(a) — ResNet-50 on ImageNet, four K80 GPUs, 20 s snapshot: GPU memory follows a clear cyclic pattern; each cycle is one mini-batch (about 1.5 s), rising during the forward pass and falling during the backward pass. Maximum and minimum GPU memory are 23 GB and 0.3 GB — a factor of 77x. The ratio scales with mini-batch size (typically 16 to 256; 128 here). (Footnote: this is actual GPU memory used; PyTorch/TensorFlow cache to avoid expensive GPU memory (de)allocations.)
• Figure 5(b) — GNMT on WMT'14 English-German, one K80 GPU, 20 s snapshot: iterations are not identical (differing sentence lengths, PyTorch dynamic graphs) but the cyclic nature persists. The max/min difference is only 3x, because of a larger model (0.4 GB) and a smaller mini-batch size (16).
• Other domains — speech, GANs, variational auto-encoders — follow a similar cyclic pattern (not shown), since the core of training is gradient descent over many mini-batch iterations.
• Predictability is leveraged three ways: (1) a job can be automatically split into mini-batch iterations, and a collection of iterations over 60 seconds forms a micro-task, which becomes the scheduling interval; (2) performing suspend at the minimum of the memory cycle dramatically reduces the GPU→CPU copy volume, making suspend/resume and migration an order of magnitude more efficient than a naïve implementation; (3) mini-batch progress rate serves as a proxy for evaluating whether packing or migration was effective.

4. Design

• Today's high latency and low utilization stem from assigning a DLT job a fixed set of GPUs exclusively (Figure 6). Exclusivity causes head-of-line blocking, prevents early feedback, and yields high queuing times; it also yields low utilization when a job cannot fully use its GPUs.

4.1 Mechanisms

Overview — three ways to remove exclusivity and fixed assignment (Figure 6): (1) during overload, incoming jobs time-share GPUs with existing jobs, via a custom suspend-resume mechanism tailored for DLT jobs plus selective packing; (2) efficient migration of a job from one GPU set to another — letting time-sliced jobs move to recently vacated GPUs, or de-fragmenting the cluster so incoming jobs get good locality; (3) a GPU grow-shrink mechanism so idle GPUs are used opportunistically. All three are supported by introspection: continuous profiling of resource usage and estimation of job performance.

Suspend-Resume and Packing.

• Suspend-resume removes GPU exclusivity. Modern OSes already do efficient CPU suspend-resume for process time-slicing; Gandiva adds custom support for GPU time-slicing.
• The key idea, given the 77x memory swing, is to suspend-resume DLT jobs when GPU memory usage is at its lowest. On a suspend call the toolkit waits for the minimum of the memory cycle, copies GPU-resident objects to the CPU, releases all GPU memory allocations including cache, and then invokes the classic CPU suspend. On resume the framework allocates GPU memory, copies the stored objects back, and resumes.
• Suspend-resume may also change GPU within the same server (e.g., six 1-GPU jobs time-sharing 4 GPUs). Changing GPU is expensive but this latency is hidden from the critical path. Measured: for typical image-classification jobs suspend-resume completes in under 100 ms; for large language-translation jobs it can take up to 1 s. With a 1-minute time-slicing interval this is an overhead of 2% or less.
• Suspend may be delayed by at most one mini-batch interval (typically a few seconds or less), a worthwhile trade because it cuts GPU-CPU copy cost and CPU memory use — and useful work is accomplished during the delay. The scheduler tracks this delay and adjusts the time-slicing interval for fairness.
• Packing is the alternative to suspend-resume: run multiple jobs on a GPU simultaneously and let the GPU time-share them. Packing is efficient only when the packed jobs do not exceed GPU resources (cores, memory) and do not adversely impact each other; when they interfere, packing can be significantly worse than suspend-resume. Gandiva therefore profiles jobs under exclusive access, packs identified candidates, keeps monitoring, and unpacks back to suspend-resume if performance degrades.

Migration.

• Migration changes the GPU set assigned to a job. Useful in three situations: (i) moving time-sliced jobs to vacated GPUs anywhere in the cluster; (ii) migrating interfering jobs away from each other; (iii) de-fragmenting the cluster so incoming jobs get good locality.
• Approach 1 — CRIU. Gandiva leverages CRIU (Checkpoint/Restore In Userspace). Because CRIU cannot migrate processes that use the GPU device, Gandiva first checkpoints GPU objects and removes all GPU state from the process before invoking CRIU. Because CRIU checkpoints the entire process memory, checkpoints are on the order of GBs for PyTorch DLT jobs, giving migration overhead of about 8-10 s for single-GPU jobs and higher for multi-GPU jobs.
• Approach 2 — checkpoint-aware DLT jobs. Frameworks already expose checkpoint/restore APIs (tensorflow.train.saver), used today so long-running jobs survive server failures. Gandiva extends the framework to migrate such jobs. By warming up the destination before migration and migrating only the necessary training state, migration overhead falls to as little as a second or two. With either approach, inter-server migration overhead is worthwhile relative to the GPU-utilization gain.

Grow-Shrink.

• The third mechanism targets an under-utilized cluster ("say, late at night"): grow a job's GPU count opportunistically during idle times, and shrink it when load increases.
• Many DLT jobs, especially in the image domain, see linear performance scaling as GPUs are added. Gandiva applies grow-shrink only to jobs that explicitly declare themselves adaptive. When multiple jobs qualify, Gandiva uses profiling to estimate each job's progress rate and allocates accordingly.

Profiling.

• Like any scheduler, Gandiva monitors CPU and GPU utilization, CPU/GPU memory. What is unique is that it introspects jobs in an application-aware manner to estimate rate of progress, using the regular pattern from §3.
• Gandiva estimates mini_batch_time — the time for one forward/backward pass over a batch — as the time between two minimums of the GPU memory usage cycle. Since jobs run millions of such iterations, the scheduler compares mini_batch_time before and after a scheduling decision to judge its effectiveness.
• Example: for packing two jobs, comparing each job's mini_batch_time before and after tells Gandiva whether packing worked. Without profiling one would have to model both jobs' performance on various GPUs and all the ways they may interfere (caches, memory bandwidth, etc.) — a non-trivial task, as the varied packing results in §6.1 show.

4.2 Scheduling Policy

Definitions and assumptions.

• Jobs are encapsulated in containers and declare the number of GPUs required, a priority (dynamically changeable), and a flag for grow-shrink capability. GPU counts are assumed to be powers of two (typical for DLT jobs today). A dedicated GPU cluster for DLT jobs is assumed.
• Height of a server = ⌈M/N⌉, where M = number of allocated GPUs and N = number of total GPUs. Suspend/resume is used only when server height exceeds one. Height of a cluster = maximum height over all its servers. Overload ⟺ cluster height > 1, i.e., the sum of requested/allocated GPUs across all jobs exceeds total GPUs.
• Affinity of a server = the type of jobs (by GPU count required) assigned to it. Servers start with affinity zero; assigning a 2-GPU job makes affinity two. Used to place jobs with similar GPU requirements on the same server.

Goals.

• Primary goal: early feedback. Instead of queueing during overload, Gandiva supports over-subscription, allocating GPUs to a new job immediately and using suspend-resume to deliver early results.
• Second goal: cluster efficiency, via a continuous optimization process using profiling and a greedy heuristic over packing, migration and grow-shrink.
• Cluster-level fairness is explicitly not a design goal. Long-term cluster-level fairness is believed feasible with Gandiva's mechanisms; the paper addresses only per-server fairness via suspend-resume and leaves cluster-level fairness to future work.
• The scheduler operates in two modes — reactive and introspective — and can be in both at the same time.

4.2.1 Reactive Mode

• Reactive mode handles job arrivals, departures and machine failures, as conventional schedulers do. Failure handling follows the conventional approach, so only job placement is discussed.

Algorithm 1 — getNodes(in job, out nodes)

 1: nodes0 ← findNodes(job.gpu, affinity ← job.gpu)
 2: nodes1 ← minLoadNodes(node0)
 3: nodes2 ← findNodes(job.gpu, affinity ← 0)
 4: nodes3 ← findNodes(job.gpu)
 5: if nodes1 and height(nodes1) < 1:
 6:     return nodes1        // Same affinity with free GPUs
 7: if nodes2 and numGPUs(nodes2) ≥ job.gpu:
 8:     return nodes2        // Unallocated GPU servers
 9: if nodes3:
10:     return nodes3        // Relax affinity constraint
11: elif nodes1:
12:     return nodes1        // Allow over-subscription
13: else:
14:     enqueue(job)         // Job queued

(The PDF prints line 3 as findNodes(jog.gpu, ...) — a typo for job.gpu.)

• findNodes returns node candidates satisfying the request with an optional affinity constraint. Gandiva first seeks nodes with the same affinity as the new job and, among those, minimum load; if such nodes exist with height less than one (lines 5-6) the node is assigned. Otherwise it tries un-affinitized nodes (lines 7-8). Failing that, it looks for nodes with free GPUs while ignoring affinity (lines 9-10) — possibly fragmenting the allocation, but migration can later de-fragment. If no free GPUs exist at all, nodes with the same affinity are used with suspend-resume (lines 11-12); otherwise the job is queued (lines 13-14).
• Figure 7 (16-GPU cluster): 1-GPU jobs are placed together while 2-GPU and 4-GPU jobs go on different servers. Over-subscription load is balanced by choosing the minimum-load server — e.g., six 1-GPU jobs on each of two servers.
• On job departure, conventional schedulers pick the next queued job. Gandiva additionally checks whether cluster height can be reduced, e.g., by migrating a suspended job to the newly vacated GPU — from the same server or any other. Departures can also trigger migrations for improving locality.
• Two factors distinguish Gandiva's placement. First, it allows over-subscription, and an over-subscribed server uses weighted round-robin scheduling to give each job its fair time-share. Second, unlike today's schedulers where allocation is a one-time arrival event, Gandiva uses introspective mode to improve utilization continuously. Consequently the placement policy itself is deliberately simple, so GPUs are allocated quickly and early feedback begins.

4.2.2 Introspective Mode

• In introspective mode Gandiva continuously monitors and re-optimizes the job-to-GPU mapping to improve utilization and job completion time.
• Packing is considered only during overload. If the combined memory requirement of the packed jobs exceeds GPU memory, the overhead of "paging" from CPU memory is significantly high, so packing is not effective. Even when combined memory fits, packing may still be worse than suspend-resume — for some jobs it increases efficiency, for others it hurts.
• Analytically modeling packing performance is a challenging problem given DLT job heterogeneity. Gandiva instead uses a greedy heuristic: on arrival, always run jobs exclusively with suspend-resume and collect profiling data (GPU utilization, memory, progress rate); maintain a list of jobs sorted by GPU utilization; greedily pick the lowest-utilization job and attempt to pack it on the lowest-utilization GPU, only if combined memory does not exceed GPU memory. Packing is deemed successful when the total throughput of packed jobs exceeds time-slicing. On failure, undo the packing and try the next-lowest-utilization GPU; on success, move to the next lower-utilization job and repeat. This simple greedy heuristic achieves 26% efficiency gains.
• Migration is used to improve locality whenever a job departs, and also as a background "defrag" process. Jobs that are not co-located are selected and a co-located placement is sought.
• Figure 8 (from the cluster experiment in §6.4): a multi-job of 4 jobs each requiring 2 GPUs was scheduled with poor affinity — only J0's two GPUs were colocated, while J1, J2, J3 were on separated GPUs. Three minutes later a background DeepSpeech job completed and released its 8 GPUs. Three of those 8 (marked D, on servers 1, 3 and 4) could improve the multi-job's efficiency, so Gandiva migrated J1, J2 and J3 to colocated GPUs.
• De-fragmentation: pick the non-idle server with the most free GPUs, then try to move its jobs to servers with fewer free GPUs, as long as there is negligible performance loss. Repeat until every non-idle server has fewer free GPUs than a threshold (3 out of 4 in the experiments) or until no job would benefit.
• Grow-shrink is triggered only when the cluster is under-utilized and only for jobs that explicitly identify themselves as amenable. Jobs are grown only up to the maximum number of GPUs available in a single server. Growth is triggered only after an idle period to avoid thrashing; shrink happens immediately when a new job needs the GPUs.
• Time-slicing uses round-robin scheduling within each server for fair GPU time-sharing. With multiple priority levels, higher-priority jobs are never suspended to accommodate lower-priority ones; if a server is saturated with high-priority jobs, the lower-priority job is migrated elsewhere if feasible.

5. Implementation

• DLT jobs are packaged as Docker containers holding customized DL toolkits plus a Gandiva client, and are submitted to Kubernetes. Gandiva implements a custom scheduler that then schedules them.

5.1 Scheduler

• Gandiva consists of a custom central scheduler plus a client component inside every DLT job container. The scheduler is just another container managed by Kubernetes: Kubernetes handles overall cluster management while the Gandiva scheduler handles DLT job scheduling. It uses the Kubernetes API to read node and container information and assigns each newly submitted container to one or more GPUs per policy.
• When a container is scheduled on a node, only the Gandiva client starts executing initially. The client polls the scheduler to learn which GPUs to expose to the job and controls job execution via suspend/resume and migrate commands. All GPUs are fully controlled by the central scheduler, though a hierarchical approach may be needed if scalability becomes a concern.

5.2 Modifications to DL toolkits

• For space, the paper describes only the time-slicing implementation for PyTorch and the migration implementation for TensorFlow.

PyTorch time-slicing.

• The Gandiva client sends SIGTSTP to signal suspension, and indicates whether resume should occur on a new GPU via an in-memory file. On receipt the toolkit sets a suspend flag and executes the suspend only at a mini-batch boundary.
• In TensorFlow, a define-and-run toolkit, mini-batch boundaries are easily identified (end of session.run()). In PyTorch, a define-by-run toolkit, the boundary is found by tracking GPU memory usage cycles inside PyTorch's GPU memory manager (THCCachingAllocator) and looking for a cycle minimum whenever GPU memory is freed.
• Once the minimum is detected, the toolkit (i) copies all stored objects from GPU to CPU, (ii) frees GPU allocations, (iii) suspends the process. On SIGCONT it allocates GPU memory, copies objects back, and resumes. To handle device address change on resume, GPU objects are tracked and patched with the new addresses.
• Changing GPU involves calling cudaDeviceReset and CudaInit, which can take 5-10 s. This latency is hidden by performing these actions in the background while "suspended".

TensorFlow migration.

• 400+ lines of Python/C++ were added to TensorFlow, plus 200+ additional lines for a Migration Helper deployed on each server supporting on-demand checkpointing and migration.
• On a migration command, the destination Helper first warms up the TF session and waits for the checkpoint; the source Helper then asks TF to save the checkpoint, moves it to the destination for cross-server migration, and finally resumes the training session. To speed this up, Ramdisk keeps the checkpoint in memory; in the cross-server case the modified TF saves directly to the remote Ramdisk over NFS.
• Checkpointing calls tf.Saver at the end of a mini-batch. For data parallelism the checkpoint includes the model from only one GPU, regardless of how many GPUs are used. The meta-graph structure is excluded from the checkpoint since it can be reconstructed from user code.
• In the warm-up phase the modified TF checks the GPU configuration and reconstructs the meta-graph, then creates the Executor and runs a warm-up operation so initialization is not deferred lazily. On resume it loads the checkpoint, with multiple GPUs loading in parallel, and continues training.

6. Evaluation

Hardware and software setup.

"Our servers are 12-core Intel Xeon [email protected] with 448GB RAM and two 40Gbps links (no RDMA), running Ubuntu 16.04. Each server has either four P100 or four P40 GPUs. All servers are connected to a network file-system called GlusterFS with two-way replication on the server disks (SSDs)."

• Only data parallelism is evaluated (more common than model parallelism), with synchronous updates (asynchronous is also supported).
• 18 models total: 8 in PyTorch 0.3 and 10 in TensorFlow 1.4. Batch sizes are the defaults from each model's reference. All models take 6 s or less per mini-batch, so the time-slicing interval is set to 60 s.

6.1 Micro-benchmarks

Time-slicing.

• Six 1-GPU ResNet-50 / Cifar10 / PyTorch jobs share a single server with four P100 GPUs. Ideally each job should get four minutes of GPU time out of every six.
• Figure 9: initially four 1-GPU long jobs run; at t = 25 min two 1-GPU short jobs are scheduled. The four long jobs drop to 4/6th of their previous share and recover when the short jobs depart. Aggregate throughput across all jobs is affected by less than 2% over the entire trace — time-slicing is an efficient mechanism for early feedback under over-subscription.

Packing.

Table 1: Packing multiple jobs on P40 (mb/s = minibatches/s)

• For small jobs with low GPU utilization, packing gives gains of as much as 412%. For middling utilization, gains vary by model — up to 46%, but as low as −16%. For high-utilization image jobs such as ResNet-50 or ResNext-50 on Cifar10, packing hurts performance by 11-13%.
• These packing results are without NVIDIA's multi-process service (MPS): MPS was found to introduce significant overhead on P40/P100 GPUs. However, hardware support for MPS in V100 GPUs suggests MPS may increase packing gains on V100.
• Predicting packing performance is challenging even for jobs of the same type, let alone across types — hence the profiling-based approach. Figure 10: two image super-resolution jobs are initially time-sliced on the same P40; the scheduler observes their memory and core utilization are small enough, packs them, and continues profiling. Because aggregate performance improves, packing is retained; otherwise packing would be undone and the jobs would revert to time-slicing.

Grow-Shrink.

• Useful primarily when the cluster is under-utilized, and applied only to opt-in jobs because users may want to adjust the learning rate and batch size depending on the number of GPUs available.
• Figure 11 (4x P100 server; ResNet-50 with PyTorch): initially a growth-capable 1-GPU job, a 1-GPU short job, and a 2-GPU short job. At t = 25 min the short job departs and, after a timeout with no new job allocated, the long job expands to 2 GPUs. At t = 45 min the second short job departs and it expands to all four GPUs. At t = 75 min a new 2-GPU job arrives and the long job immediately shrinks to two GPUs; when another 1-GPU job appears it shrinks to one GPU. Idle GPU resources are therefore effectively used.

Migration.

• Overhead measured on a server with 8 P100 GPUs using TensorFlow, migrating a ResNet-50 single-server training job from one server to another.

• Figure 12 breaks down migration time for 1, 2, 4 and 8 GPUs into components (restoring checkpoint, saving checkpoint, saving extra replicas, saving meta-graph, TensorFlow lazy initialization, CUDA lazy initialization, pre-initialization), grouped as Migration Time / Eliminated Time / Warm-up Time.

  "Using our optimized implementation, we are able to eliminate or hide the majority of the migration overhead. The actual migration time, saving and restoring checkpoints, remains almost constant regardless of the number of GPUs because we save only one copy of the model. The loading of the in-memory checkpoint in each GPU runs in parallel and does not saturate the PCI-e bandwidth. The warm-up time and the cost due to meta-graph and checkpoints from other GPUs grow with the number of GPUs. As a result, we are able to save 98% of the migration overhead of 35s for 8-GPU jobs."

• Figure 13 shows max, min and average intra-server and inter-server migration time for a 1-GPU job across the 10 models of Table 2 over 3 runs. Six of the 10 migrate within 1 second. Even the largest model — DeepSpeech, with a 1.4 GB checkpoint — migrates in about 3.5 seconds, negligible against training runs lasting hours or days. Reported checkpoint sizes: Wavenet 8 MB, Bi-Att-Flow 42 MB, InceptionV3 91 MB, ResNet-50 98 MB, Alexnet 236 MB, Language Model 252 MB, Vgg16 528 MB, GNMT 645 MB, Transformer 703 MB, DeepSpeech 1405 MB.

6.2 Model exploration in a multi-job

• AutoML — automatic model exploration through hyper-parameter search — has two parts: a hyper-parameter configuration generator and a performance evaluator. The generator proposes new candidate configurations, sometimes using prior run performance as signal. The evaluator uses early output (e.g., the learning curve) to predict final performance and decide whether to continue or terminate a job early.
• In a traditional scheduler, the number of configurations explored at any time is limited by the number of GPUs available. Gandiva offers time-slicing and dynamic prioritization: the generator is no longer GPU-limited and can emit many more configurations, and the evaluator can decide not just whether to continue or terminate but how much priority to assign.
• The paper explores one instance of this; detailed analysis of when and how many configurations to generate, and how best to allocate priority, is an open problem left for future work.
• Gandiva benefits AutoML two ways: (i) exploring more hyper-parameter configurations within a timespan, enabling better models; (ii) finding a qualified model faster given a fixed configuration set, through prioritization.

Experiment A — number of configurations explored.

• AutoML tunes a LeNet-like CNN with multiple convolution and fully connected layers on Cifar10. The hyper-parameter space has 12 dimensions including learning rate, dropout rate, number of layers and choice of optimizer.
• Configurations are generated continually by Hyperopt, with a curve-fitting method used to predict the learning curve every 1,000 mini-batches (3% of total mini-batches). Jobs with no promise — less than 30% predicted accuracy — are stopped early.
• The multi-job runs on 4 (or 16) P40 GPUs with each job requiring 1 GPU, and AutoML schedules 2 (or 8) more jobs every 1,000 mini-batches. In the baseline, jobs wait in a FIFO queue for running jobs to be terminated early or complete; in Gandiva they are scheduled with time-slicing and migration support.
• Figure 14: Gandiva explores almost 10 times the number of configurations as the baseline, in both the 4-GPU and 16-GPU cases. In the baseline, GPUs get "stuck" with a sub-optimal set of jobs that must run to completion; with time-slicing, new configurations are explored in parallel alongside them.

Experiment B — time to a qualified model.

• Hyperopt randomly generates the same set of 374 hyper-parameter configurations for both baseline and Gandiva. The metric is time to find a configuration with at least 84% accuracy (footnote: the LeNet-like CNN is small; 84% is the best accuracy found among the generated configurations).
• AutoML evaluates jobs every 1,000 mini-batches and re-prioritizes them by the learning-curve-predicted probability of reaching 84%. In Gandiva the top M jobs with the highest probabilities train exclusively — M = 2 for the 4-GPU case and 8 for the 16-GPU case — while the rest are time-sliced. The baseline is unchanged.
• Gandiva achieves a 7x speedup over baseline for the 4-GPU case and 6x for the 16-GPU case. More GPUs help the baseline because they implicitly increase the degree of parallelism of the long-running jobs. Two factors drive the gain: prioritization grants more compute to promising jobs, and running more configurations in parallel finds promising jobs quickly from early feedback.
• The first qualified configuration is scheduled 365th by both Gandiva and the baseline. Rerunning with the qualified job moved to the 25th, 50th and 75th percentile scheduling positions gives Table 3: the later the qualified configuration appears, the larger Gandiva's gain. In typical AutoML runs, quality models usually appear later, since early-stopped jobs' configurations guide the system toward better ones.

Table 3: Time to find a qualified configuration (minutes)

Experiment C — sensitivity to target accuracy.

• AutoML is run at different target accuracies on a large state-of-the-art ResNet-like model (the official ResNet example in Keras) for Cifar10. Hyperopt generates 100 configurations, with the search space covering both the network architecture and various tunable hyper-parameters. Learning-curve prediction runs every 3% of total mini-batches. The experiment uses 16 P40 GPUs with one GPU per job.

Table 4: Model searching in ResNet-like network (minutes)

• For higher target accuracy, Gandiva's gain is more notable. With 90% specified as the goal, the qualified model found achieves 92.62% validation accuracy. At a low target such as 70%, a qualified model appears early, so the time to complete a single qualified configuration run dominates the total search time and Gandiva shows little benefit. When AutoML targets high-accuracy models, Gandiva provides significant gains over the baseline.

6.3 Cluster experiments: time-slicing and packing

• The Gandiva scheduler is evaluated on a 45-server, 180-GPU cluster with roughly an equal mix of P100 and P40 GPUs, running both reactive and introspective modes. To isolate mechanism contributions, this experiment uses only time-slicing and packing and disallows migrations, and no jobs are grow-shrink enabled — so training accuracy is unaffected by Gandiva's mechanisms.

• Job mix: the eight jobs from Table 1 are mixed so that average GPU utilization is about 50%, similar to the average GPU utilization reported from a study of a large deep learning cluster. Jobs 1 and 2 (low utilization) are chosen with probability 0.3; jobs 3, 4 and 5 (mid utilization) with 0.25; jobs 6, 7 and 8 (high utilization) with 0.45. Jobs 7 and 8 require either 2 or 4 GPUs; the rest use 1 GPU each.

• Mini-batch counts are chosen so that, in isolation on a P40, each job takes between 30 and 45 minutes of GPU time. A total of 1,000 jobs drawn from this distribution arrive uniformly at random over two hours. The baseline is a scheduler that does bin-packing but does not over-subscribe.

• Early feedback is measured as the average time to complete 100 mini-batches across all jobs (Hyperband uses 100 mini-batches to evaluate a job).

  "We find that the average time to complete 100 mini-batches is 498s for Gandiva and 2,203s for the baseline, for a reduction of 77%."

• Efficiency (Figure 15): average cluster GPU utilization for baseline vs Gandiva, plus the cumulative number of successful packings on the right y-axis.

  "The average utilization (computed over the stable regime from 20 to 200 mins) achieved by Gandiva is 62.8% compared to baseline average of 50.1%, resulting in a 26% relative improvement."

• The greedy packing heuristic is mostly successful, with only a few packing decisions needing to be undone — the packing curve is mostly increasing with only small occasional dips.

6.4 Cluster experiments: time-slicing and migration

• Trace: a 9-day real-world job trace from a 2,000-GPU production cluster at Microsoft, containing over 8,800 DLT jobs across three categories: computer vision (10%), NLP (60%), and speech (30%) per user survey and log analysis. The data and code used by those jobs were unavailable due to security and privacy regulations, so 10 state-of-the-art models from GitHub with 50,000+ stars in total were substituted.

Table 2: Neural models and the ratios in the trace

• Models are mixed at the same ratios as the real trace, and mini-batch counts are set so that job running times follow the 9-day trace's distribution. The synthesized trace closely follows the real trace's running-time distribution (Figure 16). No jobs are grow-shrink enabled here, as the cluster is under high load. The trace is replayed under Hadoop's YARN capacity scheduler and under Gandiva.
• Fast-forwarding: to speed up replaying 9 days, predictability is exploited — the scheduler instructs a running job to skip mini-batches whenever no scheduling events (arrival, departure, migration, etc.) are pending, with the skipped time computed from the previously measured steady-state mini-batch performance.
• Fast-forwarding is validated on a 3-hour trace by comparing average job completion time (JCT) and makespan with and without it, under both schedulers: "The difference between the real and fast-forwarded experiment in all cases was less than 1%."

Table 5: Full trace experiment with fast-forwarding (100 GPUs: 50 P100, 50 P40)

• Gandiva improves average JCT by 26.8% and reduces total makespan by 17.8%. Figure 17 (CDF of JCT) shows Gandiva has more jobs with a JCT less than around 100 mins. "During the entire experiment, Gandiva initiates migration 470 times; i.e., approximately once every 20 minutes."

• Multi-job performance in a shared cluster: the synthesized trace runs in the same 100-GPU cluster as background jobs, emulating a realistic shared environment. At the 5,607th minute (roughly mid-trace), two multi-jobs are launched, each searching for a qualified CNN model on Cifar10, each allocated 8 GPUs. For fair comparison, each multi-job may preempt other jobs to obtain its 8 GPUs, reducing unpredictable resource sharing.

• To expose the effect of migration, the multi-job trains a 2-GPU VGG-like model that is large and locality sensitive (§3.1). Each AutoML job runs for 100,000 mini-batches and reports the learning curve every 3,000 mini-batches (3%), and can be early-stopped if the learning shows no promise. The AutoML algorithm tunes the learning rate with 40 configurations. The multi-job completes when a model reaches 99.5% training accuracy with 91.3% validation accuracy. The top M highest-probability jobs run exclusively while others are time-sliced; M = 2 (i.e., 4 GPUs).

  "As shown in Figure 18, with the capacity scheduler, it takes 1,215.74 and 1,110.62 mins, respectively, to find the qualified configuration for the two multi-jobs. ... As a result, Gandiva achieves a speedup of 13.6 and 12.9, respectively. Based on a micro-benchmark we did, we observed that time-slicing alone gave 7x gains for this AutoML experiment. Thus, the rest of the gains are attributable to improved locality due to migration."

7. Related Work

• DLT job scheduling today. DLT jobs are scheduled by big-data schedulers such as Kubernetes or YARN, in which a fixed set of GPUs is assigned exclusively for the lifetime of a job. Consequently job queueing times vary from a few minutes to even hundreds of minutes.
• An earlier production study reports average GPU utilization of only around 52%. Low utilization can be inherent — from the use of small models and/or small batch sizes chosen for better generalization — and jobs with inherently high utilization can still be adversely affected by poor GPU affinity and/or interference.
• Scheduling policies for machine learning. Recent work also identifies locality, interference, and GPU utilization as important performance factors for GPU workloads and builds analytical models to predict GPU workload performance. A Gandiva scheduler may leverage such models to guide its decisions; at its core Gandiva is designed to empower DLT schedulers with primitives such as time-slicing and migration.
• SLAQ prioritizes resources in a CPU-based cluster toward Spark jobs with high potential (e.g., a fast-improving learning curve); Gandiva can adopt the same policy for DLT on GPU clusters. Optimus derives a proper number of parameter-servers and workers for MxNet-based jobs and is complementary to Gandiva.
• AutoML. Gandiva enables co-design of DLT schedulers and AutoML algorithms: jobs in a multi-job can be promoted dynamically with more resource and/or better locality. Google Vizier, HyperDrive, and TuPAQ focus more on AutoML system design; Gandiva empowers these systems with lower-level system primitives that further improve the AutoML training experience in a multi-job.
• Big data cluster scheduling frameworks. Most recent frameworks model jobs as a data flow graph (DFG), instantiating Map/Reduce-like tasks scheduled by job progress and DFG dependency. Gandiva instead relies on the micro-task boundary implicitly defined by the mini-batch boundary. Its low-level mechanisms differ significantly from big-data scheduling systems while being surprisingly similar to a traditional operating system.
• Time-slicing, suspend-resume, and process migration. Gandiva adopts traditional OS process primitives for DLT scheduling, but unlike general purpose OS mechanisms it leverages intra-job predictability of DLT to achieve a highly efficient implementation. Explicitly: "Gandiva does not claim generality of the proposed techniques to other application domains."

8. Conclusion

"We present Gandiva, a cluster scheduling framework for deep learning, which provides a set of efficient, low-level system primitives such as time-slicing, migration, intra-job elasticity, and dynamic priority. Using these primitives, Gandiva can effectively support neural model exploration in a multi-job, finding accurate neural models up to an order of magnitude faster than using traditional schedulers in a realistic shared cluster environment. Gandiva provides an efficient implementation of the proposed mechanisms by exploiting the intra-job predictability of DLT: our system prototype demonstrates that job suspend/resume and migration can be achieved under a second, even for cross-server migration for popular deep learning toolkits such as Tensorflow and PyTorch. Combined with an introspective scheduling policy, Gandiva improves overall cluster utilization by 26%."

Consolidated Quantitative Record

Evaluation Setup Summary

Communication and Interconnect Discussion

The paper's treatment of communication is confined to locality and interference characterization; it does not analyze collective communication libraries.

• Intra-server topology taxonomy (§3.1): three affinity classes — same PCIe switch, same CPU socket / different PCIe switch, different CPU sockets — arising from asymmetric server architecture. NVLink is never mentioned in the paper.
• VGG16's 60% locality penalty is attributed directly to PCIe bus load: "model synchronization in each mini-batch incurs a higher communication load on the underlying PCIe bus." ResNet-50, a smaller model, is insensitive.
• Inter-server (§3.1): on 40G InfiniBand, 4-GPU TensorFlow jobs degrade going from local-4-GPU → 2x2-GPU → 4x1-GPU, by model-dependent amounts. NIC interference (§3.2, Fig. 4) on the same fabric costs ResNet-50 −47%, InceptionV3 −30%, DeepSpeech −5%.
• Evaluation network (§6): "two 40Gbps links (no RDMA)" — RDMA is explicitly not used.
• Migration and PCIe (§6.1): "The loading of the in-memory checkpoint in each GPU runs in parallel and does not saturate the PCI-e bandwidth." Cross-server checkpoint transfer targets a remote Ramdisk over NFS.
• Migration motivation (§4.1, §4.2.2): move communication-intensive jobs to more affinitized GPUs; de-fragment so incoming jobs receive good locality. §6.4 deliberately uses a 2-GPU VGG-like model that is "large and locality sensitive" to expose this benefit; migration accounts for the gain beyond the 7x from time-slicing alone, reaching 13.6x / 12.9x.
• Scaling assumption: grow-shrink rests on the observation that "many DLT jobs, especially in the image domain, see linear performance scaling as the number of GPUs is increased," yet Gandiva only grows within a single server.
• Absent from the paper: any discussion of NCCL, MPI, ring all-reduce, gradient compression, or parameter-server topology. Optimus (parameter-server/worker sizing for MxNet) is cited only as complementary related work.

Limitations and Future Work (as stated)

• Cluster-level fairness is explicitly not a design goal. Only per-server fairness via round-robin suspend-resume is provided; long-term cluster-level fairness is "believed feasible using the Gandiva mechanisms" and is left to future work.
• Centralized scheduler scalability: "While scheduling of all the GPUs in our cluster is fully controlled by the central scheduler, a hierarchical approach may be needed if scalability becomes a concern."
• Grow-shrink is limited to a single server's maximum GPU count and requires jobs to opt in, because users may need to retune learning rate and batch size when the GPU count changes.
• AutoML co-design is open: "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."
• 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 is used instead, and prediction is hard even for jobs of the same type.
• MPS unusable on the evaluated hardware: significant overhead on P40/P100; V100 hardware MPS may improve packing further, but this is untested.
• Trace fidelity: 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.
• No generality claim: "Gandiva does not claim generality of the proposed techniques to other application domains."
• 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, 8-10 s single-GPU migration and worse for multi-GPU — which is precisely what motivated the checkpoint-aware TensorFlow path.