THEMIS: Fair and Efficient GPU Cluster Scheduling — Detailed Summary

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

Per-section summary organized by the paper's own headings, with paragraph-level bullets and exact quantitative results where the paper provides them. Numbers appearing only inside un-labeled figures are not reconstructed; only values the paper states in text or tables are reported.

Abstract

• Distributed ML training benefits significantly from GPUs, but significant contention ensues when many such workloads share one GPU cluster; the key question is how to fairly apportion GPUs across workloads.
• Established cluster scheduling disciplines are a poor fit because of ML workloads' unique attributes: long-running tasks needing gang-scheduling, and performance sensitivity to tasks' relative placement.
• THEMIS's GPU allocation policy enforces that ML workloads complete in a finish-time fair manner — a new notion the paper introduces.
• To capture placement sensitivity and ensure efficiency, THEMIS uses a two-level scheduling architecture where ML workloads bid on available resources offered in an auction run by a central arbiter. The auction trades fairness for efficiency in the short term while ensuring finish-time fairness in the long term.
• On a production trace, THEMIS improves fairness by more than 2.25X and is ~5% to 250% more cluster efficient than state-of-the-art schedulers.

1. Introduction

• ML success (object detection, speech recognition, machine translation) has pushed models into products; training each model is time- and resource-intensive, typically running in parallel across many GPUs.
• Consolidating GPUs into a shared cluster gives operational advantages (reduced development overheads, lower GPU maintenance costs), but there are no ML-workload-specific mechanisms for sharing a GPU cluster fairly.
• Operators report fairness is crucial, specifically sharing incentive: with N users sharing cluster C, every user's performance should be no worse than on a private cluster of size C/N. Without it, users either suffer long wait times or abandon the shared cluster for their own expensive hardware.
• Fair scheduling has been studied in Quincy, DRF, and Carbyne; these are widely used to manage GPU clusters today but are "far from effective" because they were designed for big data workloads.
• Two ML-specific characteristics break them: (i) ML jobs have long-running tasks that must be gang-scheduled; (ii) each task runs many iterations while synchronizing model updates every iteration, so jobs are placement-sensitive — co-locating a job's tasks on one machine or rack can give significant speedups — and jobs differ in placement sensitivity.
• Long-running tasks mean DRF, which equally allocates GPUs released on task completion, can arbitrarily violate SI. Even with fine-timescale release and reallocation (Tiresias), placement sensitivity means jobs with the same aggregate resources can have widely different performance, again violating SI. Heterogeneity in placement sensitivity also makes existing schemes violate Pareto efficiency and envy-freedom.
• THEMIS multiplexes a GPU cluster across ML apps, where each app is one or more related ML jobs run with different hyper-parameters to train an accurate model. Its long-term metric is finish-time fairness = ratio of running time in a shared cluster with N apps to running alone in a 1/N cluster. The goal is to minimize the maximum finish-time fairness across apps while efficiently utilizing cluster GPUs.
• Idea 1 — widen the app↔︎scheduler API via round-by-round auctions. Leases account for long-running tasks; rounds begin when leases expire. At round start the scheduler requests finish-time fairness metrics and makes all available GPUs visible to the fraction of apps currently farthest in fairness. Each such app bids for GPU subsets, with bid values reflecting the app's new (placement-sensitive) finish-time fairness under each subset. A central arbiter picks global winners maximizing aggregate improvement in the finish-time fair metric. A partial allocation auction ensures truthfulness and gives Pareto efficiency and envy-freeness by design.
• A far-from-fair app that loses a round sees its bid values naturally increase (a loser's finish-time fairness worsens), improving its odds in future rounds. The approach converges to fair allocations long-term while staying efficient and placement-sensitive short-term.
• Idea 2 — two-level scheduling design: a centralized inter-app scheduler at the bottom and a narrow API to existing hyper-parameter tuning frameworks (Hyperdrive, HyperOpt) at the top, which already apportion GPUs among an app's jobs and may terminate unpromising jobs early.
• THEMIS is implemented atop Apache YARN 3.2.0 and evaluated by replaying a large enterprise trace: at least 2.25X more fair than state-of-the-art schedulers while improving cluster efficiency by ~5% to 250%. Event-driven simulation on the same trace shows greater benefits as the fraction of network-intensive apps and cluster contention increase.

2. Motivation

2.1 Preliminaries

• An ML app is a collection of one or more ML model training jobs corresponding to a user training a model for a high-level goal (speech recognition, object detection). The user either knows the hyper-parameters (single job) or trains n closely related jobs exploring hyper-parameters such as learning rate and momentum.
• Each job's work is done by parallel tasks; at any time all of a job's tasks collectively process a mini-batch of fixed size for the job's duration. Each task processes a subset of the batch and runs multiple iterations. All jobs are assumed to use synchronous SGD.
• An app's finish time is when the best model and hyper-parameters have been identified. Along the way the app may terminate jobs early whose validation accuracy improvement is significantly worse than other jobs in the same app. For single-job apps, finish time is the time to train to a target accuracy or maximum iteration count.

2.2 Characterizing Production ML Apps

• Traces come from Microsoft. The studied GPU cluster supports over 5000 unique users; analysis is restricted to a subset containing 85 ML training apps submitted through a hyper-parameter tuning framework.
• GPU clusters are known to be heavily contended, and this holds here (Figure 1): GPU demand is bursty and average GPU demand is ~50 GPUs.
• Figure 2: ~10% of apps have 1 job; ~90% perform hyper-parameter exploration with as many as 100 jobs (median 75 jobs). The number of hyper-parameters explored also varies from a few tens to about a hundred (not plotted).
• GPU time is defined by example: an app with 2 jobs × 2 GPUs for 10 minutes gives 10 min per task, 20 min per job, 40 GPU minutes for the app.
• Figures 3–4 show the long-running nature: median app = 11.5 GPU days, median task = 3.75 GPU hours, with a significant fraction of jobs and apps more than 10X shorter and many more than 10X longer.
• ML apps are therefore heterogeneous in resource usage and job count; running times are heterogeneous but much longer than big data analytics jobs (typically a few hours). This heterogeneity challenges schedulers, and the long-running nature makes controlling app performance particularly difficult under high contention.

2.3 Our Goal

• Two operator quotes from a large Microsoft GPU cluster frame the problem:

"We were scheduling with a balanced approach ... with guidance to 'play nice'. Without firm guard rails, however, there were always individuals who would ignore the rules and dominate the capacity."

"Even with existing fair sharing schemes, we do find users frustrated with the inability to get their work done in a timely way... The frustration frequently reaches the point where groups attempt or succeed at buying their own hardware tailored to their needs."

• With long app durations, capacity-dominating users impose high waiting times on others, and some users are forced to quit the shared cluster.
• Efficient use of contended GPUs matters, but the paper argues it is perhaps equally or more important for the scheduler to allocate GPUs fairly across diverse ML apps — letting all apps execute their work "in a timely way". This requires both a new fairness metric and a new scheduler architecture and API.

3. Finish-Time Fair Allocation

3.1 Fair Sharing Concerns for ML Apps

• Central question: given R GPUs in cluster C and N ML apps, what is a fair way to divide the GPUs?
• Sharing incentive (SI), the primary design goal, formalizes the operators' "timely completion" concern: if N apps share a cluster, an app should not run slower than on a dedicated cluster with 1/N of the resources.
• Two further properties central to fairness must hold: Pareto Efficiency (PE) — no app's allocation can be improved without hurting another — and Envy-Freeness (EF) — no app should prefer another app's allocation.
• Quincy and DRF aim at SI, PE, and EF but are ineffective for ML clusters because they fail to consider long ML task durations and app placement preferences.

3.1.1 ML Task Durations

• Figure 4 shows ML tasks are very long, median roughly 3.75 hours, in stark contrast with big data analytics tasks.
• DRF provides instantaneous resource fairness: freed resources go to the task from the app with the least current share. For short analytics tasks, frequent completions approximate instantaneous fairness.
• Applying this to ML "can be disastrous": running much longer ML tasks to completion makes newly arriving jobs wait inordinately long, violating SI for late arrivals.
• Attained-service schemes (Tiresias) lease GPUs for a duration and, on expiry, give available GPUs to the job with least GPU time so far — the least attained service (LAS) policy. This avoids starving late arrivals but still violates all key fairness properties because it is placement-unaware.

3.1.2 Placement Preferences

• Users train apps across CV, NLP, and speech. These models have significantly different architectures and, more importantly, different placement preferences arising from different computation and communication needs.

Table 1 — Effect of GPU resource allocation on job throughput:

• VGG16 has a strict machine-local placement preference; Inception-v3 does not. The paper attributes this to VGG-like architectures having very large numbers of parameters, incurring greater overhead for updating gradients over the network.
• Ignoring placement affects SI (Figure 5, Instance 1): two placement-sensitive apps A1 and A2 both training VGG16, each one job with 4 tasks, cluster of two 4-GPU machines. DRF equalizes dominant resource share and gives 4 GPUs each; a valid DRF allocation spreads both apps across servers, violating SI for both, since each would do better with its own dedicated server.
• Ignoring placement affects PE and EF (Figure 5, Instance 2): A1 (Inception-v3, insensitive) and A2 (VGG16, sensitive), each one job with 4 tasks, cluster of one 4-GPU and two 2-GPU machines. Giving A1 the 4-GPU machine and spreading A2 across the 2-GPU machines violates EF (A2 prefers A1's allocation) and PE (swapping improves A2 without hurting A1).

Theorem 3.1. Existing fair schemes (DRF, LAS) ignore placement preferences and violate SI, PE, EF for ML apps.

• Summary: instantaneous schemes (DRF) fail on long task durations; least-attained-service schemes fix that but neither scheme's input encodes placement preferences, and neither metric — dominant resource share or attained service — captures them. A new placement-aware fairness metric is needed that, like LAS, does not depend on rapid task completions but operates over longer time scales.

3.2 Metric: Finish-Time Fairness

• The new metric is finish-time fairness: r = Tsh / Tid.
• Tid is the independent finish time: the app's finish time in its own exclusive 1/N share of the cluster.
• Tsh is the shared finish time in the shared cluster, encompassing slowdown due to placement and any queuing delays; the worse the placement, the higher Tsh.
• Sharing incentive is attained if r ≤ 1. A footnote notes this assumes an admission-control mechanism limiting contention — e.g., rejecting apps once aggregate GPU requests cross a threshold.
• The mechanism must estimate r for different allocations, but predicting how apps react to allocations is intractable for the scheduling engine. So the paper proposes a wider interface: apps encode preferences as a table where each column is a potential GPU allocation permutation and its estimated r.

Table 2 — Example table of bids sent from apps to the scheduler:

3.3 Mechanism: Partial Allocation Auctions

• Finish-time fairness r_i(·) for app A_i is a function of its GPU allocation G⃗_i; the policy takes these r_i(·) as input and outputs allocations G⃗_i.
• Straw-man: sort apps by reported r and allocate in that order. This reduces max r but lets apps submit false r values to boost their odds. Operators confirm apps over-request and require manual monitoring ("We also monitor the usage. If they don't use it, we reclaim it and pass it on to the next approved project"). The straw-man therefore violates strategy proofness (SP), so THEMIS uses auctions instead.

3.3.1 One-Shot Auction

• Inputs. R⃗ is the total GPU resource to auction; each element is 1 and the number of dimensions is the number of GPUs auctioned. Each app's bid is its estimated r_i for several allocations G⃗_i, each element in {0,1}, a set bit meaning that GPU is allocated to the app.
• Mechanism. To provide SP, THEMIS uses a partial allocation (PA) auction (Cole, Gkatzelis, Goel), shown to incentivize truth telling and to fit modeling subsets of indivisible goods auctioned across apps.

Pseudocode 1 — Finish-Time Fair Policy:

AUCTION({A_i}, {r_i(.)}, R⃗):
  G⃗_i,pf   = arg max Π_i 1/r_i(G⃗_i)            # proportional-fair alloc per app i
  G⃗^-i_j,pf = arg max Π_{j≠i} 1/r_j(G⃗_j)       # pf alloc per app j without app i
  c_i = ( Π_{j≠i} 1/r_j(G⃗_j,pf) ) / ( Π_{j≠i} 1/r_j(G⃗^-i_j,pf) )
  G⃗_i = c_i * G⃗_i,pf                          # final allocation per app i
  L⃗   = Σ_i (1 - c_i) * G⃗_i,pf                # aggregate leftover resource
  return {G⃗_i}, L⃗

ROUNDBYROUNDAUCTIONS({A_i}, {r_i(.)}):
  while True:
    ON RESOURCE-AVAILABLE EVENT R⃗':
      {A_i^sort}   = SORT({A_i}) on r_i^current
      {A_i^filter} = top (1-f) fraction of apps from {A^sort}
      {r_i^filter} = updated r(.) from apps in {A_i^filter}
      {G⃗_i^filter}, L⃗ = AUCTION({A_i^filter}, {r_i^filter(.)}, R⃗')
      {A_i^unfilter}  = {A_i} - {A_i^filter}
      allocate L⃗ to {A_i^unfilter} at random

• Initial allocation. PA computes an intrinsically proportionally-fair allocation G⃗_i,pf by maximizing the product of the valuation functions across apps, ensuring no app's allocation can be increased without decreasing another's — satisfying PE.
• Incentivizing truth telling. PA allocates app A_i only a fraction c_i < 1 of its proportional fair allocation and takes (1 − c_i) as a hidden payment. c_i is directly proportional to the decrease in the collective valuation of the other bidding apps in a market with and without A_i.
• The final G⃗_i is not market-clearing: unallocated GPUs L⃗ remain leftover from hidden payments, so PA is not work-conserving.

Theorem 3.2. The one-shot partial allocation auction guarantees SP, PE and EF, but does not provide SI.

• Intuition: with hidden payments leaving GPUs unallocated, PA cannot guarantee r ≤ 1 for all apps. The paper moves to multi-round auctions preserving PA's properties with the slightly weaker guarantee min max r; empirically these get r ≤ 1 for most apps even without admission control.

3.3.2 Multi-round Auctions

• Goal: r ≤ 1 for as many apps as possible while remaining work-conserving, achieved via three ideas.
• Round-by-round auctions. An allocation is binding only for a lease duration; at lease end freed GPUs are re-auctioned. This handles the online case since auctions trigger on resource-available events, covering app failures, arrivals, and cluster reconfigurations. Each round solicits updated r(·) from apps, since estimated work and placement preferences are time-varying — making the policy adaptive.
• Round-by-round filtering. Each round filters the 1 − f fraction of active apps with the greatest current r, where f ∈ (0,1) is a system-wide parameter. This restricts auctions to apps at risk of missing SI, reduces contention (hence smaller hidden payments), and keeps the auction computationally tractable.
• Over many rounds, filtering maximizes the number of apps with SI. A far-from-fair app i that loses reappears with much greater likelihood than a less-unfair app k that won: k's r improves and it exits the unfair fraction, while i's r increases due to waiting. An app losing multiple rounds eventually loses its lease on all resources and makes no progress, so its r becomes unbounded — and it will likely win the next round it participates in, since any non-zero allocation yields a huge valuation improvement.
• Effect of f. As f → 1 the policy gives a greater SI guarantee at the cost of efficiency, since it restricts the set of apps receiving GPUs. With f → 0, GPUs go to apps benefiting most from better placement, improving efficiency at the risk of violating SI.
• Leftover allocation. Leftover GPUs from hidden payments are allocated at random to apps that did not participate in that round, making the overall scheme work-conserving.

Theorem 3.3. Round-by-round auctions preserve the PE, EF and SP properties of partial auctions and maximize SI.

4. System Design

4.1 Design Requirements

• Separation of visibility and allocation. The partial allocation mechanism requires making resources visible to many apps but allocating each exclusively to one app. Existing architectures couple these concerns, necessitating a new scheduler.
• Integration with hyper-parameter tuning systems. Hyperband and Hyperdrive have their own app-schedulers deciding allocation and execution schedule for jobs within an app; THEMIS aims to integrate with them with minimal modification.
• Together these motivate a two-level semi-optimistic scheduler plus supporting abstractions.

4.2 THEMIS Scheduler Architecture

4.2.1 Need for a New Scheduling Architecture

• Two-level pessimistic schedulers (Mesos) couple visibility and allocation at single-app granularity: available resources are partitioned internally by the lower-level cross-app scheduler and offered to one app at a time. This makes round-by-round auctions infeasible, since resources must be visible to many apps but allocated to one.
• Shared-state fully optimistic schedulers (Omega) couple them at multi-app granularity: all cluster resources and state are visible to all apps, which contend concurrently via transactions. This lock-free coupling makes a global policy like finish-time fairness hard to realize and causes expensive conflict resolution when the cluster is highly contended — typical for shared GPU clusters.
• Thus the combination required by multi-round auctions — multi-app resource visibility with single-app allocation granularity — is unserved by existing architectures.

4.2.2 Two-Level Semi-Optimistic Scheduling

• The two levels are multiple app-schedulers (top, minimally modified) and a cross-app scheduler called the ARBITER (bottom) holding the scheduling logic. Every GPU has a lease deciding an app's ownership duration; on expiry the resource becomes available, and the ARBITER pools available resources and runs an auction round. An AGENT co-located with each app scheduler acts as intermediary, minimizing app-side changes.

                      +----------------------------+
                      |      THEMIS ARBITER        |
                      |  (module in YARN RM)       |
                      +----------------------------+
  VISIBILITY PHASE      |  (1) ask all apps for r estimates
                        v
        (2) offer available GPUs to worst-r fraction (1-f) of apps
                        |
                        v
   +---------+     +---------+          +---------+
   | AGENT   |     | AGENT   |   ...    | AGENT   |
   | +App1   |     | +App2   |          | +Appn   |
   +---------+     +---------+          +---------+
        |  (3) each app examines offer in parallel,
        |      replies with ONE bid = r(.) valuation table
        v
  ALLOCATION PHASE
        (4) ARBITER picks winning bids via partial allocation
            + leftover allocation; notifies each AGENT
        (5) AGENT propagates allocation to app-scheduler,
            which divides GPUs among its constituent jobs

• Phase 1 — visibility (steps 1–3): the ARBITER asks all apps for current finish-time fair metric estimates; initiates auctions and makes the same non-binding resource offer to the fraction f ∈ [0,1] of apps with worst metrics (round-by-round filtering); apps examine the offer in parallel and each AGENT replies with a single bid containing preferences for desired allocations.
• Phase 2 — allocation (steps 4–5): with all bids in hand the ARBITER picks winners per the partial allocation algorithm and leftover allocation scheme and notifies each AGENT of its winning allocation (if any); the AGENT propagates it to the app scheduler, which decides the split among constituent jobs.
• The two-phase design gives semi-optimistic concurrency control: multi-app visibility as in fully optimistic control, plus conflict-free allocations guaranteeing exclusive access as in pessimistic control.
• A narrow API from app scheduler to AGENT propagates app-specific information for bid preparation; a bid contains r(·) giving, per resource subset, the estimated finish-time fair metric under that allocation.

4.3 AGENT and AppScheduler Interaction

4.3.1 Single-Job ML Apps

• For an app with one job usable on at most job_demand_max GPUs, Equation 1 gives r for allocation G⃗ in cluster C with R_C GPUs. The allocation G⃗ is assumed binding until job completion.

Equation 1:

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)

• Tsh has two terms: the time elapsed (Tcurrent − Tstart, which also captures queuing delays and starvation time), and the remaining-iteration time (iter_left × iter_time(G⃗)).
• iter_time(G⃗) assumes synchronous SGD where iteration work parallelizes across workers; under linear speedup it is the serial iteration time divided by min(||G⃗||_1, job_demand_max).
• Linear speedup does not hold in the common case due to network overheads, captured by a slowdown penalty S(G⃗) ≥ 1 that depends on GPU placement and multiplies Tsh. S(G⃗) values are typically obtained by profiling the job offline for a few iterations.
• A footnote describes online estimation of S: start from crude estimates — single machine = 1, cross-machine = 1.1, cross-rack = 1.3 — and replace them with accurate estimates by profiling iteration times when the ARBITER allocates previously unseen placements. The multi-round nature of allocations means errors in early estimates do not have a significant effect.
• Tid is the estimated finish time in an independent 1/Navg cluster, where Navg is the average contention — the weighted average number of apps in the system during the app's lifetime. It is approximated as Tcluster × Navg, where Tcluster assumes linear speedup with all cluster resources R_C (or max app demand, whichever is lesser) and assumes no slowdown.

4.3.2 Generalizing to Multiple-Job ML Apps

• Hyper-parameter optimizers typically go from aggressive exploration to aggressive exploitation. Among the algorithms for choosing best hyper-parameters, the paper focuses on early stopping criteria, since these affect app finish time. Prior work divides automatic stopping into Successive Halving and Performance Curve Stopping.

Successive Halving:

• Starts from a total time or iteration budget B and apportions it by periodically stopping unpromising jobs. From n hyper-parameter options, each is a job with demand of 1 GPU for a fixed number of iterations I; after I iterations only the best n/2 jobs are retained, each with max demand 2 GPUs for the same I iterations, continuing until 1 job with max demand n GPUs — a total of log2(n) phases. Used in Hyperband and Google Vizier.
• The allocation G⃗ is assumed to last until app completion and total time is the sum over phases. For phase i with J = n / 2^(i−1) jobs:

Equation 2:

Tsh(i)   = max_j { T(G⃗_j) }
Tsh      = Σ_i Tsh(i)
Tcluster = B / min(R_C, app_demand_max)
Tid      = Tcluster * Navg

• The design assumes a separation of concerns in which the hyper-parameter optimizer determines the optimal GPU allocation within a phase and can estimate S(G⃗_j). With iter_left and serial_iter_time, the AGENT estimates Tsh for each job; a phase finishes when its slowest/last job finishes (max over j), and the app's shared finish time is the sum over all phases.
• The ideal finish time is the total time to execute the app on the full cluster, using budget B as aggregate work and assuming linear speedup up to app_demand_max.
• The AGENT generates r for all possible subsets {G⃗}, producing a bid table like Table 2. The AGENT ↔︎ optimizer API is Figure 7.

Figure 7 — API between AGENT and hyperparameter optimizer:

class JobInfo(int itersRemaining,
              float avgTimePerIter,
              float localitySensitivity);

// Successive Halving
List<JobInfo> getJobsInPhase(int phase, List<Int> gpuAlloc);
int getNumPhases();

// Performance Curve
List<JobInfo> getJobsRemaining(List<Int> gpuAlloc);

Performance Curve Stopping:

• A job's convergence curve is extrapolated to determine which jobs are more promising; used by Hyperdrive and Google Vizier.
• Tsh is computed by estimating, for each running job, the iteration at which it will be terminated; Tsh is determined by the job finishing last. G⃗ is again assumed to last until app completion.
• Because estimates are probabilistic (convergence iteration has an error bar), THEMIS over-estimates, using the most optimistic convergence curve that yields the maximum forecasted completion time. As the job progresses, convergence-curve estimates get more accurate, improving Tsh accuracy.
• The optimizer-side API here is simpler, only requiring a list of running jobs.

4.3.3 End-to-End Example

• Setup: a 16 GPU cluster; an app with 4 ML jobs using successive halving, running alongside 3 other apps. Serial per-iteration times are 80, 100, 100, 120 seconds; total budget 10,000 seconds of GPU time; job_demand_max = 8 GPUs; S(G⃗) = 1. A footnote notes per-iteration time depends on the hyper-parameter tuned: batch size or quantization affect it, learning rate does not.
• The optimizer forms 3 phases with 4, 2, 1 jobs, budgeting ≈8, 16, 36 iterations per phase to divide the budget evenly.
• Tid = 10000 × 4 / 16 = 2500 s.
• Computing Tsh for the 2-GPU subset when the ARBITER offers 16 GPUs:
  • Phase 1: 4 jobs serialized 2 at a time → Tsh(1) = (120 × 8) + (80 × 8) = 1600 s (two 100 s jobs run serially on one GPU; the 80 s and 120 s jobs on the other; Tsh is when the last job finishes).
  • Phase 2: which jobs get terminated is not yet known, so the median job by per-iteration time is used for future phases: 2 jobs, one per GPU, each 100 s/iteration → Tsh(2) = 100 × 16 = 1600 s.
  • Phase 3: 1 job on 2 GPUs for 36 iterations → Tsh(3) = (100 × 36)/2 = 1800 s.
  • Total Tsh = 1600 + 1600 + 1800 = 5000 s → r = 5000/2500 = 2. Placement did not matter here, so any 2 GPUs were considered.

Table 3 — Example of bids submitted by AGENT:

• If the jobs chosen for the next phase do not match the median iteration time, estimates are revised next round. E.g., if the chosen jobs have iteration times 120 and 100, the bid updates to Tsh(2) = 120 × 16 = 3200 s (each job gets one GPU, and the 120 s/iteration job finishes last in the phase) and Tsh(3) = (120 × 36)/2 = 2160 s.
• Because job_demand_max = 8, the r value for 16 GPUs does not decrease linearly from that of 8 GPUs (0.34 vs 0.5).

5. Implementation

• THEMIS is built on Apache Hadoop YARN 3.2.0, which includes Submarine, a framework for running ML training jobs on YARN. The Submarine client is modified to support submitting a group of ML training jobs as required by hyper-parameter exploration apps.
• A submitted app is managed by a Submarine Application Master (AM); the AM is changed to implement the ML app scheduler (using Hyperband) and the AGENT.
• A profiler in the AM parses TensorFlow logs and tracks iteration times and loss values for all jobs. Since allocations change over time, iteration times are used to accurately estimate the placement preference S for different GPU placements; loss values feed the Hyperband implementation for early stopping.
• The ARBITER is a separate module in the YARN Resource Manager, with gRPC-based interfaces to AGENTs carrying offers, bids, and winning allocations. The ARBITER tracks GPU leases so it can offer reclaimed GPUs as part of offers.
• All evaluated jobs are TensorFlow programs with configurable hyper-parameters. To handle runtime allocation changes, they checkpoint model parameters to HDFS every few iterations and resume from the most recent checkpoint after a change.

6. Evaluation

• THEMIS is evaluated on a 64 GPU cluster and with an event-driven simulator modeling a 256 GPU cluster. Three stated highlights:
  • Better than other schemes on finish-time fairness while also offering better cluster efficiency (Figures 9–12).
  • Benefits improve with increasing fraction of placement-sensitive apps and increasing contention, and hold even with random and strategic errors in finish-time fair metric estimation (Figures 14–18).
  • Enables a trade-off between long-term fairness and short-term placement efficiency; sensitivity analysis (Figure 19) shows f = 0.8 and a 10-minute lease give maximum fairness while using the cluster efficiently.

6.1 Experimental Setup

• Workload 1: a publicly available trace of DNN training workloads at Microsoft, scaled down using a two-week snapshot, focusing on the subset of jobs corresponding to hyper-parameter exploration triggered by Hyperdrive.
• Workload 2: uses Workload 1's app arrival times, generates jobs per app using the successive-halving pattern characteristic of Hyperband, and increases the number of tasks per job relative to Workload 1. Figure 8 shows the tasks-per-job and jobs-per-app distributions for both.
• Category mix: CV 10%, NLP 60%, speech 30%, using the same per-category model mix as Gandiva.

Table 4 — Models used in the trace:

Baselines — each is the best possible baseline for one objective:

Metrics:

• Finish-time fairness: distribution of r across apps and the max across apps; tighter distribution and lower max r indicate higher fairness.
• GPU Time: utilization efficiency. For schemes S1, S2 with GPU times G1, G2 for the same work, S1 is more efficient if G1 < G2.
• Placement Score: each allocation gets a score ≤ 1, inversely proportional to the slowdown S the app experiences. Slowdown depends on the app's properties and the network interconnects between allocated GPUs; a score of 1.0 for as many apps as possible is desirable.

6.2 Macrobenchmarks

• All baselines are evaluated on all workloads in the testbed with f = 0.8 and lease = 10 minutes, informed by Section 6.4.
• Figures 9–10: THEMIS has a narrower distribution of r values, meaning it comes closest to giving all jobs an equal sharing incentive, and gives 2.2X to 3.25X better (smaller) maximum r values than all baselines.
• Figures 11–12 compare aggregate GPU time. Workload 1 shows similar efficiency across THEMIS and baselines, because all jobs are 1- or 2-GPU jobs and almost all allocations end up efficient regardless of scheme.
• Workload 2: THEMIS betters Gandiva by ~4.8% and outperforms SLAQ by ~250%. The paper attributes this to global visibility of app placement preferences via the auction abstraction enabling globally optimal decisions, whereas Gandiva takes greedy locally optimal packing decisions.

6.2.1 Sources of Improvement

Table 5 — Details of 2 jobs to understand the benefits of THEMIS [TESTBED]:

• THEMIS offers better sharing incentive for both short and long apps and induces altruistic behavior in long apps, attributed to the choice of the r metric: under less-than-ideal allocations long apps see Tsh increase but r does not rise drastically because of a higher Tid in the denominator. Shorter apps degrade much more drastically, and round-by-round filtering of the farthest-from-fair apps makes shorter apps participate in auctions more often.
• Tiresias offers poor sharing incentive for short apps because it treats short and long apps identically, only worsening short apps' sharing incentive.
• Figure 13: THEMIS gives the best placement scores (closer to 1.0 is better) in Workload 2, with Gandiva and Optimus closest. Workload 1 has very low GPU demand per job so almost all allocations score 1 regardless of scheme. Other schemes are poor because they do not account for placement preferences; Gandiva does greedy local packing and Optimus greedy throughput scaling, neither globally optimal.

6.2.2 Effect of Contention

• Contention is induced by halving and quartering the cluster size, producing 2X and 4X contention.
• Figure 14 (Workload 1): THEMIS is the only scheme that maintains sharing incentive even in high contention. SRSF comes close because it preferentially allocates to shorter-service apps — behavior similar to THEMIS, which induces altruistic shedding of resources by longer apps and thereby gives shorter apps preference under higher contention.

6.2.3 Systems Overheads

• The 95th-percentile bid time is high because enumerating possible bids traverses a larger search space when many resources are up for auction.
• The ARBITER's high tail likewise appears when both offered resources and bidding apps are numerous, but the time is small relative to the lease time.
• Network overhead for ARBITER↔︎app communication is negligible because THEMIS uses the existing Apache YARN mechanisms.

6.3 Microbenchmarks

Placement preferences:

• Six workloads are synthetically constructed varying the percentage of network-intensive apps from 0% to 100%.
• Figure 15: sharing incentive degrades most under a heterogeneous mix of compute- and network-intensive apps (at 40% and 60%). THEMIS has max r closest to 1 across all scenarios and is the only scheme ensuring sharing incentive. With a workload of solely network-intensive apps, THEMIS performs ~1.24X to 1.77X better than existing baselines on max fairness.
• Figure 16: with only compute-intensive apps all schemes utilize the cluster equally efficiently. As the network-intensive percentage rises, THEMIS has lower GPU times for the same workload; at 100% network-intensive, THEMIS performs ~8.1% better than Gandiva, the state-of-the-art for efficiency.

Error analysis:

• Evaluates handling of errors in estimating iteration count and slowdown S. All apps are assumed equally susceptible; percentage error is sampled at random from [−X, X] per app.
• Figure 17: even at X = 20%, the change in max finish-time fairness is only 10.76%, which the paper deems not significant.

Truth-telling:

• Simulation: 64 GPUs, 8 identical apps with equivalent placement preferences; the cluster has a single 8-GPU machine and the rest are 2-GPU machines, making the 8-GPU machine the most preferred allocation. There is 1 strategically lying app and 7 truthful apps.
• In each round it joins, the lying app over-reports slowdown for staggered placement or under-reports slowdown for dense placement by X%, to raise its chance of winning the 8-GPU machine; X is varied over [0, 100].
• Figure 18: at first the lying app sees no decrease in its own completion time while truthful apps do better on average completion time, because the lying app's per-round hidden payment stays the same while the others' payments keep decreasing.
• There is a sudden tipping point at X > 34%: the lying app's hidden payment jumps and it loses a big chunk of resources to other apps. In essence, THEMIS incentivizes truth-telling.

6.4 Sensitivity Analysis

• Figure 19(a) — effect of f on max r: filtering the (1 − f) fraction helps ensure better sharing incentive. As f rises from 0 to 0.8 fairness improves; beyond f = 0.8 max fairness worsens by around a factor of 1.5X.
• Sharing incentive quality (max r) degrades at f = 1 because only a single app — the one with highest r — participates, and it is forced into sub-optimal allocations because available resources are poorly placed relative to the app's already-allocated resources.
• Smaller lease times promote better fairness, since frequently filtering apps reduces the time queued apps wait for an allocation.
• Figure 19(b) — effect of f on efficiency: efficiency decreases as f increases, because fewer apps can bid on an offer, giving the ARBITER fewer opportunities to pack jobs efficiently. Lower lease values require more frequent checkpointing (GPUs are released at lease expiry), so higher lease values are more efficient.
• These opposing effects yield the operating point f = 0.8, lease = 10 min.

7. Related Work

• ML cluster scheduling is targeted by SLAQ, Gandiva, Tiresias, and Optimus; these target different objectives and are compared against in Section 6.
• THEMIS builds on cluster scheduling disciplines and two-level schedulers. Those disciplines do not directly apply, but THEMIS borrows ideas such as resource offers from Mesos.
• Sharing incentive was outlined by DRF, but THEMIS focuses on long-term fairness via the finish-time metric.
• Tetris proposes resource-aware packing with an option to trade off for fairness, using multi-dimensional bin-packing. THEMIS inverts this: fairness first, with an option to trade off for placement-aware packing, using auctions as the mechanism.
• Earlier schemes (Carbyne, Graphene) also emulated long-term fair-allocation effects by re-allocating unused resources around occasional barriers. THEMIS differs in three ways: (i) those systems target batch analytics; (ii) they rely on instantaneous resource fairness (akin to DRF), which is placement-unaware and ignores long tasks; (iii) in the ML context there are no occasional barriers — barriers arise from parameter synchronization at every iteration. Also, resources unilaterally given up by one job may not be usable by another due to placement preferences.

8. Conclusion

• THEMIS is a fair scheduling framework for ML training workloads; existing fair allocation schemes are insufficient for the long-running tasks and placement preferences of ML workloads.
• Its answers are a new long-term fairness objective (finish-time fairness) and a two-level semi-optimistic scheduling architecture where ML apps bid on resources offered in an auction.
• Experiments show THEMIS improves both fairness and efficiency compared to state-of-the-art schedulers.

Appendix — Proofs

• Theorem 3.1. The Figure 5 / Section 3.1.2 examples show DRF violates SI, EF, and PE, and the same examples hold for Tiresias's LAS policy: under LAS the service metric (GPU) is identical for A1 and A2 in both instances and is deemed fair over time, yet Instance 1 violates SI (both VGG16 apps would prefer their own independent GPUs) and Instance 2 violates EF (A2/VGG16 prefers A1/Inception-v3's allocation) and PE (the placement-aware optimum would interchange the two allocations).
• Theorem 3.2. The valuation function r(·) for ML jobs is homogeneous: r(m * G⃗) = m * r(G⃗). Reasoning: for a job spread across a set of M machines, keeping M fixed and scaling up the GPUs allocated on those machines by a factor decreases Tsh proportionally, because slowdown S is unchanged — S is determined by the slowest network interconnect between the machines, and the larger allocation does not change M. Tid is unchanged, so r scales by the same factor. Given homogeneous valuations, PA guarantees SP, PE, and EF; PA violates SI due to hidden payments, which also make it non-work-conserving.
• Theorem 3.3. Truth-telling of r estimates in the visibility phase is ensured by the AGENT using the cached r(·) estimates from the last auction the app participated in; if an app gets leftover allocations, the AGENT updates the r estimate again from the cached r(·) table — guaranteeing SP under multi-round auctions. Per Theorem 3.2 each auction ensures PE and EF, and since every round allocates all available resources via auctions, end-to-end PE and EF hold. For SI, a fraction (1 − f) of apps is taken each round; a wise choice of f filters in all apps with r > 1 that have poor sharing incentive, and resources are auctioned only to those apps.

Cross-Cutting Empirical Take-Aways

Limitations

• The r metric relies on app-supplied estimates — iter_left, serial_iter_time, and slowdown S(G⃗). S comes from offline profiling or is bootstrapped from crude constants (1 / 1.1 / 1.3 for single-machine / cross-machine / cross-rack); error tolerance is characterized only up to ±20%.
• Equations 1 and 2 both assume the allocation G⃗ is binding until job completion when computing r — an assumption the round-by-round lease mechanism itself violates.
• Tid uses Navg, the average contention, as an approximation, and Tcluster assumes linear speedup with no slowdown.
• The AGENT must enumerate r over all possible subsets of the offered GPUs; the paper notes the 95th-percentile bid time is high precisely because this search space grows with the number of auctioned resources.
• The r ≤ 1 sharing-incentive criterion assumes an admission-control mechanism limiting aggregate GPU demand; the multi-round design only empirically achieves r ≤ 1 for most apps without it, and formally provides only min-max r.
• Gandiva's time-slicing and GPU packing are explicitly not modeled in the baseline implementation.
• The simulator assumes loss-curve estimates for jobs are known ahead of time.
• The evaluation testbed uses Tesla K80 GPUs, while the Table 1 placement microbenchmark is on P100 GPUs.
• Allocation changes require checkpointing model parameters to HDFS (5–10 s) and container churn of ~35 s at the median, bounding how short leases can usefully be.