Architecture & Measurement-Design Analysis

Optimus: An Efficient Dynamic Resource Scheduler for Deep Learning Clusters

Source: Peng, Y.; Bao, Y.; Chen, Y.; Wu, C.; Guo, C. EuroSys '18: Thirteenth EuroSys Conference 2018, April 23-26, 2018, Porto, Portugal. ACM, New York, NY, USA, 14 pages. DOI: https://doi.org/10.1145/3190508.3190517 ISBN: 978-1-4503-5584-1/18/04 Affiliations: The University of Hong Kong (Peng, Bao, Chen, Wu); Bytedance Inc. (Guo). Reader: gemini-reader delegated in parallel; pdftotext -layout extraction of the full 14-page proceedings PDF used as the authoritative source for exact table and figure values. Analyst: Vishwakarma Date: 2026-09-01

Table of Contents

1. System Architecture (the model-driven scheduler stack)
2. System-Under-Test Architecture (parameter server jobs, testbed, simulator)
3. Design-Space Diagram (axes swept, axes held fixed)
4. Algorithm & Control-Flow Diagrams (fitting, allocation, placement, PAA)
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 model-driven scheduler stack)

Optimus is a cluster scheduler whose entire architecture is organized around one claim: a deep learning job's remaining completion time is predictable online, from the job itself, without any prior run and without any knowledge of the model internals or the hardware. Every other component exists to produce, feed, or consume that prediction. Two models are fitted per job while it runs — a convergence model that answers "how many more epochs?" and a resource-speed model that answers "how fast, at this resource configuration?" — and their quotient is the remaining-time estimate t_j that drives a greedy allocator.

This is the architectural inversion relative to Yarn/Mesos/Borg. Those schedulers accept a fixed resource request from the job owner at submission time and never revisit it. Optimus accepts only the per-task resource shape (how many cores and how much memory one worker or one parameter server needs) from the owner, and takes the counts — how many workers w_j, how many parameter servers p_j — as its own decision variable, re-decided every scheduling interval.

+---------------------------------------------------------------------+
|                     DL Cluster (7 CPU + 6 GPU servers)              |
|                                                                      |
|  +---------------------------------------------------------------+  |
|  | Kubernetes 1.7 master                                          |  |
|  |   - container orchestration, pod lifecycle, node inventory     |  |
|  |   - does NOT decide (p_j, w_j) for DL jobs                     |  |
|  +--------------------------+------------------------------------+  |
|         ^ create/delete pods |  poll: cluster info, job states       |
|         |                    v                                       |
|  +---------------------------------------------------------------+  |
|  | OPTIMUS SCHEDULER   (itself a normal Kubernetes pod)           |  |
|  |                                                                |  |
|  |  +------------------------+   +---------------------------+    |  |
|  |  | Progress Estimator     |   | Speed Estimator           |    |  |
|  |  |  (Sec 3.1)             |   |  (Sec 3.2)                |    |  |
|  |  |  online NNLS fit of    |   |  online NNLS fit of       |    |  |
|  |  |  l = 1/(b0*k+b1) + b2  |   |  f(p,w) from Eqn 3 / 4    |    |  |
|  |  |  -> Q_j = steps left   |   |  -> steps per second      |    |  |
|  |  +-----------+------------+   +-------------+-------------+    |  |
|  |              |                              |                  |  |
|  |              +--------------+---------------+                  |  |
|  |                             v                                  |  |
|  |                  t_j = Q_j / f(p_j, w_j)                       |  |
|  |                             |                                  |  |
|  |                             v                                  |  |
|  |  +---------------------------------------------------------+   |  |
|  |  | Resource Allocator  (Sec 4.1)                            |   |  |
|  |  |   minimize SUM_j t_j  s.t. cluster capacity              |   |  |
|  |  |   greedy: marginal gain per unit dominant resource       |   |  |
|  |  |   -> (p_j, w_j) for every active job j                   |   |  |
|  |  +----------------------------+----------------------------+   |  |
|  |                               v                                |  |
|  |  +---------------------------------------------------------+   |  |
|  |  | Task Placer  (Sec 4.2, Theorem 1)                        |   |  |
|  |  |   smallest server count; equal ps and equal workers      |   |  |
|  |  |   on each chosen server; smallest job placed first       |   |  |
|  |  +----------------------------+----------------------------+   |  |
|  |                               v                                |  |
|  |  +---------------------------------------------------------+   |  |
|  |  | Job Lifecycle Manager                                    |   |  |
|  |  |   checkpoint -> HDFS -> restart with new (p_j, w_j)      |   |  |
|  |  |   straggler detect + replace; data-chunk reassignment    |   |  |
|  |  +---------------------------------------------------------+   |  |
|  +---------------------------------------------------------------+  |
|         |  job state (fault-tolerant)      | training telemetry      |
|         v                                  ^                         |
|  +----------------+            +-----------+---------------------+  |
|  | etcd           |            | MXNet jobs (workers + ps pods)  |  |
|  | (K-V store of  |            |   emits (k, loss) per step and   |  |
|  |  job states)   |            |   (p, w, f(p,w)) samples;        |  |
|  +----------------+            |   PAA patch inside the MXNet ps  |  |
|                                +-----------------+----------------+  |
|                                                  v                   |
|                                +----------------------------------+  |
|                                | HDFS 2.8 (128 MB chunks, repl 2) |  |
|                                |   training data + checkpoints    |  |
|                                +----------------------------------+  |
+---------------------------------------------------------------------+
^ Fig 1: Optimus system architecture. Kubernetes retains orchestration;
  Optimus retains the resource-count decision. The two estimators are the
  only components that touch the running job's data stream, and everything
  downstream consumes a single scalar per job: t_j, the remaining time.

The control-plane placement of the two estimators is the load-bearing design choice. They sit inside the scheduler, not the framework, and consume only quantities the framework already emits — per-step training loss and observed steps-per-second. That is why the paper can claim the model "requires no knowledge about internals of the ML model and hardware configuration of the cluster," in explicit contrast to the per-operator modeling of Yan et al. [69]. The cost appears later: the loss-curve form is hard-coded to the O(1/k) shape of SGD, so any job whose curve differs (the paper names A3C, and any job with a step learning-rate schedule such as ResNet) falls outside the model.

A second structural point: Optimus never modifies the training semantics. The scheduler changes w_j, but for synchronous jobs it holds the global batch size M fixed and lets the per-worker mini-batch be m = M / w, so the model that comes out is the same model regardless of how many workers touched it. This is what makes elasticity safe, and it is also what creates the counter-intuitive result in Fig. 9(c) that adding workers to a synchronous job can slow it down.

  +--------------------------------------------------------------+
  |  What the job owner specifies   |  What Optimus decides       |
  |---------------------------------|-----------------------------|
  |  resource shape of one worker   |  number of workers   w_j    |
  |  resource shape of one ps       |  number of ps        p_j    |
  |  global batch size M            |  placement of both on nodes |
  |  convergence threshold  delta   |  when to rescale (10 min)   |
  |  sync or async training mode    |  which jobs get paused      |
  +--------------------------------------------------------------+
^ Fig 2: The interface split. The owner keeps everything that changes the
  learned model; Optimus takes everything that only changes how fast it is
  learned. The split is what allows re-allocation without owner consent.

2. System-Under-Test Architecture

2.1 The job model — parameter server, two synchronization modes

Every quantity in the resource-speed model is derived from the message pattern of the parameter server architecture, so the SUT must be described at that level.

                     +----------------------------------+
                     |  p PARAMETER SERVERS             |
                     |  model of size S split p ways    |
                     |  each holds S/p bytes            |
     +---------------+  bandwidth capacity B per ps     +--------------+
     |               |  update cost T_update for size S |              |
     |               +----+----------------+------------+              |
     |                    ^                |                           |
     |     push gradients |                | pull updated params       |
     |        (S/p bytes) |                | (S/p bytes)               |
     |                    |                v                           |
  +--+---------+   +------+-----+   +------+-----+          +---------+-+
  | worker 1   |   | worker 2   |   | worker 3   |  ...     | worker w  |
  | m*T_fwd    |   | m*T_fwd    |   | m*T_fwd    |          | m*T_fwd   |
  | + T_back   |   | + T_back   |   | + T_back   |          | + T_back  |
  +------------+   +------------+   +------------+          +-----------+
        |                |                |                       |
        +----------------+----------------+-----------------------+
                                  |
                     data partition from HDFS
                     (equal chunks, round robin)

  Per-step duration model (Eqn 2), taken over the slowest ps rho:

    T = max_rho [ m*T_forward + T_back
                  + 2 * (S/p) / (B / w'_rho)      <- push + pull, symmetric
                  + T_update * w'_rho / p          <- update at the ps
                  + delta*w + delta'*p ]           <- connection/control overhead

  where w'_rho = number of workers concurrently talking to ps rho.
^ Fig 3: The parameter server job as Optimus models it. The bandwidth
  bottleneck is asserted to be at the PARAMETER SERVER side, which is why
  the effective per-worker bandwidth is B/w'_rho and not B. Every term in
  Eqn 2 becomes one theta coefficient in Eqn 3 / Eqn 4.

Two modes are supported and modeled separately:

The theta_0*(M/w) term appearing only in the synchronous form is the entire explanation for the "more workers can be slower" phenomenon: with M held fixed, each additional worker shrinks m = M/w, and below some point the GPU is under-utilized on a mini-batch that small while theta_3*w (synchronization cost) keeps growing.

2.2 The physical testbed

+---------------------- Testbed: 13 servers total ---------------------+
|                                                                       |
|  7 x CPU SERVER                        6 x GPU SERVER                 |
|  +-------------------------+           +-------------------------+    |
|  | 2 x 8-core Intel E5-2650|           | 1 x 8-core Intel E5-1660|    |
|  | 80 GB memory            |           | 48 GB memory            |    |
|  | 2 x 300 GB HDD          |           | 2 x GeForce 1080Ti      |    |
|  |                         |           | 1 x 500 GB SSD          |    |
|  |                         |           | 1 x 4 TB HDD            |    |
|  +------------+------------+           +------------+------------+    |
|               |                                     |                 |
|               +======================+==============+                 |
|                                      |                                |
|                 +--------------------+--------------------+           |
|                 | 48-port Dell N1548  1 GbE switch        |           |
|                 +----------------------------------------+           |
|                                                                       |
|  Software:  Kubernetes 1.7  |  HDFS 2.8  |  MXNet  |  etcd            |
|  Workload:  9 DL jobs (Table 1), 5 CPU cores + 10 GB per container    |
+-----------------------------------------------------------------------+
^ Fig 4: The testbed. The interconnect is 1 GbE - not 10/25/100 GbE, not
  RDMA - and the GPUs are consumer 1080Ti. Communication is therefore the
  dominant cost in every job, which is precisely the regime in which the
  Eqn 2 communication terms (2*(S/p)/(B/w')) carry the most weight.

Three other machines produce the paper's model-fitting figures and must not be confused with the scheduling testbed: Fig. 2's per-model training times come from a single TITAN X Pascal; Fig. 5's nine loss curves from a server with one E5-1650 v4 CPU and two NVIDIA TITAN X GPUs running MXNet tutorial examples at a fixed learning rate; Fig. 12's scheduling times from one core of an Intel E5-1620 v4.

The nine workloads (Table 1 of the paper, reproduced exactly):

Fig. 2 of the paper measures these nine on a single TITAN X Pascal and reports a training-time spread from minutes (CNN-rand) to weeks (ResNet-50) — a range of roughly four orders of magnitude on a log axis. That spread is the motivating fact for size-aware scheduling: FIFO and DRF are both blind to it.

2.3 The simulator

  +--------------------------------------------------------------+
  |  TESTBED (13 servers)          |  SIMULATOR (discrete-time)  |
  |--------------------------------|-----------------------------|
  |  emits traces:                 |  replays those traces:      |
  |    - loss curve per job kind   |    - up to 16,000 nodes     |
  |    - f(p,w) per configuration  |    - up to 8,000 jobs       |
  |    - per-server capacities     |    - 100 repeats per point  |
  |    - worker/ps resource shapes |      in the error sweeps    |
  |    - model parameter sizes     |                             |
  |  6 hours per run, 3 repeats    |                             |
  +--------------------------------------------------------------+
^ Fig 5: The two-tier evaluation instrument. Every simulator input is a
  measured testbed trace, so the simulator extrapolates SCALE but not
  PHYSICS - it cannot surface a bottleneck that did not appear on the
  13-server testbed.

3. Design-Space Diagram (axes swept, axes held fixed)

+---------------------------------------------------------------------+
|                        OPTIMUS DESIGN SPACE                          |
|                                                                      |
|  Axis 1: SCHEDULER  (3 levels)                                       |
|    [Optimus]  [DRF fairness (Yarn/Mesos/Hadoop)]  [Tetris]           |
|    - both baselines re-implemented on Kubernetes                     |
|    - both given Optimus's speed + convergence estimates              |
|    - both fixed at ps:worker = 1:1                                   |
|                                                                      |
|  Axis 2: TRAINING MODE  (3 levels)                                   |
|    [random mix per job]  [all async]  [all sync]                     |
|                                                                      |
|  Axis 3: JOB ARRIVAL PROCESS  (3 levels)                             |
|    [uniform random over 0..12,000 s]                                 |
|    [Poisson, 3 arrivals per scheduling interval]                     |
|    [Google cluster trace, 7-hour window]                             |
|                                                                      |
|  Axis 4: PREDICTION ERROR INJECTED  (4 levels x 2 kinds)             |
|    error e in {0%, 15%, 30%, 45%}                                    |
|    injected into: [convergence epochs]  and  [training speed]        |
|    input becomes v*(1+e) or v*(1-e), decaying with job progress      |
|                                                                      |
|  Axis 5: SCALE (simulator only)                                      |
|    nodes:  10^3 .. 1.6x10^4      jobs: 1000, 2000, 4000, 8000        |
|                                                                      |
|  Axis 6: ABLATION TARGET  (4 levels)                                 |
|    [full Optimus]                                                    |
|    [Optimus placement + DRF/Tetris allocation]                       |
|    [Optimus allocation + DRF/Tetris placement]                       |
|    [PAA vs MXNet default parameter distribution]                     |
|                                                                      |
|  HELD FIXED (never swept):                                           |
|    scheduling interval 10 min | probe budget 5 (p,w) pairs           |
|    container 5 cores + 10 GB  | priority factor 1 (0.95 tested once) |
|    small-block cutoff 1% avg  | convergence threshold 1%-5%, unswept |
|    framework MXNet only       | interconnect 1 GbE only              |
|    elasticity = checkpoint    | loss form 1/(b0*k+b1)+b2 only        |
+---------------------------------------------------------------------+
^ Fig 6: The six swept axes and the ten held-fixed knobs. Note that the
  two knobs with the largest apparent leverage - the scheduling interval
  and the number of initial probe runs - are both FIXED, so the paper
  never reports the cost/benefit curve of its own sampling budget beyond
  the 8/16/24-sample accuracy sweep of Fig. 8.

The baselines are constructed with unusual generosity, and this matters when reading the headline numbers. Tetris has no native way to estimate a DL job's remaining time, so the authors give Tetris Optimus's own speed function and convergence estimator; DRF runs on Kubernetes' default load-balancing placement. The comparison is therefore not "model-driven vs model-free" but "model-driven allocation policy vs fairness/packing allocation policy, both fed the same model" — which makes the 62% allocation-ablation number (Sec. 5.5) the honest measure of the policy itself.

4. Algorithm & Control-Flow Diagrams

4.1 Notation

4.2 Online convergence fitting (Sec. 3.1)

  every training step k
        |
        v
  (1) COLLECT loss point (k, l)
        |
        v
  (2) OUTLIER REMOVAL
      is l within [min loss in next 5 epochs, max loss in prev 5 epochs]?
        no  --> replace l with the average of its neighbours
        yes --> keep
        |
        v
  (3) NORMALIZE: l <- l / (max raw loss seen so far)
                 so every job's curve lives in [0, 1]
        |
        v
  (4) OPTIONAL DECIMATION (when convergence needs 10^5+ steps)
      sample every few steps, or average all losses within one epoch
        |
        v
  (5) NNLS FIT (scipy nnls) of      l = 1/(b0*k + b1) + b2
      over ALL points collected so far
        |
        v
  (6) SOLVE for total steps to reach the owner's threshold delta
      -> total epochs, and Q_j = total - completed
        |
        v
  RE-FIT NEXT STEP (the fit strictly improves as data accumulates)
^ Fig 7: The convergence estimator. The 1/(b0*k+b1) form is chosen because
  SGD converges at rate O(1/k) in the number of steps - the functional form
  is a THEORETICAL prior, not a curve-family search. Nonnegativity of the
  coefficients is enforced by the solver, which is what keeps the fitted
  curve monotone and physically meaningful on extrapolation.

Fitted example from Fig. 7 of the paper (Seq2Seq): b0 = 0.21, b1 = 1.07, b2 = 0.07. Fig. 6 reports the prediction error envelope across all nine jobs as roughly -15% to +15%, tightening monotonically as training progresses.

4.3 Online speed fitting (Sec. 3.2)

  BEFORE the job runs:
  +-----------------------------------------------------------+
  | PROBE PHASE                                               |
  |   run the model on a SMALL SAMPLE of training data        |
  |   for a few steps, under several (p, w) combinations      |
  |   each probe run: tens of seconds                         |
  |   testbed default: 5 combinations                         |
  |   -> data points (p, w, f(p,w))                           |
  +---------------------------+-------------------------------+
                              v
  +-----------------------------------------------------------+
  | NNLS FIT of Eqn 3 (async) or Eqn 4 (sync) for theta's     |
  +---------------------------+-------------------------------+
                              v
  DURING the job:
  +-----------------------------------------------------------+
  | keep collecting (p, w, f(p,w)) at every realized config   |
  | re-fit -> calibrated theta's                              |
  +-----------------------------------------------------------+
^ Fig 8: Why the probe phase exists. The (p,w) pairs actually visited
  during a real run are few and correlated; a model fitted only on them
  is biased, and the bias steers allocation away from the optimum. The
  probe phase is a deliberate, bounded exploration budget spent BEFORE
  the policy starts exploiting.

Fitted coefficients (Table 2 of the paper, reproduced exactly as printed; the column labels theta_1..theta_5 correspond to the coefficients of Eqn 3 / Eqn 4 in order):

The authors read these coefficients directly as an attribution: "forward propagation, backward propagation and data transfer make up most of the training time in one step, since coefficients of these quantities are relatively large." The near-zero coefficients on the p term in both modes say that, in this testbed's regime, adding parameter servers costs almost nothing in per-step overhead — the constraint that binds is the worker side.

4.4 Resource allocation (Sec. 4.1)

The optimization problem, exactly as posed:

    minimize    SUM_{j in J}  t_j                                   (5)
    subject to  t_j = Q_j / f(p_j, w_j)              for all j      (6)
                SUM_{j in J} ( w_j*O_j^r + p_j*N_j^r ) <= C^r
                                                     for all r      (7)
                p_j in Z+,  w_j in Z+                for all j      (8)

Constraint (6) is neither linear nor convex, so (5)-(8) is a non-linear, non-convex integer program — NP-hard in general, and unsolvable by LP or convex solvers. The paper does not attempt an approximation guarantee; it substitutes a greedy heuristic driven by a marginal-gain ratio:

   gain_j = max {   ( Q_j/f(p_j,w_j)  -  Q_j/f(p_j+1, w_j) ) / N_j^D ,
                    ( Q_j/f(p_j,w_j)  -  Q_j/f(p_j, w_j+1) ) / O_j^D'  }   (9)

   term 1 = completion-time reduction from ONE MORE PARAMETER SERVER,
            per unit of its dominant resource
   term 2 = completion-time reduction from ONE MORE WORKER,
            per unit of its dominant resource
   dominant resource = the type with maximal share of cluster capacity
                       among the resources that task consumes  [DRF, ref 34]

The paper's own labelling of D and D' is internally inconsistent: the prose reads "D (D') is the dominant resource of workers (parameter servers)," but Eqn 9 pairs N_j^D (a parameter-server quantity) with the parameter-server increment and O_j^{D'} (a worker quantity) with the worker increment. Read by term semantics, D indexes the parameter-server dominant resource and D' the worker's. Nothing downstream depends on which convention is intended — both terms are gains per unit of the added task's own dominant resource.

  START of scheduling interval (every 10 minutes)
        |
        v
  (1) SEED: give EVERY active job 1 worker + 1 parameter server
      (starvation floor - no job can be allocated zero)
        |
        v
  (2) COMPUTE gain_j from Eqn 9 for every job
        |
        v
  (3) OPTIONAL DISCOUNT: if job j is at the beginning of training
      (large prediction error), multiply gain_j by a priority
      factor (e.g. 0.95) -> less resource to poorly-estimated jobs
        |
        v
  (4) SORT jobs by gain_j, descending
        |
        v
  (5) POP the job with the largest gain_j
      add ONE unit - a worker if term 2 was larger,
                     a parameter server if term 1 was larger
        |
        v
  (6) RE-COMPUTE gain_j for that job only; re-insert into the order
        |
        +---> loop back to (5)
        |
        v  exit when EITHER
  (7) some cluster resource type is exhausted
      OR all gain_j are non-positive
        |
        v
  EMIT allocation vector { (p_j, w_j) : j in J }
^ Fig 9: Marginal-gain allocation. Two properties matter. First, the exit
  on non-positive marginal gain means Optimus is deliberately NOT
  work-conserving: it will leave a machine idle rather than hand a job a
  worker that slows it down. Second, the 0.95 discount is an explicit
  uncertainty penalty - the policy trusts its model less early in a job
  and allocates accordingly.

The non-work-conserving property is the single most important behavioural difference from DRF, and Fig. 14(a) of the paper makes it visible: Optimus runs fewer concurrent tasks than DRF for most of the trace while finishing sooner.

4.5 Task placement (Sec. 4.2 and Theorem 1)

The motivating example: 3 servers, one synchronous job with 2 parameter servers and 4 workers, each server hosting at most 3 tasks, unit bandwidth at every task, unit data transferred per ps-worker pair per step.

  Placement (a)                 Placement (b)              Placement (c)  BEST
  +-------+-------+-------+     +-------+-------+---+      +---------+---------+
  |ps1 ps2| w2 w3 | w4 ...|     | ...   | ...   |...|      | ps1 w1  | ps2 w3  |
  | w1    |       |       |     |       |       |   |      | w2      | w4      |
  +-------+-------+-------+     +-------+-------+---+      +---------+---------+
   cross-server units per task:
     ps1:3  ps2:3  w1:1  w2:1  w3:2  w4:2
   step transfer time = max = 3    time = 3                 time = 2
^ Fig 10: The placement example of Fig. 10 in the paper. Transfer time is
  set by the SLOWEST task, so the objective is a min-max, and colocating a
  parameter server with workers is what shrinks the max.

Theorem 1. Given the numbers of workers and parameter servers in a synchronous training job, the optimal worker/parameter server placement principle to achieve the maximal training speed for the job, in a cluster of homogeneous servers, is to use the smallest number of servers to host the job, such that the same number of parameter servers and the same number of workers are deployed on each of these servers.

The Appendix proof decomposes the min-max objective

   max_k {  (S_j/p_j)*(w_j - w_jk) / B_j ,  (S_j/p_j)*(p_j - p_jk) / b_j  }

into two independent lexicographical min-max subproblems — one over w_jk, one over p_jk — each of whose optima is an even spread; the combination is then an optimum of the original. A separate induction argument shows a smaller number of hosting servers K yields smaller transfer time, because more tasks per node means less data crosses the inter-server network.

  PLACEMENT PROCEDURE
        |
        v
  (1) SORT servers DESCENDING by current resource availability
      (available CPU capacity, in the experiments)
        |
        v
  (2) SORT jobs ASCENDING by resource demand (smallest job first,
      to avoid starving small jobs)
        |
        v
  (3) for each job, k <- 1
        |
        v
  (4) do the first k servers have enough capacity for the whole job?
        no  --> k <- k+1, retry (k+1, k+2, ... servers)
        yes --> PLACE ps and workers EVENLY across those k servers
        |
        v
  (5) UPDATE availability on those k servers; RE-SORT the server list
        |
        +---> next job
        |
        v
  (6) jobs that cannot be placed are PAUSED and retried next interval
      (the allocator reasons over cluster-wide totals; the placer
       reasons over per-server fits, so the two can disagree)
^ Fig 11: Placement as a first-fit over a re-sorted server list. Step (6)
  is the honest admission that allocation and placement are solved
  separately: a feasible allocation is not necessarily a placeable one.

4.6 Parameter assignment algorithm — PAA (Sec. 5.3)

MXNet's default rule assigns a parameter block to one random parameter server if the block has fewer than 10^6 parameters, and slices it evenly across all parameter servers otherwise. A single global threshold cannot suit models with different layer-size distributions, and the paper identifies the resulting load imbalance as common to TensorFlow as well.

PAA minimizes three quantities simultaneously: (a) the maximal difference in parameter bytes between two parameter servers, (b) the total number of parameter update requests per step, and (c) the maximal difference in request count between two parameter servers.

  avg_size <- (total parameter size) / (number of parameter servers)
  sort parameter blocks DESCENDING by size
        |
        v
  for each block:
        |
        +-- size < 1% of avg_size ------------> assign to the ps with the
        |                                       FEWEST update requests
        |
        +-- 1% of avg_size <= size <= avg_size -> BEST FIT: assign to the ps
        |                                       with the SMALLEST remaining
        |                                       capacity that still fits
        |
        +-- size > avg_size --------------------> SLICE into partitions of
                                                 avg_size (last may be
                                                 smaller); assign each to
                                                 the ps holding the least
                                                 total parameter size
        |
        v
  on every assignment: increment that ps's request counter by 1
^ Fig 12: PAA. Three size classes, three different objectives - request
  balance for tiny blocks, byte balance for medium blocks, byte balance
  after slicing for large blocks. The design recognizes that a tiny block
  costs a REQUEST but almost no BYTES, so the two costs must be balanced
  by different rules.

4.7 Elasticity, stragglers, and data serving

  Optimus scheduler        MXNet job            HDFS
  --------------------|--------------------|-----------------
  (1) new (p_j, w_j)  |                    |
      decided --------+-> (2) CHECKPOINT   |
                      |     parameters  ---+--> saved
          <-- ack ----+                    |
  (3) tear down pods, |                    |
      create new pods +-> (4) RESTART   <--+--- loaded
                      |     from ckpt      |
  (5) REASSIGN data chunks round-robin so every worker keeps a
      similar workload after the worker count changed
  (6) STRAGGLER WATCH
      async: worker speed < 1/2 of median -> straggler
      sync : per-worker speed inferred from the ARRIVAL TIME of
             its gradients at the parameter servers, step to step
          -> replace the straggler by launching a new worker
^ Fig 13: Elastic rescaling by checkpoint-restart, plus straggler
  detection. For synchronous jobs all worker speeds are equal by
  construction, so the only observable that can expose a straggler is the
  gradient ARRIVAL TIME at the parameter server - a server-side, not
  worker-side, measurement.

The checkpoint-restart mechanism is chosen "due to its simplicity and general implementability" — it needs almost no framework modification and ports to other frameworks. Its measured price is 2.54% of makespan (Sec. 5.2 below), and the paper concedes it would be "quite large" for jobs with hundreds of tasks.

5. Quantitative Results — Empirical Findings by Regime

5.1 Headline comparison (testbed, 13 servers, mixed sync/async)

Normalized to Optimus = 1.00 (Fig. 11), with absolute values from Fig. 13:

The abstract's "139% and 63%" are these same numbers expressed as percentage improvements over DRF (2.39x -> 139% more time for DRF; 1.63x -> 63% longer makespan).

5.2 Resource-efficiency mechanism (Fig. 14)

The mechanism is stated plainly: "DRF is work-conserving and allocates as many resources to a job as possible, but more resources do not mean higher training speed." Optimus wins by allocating less and utilizing what it allocates.

5.3 Scalability (simulator)

5.4 Sensitivity to prediction error (simulator, 100 repeats per point)

Errors injected as v*(1+e) or v*(1-e) at job start, decaying with progress; e swept over 0, 15, 30, 45%.

Additional exact findings:

• With 20% convergence error and 10% speed error, the performance gap versus zero-error is about 15%.
• Speed error hurts more than convergence error per unit of error — which is fortunate, because speed is the quantity Optimus estimates better (≈10% error) than convergence (≈20% error).
• Both curves rise with diminishing slope: the marginal cost of additional estimation error falls off.
• Setting the priority factor to 0.95 (rather than 1) reduces average JCT by 2.66% and makespan by 1.88%.

Speed-model sample efficiency (Fig. 8), for a ResNet-50 job in a 40-container cluster where 780 distinct (p,w) pairs exist:

5.5 Ablations — where the gain actually comes from

Resource allocation (Fig. 18: Optimus placement held constant, allocation policy swapped):

"the average completion time and makespan are reduced by 62% and 31% respectively when using Optimus, as compared to the fairness scheduler."

Task placement (Fig. 19: Optimus allocation held constant, placement policy swapped):

"our algorithm reduces average completion time and makespan by about 10% compared to Tetris and 15% compared to DRF."

The paper's own summary attributes the three mechanisms as 62% (allocation) / 17% (placement) / 20% (PS load balancing).

5.6 Parameter-server load balancing (PAA)

ResNet-50, 25 million parameters organized into 157 parameter blocks:

PAA reaches the theoretical minimum on request count — 157 requests for 157 blocks means no block is ever split, so no extra request is manufactured — while simultaneously driving the byte imbalance from 3.6 M down to 0.1 M and the request imbalance from 43 down to 1.

Training-speed effect (ResNet-50 on ILSVRC2012-ImageNet, synchronous, 10 workers fixed, p varied 4 to 20, Fig. 20; and 10 workers with 10 parameter servers across four models, Fig. 21):

5.7 Workload sensitivity

Training mode (Fig. 16), normalized to Optimus:

Optimus's advantage is larger under synchronous training, and the paper gives the mechanism: synchronous workers all hold the most recent parameters, so convergence is more stable and convergence-estimation error is smaller; and all worker speeds are identical, so speed-estimation error is smaller too. Optimus's gain is a direct function of how predictable the job is.

Arrival process (Fig. 17), normalized to Optimus:

The Google trace produces the larger gain, attributed to arrival spikes: Optimus absorbs bursts by shrinking the allocations of already-running jobs, whereas a static-allocation scheduler can only queue.

6. Configuration-Regime Trade-off Tables

6.1 Allocation policy

6.2 Placement policy

6.3 Synchronous vs asynchronous, as seen by the scheduler

6.4 Parameter distribution policy

6.5 Estimation budget vs estimation accuracy

The Bayesian-optimization rejection is worth stating precisely because it is a design decision, not an oversight: BO (FABOLAS, BOAT, CherryPick) finds a good configuration for one job, but Optimus needs a closed-form f(p,w) it can differentiate-by-increment across all concurrent jobs simultaneously to compute Eqn 9. A black-box optimizer gives you an argmax; a parametric model gives you a gradient you can compare between jobs.

7. Bottlenecks & Insights Surfaced by the Measurements

7.1 More resources can make a job slower — and no fair scheduler knows it

Fig. 4 of the paper is the motivating measurement: ResNet-50 on ImageNet, synchronous, containers of 5 CPU cores + 10 GB.

• Fixing the total at 20 containers, maximum speed occurs at 8 workers + 12 parameter servers — not at any balanced split, and not at the maximum worker count.
• Fixing ps:workers = 1:1 and scaling both up, "increasing resources do not lead to linear training speed improvement, and can even slow down model training."

Both baselines are pinned at ps:worker = 1:1, the common practice Optimus argues against. The 8:12 optimum is not a small perturbation of 1:1 — it is a 50% surplus of parameter servers over workers, following directly from Eqn 2: the bottleneck sits at the parameter server side, so relieving it buys more than adding compute.

7.2 Work-conservation is an anti-pattern for DL clusters

DRF runs more tasks and finishes later. Fig. 14 separates the two things that "utilization" usually conflates: allocated capacity and used capacity. DRF wins on the first and loses on the second, because Optimus refuses any allocation whose marginal gain is non-positive. The generalizable insight: in any system where a task's performance curve is non-monotone in resources, greedily filling the cluster is a pessimization, and the only defence is knowing the curve.

7.3 The estimator's accuracy is worth far less than one would expect

The sensitivity sweep is the paper's most useful negative result. At 20% convergence error and 10% speed error — roughly the accuracy Optimus actually achieves — the gap to a perfect oracle is only about 15%, and the curves flatten as error grows. The paper says so outright: "Further improvement of estimation accuracy will not increase Optimus's performance much (15%)." The reason is that the ranking the estimator induces matters more than its absolute values — the greedy allocator only ever compares gain_j across jobs, and a uniformly biased estimator produces the same ranking as an unbiased one.

7.4 Speed is predictable; convergence is not

f(p,w) reaches ≈10% error from ~10 probe samples; convergence-epoch prediction sits at ≈20% with a ±15% envelope across the job's lifetime (Fig. 6). The asymmetry is structural: speed is a property of the system, a smooth function of counts with a physically-derived form and cheap i.i.d. samples, while convergence is a property of the optimization problem, extrapolated from a one-sided non-stationary curve with no repeatable sampling. Hence the design leans on the quantity it can measure and hedges the one it cannot, via the 0.95 priority discount for early-stage jobs.

7.5 An imbalance bug in the framework was worth 20% of the total gain

PAA fixes MXNet's parameter-distribution heuristic and accounts for about 20% of Optimus's improvement — a third as much as the entire allocation algorithm. The root cause is a single hard-coded global threshold (10^6 parameters) applied across models whose layer-size distributions differ by orders of magnitude; the paper notes the same class of problem in TensorFlow. The architectural lesson is that a global constant chosen for a "typical" workload becomes a load-imbalance generator the moment the workload distribution widens, and that a scheduler's own optimality is capped by the imbalance of the layer below it.

7.6 Predictability, not just performance, is a scheduling resource

Optimus beats DRF by 2.29x under all-synchronous training and 1.97x under all-async (1.91x vs 1.64x against Tetris), and the delta is entirely explained by estimation error being smaller in synchronous mode. A model-driven scheduler's advantage is proportional to how legible the workload is — which means the workloads most in need of good scheduling (irregular, straggler-prone, async) are the ones where the approach helps least.

7.7 Allocation and placement are solved separately, and can disagree

The allocator reasons over cluster-wide capacity totals (constraint 7); the placer reasons over per-server fits. The paper concedes that "the number of jobs the servers can accommodate might be smaller than the number of jobs we allocate resource to," and pauses the leftovers until the next interval. This is a classic relaxation-vs-realization gap absorbed by a delay: at 10-minute intervals the delay is cheap; at second-scale intervals it would not be.

8. Limitations of the Methodology

The most consequential limitation is the coupling of the whole design to the parameter server architecture. Eqn 2 — the source of every theta — is a literal transcription of the PS message pattern: push S/p bytes, update at the server, pull S/p bytes back, bottleneck asserted at the server side. A job using allreduce has no p at all, so the action space (p, w) collapses to (w), Theorem 1's ps/worker-balance clause becomes vacuous, and PAA has nothing to balance. Optimus is a scheduler for the specific architecture that dominated 2018 and that allreduce frameworks displaced shortly afterwards. The second is the 1 GbE testbed: communication is expensive enough there that adding parameter servers is nearly always profitable (Table 2's near-zero p coefficients), which is exactly the regime in which the (p, w) decision has the most leverage. On a fabric where communication is cheap, the speed surface flattens, gain_j differences shrink, and the marginal-gain ranking has less to rank.

9. Note on NCCL Tuning

The transferable mechanism here is the probe-then-fit-then-rank structure, not the scheduler. Optimus does not search its configuration space — 780 valid (p, w) pairs exist for one ResNet-50 job — it instead assumes a parametric form derived from the communication pattern, spends a bounded budget of about ten short probe runs to fit the coefficients by non-negative least squares, and then uses closed-form finite differences of that fitted surface to rank candidate moves. Its measured payoff curve is the useful part: under 10% speed-prediction error from roughly ten samples, with clearly diminishing returns past that, and an end-to-end penalty of only ~15% even when the estimates are off by 10-20%. That combination argues that for choosing among discrete communication configurations, a small physically-motivated cost model fitted from a handful of timed runs may capture most of the available gain, and that the ranking it induces matters more than its absolute accuracy — a much cheaper posture than exhaustive sweeps, and one the paper explicitly prefers over black-box Bayesian optimization because a parametric surface can be compared across simultaneous decisions while an argmax cannot.

10. Analogy

Optimus is a hospital operating-theatre manager who reads the patient charts.

The conventional manager — DRF, Yarn, Borg — works from the booking sheet alone. A surgeon requests two theatres and four nurses at admission, and gets exactly that for the entire stay, whether the operation takes twenty minutes or two weeks. When a theatre frees up at 3 a.m. nobody is moved into it, because the bookings were fixed at admission. And when the manager does allocate, it allocates everything it has, on the reasonable-sounding theory that an idle theatre is a wasted theatre.

Optimus reads the charts. From the patient's vital-sign trend it fits a recovery curve — the 1/(b0*k+b1) shape — and answers "how many more days?" From ten short trial runs before the operation starts, it fits a staffing curve and answers "how much faster does this operation go with one more nurse?" The quotient of those two is the only number it needs: time remaining. It then walks the ward handing out one nurse at a time to whichever patient's remaining time drops the most per unit of staff, re-checking after every single assignment.

Three consequences follow, and each is a measured result. First, the manager sometimes leaves a theatre empty. A recovery that gains nothing from a fifth nurse does not get a fifth nurse, because the fifth nurse in a crowded room slows everyone down — this is theta_0 * (M/w), the shrinking mini-batch, and it is why Optimus runs fewer tasks than DRF while finishing 2.39x sooner. Second, the manager keeps each operation in as few rooms as possible, with equal staff in each room, because every instrument passed between rooms crosses a corridor and the operation moves at the speed of the slowest corridor — that is Theorem 1, worth about 17% of the total gain. Third, the manager discovered that the hospital's own supply desk had been handing out instrument trays by a fixed size rule, leaving one nurse with 3.6 million instruments and another with almost none; rebalancing the trays alone was worth 20%.

The analogy also marks the boundary. This manager only understands operations performed in the specific way the hospital ran them in 2018: a central instrument desk that every surgeon pushes to and pulls from. An operation where the surgeons pass instruments directly around the table in a ring has no instrument desk to staff, so the manager's central decision — how many desk clerks versus how many surgeons — has nothing to decide. And the manager's whole advantage rests on the charts being legible: it is 2.29x better than the booking sheet for the predictable, synchronized operations, and only 1.97x better for the ragged asynchronous ones. It helps most exactly where it is needed least.