Architecture & Measurement-Design Analysis

Tiresias: A GPU Cluster Manager for Distributed Deep Learning

Source: Gu, J.; Chowdhury, M.; Shin, K. G.; Zhu, Y.; Jeon, M.; Qian, J.; Liu, H.; Guo, C. 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI '19), Feb. 26-28, 2019, Boston, MA, pp. 485-500. URL: https://www.usenix.org/conference/nsdi19/presentation/gu Code: https://github.com/SymbioticLab/Tiresias Authors: University of Michigan Ann Arbor + Microsoft + Bytedance + UNIST + Alibaba. Reader: Direct text extraction from PDF (canonical gemini_read.py pinned to a retired model) Analyst: Vishwakarma Date: 2026-09-01

Table of Contents

1. System Architecture (the cluster manager)
2. System-Under-Test Architecture (testbed, production cluster, simulator)
3. Design-Space Diagram (axes swept, axes held fixed)
4. Algorithm & Control Flow Diagrams (2DAS, discretization, placement, profiler)
5. Quantitative Results -- Empirical Findings by Regime
6. Configuration-Regime Trade-off Tables
7. Bottlenecks & Insights Surfaced by the Measurements
8. Limitations of the Methodology
9. Note on NCCL Tuning
10. Analogy

1. System Architecture (the cluster manager)

Tiresias is a centralized GPU cluster resource manager whose entire design premise is a negative result: a distributed deep learning (DDL) job's remaining execution time cannot be predicted in production, so any scheduler that needs that number is unbuildable. Everything follows from replacing the missing prediction with two substitutes that are cheap and externally observable -- attained service (GPU-time already consumed) for scheduling, and tensor-size skew (how lopsided the job's message-size distribution is) for placement. The system has exactly three modules and one shared queue; there is no per-job model, no loss-curve reader, and no framework modification.

+------------------------------------------------------------------+
|                    Tiresias Central Master                       |
|   (1) submit job (PS_J, W_J)                                     |
|        v                                                         |
|  +--------------------+                                          |
|  | WAITQUEUE          |  <--(2b) preempt-------+                 |
|  | (all-or-nothing    |                        |                 |
|  |  gang requests)    |                        |                 |
|  +---------+----------+                        |                 |
|            | (2a) schedule                     |                 |
|            v                                   |                 |
|  +-------------------------------------+       |                 |
|  | Scheduler  (Discretized 2DAS)       |-------+                 |
|  |  - K logical priority queues        |                         |
|  |  - priority = f(W_J * t_J)          |                         |
|  |  - LAS  (no prior knowledge)        |                         |
|  |  - Gittins (duration distribution)  |                         |
|  |  - STARVELIMIT / PROMOTEKNOB        |                         |
|  +------------------+------------------+                         |
|                     | (3) allocate GPUs                          |
|                     v                                            |
|  +-------------------------------------+                         |
|  | Placement Manager                   |                         |
|  |  - compare skew S_J vs PACKLIMIT    |                         |
|  |  - S_J > PACKLIMIT -> consolidate   |                         |
|  |  - else -> defragment (spread)      |                         |
|  +------------------+------------------+                         |
|                     | (4) profile if first run                   |
|                     v                                            |
|  +-------------------------------------+                         |
|  | Profiler (central RDMA aggregator)  |                         |
|  |  - derives S_J, model size,         |                         |
|  |    iteration boundaries             |                         |
|  +------------------+------------------+                         |
+---------------------|--------------------------------------------+
        +-------------+---------------------------+
        v                                         v
+-------------------+                   +---------------------+
| GPU Cluster       |                   | Shared FS (GPFS)    |
| N servers x 4 GPU |== checkpoints ==> | 1.2 GB/s r + w      |
| ibverbs shim on   |                   | preemption state    |
| every server      |                   +---------------------+
+-------------------+
^ Fig 1: Tiresias components and the four-step job lifecycle
  (submit -> schedule/preempt -> place -> profile). The profiler runs
  only on a job's first execution; the placement decision it yields
  is then reused on every subsequent resume.

Two structural decisions dominate. First, the profiler is invoked once per job, not once per scheduling event -- a DDL job's communication volume is identical every iteration, so a handful of trial iterations characterises it for its whole lifetime, converting a per-decision measurement cost into a one-time admission cost. Second, the scheduler and placement manager are decoupled by a single scalar: the scheduler never sees skew, the placement manager never sees priority.

1.1 Where Tiresias sits in the stack

+----------------------------------------------------+
|  Users / AutoML hyperparameter sweep               |  <- job source
|  (submits (PS_J, W_J); no duration hint required)  |
+----------------------------------------------------+
|  Tiresias Central Master                           |  <- this paper
|  scheduler | placement | profiler                  |
+----------------------------------------------------+
|  TensorFlow 1.3.1 (RDMA extension), UNMODIFIED     |  <- framework
|  synchronous data parallelism, PS architecture     |
+----------------------------------------------------+
|  Tiresias ibverbs interception library             |  <- observability
|  (loadable .so on every server)                    |     insertion point
+----------------------------------------------------+
|  RDMA verbs / GPUDirect                            |  <- transport
+----------------------------------------------------+
|  100 Gbps EDR InfiniBand + 4x P100 per server      |  <- hardware
+----------------------------------------------------+
^ Fig 2: Software stack. Tiresias makes two insertions -- one above
  the framework (resource decisions) and one below it (RDMA
  observability) -- and zero inside it, which is what makes the
  design "readily deployable."

The two insertion points are the whole trick. The manager cannot ask TensorFlow what tensors it has, because the tensor-to-parameter-server mapping is a framework internal. So instead of reaching into the framework it reaches underneath and reconstructs model structure from the wire -- inference by observation rather than by instrumentation.

1.2 Job state machine

                     Submit Job
                          |
                          v
                   +--------------+     enough resources
      promote /    |   WAITING    |----------------------+
      timeout      +------+-------+                      |
        |                 | not enough                   v
        |                 v                       +--------------+
        |          +--------------+   scheduled   |   RUNNING    |
        +----------|   STARVING   |-------------->|              |
        |          +--------------+               +---+------+---+
        |                                             |      |
        +---------------- preempted ------------------+      | complete
                                                             v
                                                     +--------------+
                                                     |  COMPLETED   |
                                                     +--------------+
^ Fig 3: Job state transitions (paper Fig. 9). STARVING is not a
  failure state -- it is a timer that, on expiry, resets t_J to zero
  and re-enqueues the job at Q1. Both t_J and the waiting time
  delta_J are zeroed on promotion so a promoted job is not demoted
  immediately.

STARVING exists because Discretized 2DAS is a service-based discipline: a job that has attained a lot of service sinks to Q_K and, in an oversubscribed cluster, may never be reached again. Promotion is the safety valve, exposed as a single operator knob (PROMOTEKNOB). Setting it to infinity disables promotion and optimises purely for average JCT; smaller values trade average JCT for tail JCT.

1.3 The Discretized 2DAS queue structure

  Attained service a_J = W_J x t_J   (GPU-seconds)

  +--------+   a_J >= Q1_hi   +--------+          +--------+
  |   Q1   | ---------------> |   Q2   | -- ... ->|   QK   |
  | [0,    |    demote        | [Q1_hi,|          | [.., ) |
  |  Q1_hi)|                  |  Q2_hi)|          |   inf  |
  +---^----+                  +--------+          +--------+
      |          promote (WAITING > STARVELIMIT, or               |
      +--------- delta_J >= PROMOTEKNOB * t_J) ------------------+

  Ordering WITHIN a queue:
    LAS variant     : FIFO on job START time (not submit time)
    Gittins variant : sort by G_J descending, on every event
                      (Q_K excepted: Delta_K = inf, so Gittins
                       degenerates to FIFO there)

  Deployed: testbed K = 2, threshold 3200 GPU-s
            simulation K = 2, threshold 1 h GPU-time
^ Fig 4: Multi-Level Feedback Queue realisation of Discretized 2DAS.
  Discretization is a preemption-rate limiter, not an accuracy
  improvement: it deliberately coarsens the priority signal so jobs
  cross a boundary O(K) times instead of continuously.

The FIFO-on-start-time detail is load-bearing. Because DDL jobs are all-or-nothing, a high-priority job that cannot find W_J free GPUs is skipped so the cluster does not idle. Had within-queue ordering used submission time, that skipped job would keep displacing running jobs as soon as GPUs freed up; ordering on start time makes the skip stable.

1.4 Profiler data flow

  Server 0            Server 1            ...      Server n-1
 +-----------+       +-----------+              +-----------+
 | TF worker |       | TF PS_0   |              | TF PS_j   |
 +-----+-----+       +-----+-----+              +-----+-----+
       | ibverbs           | ibverbs                  | ibverbs
 +-----v-----+       +-----v-----+              +-----v-----+
 | intercept |       | intercept |              | intercept |
 | shim (.so)|       | shim (.so)|              | shim (.so)|
 +-----+-----+       +-----+-----+              +-----+-----+
       |                   |                          |
       +== {msg size, src, dst, timestamp, conn} =====+
                           |
                           v
               +---------------------------+
               |  Central Profiler         |
               |   group by iteration      |
               |   per-PS byte totals s_j  |
               |   skew S_J = f(max s_j)   |
               +-------------+-------------+
                    S_J  vs  PACKLIMIT
                 +-----------+-----------+
                 v                       v
          S_J > PACKLIMIT          S_J <= PACKLIMIT
         CONSOLIDATE job          SPREAD to defragment
         (min # machines)         (fill partial servers)
^ Fig 5: Profiler data flow. Note the direction of inference: the
  system observes *messages on the wire*, reconstructs *model
  structure*, and converts that structure into a binary placement
  policy. Nothing about the model is ever declared by the user.

The profiler is the paper's most transferable artifact: a loadable library intercepting RDMA ibverbs calls, working with or without GPUDirect, and extensible to TCP/IP by intercepting socket APIs instead. Because DDL iterations are byte-for-byte periodic, a few of them suffice to recover message-size distribution, model size, and iteration boundaries -- quantities that normally require framework cooperation.

2. System-Under-Test Architecture

The paper evaluates on three distinct vehicles, and keeping them apart is essential to reading the numbers: a 60-GPU physical testbed running real TensorFlow jobs, a discrete-event simulator, and a 10-week Microsoft production trace that supplies the job-arrival and job-size distributions for both.

2.1 The physical testbed (Michigan ConFlux)

+------- Testbed: 15 servers x 4 GPUs = 60 NVIDIA Tesla P100 --------+
|   Server 0            Server 1          ...        Server 14       |
| +--------------+   +--------------+            +--------------+    |
| | IBM PowerNV 8335-GTB                                        |    |
| | 2x 10-core POWER8 (8 threads/core) | 256 GB DDR4            |    |
| | 4x Tesla P100, 16 GB HBM each, NVLink intra-server          |    |
| +------+-------+   +------+-------+            +------+-------+    |
|        |                  |                           |            |
|        +==================+===========================+            |
|              100 Gbps EDR InfiniBand (Mellanox, RDMA)              |
|                              |                                     |
|                    +---------+---------+                           |
|                    | GPFS shared FS    |                           |
|                    | 1.2 GB/s r + w    |                           |
|                    | (checkpoint path) |                           |
|                    +-------------------+                           |
+--------------------------------------------------------------------+
^ Fig 6: The 60-GPU ConFlux testbed. GPFS sits on the critical path
  of every preemption -- the checkpoint/restore cost measured later
  is a function of this 1.2 GB/s figure and of the number of tensors
  the framework must serialise.

NVLink is present within a server and 100 Gbps IB between servers. That hierarchy is what makes the consolidation question meaningful: consolidating keeps a job's parameter-server traffic on the intra-server path, spreading pushes it onto InfiniBand.

2.2 The production cluster the trace comes from (Microsoft "P")

+-------------- Microsoft Project Philly cluster P ------------------+
|  2016: ~100 servers x 4 GPUs  --> 2017: + >250 servers x 8 GPUs    |
|            total GPU count grew 5x year-over-year                  |
|                                                                    |
|  Interconnect 100 Gbps RDMA (IB) | Frameworks TF / Caffe / CNTK    |
|  Manager Apache-YARN-like        | Monitoring Ganglia, per-minute  |
|  Trace window 10 weeks, Oct.-Dec. 2017, jobs running >= 1 min      |
|                                                                    |
|  Observed workload facts:                                          |
|    DDL jobs (>=2 GPU)        : 10.5x growth YoY                    |
|    Large jobs   (>8 GPU)     :  9.4x growth YoY                    |
|    Largest job               : 128 GPUs (2017) vs 32 GPUs (2016)   |
|    Average queueing delay    : 4102 s                              |
|    Model sizes               : ~100s of MB to a few GB, max 7.5 GB |
|    Job arrival intervals     : mostly < 1 h; many < 1 s (AutoML)   |
|    Cost per 8-GPU server     : ~USD 100,000                        |
+--------------------------------------------------------------------+
^ Fig 7: The production cluster whose trace drives the study. The
  4102 s average queueing delay is the problem statement; sub-second
  arrival intervals are the fingerprint of automated hyperparameter
  sweeps, which is why so many jobs are short-lived and killed early.

The $100K-per-server figure is quoted deliberately: it is the argument against solving queueing delay by buying GPUs. The 10.5x year-over-year growth in DDL job count against 5x growth in GPU count is the scissor that produces the 4102 s delay.

2.3 The three evaluation vehicles

The simulator replays actual job completion times rather than modelling them, so its numbers isolate the scheduling contribution and act as an upper bound on it. The fidelity check is honest: replaying the testbed workload in simulation gives 5.11x average improvement over YARN-CS versus 5.5x measured on hardware, and 1.50x at the 95th percentile; against SRTF it reports 0.74x average and 0.55x at the 95th percentile, and against Tiresias-G 1.01x average / 1.13x at the 95th percentile.

2.4 Workload construction

Job bins used throughout the results:

In the unscaled trace the thresholds are 8 GPUs and 4 hours, matching P's 8-GPU servers. The 63.5% concentration in Bin 1 is the single most important workload fact in the paper: two thirds of all jobs are both small and short, precisely the population that FIFO head-of-line blocking destroys.

2.5 The 10 benchmark models and their structural skew

This table is the empirical basis for the placement design. The motivating measurement (paper Fig. 3) ran four concurrent 8-worker, 8-PS jobs on eight 4-GPU servers under random versus consolidated placement -- medians of 20 and 10 runs respectively -- and found only the VGG family and AlexNet materially affected.

3. Design-Space Diagram

             DESIGN SPACE OF THE TIRESIAS EVALUATION
+------------------------------------------------------------------+
|  Axis 1: SCHEDULER (6 levels)                                    |
|    [YARN-CS]      FIFO, non-preemptive, production baseline      |
|    [Best-effort]  YARN-CS minus HOL blocking (sim only)          |
|    [Gandiva]      time-sharing (sim only)                        |
|    [SRTF]         oracle: exact remaining time                   |
|    [Tiresias-L]   Discretized 2D-LAS, zero prior knowledge       |
|    [Tiresias-G]   Discretized 2D-Gittins, duration distribution  |
|    (+ SF and SRSF appear in the motivating sim, Table 1)         |
|  Axis 2: K, NUMBER OF PRIORITY QUEUES -- [2] [3] [4]             |
|  Axis 3: QUEUE THRESHOLD / SERVICE QUANTUM                       |
|    [0.5 h] [1 h] [2 h] [4 h] GPU time (testbed: 3200 GPU-s)      |
|  Axis 4: PROMOTEKNOB -- [inf] [8] [4] [2] [1]                    |
|  Axis 5: PLACEMENT                                               |
|    [always consolidate] [random] [profile-based (Tiresias)]      |
|    (+ an ILP formulation, Appendix D, evaluated and rejected)    |
|  Axis 6: JOB BIN (reporting axis) -- [SS] [SL] [LS] [LL]         |
|                                                                  |
|  Held FIXED (no sweep):                                          |
|    - Parallelism: synchronous data parallelism only              |
|    - Aggregation architecture: parameter server only             |
|      (no all-reduce / collective path is evaluated anywhere)     |
|    - #PS per job == #workers per job                             |
|    - Framework: TensorFlow 1.3.1 + RDMA extension                |
|    - Transport: 100 Gbps InfiniBand RDMA                         |
|    - Preemption mechanism: full model checkpoint to GPFS         |
|    - Resource request: user-specified, never resized             |
|    - Model set: the 10 TF-benchmark models in Table 6            |
|    - PACKLIMIT: set by a "simple linear classifier" on job       |
|      history; its numeric value is never published               |
|    - Cluster scale: 60 GPUs (testbed); trace scale in simulation |
+------------------------------------------------------------------+
^ Fig 8: Six swept axes and the fixed frame. The most consequential
  fixed choice is the parameter-server architecture: every placement
  finding here is a statement about PS-to-worker point-to-point
  message patterns, not about collective communication.

Three absences shape how far the results generalise. No all-reduce baseline is measured -- the skew rule is derived entirely from PS traffic, where one huge tensor lands on one parameter server and creates a hotspot. The job's resource request is never modified, unlike Optimus which resizes jobs. And PACKLIMIT's value is never reported, only its determination method.

4. Algorithm & Control Flow Diagrams

4.1 The priority function (Pseudocode 1)

  PRIORITY(Job J, Distribution D):
      if D is empty:                       # information-agnostic
          R_J = - W_J * t_J                # LAS: less service = higher
      else:                                # partial information
          R_J = GITTINS_INDEX(J, D)

  GITTINS_INDEX(Job J, Distribution D):
      a_J = W_J * t_J                      # 2D attained service
                    P( S - a_J <= Delta | S > a_J )
      G_J = sup   -----------------------------------------
           Delta>0  E[ min{S - a_J, Delta} | S > a_J ]

  S ~ D is the job-duration random variable; Delta is the service
  quantum. Numerator  = probability the job finishes within the next
  quantum (the reward). Denominator = expected service it will
  actually consume (the cost). G_J is a reward-per-unit-cost ratio
  maximised over quantum size.
^ Fig 9: The 2DAS priority function. The single move that makes both
  branches "two-dimensional" is the product W_J * t_J -- GPU-seconds
  rather than seconds. Everything else is classical.

The product rather than either factor alone is justified empirically in Table 1 (Sec. 5.1): a purely spatial scheduler (smallest-first) and a purely temporal one (SRTF) both lose to the two-dimensional SRSF, which orders by remaining GPU-seconds.

4.2 The scheduler main loop (Pseudocode 2)

  START of a scheduling event (arrival / completion / resource change)
        |
        v
  (1) For every RUNNING job J: r_J = PRIORITY(J, D)
        |
        v
  (2) For every job WAITING longer than STARVELIMIT:
          reset t_J ; enqueue J into Q1          <- starvation valve
        |
        v
  (3) while cluster has available GPUs:
        for i = 1 .. K:                          <- strict queue order
             if D nonempty and i < K:
                  sort Q_i by Gittins index
             for each job J in Q_i (queue order):
                  if available GPUs >= W_J:
                       reserve W_J GPUs          <- job will run
                  else:
                       add J to preempt-set P
                       preempt J if RUNNING      <- all-or-nothing
        |
        v
  (4) For every job J not in P and not already RUNNING:
          if J was never profiled:  PROFILE(J)   <- trial iterations
          record J's start time                  <- FIFO key for LAS
          place J by comparing S_J to PACKLIMIT
        |
        v
  END
^ Fig 10: The 2DAS scheduler loop. Step (3) is where all-or-nothing
  gang semantics bite: a job that cannot get all W_J GPUs is not
  partially started, it is skipped and its resources offered to the
  next job in queue order -- keeping utilisation high at the cost of
  some priority inversion.

The loop is O(jobs) per event, plus a sort in the Gittins variant, and that sort is the direct cause of Tiresias-G's higher preemption count (297 versus 221 on the testbed): re-sorting on every event reshuffles within-queue order, and every reshuffle is a potential preemption. The LAS variant's FIFO order is stable by construction.

4.3 Placement decision flow and the rejected ILP

  Job J needs W_J workers and PS_J parameter servers
        |
        v
  Has J been profiled before?
        +-- No --> run J in a trial environment for a few iterations
        |            -> profiler aggregates per-server RDMA metadata
        |            -> compute skew S_J from per-PS byte totals s_j
        +-- Yes ----+
                    v
             S_J > PACKLIMIT ?
                /            \
             Yes              No
              v                v
   +--------------------+  +---------------------------+
   | CONSOLIDATE        |  | SPREAD to defragment      |
   | minimum # machines |  | fill partially-used       |
   | keeps the huge     |  | servers; reduces          |
   | tensor's traffic   |  | fragmentation and thus    |
   | off the network    |  | future queueing delay     |
   +--------------------+  +---------------------------+
^ Fig 11: Placement control flow. The branch is binary and the
  predicate is a single scalar comparison -- deliberately simpler
  than the Appendix-D ILP, and reported to perform *better* than it.

The rejected ILP is a clean example of optimising the wrong objective. It minimises the maximum per-machine network load:

  T_i = t_i + w_i * ( M - sum_j p_ji * s_j )
              + sum_j p_ji * s_j * ( W - w_i )

  minimize   max_{i in N}  T_i
  subject to w_i <= g_i                (free GPUs per node)
             sum_i w_i = W             (all workers placed)
             sum_i p_ji = 1  for all j (each PS on exactly one node)

with t_i node i's existing traffic, g_i its free GPUs, M the model size, s_j the bytes hosted by parameter server j, w_i the workers on node i, and p_ji a binary PS-placement indicator. The paper reports two failures: it is too slow at cluster scale, and minimising balanced network load "does not necessarily improve DL training performance" -- the objective has no term for the fact that VGG's single 392 MB tensor is qualitatively worse than ResNet152's 778 small ones at the same aggregate byte count.

4.4 Preemption sequence (what a demotion actually costs)

  Scheduler        Chief Worker      Other Workers        GPFS
      |                 |                  |                |
  (1) |-- pause ------->|-- halt --------->|                |
  (2) |                 |== checkpoint model bytes =========>|
      |<-- paused ------|  (serialise every tensor)          |
      |  ... GPUs reassigned to a higher-priority job ...    |
  (3) |-- resume ------>|-- build model -->|                |
      |                 |<== load checkpoint ================|
      |                 |-- warm up ------>|                |
      |<-- running -----|                  |                |
      v                 v                  v                v
^ Fig 12: One preemption round trip. Resume is strictly more
  expensive than pause because it has three phases (build model,
  load checkpoint, warm up) executed on *every* worker, whereas only
  the chief worker checkpoints -- which is why the paper measures
  pause and resume separately.

5. Quantitative Results -- Empirical Findings by Regime

5.1 Why two dimensions (motivating simulation, Table 1)

Normalised performance of single-dimensional schedulers with respect to SRSF (shortest-remaining-service-first = remaining time x GPUs). All schedulers are given exact durations for this comparison.

The tail is where the two-dimensional discipline earns its keep: SF is 3.45x and SRTF 1.55x worse than SRSF at the 95th percentile, versus only 1.52x and 1.03x on the average.

5.2 Testbed JCT improvements

The 27x median versus 5.5x average gap is the signature of a head-of-line-blocking fix. Averages are dominated by long jobs, whose JCT Tiresias barely changes; medians are dominated by the 63.5% of jobs in Bin 1, exactly the population previously stuck behind large jobs.

Inverting the Bin-1 ratios implies a YARN-CS Bin-1 average JCT of roughly 8,300 s: a small, short job that should finish in five minutes was taking well over two hours, almost all of it queueing. Paper Fig. 10b carries two off-axis annotations, 27.7 and 23.4, for the Bin-1 YARN-CS bars, which exceed the plotted 0-8 range.

5.3 Source of improvement I -- queueing delay (Table 4)

Read the median column first. YARN-CS's median queueing delay is 7464 s; Tiresias-L's is 13 s -- a 574x reduction. The average falls only 8.5x and the 95th percentile just 2.0x. Tiresias's average delay is worse than the SRTF oracle's (963 vs 593) but its median is better (13 vs 32): the information-agnostic policy protects the common case at least as well as the oracle and pays for it in the tail.

5.4 Source of improvement II -- placement, utilisation, makespan

Re-running the testbed workload with the profiler disabled (random placement) isolates the placement contribution: up to 1.67x training-time improvement, with fewer than 30% of DDL jobs showing limited loss. The authors state plainly that placement is the smaller effect -- "the major improvement comes from the job scheduling by avoiding HOL blocking."

Cluster-wide 10-s-averaged GPU utilisation distributions "look similar" across all four solutions. This is the important null result: Tiresias does not win by raising utilisation, it wins by reordering. The same GPU-seconds are delivered; they are simply delivered to short jobs first.

5.5 Preemption overhead

The ordering is what the design predicts. SRTF uses continuous priorities and preempts most; Tiresias-G discretizes but re-sorts within a queue on every event; Tiresias-L is FIFO-stable within a queue. Discretization buys a 30% reduction in preemption count (316 -> 221) relative to the continuous-priority oracle.

5.6 Preemption cost is governed by tensor count, not model bytes

Pause (checkpoint) times measured on the testbed, aligned against the structural data of Table 6:

  checkpoint time (s)
   30 |                                          * ResNet152
      |                              * Inception4
   20 |                    * ResNet101
      |             * Inception3
   10 |        * ResNet50
      |   * GoogleNet
    0 | * VGG11/16/19 and AlexNet all cluster here (1.3 - 2.7 s)
      +----+-----+-----+-----+-----+-----+-----+-----+---
      0   100   200   300   400   500   600   700   800
                     number of tensors
^ Fig 13: Checkpoint cost against tensor count is monotone and close
  to linear at roughly 33 ms per tensor. Against model size the same
  relationship is not merely weak, it is *inverted*: the four largest
  models (VGG19 at 548 MB down to AlexNet at 236 MB) are the four
  fastest to checkpoint.

VGG19 is 548 MB and checkpoints in 2.7 s; ResNet152 is 230 MB and checkpoints in 26.3 s -- 2.4x less data takes 9.7x longer because it is spread across 778 tensors instead of 39. At GPFS's 1.2 GB/s, VGG19's 548 MB should take about 0.46 s of pure I/O, so even the fast case is serialisation-bound, not bandwidth-bound. Resume is measured separately across 1-, 2-, and 8-worker runs and decomposes into build model / load checkpoint / warm up, reaching roughly 60-70 s at the top of the range.

5.7 Large-scale trace-driven simulation (Table 5)

All values normalised by Tiresias-L; > 1 means Tiresias-L is better.

Four readings matter. (a) Tiresias-L matches the SRTF oracle on average and median and loses only in the tail (0.84x) -- an information-agnostic policy reaching parity with perfect knowledge. (b) Best-effort captures a large share of the gain: removing HOL blocking alone moves 2.41x down to 1.50x, so roughly 40% of the improvement is "let small jobs jump the queue" and the remaining 60% is genuine 2DAS prioritisation. (c) Gandiva's time-sharing loses on all three statistics, confirming that fair sharing is not an average-JCT policy. (d) Tiresias-G is marginally better than Tiresias-L at scale -- the reverse of the testbed result, because the simulator does not charge Gittins for its extra preemptions.

5.8 Sensitivity analysis

Normalised average JCT, each variant against its own (K=2, 1 h) configuration:

The configuration surface is remarkably flat. Going from 2 queues to 4 buys 1%; going from a 1 h threshold to 4 h buys nothing. The authors explain the threshold insensitivity directly: 1 h of GPU time already covers more than 60% of all jobs, so the boundary sits past the mass of the distribution. PROMOTEKNOB is the only knob with visible effect, and it is a pure tail knob -- it cuts Tiresias-G's maximum JCT by 35% and Tiresias-L's 95th percentile by 6.4%, with essentially no dependence on the value once promotion is enabled at all.

6. Configuration-Regime Trade-off Tables

6.1 Scheduling discipline

For a deployment with no reliable duration logs, prefer Discretized 2D-LAS: it matches the oracle on average and median JCT in simulation, needs nothing from the user, and preempts 30% less than the oracle. Gittins earns its extra complexity only when the duration distribution is both available and stable -- and even then the testbed shows its extra preemptions eat the analytical advantage, leaving Tiresias-G 1.06x worse than Tiresias-L on real hardware.

6.2 Placement policy

Prefer profile-based placement: it is the only policy that spends the scarce resource -- whole free servers -- exclusively on the jobs that can convert it into speed. It beats the ILP because the ILP's objective, balanced network load, cannot represent that one 392 MB tensor and 778 small tensors damage a job differently at equal aggregate bytes.

6.3 Discretization depth and the fairness knob

Prefer K=2 and any finite PROMOTEKNOB. Larger K performs close to K=2 when preemption overhead is ignored and worse once it is charged, because K bounds how many times a job can be demoted and therefore preempted -- a genuine case of a coarser signal producing a better system. The Tiresias-G max-JCT row is equally decisive: enabling promotion at all cuts worst-case JCT by 35%, and the specific value from 8 down to 1 changes nothing further. That is a knob with a cliff at "on" and a plateau afterwards, the best possible shape for an operator-facing parameter.

7. Bottlenecks & Insights Surfaced by the Measurements

7.1 The bottleneck was never the network -- it was the queue

The decomposition is unambiguous: scheduling delivers 5.5x, placement up to 1.67x on the subset of jobs it affects. The average job in the Microsoft trace waits 4102 s before it starts computing. Every network optimisation in the DDL literature attacks the fraction of iteration time spent in aggregation; Tiresias points out that for two thirds of jobs the dominant term is time spent doing nothing at all.

The core epistemic move that fixes it is replacing an unobservable (remaining time) with an observable that is monotone in it under a heavy-tailed distribution (attained service). Under heavy tails a job that has already run a long time is expected to run even longer, which inverts the usual intuition and makes least-attained-service a good proxy for shortest-remaining-time. Tiresias-L matching SRTF at 1.00x average and median confirms the proxy is nearly lossless here.

7.2 Skew, not size, predicts placement sensitivity

              PLACEMENT SENSITIVITY vs LARGEST-TENSOR RATIO

  sensitive  |  VGG11(77.3) VGG16(74.3) VGG19(71.5) AlexNet(61.0)
             |                                                |
             |                                          PACKLIMIT
             |                                       must lie here
             |                                                |
insensitive  |  GoogleNet(14.6) ResNet50(9.2) Incep3(8.6)
             |  ResNet101(5.3) ResNet152(3.9) Incep4(3.6)
             +--------------------------------------------------
              0%        20%        40%        60%        80%
                        largest tensor / model size

  Control pair:  AlexNet   235.9 MB, ratio 61.0%  -> SENSITIVE
                 ResNet152 230.2 MB, ratio  3.9%  -> INSENSITIVE
^ Fig 14: The separating statistic. Two models of nearly identical
  total size fall on opposite sides of the sensitivity boundary, and
  the gap between the clusters (61.0% vs 14.6%) is a factor of 4.2 --
  wide enough that a single scalar threshold is robust.

The mechanism the paper gives is that message size determines susceptibility to network contention: one huge tensor cannot interleave with anything, whereas many small tensors "tend to interleave better with each other." Model size is a non-predictor; skew is the predictor.

7.3 Two structural signals pull in opposite directions

            +----------------------------------------+
            |  Tensor size distribution of the model  |
            +---------+--------------------+----------+
        few, huge tensors            many, small tensors
                      |                    |
          +-----------v------+    +--------v----------+
          | HIGH SKEW        |    | LOW SKEW          |
          | VGG*, AlexNet    |    | ResNet*, Incep*   |
          +--------+---------+    +---------+---------+
                   |                        |
   placement : CONSOLIDATE          placement : SPREAD
               (needs whole                   (fits anywhere,
                servers, raises                cheap to schedule)
                queueing delay)
   preempt   : CHEAP, 1.3 - 2.7 s   preempt   : EXPENSIVE,
                                                5.7 - 26.3 s
                   v                        v
     "hard to place, easy to move"  "easy to place, hard to move"
^ Fig 15: The skew duality. Consolidation-sensitivity and preemption
  cost are anti-correlated because both derive from the same
  tensor-count property, in opposite directions.

Tiresias exploits the first signal and measures the second, but never joins them. A scheduler that did would demote high-skew jobs freely -- they resume in 1-3 s -- and protect low-skew jobs, since ResNet152 pays 26.3 s of checkpoint on every priority change. The profiler already collects everything needed to make that join.

7.4 Discretization is cost control; utilisation is a poor metric

The usual reason to discretize a priority is tractability. Here the reason is that each priority change costs 57-62 s of GPU time, so the number of changes is itself the quantity to minimise. This reframes MLFQ from "an approximation to SRPT" into "a rate limiter on reconfiguration," and explains why the analytically stronger Gittins variant loses on real hardware: its within-queue re-sorting reintroduces exactly the churn discretization was installed to suppress. The corollary is that cluster-wide GPU utilisation -- statistically indistinguishable across all four solutions while average JCT differs by 5.5x -- would have been blind to the entire improvement. Only the distribution of completion times resolves it.

7.5 Observing the wire is enough to recover the model

The profiler recovers model size, tensor-size distribution, skew, and iteration boundaries purely from intercepted ibverbs metadata. This works because synchronous DDL is byte-for-byte periodic: the same property that makes iteration time predictable makes a few iterations a sufficient sample. It is a strong argument for placing observability below a system rather than inside it whenever the system's traffic is periodic.

8. Limitations of the Methodology

The two limitations that most constrain generalisation are the PS-only scope and the checkpoint-based preemption mechanism. The first means the placement insight is about point-to-point hotspots, not about collective algorithm behaviour. The second means every conclusion about K, discretization depth, and Gittins-versus-LAS is conditional on preemption costing tens of seconds -- as the authors say, with lightweight preemption "many classic and efficient algorithms in network flow and CPU scheduling can be applied."

9. Note on NCCL Tuning

The transferable idea here is the profiler, not the scheduler. Tiresias shows that a loadable shim intercepting ibverbs can recover a job's message-size distribution from the wire in a few iterations, with no framework cooperation, and that a single scalar summarising that distribution's skew is enough to flip a binary configuration decision correctly across ten very different models. A collective-library tuner faces the structurally identical problem: message-size distribution is the primary determinant of the right algorithm and protocol, and it is observable at the transport layer long before any model metadata is available. Two further lessons carry over. First, skew beats aggregate size -- the AlexNet/ResNet152 pair shows two workloads with the same total bytes needing opposite configurations, which argues against tuning on total message volume alone. Second, discretize the decision to limit churn: Tiresias uses K=2 queues because reconfiguration costs 57-62 s, and its Gittins variant, the analytically better policy, loses on real hardware purely because it re-evaluates too often.

10. Analogy

Tiresias is an emergency-department triage desk that has no diagnostic equipment. It cannot run a scan to learn how long any patient will take -- the DL equivalent of a loss curve is unreliable, and most patients leave before treatment finishes anyway. So the triage nurse uses the only two things visible from the waiting room. The first is how long you have already been treated, weighted by how many staff you are occupying (attained service, W_J x t_J): under a heavy-tailed case mix, the patient who has already tied up six nurses for three hours is statistically the one who will tie them up for six more, so newcomers go first. That single substitution turns a two-hour wait for a five-minute case into a thirteen-second one.

The second visible signal is the shape of the case, not its size. Two patients may need the same total volume of care, but one needs a single uninterruptible four-hour procedure while the other needs seven hundred short independent checks. The first must be given a whole operating theatre -- splitting it across rooms is catastrophic. The second can be done anywhere, in any spare corner, and should be, so the theatres stay free. Tiresias learns which kind of case it is by listening at the door rather than reading the chart: it intercepts the traffic between workers and parameter servers and reconstructs the model's tensor structure from message sizes alone. This is why AlexNet and ResNet152, at 235.9 MB and 230.2 MB, get opposite treatment -- the byte count is the same, the shape is not.

The design's final discipline is knowing that moving a patient between rooms costs a minute of everyone's time. A perfectly responsive triage policy that re-ranked the queue continuously would spend the whole shift wheeling gurneys. So the desk keeps only two priority levels and moves a patient at most once. The paper's most instructive result is that this deliberately coarse policy, which knows nothing about how long anyone will take, finishes the day's caseload as fast as an oracle that knew every duration in advance.