THEMIS: Fair and Efficient GPU Cluster Scheduling

Kshiteej Mahajan, Arjun Balasubramanian, Arjun Singhvi, Shivaram Venkataraman, Aditya Akella, Shuchi Chawla (University of Wisconsin–Madison); Amar Phanishayee (Microsoft Research) | 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI '20), Feb 25–27 2020, Santa Clara, CA | ISBN 978-1-939133-13-7

Problem

Organizations consolidate GPUs into shared clusters for lower cost and reduced development overhead, but there are no ML-workload-specific mechanisms for sharing such a cluster fairly. Operators report that what users actually need is sharing incentive: with N users sharing cluster C, no user should perform worse than on a private cluster of size C/N. Existing fair schedulers — Quincy, DRF, Carbyne — were built for big data analytics and are "far from effective" here, because ML workloads have two attributes those schedulers never modeled. First, ML jobs have long-running, gang-scheduled tasks: the median task in the studied Microsoft trace is 3.75 GPU hours and the median app is 11.5 GPU days, so DRF-style instantaneous fairness (which relies on frequent task completions to redistribute resources) makes late arrivals wait inordinately long. Second, because tasks synchronize model updates every iteration, jobs are placement-sensitive, and they differ in how sensitive they are. Attained- service schemes such as Tiresias's LAS fix the starvation problem but remain placement-unaware, so jobs with identical aggregate resources can perform very differently. The paper proves (Theorem 3.1) that DRF and LAS therefore violate sharing incentive, Pareto efficiency, and envy-freeness for ML apps.

Core Insight

Replace instantaneous resource fairness with a long-term, placement-aware metric — finish-time fairness r = Tsh / Tid, the ratio of an app's finish time in the shared cluster to its finish time alone in a 1/N cluster — and let apps themselves report r for each candidate GPU subset through a repeated partial allocation auction, which trades fairness for placement efficiency within a round while converging to fairness across rounds.

Method

Metric. r = Tsh / Tid, where Tsh is the shared finish time (including placement slowdown and queuing delay) and Tid is the finish time on an exclusive 1/N share. Sharing incentive holds when r ≤ 1. Because the scheduler cannot predict how apps react to allocations, THEMIS widens the API: each app returns a table mapping candidate GPU allocations to estimated r.

Estimating r (Equation 1, single-job app):

r(G⃗)          = Tsh(G⃗) / Tid
Tsh            = (Tcurrent - Tstart) + iter_left * iter_time(G⃗)
Tid            = Tcluster * Navg
iter_time(G⃗)  = iter_time_serial * S(G⃗) / min(||G⃗||_1, job_demand_max)
Tcluster       = iter_total * iter_serial_time / min(R_C, job_demand_max)

S(G⃗) ≥ 1 is a placement-dependent slowdown penalty, profiled offline or bootstrapped online from crude constants (single machine = 1, cross-machine = 1.1, cross-rack = 1.3). Multi-job apps use per-phase sums (Equation 2) for Successive Halving (log2(n) phases; Hyperband, Vizier) and last-job-to-finish extrapolation for Performance Curve Stopping (Hyperdrive, Vizier).

Mechanism. A naive "sort by reported r" policy invites lying, violating strategy proofness. THEMIS instead uses a partial allocation (PA) auction: it computes a proportionally-fair allocation by maximizing Π 1/r, then hands each app only a fraction c_i < 1 of it, keeping (1 − c_i) as a hidden payment sized by how much that app's presence hurts other bidders. One-shot PA gives SP, PE, and EF but not SI (Theorem 3.2), because hidden payments leave GPUs unallocated. Multi-round auctions restore SI via three additions: round-by-round re-auctioning on lease expiry, round-by-round filtering to the worst-r (1 − f) fraction of apps, and random allocation of leftover GPUs to non-participating apps (restoring work conservation). Theorem 3.3 shows this preserves PE, EF, SP while maximizing SI.

Architecture — two-level semi-optimistic scheduling. Mesos-style pessimistic schedulers offer resources to one app at a time; Omega-style optimistic schedulers let all apps contend concurrently. Auctions need neither, but one half of each: multi-app visibility with single-app allocation.

  +----------------------------------------------------------+
  |  THEMIS ARBITER  (module in YARN Resource Manager)        |
  +----------------------------------------------------------+
   VISIBILITY PHASE                 ALLOCATION PHASE
   (1) ask all apps for r           (4) pick winning bids via
   (2) offer available GPUs to          partial allocation +
       worst-r (1-f) fraction           leftover allocation
                |    ^                       |
                v    | (3) one bid per app   v (5) allocation
   +---------+  +---------+          +---------+
   | AGENT   |  | AGENT   |   ...    | AGENT   |   AGENT then hands
   | +App1   |  | +App2   |          | +Appn   |   GPUs to the app
   +---------+  +---------+          +---------+   scheduler, which
                                                   splits across jobs

Implementation. Apache Hadoop YARN 3.2.0 with Submarine; the Submarine Application Master hosts the app scheduler (Hyperband), the AGENT, and a profiler parsing TensorFlow logs for iteration times (to estimate S) and loss values (for early stopping). The ARBITER is a YARN Resource Manager module using Gurobi; AGENT↔︎ARBITER traffic is gRPC; jobs checkpoint to HDFS to survive allocation changes.

Experimental Setup

Headline Quantitative Results

Placement sensitivity is model-dependent (Table 1, 4 P100 GPUs):

End-to-end (production trace): more than 2.25X fairness improvement and ~5% to 250% better cluster efficiency vs. state-of-the-art schedulers.

Testbed macrobenchmarks:

• THEMIS gives 2.2X to 3.25X better (smaller) maximum r than all baselines, with a narrower r distribution.
• Workload 2 efficiency: ~4.8% better than Gandiva, ~250% better than SLAQ. Workload 1 shows similar efficiency across all schemes because its jobs are all 1- or 2-GPU.

Short vs. long apps (Table 5, testbed):

THEMIS induces altruistic behavior in long apps: a worse allocation raises their Tsh but their large Tid denominator keeps r from spiking, so filtering sends shorter apps into auctions more often.

Network-intensive workloads (simulator): at 100% network-intensive apps, THEMIS is ~1.24X to 1.77X better than baselines on max fairness and ~8.1% better than Gandiva on GPU time. Sharing incentive degrades most for all schemes under a heterogeneous mix (40% and 60% network-intensive).

Contention: at 2X and 4X contention (cluster halved and quartered), THEMIS is the only scheme that maintains sharing incentive; SRSF comes closest.

Robustness: with bid-value errors sampled from [−20%, +20%], max finish-time fairness changes by only 10.76%. A single lying app among 8 gains nothing while truthful apps improve; past a tipping point of X > 34% misreporting, its hidden payment jumps and it loses a large chunk of resources.

Sensitivity: fairness improves as f rises 0 → 0.8, then max fairness worsens by ~1.5X beyond f = 0.8 (at f = 1 only one app bids and is forced into poorly-placed allocations). Efficiency decreases monotonically with f; shorter leases help fairness but force more frequent checkpointing.

Systems overheads:

Limitations

• r depends on app-supplied estimates (iter_left, serial_iter_time, slowdown S); S comes from offline profiling or crude 1 / 1.1 / 1.3 constants, with error tolerance characterized only to ±20%.
• Equations 1 and 2 both assume the allocation G⃗ is binding until job completion — an assumption the round-by-round lease mechanism itself violates.
• Tid approximates contention with Navg, and Tcluster assumes linear speedup with no slowdown.
• The AGENT enumerates r over all subsets of the offered GPUs; the paper attributes its high 95th-percentile bid time to this growing search space.
• The r ≤ 1 criterion assumes admission control; without it the multi-round design only empirically achieves r ≤ 1 for most apps, formally guaranteeing min-max r.
• Gandiva's time-slicing and GPU packing are explicitly not modeled in the baseline.
• The simulator assumes loss-curve estimates are known ahead of time.
• The testbed uses Tesla K80 GPUs while the Table 1 placement microbenchmark uses P100 GPUs.
• Checkpointing to HDFS (5–10 s) plus ~35 s median container churn bounds how short leases can usefully be.

Open Problems

These are questions the paper leaves open rather than problems it enumerates:

1. Removing the admission-control assumption so that r ≤ 1 can be guaranteed rather than empirically observed, and closing the gap between min-max r and true sharing incentive.
2. Making bid construction scale, since the AGENT enumerates r over all subsets of the offered GPUs and the paper already sees this in its tail latency.
3. Reconciling the "allocation is binding until completion" assumption in the r estimator with the lease-based mechanism that repeatedly revokes it.
4. Lowering the cost of reallocation (HDFS checkpoint plus container churn), which currently sets the floor on lease duration and thus on how fast fairness can converge.