Looking Beyond GPUs for DNN Scheduling on Multi-Tenant Clusters (Synergy)

Jayashree Mohan, Amar Phanishayee, Janardhan Kulkarni (Microsoft Research); Vijay Chidambaram (UT Austin / VMware Research) | OSDI '22, July 11–13, 2022, Carlsbad, CA | Open source: https://github.com/msr-fiddle/synergy

Problem

DNN training runs on shared, multi-tenant GPU clusters where the user requests a fixed number of GPUs and the scheduler hands out CPU and memory proportional to that GPU count — GPU-proportional allocation. Every prior DNN cluster scheduler (Gandiva, Tiresias, Themis, Gandiva-Fair, AFS, Pollux) does this, treating the GPU as the dominant resource and auxiliary resources as a derived quantity.

But DNNs are not uniformly sensitive to CPU and memory. Data ingestion — reading from storage into memory and pre-processing at the CPU — is expensive and produces data stalls; some image and video recognition models achieve up to 3× speedup when their CPU allocation exceeds the GPU-proportional share, while GNMT is unaffected even by less than its share. GPU-proportional allocation neither gives sensitive jobs more nor reclaims the surplus idling on insensitive ones. Prior characterization of Microsoft's Philly cluster confirms CPU cycles are under-utilized in multi-tenant clusters.

Core Insight

Allocating these auxiliary resources in a workload-aware fashion, rather than the traditional GPU-proportional allocation can significantly improve performance by effectively utilizing cluster-wide resources.

Co-locating a CPU-sensitive job with a CPU-insensitive one (and likewise for memory) creates slack that can be redistributed, under one guardrail: a job receives less than GPU-proportional auxiliary resources only when that does not degrade its throughput below the GPU-proportional baseline.

Method

Synergy is a round-based scheduler that arbitrates GPU, CPU, and memory in a homogeneous cluster. It leaves GPU demand untouched (user-specified, fixed for the job's lifetime) and only tunes the fungible auxiliary dimensions.

 job arrives -> [ Optimistic Profiling ]  once per job lifetime; emits W_j
                          |
                          v
                 [ Priority Job Queue ]   ordered by FIFO/SRTF/LAS/FTF
                          |  runnable set J_t for this round
                          v
                 [ Mechanism: GREEDY | TUNE | OPT ]
                          |  (GPU, CPU, Mem) placement per job
                          v
                 [ Deploy: lease grant/terminate, Synergy iterator + gRPC ]

1. Optimistic profiling. Building the full CPU × memory sensitivity matrix naively costs 24 × 10 = 240 minutes (4 hours) at 1 minute per point on a 24-CPU / 500 GB server. Synergy profiles only the CPU axis at full memory empirically and models the memory axis analytically — valid because the DNN-aware MinIO cache guarantees a fixed number of cache hits per epoch — a 10× reduction, to 24 minutes. CPU points are then chosen by binary search: descend into the lower half when a profiled point yields less than a fixed threshold (say 10%) throughput improvement, else profile more of the upper half. That reaches under 8 minutes with 8 CPU points instead of 24 — the up to 30× total reduction.

2. Synergy-OPT (upper bound, not deployable). The allocation problem is NP-hard, so it is relaxed to two LPs. The first assumes all resources sit on one super-machine with G/C/M units and uses binary variables y_{c,m,j} over the discrete sensitivity matrix W_j:

(1)  Maximize   SUM_{j in J_t} SUM_{[c,m]}  W_j[c,m] * y_{c,m,j}
(2)  SUM_j SUM_{[c,m]} c * y_{c,m,j} <= C     (3)  SUM_j SUM_{[c,m]} m * y_{c,m,j} <= M
(4)  for all j:  SUM_{[c,m]} y_{c,m,j} = 1                       (one config per job)
(5)  for all j:  SUM_{[c,m]} W_j[c,m]*y_{c,m,j} >= W_j[C_g, M_g] (>= fair share)

with C_g = C_i / G_i * g_j and M_g = M_i / G_i * g_j. Theorem 4.1 proves LP(1–5)'s throughput is at least that of an optimal solution. A second LP maps the result onto real machines while minimizing fragmented jobs, provably fragmenting at most 3s jobs for s machines. Synergy-OPT is unusable in practice: per-round solve time grows exponentially, and it yields fractional GPU allocations (e.g. 3.3 GPUs on one server, 2.7 on another for a 6-GPU job).

3. Synergy-TUNE (the deployed heuristic). Runnable jobs are the top n whose GPU demands are exactly satisfiable — auxiliary demands are ignored at selection time, so no job is skipped and GPUs are never idled at full load. Jobs are sorted by GPU, then CPU, then memory demand, each placed on the server with the least free resources that still fits. If a job does not fit: revert its demand to GPU-proportional if it was above; otherwise find a server satisfying only its GPU need, identify co-resident jobs holding more than GPU-proportional, and revert just enough of them. In the worst case every job in a round falls back to GPU-proportional — hence Synergy is never worse than the baseline.

4. Synergy-GREEDY (the strawman). First-fit packing that skips any job not fitting in all dimensions — this exhausts CPU/memory while leaving GPUs fragmented and idle, and starves skipped jobs, breaking the policy's fairness.

5. Implementation. Python, event-driven, with an accompanying simulator. Jobs use a thin Synergy data iterator wrapping the PyTorch and NVIDIA DALI iterators; it registers the job, sends lease updates, checkpoints to shared storage on lease termination, and synchronizes GPU processes. gRPC carries scheduler↔︎job traffic; cvxpy solves Synergy-OPT in the simulator.

Experimental Setup

Headline Quantitative Results

Motivating sensitivity measurements:

Physical cluster, 32 GPUs (Table 5, hours):

Simulator fidelity is within 5% of the physical cluster; Synergy-TUNE lands within 4% of optimal here.

Simulation, 512 GPUs on the real Philly trace, split (20,70,10) — average JCT (hrs):

Under SRTF, short (JCT < 4 hrs) vs. long jobs:

That is a 2.2× short-job tail reduction and 15% average-JCT reduction for both classes; individual jobs speed up by up to 9×.

Simulation, 128 GPUs, varying load: average JCT improves up to 3.4× (single-GPU trace) and up to 1.6× (multi-GPU trace), with gains growing under load because Synergy cuts both queueing delay and per-job runtime. FIFO single-GPU at 9 jobs/hr goes 81 hrs → 22 hrs against a Synergy-OPT bound of 20 hrs; FTF sees 2.3× / 2× (single / multi-GPU); LAS multi-GPU cuts the 95th-percentile JCT of long jobs by 2×. Synergy-TUNE stays within 10% of Synergy-OPT in all cases and at 128 GPUs runs 200× faster (sub-second per round vs. exponential growth).

Utilization and robustness:

Limitations

• Homogeneous clusters only. The heterogeneous extension needs a third profiling dimension (GPU type) and appears only in the extended version.
• Fixed GPU allocation per job lifetime. GPU elasticity and spatial sharing are out of scope; Synergy-OPT's fractional GPU allocations are unrealizable for this reason, and Synergy-OPT itself is not deployable (exponential per-round solve time) — it serves only as a simulated upper bound.
• Depends on MinIO. Without DNN-aware caching the analytical memory model breaks and profiling cost rises.
• Data-parallel jobs only; model- and pipeline-parallel jobs would require per-stage profiling.
• Storage and network bandwidth are not allocated — only CPU and memory. Nor is the augmentation pipeline varied (it is held fixed to avoid affecting accuracy), so the CPU-intensiveness axis is unexplored.
• Consolidation is enforced when a job's GPU demand fits on one server, even though giving up consolidation could sometimes pay off.
• Profiling is a one-time per-job overhead (up to ~8 minutes in the validated case), justified only because jobs run for hours.
• Gains shrink as CPU:GPU ratio rises — 3.4× at ratio 3 down to 1.8× at ratio 6 — so the benefit is partly a function of today's server SKUs.
• Worst-case workload splits yield no gain: at (50,0,50) Synergy-TUNE merely matches GPU-proportional allocation.

Open Problems

1. Extending resource-sensitivity awareness to heterogeneous clusters via a 3-dimensional sensitivity matrix over (CPU, memory, GPU type).
2. Combining resource-sensitivity awareness with GPU spatial sharing for the subset of jobs insensitive to auxiliary resources.
3. Reasoning about per-job storage and network bandwidth demands, not just CPU and memory.
4. Exploring the consolidation-vs-allocation trade-off for multi-GPU jobs, accounting for the network penalty of splitting a job across servers.
5. Profiling and scheduling model- and pipeline-parallel jobs, where each stage has a distinct CPU:GPU and memory:GPU requirement.