Tiresias: A GPU Cluster Manager for Distributed Deep Learning — Detailed Summary

Juncheng Gu, Mosharaf Chowdhury, Kang G. Shin (Univ. of Michigan, Ann Arbor); Yibo Zhu (Microsoft / Bytedance); Myeongjae Jeon (Microsoft / UNIST); Junjie Qian (Microsoft); Hongqiang Liu (Alibaba); Chuanxiong Guo (Bytedance) | NSDI '19, Feb 26–28 2019, Boston MA | ISBN 978-1-931971-49-2 | Code: github.com/SymbioticLab/Tiresias

Per-section summary following the paper's own headings. Every paragraph produces at least one bullet; all tables, equations, and figure values are preserved exactly.

Abstract

• DL training jobs stress cluster managers in three ways: unpredictable training times, an all-or-nothing execution model, and inflexible GPU sharing.
• Analysis of a large production GPU cluster shows existing big-data schedulers cause long queueing delays and low overall performance.
• Tiresias schedules and places DDL jobs to reduce job completion time (JCT), using two algorithms: Discretized 2D-Gittins index (needs the job-duration distribution) and Discretized 2D-LAS (fully information-agnostic).
• It also identifies when the consolidated-placement constraint can be relaxed and exploits that without user input.
• On the Michigan ConFlux cluster with 60 P100 GPUs plus large-scale trace-driven simulation, Tiresias improves average JCT by up to 5.5× over a YARN-based production manager, and performs comparably to solutions assuming perfect knowledge.

1. Introduction

• DL training is compute-intensive; growing datasets make distributed DL (DDL) standard, and providers build shared GPU clusters. Microsoft traces show a 10.5× year-over-year increase in DL jobs since 2016. Efficient scheduling plus smart placement are the keys to minimizing average JCT and maximizing GPU utilization.
• Limitation 1 — naïve scheduling from unpredictable training time. SJF and SRTF minimize average JCT but need (remaining) execution time, usually unknown for DL. Optimus predicts it from the repetitive iteration pattern assuming the loss curve converges — an over-simplification, since real jobs neither always have smooth loss curves nor always run to completion (§2.2).
• Consequently production managers are naïve: Microsoft's extends Apache YARN's Capacity Scheduler (built for big-data jobs) and does only non-preemptive arrival-order orchestration, so users see queueing delays up to several hours even for small jobs (Appendix A).
• Limitation 2 — over-aggressive consolidation. Managers pack a DDL job onto the minimum number of servers with enough GPUs; a 16-GPU job needs ≥4 servers on 4-GPU machines and may be blocked without four completely free servers. The assumption is that the network must be avoided because it bottlenecks and wastes GPU cycles — the paper finds this only partially valid.
• Tiresias addresses both (§3), grounded in production trace analysis and measurements of many DL models, and is deliberately transparent to users: existing jobs run with no additional configuration.
• Idea 1 — the 2DAS framework. Two instantiations: Discretized 2D-LAS and Discretized 2D-Gittins index. The Gittins index policy is optimal in the single-server case for average JCT when JCT distributions are known; classic LAS (Least-Attained Service) is widely used in information-agnostic settings such as datacenter network scheduling. Both assign time-varying priorities and schedule in priority order.
• Adaptation challenge 1 (dimensionality): priority must consider both the spatial (how many GPUs) and temporal (for how long) dimensions; one alone is insufficient. Tiresias's attained service jointly considers both.
• Adaptation challenge 2 (preemption cost): continuously changing priorities cause continuous preemption. Tolerable for network flows, but preempting a DDL job means copying data and model back and forth between main memory and GPU memory. Fix: priority discretization — priority changes only after fixed intervals.
• Selection rule: with a distribution of past execution times still valid in the near future, use Discretized 2D-Gittins index; with no prior knowledge, use Discretized 2D-LAS.
• Idea 2 — model structure loosens consolidation. Only some DL models are consolidation-sensitive, and the cause is skew in tensor size distributions. Jobs split into high-skew (sensitive) and the rest. Tiresias implements an RDMA network profiling library that infers model structure from network-level activity; exploiting DDL's iterative nature, it runs a job in a trial environment for a few iterations, then picks placement from criteria summarized in prior measurements.
• Implemented and evaluated with unmodified TensorFlow jobs on 15 servers (4 P100 GPUs with NVLink each) using traces derived from a Microsoft production cluster, plus simulation: up to 5.5× w.r.t. production solutions and 2× w.r.t. Gandiva, comparable to perfect-knowledge solutions.
• Contributions: first information-agnostic GPU-cluster resource manager and first to apply two-dimensional extension and priority discretization to DDL scheduling (also exploiting partial knowledge when available); a simple externally-observable, model-specific criterion for relaxing worker-GPU collocation; a practical, readily deployable design with significant gains.

2. Background and Motivation

2.1 Distributed Deep Learning

• Focus is data parallelism (Figure 1: 2 parameter servers, 3 workers, push/pull against a global model); each worker occupies a GPU with a local model copy, and the dataset is split equally. All jobs train synchronously, observed to converge faster than asynchronous training on GPUs. Model parallelism is noted as job-specific and much less popular.
• Periodic iterations. Each iteration does forward-backward compute on a minibatch, then model aggregation. Because compute load and communication volume are exactly the same across iterations, iteration time is highly predictable — the property the profiler exploits.
• Parameter server architecture. The PS holds the master model copy and applies workers' local results; workers pull the updated model at the start of each iteration. A job may have multiple parameter servers.
• Trial-and-error exploration. Hyperparameters must be swept over a very large search space. AutoML automates this, spawning many jobs per target model; most are killed for random errors or low improvement quality, and only a very small fraction run to completion.

2.2 Challenges

• Unpredictable job duration. Existing predictors assume smooth loss curves and completion at the training target. Figure 2 shows two Microsoft production jobs violating this: one with spikes (~251 epochs) and one with a non-decreasing curve (~26 epochs). Public models also show non-smooth curves. Termination is non-deterministic — AutoML kills most trials on quality grounds, and users set a max epoch count as fallback. Conclusion: a practical manager must not rely on accuracy/loss curves.
• Over-aggressive job consolidation. Minimizing aggregation traffic is a common optimization, so managers blindly assign all PSs and workers to the same or minimum number of servers; jobs then wait even when spare resources exist elsewhere, causing longer queueing and under-utilization.
• Experiment (Figure 3): four concurrent 8-GPU jobs on eight 4-GPU servers, each with eight parameter servers (= worker count), random vs. always-consolidate, normalized to consolidation, median of 10 runs (consolidation) / 20 runs (random). Worker locality mainly impacts the VGG family and AlexNet (dropping toward ~0.4–0.6 under random placement); ResNet50/101/152, Inception3/4, and GoogleNet are largely insensitive. Critically, neither operators nor users can tell which category a job is in.
• Time overhead of preemption. Production does not preempt at all because of the cost. Manual test: on pause the chief worker checkpoints the model to shared storage; on resume all workers load it.

Figure 4 — checkpoint (pause) time in TensorFlow, chief worker only:

• Note the inversion versus size: VGG19 is the largest model (548.1 MB) yet checkpoints in 2.7 s, while ResNet152 (230.2 MB) takes 26.3 s — cost tracks tensor count (39 vs. 778), not bytes.
• Figure 5 — resume time measured for 1-, 2-, and 8-worker configurations of each of the same ten models, decomposed into build model, load checkpoint, and warm up; y-axis spans 0–70 seconds. Every Tiresias preemption must absorb this pause-plus-resume cost.

2.3 Potential for Benefits

• Myth I: "jobs cannot be scheduled well without exact job duration." Even if individual durations are unpredictable, their distribution is learnable from history logs; the Gittins index policy (from the multi-armed bandit problem) reduces average JCT given that distribution, and LAS works with none.
• Myth II: "DDL jobs should always be consolidated." Consolidation may minimize a job's communication time, but some jobs are insensitive; the core factor is model structure (§3.3).
• Section closes with the headline: smarter placement and scheduling improve average total JCT by more than 5× on the same job set.

3. Tiresias Design

3.1 Overall Architecture

• Objectives: (1) minimize average JCT regardless of job requirements (user-centric); (2) high GPU utilization across the cluster (operator-centric); (3) starvation freedom — no job waits arbitrarily long (balances the two).
• Assumptions/constraints: (1) online job arrival — a job's PS_J and W_J are given but unknown before arrival; model/data partitioning is the framework's or user's job, and Tiresias handles only allocation and scheduling. (2) Unknown job durations — though the distribution may exist in history logs. (3) Unknown job-specific characteristics — users neither know nor control tensor-to-PS assignment or the resulting skew. (4) All-or-nothing allocation — unlike big-data tasks, all parameter servers and workers must be simultaneously active.
• Job lifecycle (Figure 6: Profiler, Scheduler, Placement, GPU Cluster; each machine has 4 GPUs, shaded = in use). On submission GPU requirements become known and the job joins the WAITQUEUE (1). The scheduler (§3.2) periodically schedules from and preempts into the WAITQUEUE (2a, 2b) on job arrival, job completion, and resource-availability changes. On first start or resume it calls placement (§3.3) to allocate GPUs (3). A first-time job is first profiled for skew in tensor distribution to decide consolidation (4).

3.2 Scheduling

• The scheduler must minimize average JCT, raise utilization, and avoid starvation. Preemption is necessary to avoid head-of-line (HOL) blocking of small/short jobs by large/long ones — a known problem of production FIFO.
• Candidates: time-sharing (a.k.a. processor-sharing, used by Gandiva), SJF, SRTF. Time-sharing targets isolation via fair sharing, not average JCT. SJF/SRTF are inapplicable because DL duration is difficult if not impossible to predict. Pure size-based heuristics (GPU count) ignore duration.

3.2.1 Why Two-Dimensional Scheduling?

• One dimension is not enough. SRTF failure mode: large jobs with short remaining time hog many GPUs, delaying many small new jobs. Smallest-first failure mode: large jobs are blocked by a stream of small jobs even when near completion.
• Simulation on the Microsoft trace compares smallest-first (SF), SRTF, and shortest-remaining-service-first (SRSF), where remaining service = remaining time × GPU count. Job durations were assumed given.

Table 1 — Normalized performance of single-dimensional schedulers w.r.t. SRSF:

• SRSF wins on average JCT and has a much smaller tail, so Tiresias adopts both dimensions.
• Caveats: SF is not time-based and does not actively minimize average JCT; SRTF is not always worse than SRSF, since large-and-short jobs can mislead SRSF and block smaller jobs. But in DL, multiple GPUs typically go to jobs with well-tuned hyperparameters that run to completion, so large-and-short jobs are rare in practice.

3.2.2 Two-Dimensional Attained Service Scheduler (2DAS)

• 2DAS generalizes LAS and the Gittins index to DL by covering spatial and temporal aspects plus all-or-nothing allocation. Priority derives from attained service, computed from GPUs used (W_J, known at arrival) and running time (t_J, continuously increasing).
• With no duration information → LAS: priority inverse to attained service. With a duration distribution → priority is the Gittins index value.
• In the Gittins branch, the ratio (Pseudocode 1, Line 11) is between (1) the probability the job completes within service quantum Δ — the possibility of reward when adding up to Δ overhead to all subsequent jobs — and (2) the expected service the job still requires.
• LAS semantics: prefers less-served jobs; all jobs start at highest priority and decay. Gittins semantics: the index expresses how likely an already-served job completes within the next quantum, so higher index = higher priority.

Pseudocode 1 — Priority function in 2DAS:

1: procedure PRIORITY(Job J, Distribution D)
2:     if D is empty then            # w/o distribution, apply LAS
3:         R_J = -W_J x t_J
4:     else                          # w/ distribution, apply Gittins index
5:         R_J = GittinsIndex(J, D)
6:     return R_J

9:  procedure GITTINS_INDEX(Job J, Distribution D)
10:     a_J = W_J x t_J
11:     G_J = sup_{Delta>0}   P(S - a_J <= Delta | S > a_J)
                             -------------------------------------
                             E[ min{S - a_J, Delta} | S > a_J ]
12:     # P = probability, E = mean, both from D; Delta = service quantum
13:     return G_J

• Worked example (Figure 7). Three jobs arrive simultaneously at a two-GPU machine as (GPUs, duration) pairs: Job 1 = (2,2), Job 2 = (1,8), Job 3 = (2,6); scheduling interval is one time unit; job index breaks ties. Only SRSF knows durations; 2D-Gittins knows the distribution; 2D-LAS knows nothing. Average JCTs: SRSF 9.3, 2D-Gittins 10, 2D-LAS 11.7 time units — more information yields better average JCT.

3.2.3 Priority Discretization

• Continuous priorities cause a cascade of preemptions and resumptions. Unlike a network flow or CPU process, preempting/resuming a DL job on GPUs is expensive (§2.2), which can make 2DAS infeasible; worse, continuous preemption degenerates 2DAS into fair sharing by time-division multiplexing, increasing average JCT.
• Fix: priority discretization based on the classic Multi-Level Feedback Queue (MLFQ).
• Structure (Figure 8): maintain K logical queues Q1...QK with priority decreasing from Q1 to QK. Queue i holds jobs with attained service W_J * t_J in [Q_i^lo, Q_i^hi), where Q_1^lo = 0, Q_K^hi = ∞, and Q_{i+1}^lo = Q_i^hi.
• Four lifecycle events set priority (Figure 9 state machine: WAITING → RUNNING → COMPLETED, RUNNING → WAITING on Preempted, WAITING → STARVING on Timeout → RUNNING on Scheduled): Arrival — a new job enters Q1 if resources are free; Activity — demoted Qi → Q(i+1) when W_J t_J crosses Q_i^hi; Starvation — priority reset after being preempted too long; Completion — removed from its queue. Jobs with similar W_J t_J stay together; dissimilar ones separate by level.
• Intra-queue ordering. Under LAS, same-queue jobs run FIFO by start time (when first scheduled), not submission time, with no HOL-blocking risk. Rationale: all-or-nothing means high-priority jobs lacking GPUs must be skipped over to keep utilization high, so FIFO on submission time would cause unnecessary preemptions.
• Under Gittins, Δ is also discretized: for jobs in Qi, Δ_i = Q_i^hi, and exhausting the quantum demotes the job; same-queue jobs order by index value. In the last queue Δ_K = ∞, so Gittins degenerates to LAS and QK runs FIFO.
• Determining K and thresholds. Optimal choice is an open problem. Instead of repeatedly solving an ILP or running a heavyweight DL mechanism, Tiresias uses the classic foreground-background queueing idea, known to work well for heavy-tailed distributions: K = 2 with one threshold. Sensitivity analysis shows K = 2 is close to larger K ignoring preemption overhead, and in practice K = 2 limits how often a job can be preempted, reducing JCT.
• Avoiding starvation. A continuous stream of small-and-short arrivals can starve jobs — same-queue jobs get skipped for lack of free GPUs, and lower-queue jobs may never get enough. Mitigation: promote a job to Q1 after WAITING longer than STARVELIMIT (Pseudocode 2, Line 6).
• Trade-off: promoting too often nullifies discretization's benefit. A single operator knob PROMOTEKNOB promotes when waiting time δ_J exceeds PROMOTEKNOB times execution time t_J:

δ_J  >=  PROMOTEKNOB * t_J

• PROMOTEKNOB = ∞ disables promotion and purely minimizes average JCT; smaller values make 2DAS more fair, trading average JCT for tail JCT. Both t_J and δ_J are reset to zero so a promoted job is not demoted immediately.

3.3 Placement

• Given job J needing PS_J parameter servers and W_J workers with enough free resources, Tiresias decides consolidate into as few machines as possible vs. distribute. Microsoft production enforces consolidation, so jobs sit in the WAITQUEUE even with GPUs free cluster-wide.
• The authors first built an ILP minimizing and balancing inter-machine network transfers (Appendix D). Takeaways: (1) it is extremely slow at cluster scale with many DDL jobs; (2) small-scale experiments show explicitly minimizing and balancing network load does not necessarily improve DL training performance.
• How important is consolidation? The reframed question — which jobs benefit — is answered by the skew of the model structure (S_J). The consolidation-sensitive models of Figure 3 have huge tensor(s) whose largest tensor dominates the model (Table 6).
• Mechanism: aggregation message sizes follow model structure. A TensorFlow model is many tensors, and each tensor is wrapped as a single communication message (footnote: other frameworks may split a tensor, but messages are still sent in clear per-tensor batches). So the DDL message-size distribution follows the tensor size distribution, which is often uneven — sometimes one huge tensor holds most parameters. Consequently aggregating larger tensors suffers network contention far more severely, while smaller tensors' transfers interleave better.

3.3.1 Profiler

• The profiler measures skew in tensor distributions across parameter servers (S_J) without user input and framework-agnostically. Skew depends on both the tensor size distribution and the framework's tensor-to-PS mapping (e.g., TensorFlow assigns round-robin); rather than forcing equal-sized tensors or assuming a mapping algorithm, skew is found automatically by profiling.
• Because each PS periodically sends its slice of the updated model to each worker (§2.1), observing that traffic reveals skew. Most production DL jobs use RDMA (InfiniBand at Microsoft) for PS–worker traffic, and — to the authors' knowledge — no RDMA-level traffic monitoring tool existed, so they built one.
• It intercepts communication APIs including low-level RDMA ibverbs on each machine to gather process-level traces; whether the job uses RDMA directly or via GPUDirect, Tiresias captures metadata such as message sizes.
• During a profiling run, information is aggregated across all relevant machines to compute S_J. Because every iteration is communication-identical, profiling need not run long, and the same predictability yields the job's iteration boundaries, model size, and skew characteristics.

3.3.2 The Placement Algorithm

• Compare S_J against threshold PACKLIMIT: if S_J > PACKLIMIT, consolidate into as few machines as possible (a high-skew job suffers under a skewed communication pattern when spread out); otherwise allocate across machines to decrease fragmentation.
• Simple but very effective, and better than the ILP design, because the ILP cannot capture consolidation's differing effect across models.
• Determining PACKLIMIT: updated periodically from job history using a simple linear classifier over a job's placement and corresponding performance as features; more sophisticated dynamic determination is future work.

3.4 Summary

Table 2 — Comparison of DL cluster managers:

• Versus YARN-CS and Gandiva, Tiresias explicitly targets average JCT; versus Optimus, it works with no or partial prior knowledge; and it places jobs from model structure captured automatically by the profiler.

Pseudocode 2 — 2DAS Scheduler:

1:  procedure 2D-LAS(Jobs J, Queues Q1...QK, Distribution D)
2:      P = {}                                # jobs to preempt
3:      for all Job J in J do
4:          if J is RUNNING then
5:              r_J = PRIORITY(J, D)
6:          if J is WAITING longer than STARVELIMIT then
7:              Reset t_J
8:              Enqueue J to Q1               # promote if STARVING
9:      while Cluster has available GPUs do
10:         for all i in [1,K] do             # prioritize across queues
11:             if D is not empty and i in [1, K-1] then
12:                 Sort GittinsIndex(Qi)
13:             for all Job J in Qi do
14:                 if Available GPUs >= W_J then
15:                     Mark W_J GPUs as unavailable
16:                 else
17:                     P = P union J
18:                     Preempt J if already RUNNING
19:     for all Job J in J and J not in P do
20:         if J is not already RUNNING then
21:             if J was not profiled before then
22:                 Profile J                          # Sec 3.3.1
23:             Store J's start time     # FIFO key for Discretized 2D-LAS
24:             Assign GPUs by comparing S_J to PACKLIMIT    # Sec 3.3

4. Implementation

• Tiresias is a centralized resource manager; scheduler, placement algorithm, and profiler live in the central master. Users submit jobs with PS_J and W_J as today; the manager handles allocation at start and reclamation at completion.
• Placement decisions rely on a network monitoring library on every server talking to the central profiler to determine each new job's skew.
• Central master. Beyond starting and completing jobs, its major function is preempting running jobs when their GPUs are reassigned. DL's iterative nature means preemption need not save all GPU/main memory — Tiresias uses the checkpoint function provided by almost every DL framework and saves only the most updated model. Sequence: pause → chief worker checkpoints to a cluster-wide shared file system → on resume the latest checkpoint is loaded before restart. The master also runs the placement algorithm and profiler.
• Distributed RDMA monitoring. The profiler is a loadable library intercepting RDMA ibverbs APIs, recording connection setup, sends, and receives on each server. Per-worker and per-PS RDMA information is aggregated centrally; from message sizes and total traffic, Tiresias resolves detailed model information including skew. Though built for RDMA, it extends easily to TCP/IP by intercepting socket APIs.

5. Evaluation

Stated highlights: on the testbed Tiresias improves average JCT by up to 5.5× and makespan by 1.21× vs. YARN-CS and performs comparably to SRTF with complete prior information (§5.2), driven by placement benefits for skewed jobs and reduced queueing delay; benefits hold in large-scale simulation of the Microsoft trace (§5.3); and Tiresias is robust to configuration parameters and workload variation (§5.4). Tiresias-G = Discretized 2D-Gittins index; Tiresias-L = Discretized 2D-LAS.

5.1 Experimental Setup

• Simulator. A discrete-time simulator replays a real Microsoft trace, modeling arrival, completion, demotion, promotion, and preemption. Stated limitation: it cannot determine job training time in a dynamic cluster, so it uses actual job completion times.
• Baselines. YARN-CS (Microsoft's Apache YARN capacity scheduler); SRTF implemented with complete information — the eventual training time that in practice cannot be known before running — and using Tiresias's placement mechanism; Gandiva's time-sharing scheduler in the large-scale simulation. Durations are unknown to both Tiresias and YARN-CS.
• All results (including Tiresias-G) are normalized by Tiresias-L unless noted; FOI > 1 means Tiresias-L is better.

Table 3 — Job bins by spatial (GPU count) and temporal (training time):

• Original trace: small ≤ 8 GPUs (Microsoft uses 8-GPU machines), short < 4 hours. Scaled-down workload: small ≤ 4 GPUs (4-GPU machines), short < 800 seconds.

5.2 Testbed Experiments

• Configuration: K = 2 with threshold 3200 GPU seconds; PROMOTEKNOB disabled.

5.2.1 JCT Improvements

• Tiresias-L achieves 5.5× improvement in average JCT w.r.t. YARN-CS (Figure 10a: per-job JCT CDFs spanning 10 s–100,000 s; Figure 10b: per-bin averages and 95th percentiles, with YARN-CS bars reaching 27.7 and 23.4). Median JCT is 27× better than YARN-CS.
• Tiresias-G is nearly identical — 1.06× average, 1.05× median — its negligible loss attributed to more preemptions (§5.2.4). Half of all jobs avoid severe queueing delays, and Tiresias is not far from SRTF.
• Bin 1 (SS) average JCT is 300 s (Tiresias-L) and 330 s (Tiresias-G), i.e. 27.6× and 25.2× better than YARN-CS. Bin 4 (LL) jobs have almost the same average JCT under Tiresias and YARN-CS — waiting time shifts from small/short jobs onto large/long ones rather than being created from nothing.

5.2.2 Cluster-Wide GPU Utilization

• Figure 11 (CDF of 10-second-averaged GPU utilization) shows overall utilization looks similar across all solutions, with small variations.
• Makespan differs:

• Tiresias-L's makespan is 1.21× smaller than YARN-CS.

5.2.3 Sources of Improvements

Table 4 — Queueing delays for DDL jobs:

• Average queueing delay falls from over 8000 s to around 1000 s, and half of jobs are delayed ≤ 13 s (Tiresias-L) or ≤ 39 s (Tiresias-G) — negligible versus YARN-CS's median. Tiresias's average delay exceeds SRTF's, but smaller jobs see similar or shorter delays.
• Faster training (placement contribution). Rerunning Tiresias-L without the profiler (random placement) and taking the ratio of random-placement training time to Tiresias-L training time (single-GPU jobs excluded, Figure 12, x-axis 0.8–1.8) gives up to 1.67× improvement w.r.t. random placement, because sensitive jobs are identified and packed onto a minimal machine count. Fewer than 30% of DDL jobs experience limited performance loss.
• Because of the highly skewed job distribution and model variety, the major improvement comes from scheduling — avoiding HOL blocking of small/short jobs by large/long ones — with placement the smaller secondary contributor.

5.2.4 Overheads

• The major overhead is preemption. Two events trigger it under Discretized 2DAS: job arrivals/promotions, and demotions that change a job's queue.

• Tiresias-G preempts more because same-queue jobs are re-sorted by Gittins index at every event, while Tiresias-L never re-sorts under FIFO ordering. SRTF uses continuous priorities, so arriving short jobs can preempt longer-remaining jobs whenever resources are short. The exact per-preemption overhead depends on the job and cluster conditions.

5.3 Trace-Driven Simulations

• Additional baseline Best-effort = YARN-CS without HOL blocking, letting small jobs jump ahead of large jobs that lack enough available GPUs.
• Simulator fidelity (§5.3.1). Replaying the testbed workload gives results similar to the testbed: 5.11× average / 1.50× 95th-percentile improvement w.r.t. YARN-CS, 0.74× / 0.55× w.r.t. SRTF, and 1.01× / 1.13× w.r.t. Tiresias-G. Differences come from the simulator not capturing preemption overhead, placement impact, or cluster dynamics.

Table 5 — Improvements in JCT in simulation (normalized by Tiresias-L):

• Tiresias-L improves average JCT by 2.4×, 1.5×, and 2× over YARN-CS, Best-effort, and Gandiva, and cuts median JCT by 30.8× and 9× vs. YARN-CS and Best-effort — half of Microsoft's jobs would see much shorter queueing delays. Tiresias-G matches on median and is slightly better on average and 95th (0.97× / 0.85×). Tiresias performs similarly to SRTF, which uses complete knowledge; SRTF is better only at the 95th percentile (0.84×). Figure 13 plots all six JCT distributions on a log x-axis from 100 s to 10,000,000 s.

5.4 Sensitivity Analysis

Notation (K, threshold1, threshold2, ...); e.g. (2, 1h) = two queues with a 1-hour-GPU-time threshold.

Queue thresholds (§5.4.1) — Figures 14a / 15a, normalized average JCT w.r.t. (2, 1h):

• (2, 0.5h) is slightly worse for Tiresias-L; at ≥ 1 hour performance is flat, and all Δ values behave identically for Tiresias-G — because 1 hour of GPU time covers more than 60% of all jobs.

Number of queues K (§5.4.2) — Figures 14b / 15b, with settings (2, 1h), (3, 1h, 2h), (4, 1h, 2h, 4h):

• K has no significant effect: 3- and 4-queue setups improve average JCT by only 1% over 2-queue Tiresias-L.

PROMOTEKNOB (§5.4.3) — based on (2, 1h), starting at 1 and increasing by powers of 2; ∞ disables promotion, smaller values promote long-delayed jobs more often:

• For Tiresias-G, maximum JCT is cut to 0.65× by any finite PROMOTEKNOB, but the trace is otherwise insensitive to its value. For Tiresias-L the 95th JCT changes only minutely; the key reason PROMOTEKNOB matters little on this trace is its heavy-tailed nature.

6. Discussion and Future Work

• Formal analysis. Discretized 2DAS lacks formal analysis of its applicable boundaries (cluster resources, DL job requirements); such analysis would simplify configuration in practice.
• Lightweight preemption. Existing DL preemption primitives are time-consuming, which is why Tiresias uses MLFQ discretization to cut preemption count. Gandiva proposes a better mechanism, but it requires DL framework modifications and its overhead remains non-negligible. With lightweight preemption, many classic network-flow and CPU-scheduling algorithms would become applicable to DDL.
• Fine-grained job placement. The profile-based scheme only coarsely avoids network transfers; intra-server interference (e.g., on the PCIe bus) when too many workers and parameter servers are collocated is unmodeled. Suggested directions: topology-aware schemes and fine-grained placement of DL computational graphs.

7. Related Work

• Cluster managers and schedulers. Many CPU-cluster managers exist for heterogeneous or traditional ML workloads (DRF, Mesos, Borg, YARN, Firmament, Graphene, Tetrisched, Morpheus, Fuxi, SLAQ), but none handle DDL's all-or-nothing task scheduling or unpredictable duration and resource requirements on GPU clusters.
• Resource management in DDL clusters. Optimus builds a resource-performance model on the fly and dynamically adjusts allocation and placement; it is complementary — Tiresias optimizes initial placement from job characteristics while Optimus adjusts online from realtime status — but Optimus assumes predictable remaining time (§2.2). Gandiva removes HOL blocking via GPU time-sharing, but time-slicing gives limited average-JCT improvement.
• Resource management with partial or no information. Tiresias is claimed as the first DDL cluster scheduler minimizing average JCT with partial or no information. Similar ideas exist in networking and CPU scheduling, but GPU clusters bring high preemption overheads and all-or-nothing scheduling. All-or-nothing gang schedulers exist for CPU but are not information-agnostic; fair schedulers need no prior knowledge but cannot minimize average JCT. SERPT also needs only partial duration knowledge, but the Gittins index is proven better because it prioritizes a larger number of potentially shorter jobs.

8. Conclusion

• Tiresias minimizes DDL job completion times with partial or no a priori knowledge, without relying on intermediate DL algorithm state (e.g., training loss) or framework specifics (e.g., tensor-to-PS mapping).
• The key idea is the 2DAS framework with Discretized 2D-LAS (no knowledge) and Discretized 2D-Gittins index (partial knowledge); the profile-based placement scheme preserves GPU utilization without hurting job performance.
• Against YARN-CS and Gandiva, Tiresias shows significant average-JCT improvements. Acknowledgments credit the Michigan ConFlux team; funding via NSF CCF-1629397, CNS-1563095, CNS-1617773, and OAC-1531752.

Appendix A — Characteristics of the Production Cluster

• The cluster, Project Philly ("P"), is a Microsoft internal production cluster shared by several search-engine teams, run by an Apache-YARN-like manager with a website/REST API front end, supporting TensorFlow, Caffe, and CNTK.
• Scale: ~100 4-GPU servers in 2016, expanded in 2017 by more than 250 8-GPU servers — total GPU count grew 5×; servers interconnect over a 100-Gbps RDMA (InfiniBand) network.
• Traces span a 10-week period, Oct.–Dec. 2017. Ganglia collects per-minute per-server hardware statistics; jobs running under one minute (config bugs) are excluded; per-job framework logs give per-iteration time and accuracy over time; the Tiresias profiler logs every RDMA send/receive with timestamps, plus hooks intercepting framework calls such as iteration or aggregation start.
• Proprietary model details cannot be disclosed, so public models serve as proxies.
• Large and varied model sizes (Figure 16). Production models range from a few hundred MB to a few GB; the largest is 7.5 GB. Size distribution is largely independent of GPU count — users say GPU count depends more on training-data volume and job urgency than model size. Larger models mean heavier per-iteration communication and can congest even a 100 Gbps network, which is why placement policy intuitively consolidates; a footnote points to §3.3, noting performance in fact mostly depends on model structure.
• Staggering DDL job growth. Comparing Oct.–Dec. 2017 with the same ten weeks of 2016, DDL jobs (≥ 2 GPUs) grew 10.5× year over year; "large jobs" (> 8 GPUs, hence multi-server since P has 8 GPUs/server) grew 9.4×. The largest job ran on 128 GPUs in 2017 vs. 32 GPUs in 2016, a trend expected to continue with larger datasets.
• Long queueing time. DDL job count grows faster than cluster expansion, so jobs queue when overloaded: from the trace, the average queueing delay of all jobs is 4102 seconds. Brute-force GPU expansion is prohibitive — each 8-GPU server in P costs around 100K US dollars at public GPU prices — so providers seek better JCT (including queueing) under a fixed GPU budget.
• Unpredictable arrivals (Figure 18). With multiple teams submitting on demand, arrival intervals are naturally unpredictable: mostly under one hour, and many less than one second, suggesting AutoML hyperparameter sweeps.
• Varying aggregation frequency (Figures 17, 19). Communication overhead also depends on aggregation frequency, set by minibatch size, which developers choose — larger minibatches give larger learning steps that may escape local optima but risk convergence. Per-iteration time varies widely across jobs (0–600 s in Figure 17), but the distribution for large (>8 GPU) jobs closely matches all jobs, implying users do not pick minibatch size based on GPU count. Figure 19 gives job-duration CDFs (0.1–1000 hours) for all jobs and

  8-GPU jobs.

Appendix B — Characteristics of Popular DNN Models

Table 6 — Characteristics of 10 popular DNN models in TensorFlow:

• For the VGG family and AlexNet, model size is dominated by the largest single tensor (61.0%–77.3%); for the rest, tensor size distributions are far less skewed (3.6%–14.6%) — exactly the split observed in Figure 3's placement-sensitivity experiment.

Appendix C — 2D-Gittins Index Value

• Under 2D-Gittins scheduling, priorities come from the index value mapped to attained service. Figure 20 plots this mapping for the three jobs of Figure 7, where jobs have required service 4, 8, and 12, each with probability 1/3; index values span 0–0.8 over attained service 0–12.

Appendix D — ILP Formulation for DDL Placement

• Rationale: a DDL job's traffic affects every job sharing its machines or links, and existing network state affects the new job, so the objective is cluster-wide — minimize total network traffic and balance load across machines, concretely minimizing the maximal per-machine network load when placing a new job.
• Assumption: all DDL jobs have equal numbers of parameter servers and workers (common practice); changing PS count does not change the total aggregated data volume in the PS architecture.

Total traffic on N_i = existing traffic + traffic from J's workers on it + traffic from J's parameter servers on it, minus traffic between collocated PS and workers:

T_i = t_i + w_i * ( M - SUM_{j in K} p_ji * s_j )
          + SUM_{j in K} p_ji * s_j * ( W - w_i )

minimize  max_{i in N} { T_i }

(1)  for all i in N:   w_i <= g_i             # GPU resource limit per node
(2)  SUM_{i in N} w_i = W                     # all workers of J are placed
(3)  for all j in K:   SUM_{i in N} p_ji = 1  # each PS has exactly one host

• Further constraints (CPU, host memory) could be added. This formulation was rejected in favor of the skew/PACKLIMIT heuristic: it is too slow at scale and, more fundamentally, cannot capture consolidation's differing effect on different models (§3.3).

Limitations (stated or implied by the paper)

• No formal analysis of Discretized 2DAS's applicable boundaries; K, thresholds, PACKLIMIT, and PROMOTEKNOB are set empirically, and optimally choosing K and thresholds is acknowledged as an open problem.
• Preemption stays checkpoint-based and expensive — 221–297 preemptions cost 13,724–17,425 s of wall-clock overhead in one testbed run; Tiresias mitigates but does not eliminate this.
• Placement is coarse-grained (consolidate vs. distribute only) and ignores intra-server interference such as PCIe contention among collocated workers and parameter servers.
• Parameter-server architecture only; all-reduce aggregation is not evaluated, and the skew argument is framed around tensor-to-PS mapping.
• Data parallelism and synchronous training only; model parallelism is explicitly out of scope.
• The simulator cannot capture preemption overhead, placement impact, or cluster dynamics and instead replays actual completion times — hence the gap between testbed (5.5×) and simulated (5.11×) fidelity numbers.
• Scale gap: the testbed is 60 P100 GPUs on 15 machines versus production P's 100 4-GPU plus 250+ 8-GPU servers, and the 480-job workload is a scaled-down trace, not the trace itself.
• PACKLIMIT is learned by a simple linear classifier; a more sophisticated dynamic mechanism is left as future work.
• The Gittins index requires a duration distribution that remains valid in the near future; no mechanism is given for detecting distribution drift.