Shockwave: Fair and Efficient Cluster Scheduling for Dynamic Adaptation in Machine Learning — Detailed Summary

Pengfei Zheng, Rui Pan, Tarannum Khan, Shivaram Venkataraman, Aditya Akella | University of Wisconsin-Madison / UT Austin | arXiv:2210.00093v1 [cs.DC], 30 Sep 2022 | Open source: https://github.com/uw-mad-dash/shockwave

Per-section summary organized by the paper's own headings. Every paragraph produces at least one bullet; all quantitative tables, equations, and named methods are preserved.

Abstract

• Dynamic adaptation — changing model structure (lottery ticket hypothesis) or hyperparameters (batch size) mid-training — is now essential for accelerating distributed ML training, but existing ML cluster schedulers are not designed for it; the authors show existing schemes fail to provide fairness and degrade efficiency when training throughput changes over time.
• Shockwave is a scheduler with future planning built on two ideas: (i) extending classic market theory from static to dynamic settings to co-optimize efficiency and fairness; (ii) using stochastic dynamic programming to handle dynamic changes. It is validated with both trace-driven simulation and physical cluster experiments.
• Headline: for traces of ML jobs with dynamic adaptation, Shockwave improves makespan by 1.3× and fairness by 2× versus existing fair scheduling schemes.

1. Introduction

• Motivation. DNN training is a core datacenter workload; model and dataset sizes force distributed multi-GPU training, and enterprises consolidate hardware into shared GPU clusters — making fair arbitration plus efficient packing a first-order systems problem.
• Gap in prior schedulers. Gandiva and Tiresias optimize makespan/average JCT (dynamic scaling, time-slicing, over-subscription) but ignore fairness. Processor-sharing approaches (DRF, Gavel's weighted max-min fairness) give instantaneous fair share each round but significantly undermine efficiency. Stride-scheduling approaches (Gandiva-Fair) require operators to specify each job's share explicitly (e.g., A 20% / B 80% of GPUs), and manually fixed shares can violate long-term fairness. AlloX and Themis use a filter — each round, filter the jobs furthest from fair share, then maximize efficiency among them — but the filter value needs onerous hand-tuning and even tuned, a fixed filter is sub-optimal on both axes.
• Shockwave's approach. Formulate a Fisher market: every job gets an equal budget to buy resources from a central arbiter, which computes prices reaching equilibrium. At equilibrium each job's budget maximizes its performance (e.g., training throughput) and all resources are sold — giving fairness (equal purchasing power) and efficiency (work conservation plus per-job performance maximization under budget).
• Why static markets break. Prior economic systems (DRF, Themis, REF) assume static, known resource requests. That is false for elastic ML jobs: requirements change over time, the changes depend on model update patterns, and they are unknown a priori. Evidence cited: OpenAI scaled batch size from 32 to 32M to accelerate GPT-3 training by 500×; BERT-Large training uses dynamic batch sizes 256 to 4096 for a 2.5× speedup.
• Why reactive scheduling fails. An optimal schedule or weight assignment at the current instant can be suboptimal later, and reactively re-prioritizing is too late to compensate for early under-prioritization. Pollux accommodates dynamism but does so on behalf of jobs (auto-scaling batch size), which the authors find can hurt training accuracy (§2.3); Shockwave's aim is to let users perform elastic changes as their algorithms demand.
• Discrete-time dynamic market — worked example. Over 20 scheduling rounds, if a job's per-GPU batch size doubles after 10 rounds due to GNS scaling, its utility from one GPU (u₀) also doubles (u₁ = 2u₀). A static market assumes time-invariant utility → accrued utility 20u₀; a dynamic market captures the change → 30u₀. The formulation (§4.2) is proven to guarantee maximized Nash social welfare over time, Pareto optimality over time, and sharing incentive.
• Two implementation challenges. (1) The market needs future utility values, but adaptation is non-deterministically triggered by gradient values that vary across models and datasets. (2) Solving dynamic market equilibrium over an infinite horizon is computationally prohibitive and requires forecasting every job's future performance; online arrivals/completions force periodic re-solves at low overhead.
• Two corresponding mechanisms. (1) A dynamic adaptation predictor — real-world adaptation follows a handful of patterns, predictable with Bayesian statistics, integrated into the market. (2) An approximate dynamic market — plan only a finite window (e.g., 30–60 minutes), plus estimators capturing the long-term fairness and efficiency effects of short-term planning.
• Evaluation preview. 32-GPU testbed plus a simulator, workloads derived from Gavel and Pollux: 1.3× makespan and 2× fairness over Themis, Gavel, AlloX, etc.; scales to 900 active jobs on 256 GPUs maintaining 1.26–1.37× makespan and 2.5–3.1× fairness gains; solver overhead < 12.5% of a two-minute round, running asynchronously in a separate thread.

2. Motivation

2.1 Jointly Optimizing Fairness and Efficiency

• Fairness metric. The paper adopts Finish Time Fairness (FTF) as used by Themis, Gavel, and Pollux:

ρ(G) = t_schedule / t_egalitarian, where t_egalitarian = t_exclusive · N

t_schedule = job finish time under policy G; N = number of contending jobs; t_exclusive = run time when running exclusively with requested resources. ρ > 1 → unfair; ρ ≤ 1 → fair. The market formulation extends to other metrics — unequal budgets give weighted proportional fairness with budgets encoding priorities.

• Efficiency metric. A policy is efficient if it minimizes makespan (equivalently maximizes cluster utilization) for a given job sequence.
• Instantaneous fair-share sacrifices efficiency. PS and its multi-dimensional extension DRF guarantee every job exactly 1/N of the (dominant) resources at each instant. This degrades long-term efficiency: Altruistic Scheduling showed that sacrificing instantaneous fair share and letting some jobs altruistically contribute resources improves efficiency by 26%.
• Filters are suboptimal. AlloX and Themis select a fixed fraction f of least-served jobs each round, then maximize efficiency within that set; across rounds the filter compensates for past unfairness. A fixed f incurs a loss in average JCT or makespan, and tuning it is hard — especially as the workload varies.

Table 1 — Themis filter toy example (3 jobs):

• Fixed f = 1 and f = 2/3 violate FTF (ρ > 1); f = 1/3 yields worse JCT (5.7 vs 5.0). Only an adaptive filter achieves both.
• Figure 1 setting. Cluster: 4 GPUs. Jobs A, B, C — three DNN training jobs, one iteration each. Serial (1-GPU) iteration times: A = 12, B = 8, C = 6. Requested GPUs per iteration: A = 3, B = 2, C = 2. With static filter f = 2/3, FTF-ρ for (A, B, C) is (0.78, 0.83, 1.1) — the static filter hurts fairness. A linear slowdown is assumed when allocated GPUs < requested. This argues for a rigorous, systematic approach that jointly and intrinsically (without knob-tuning) optimizes efficiency and fairness.

2.2 Handling Dynamic Batch Size Scaling

• Sources of dynamism. (a) Job arrivals → time-variant cluster contention; AFS targets this, improving JCT by adjusting shares on arrivals. (b) Jobs changing their own configuration — e.g., GNS-driven batch size change, where a larger batch size decreases per-epoch time and thus remaining running time. Unlike prior systems handling only arrival-driven dynamism, Shockwave (and Pollux) target dynamic batch size changes.
• Agnostic/reactive scheduling breaks FTF. FTF implies a soft deadline t_egalitarian = t_exclusive · N. Computing t_exclusive is easy for static jobs (throughput × remaining work), but under dynamic adaptation future epochs may be much faster. Agnostic and reactive scheduling are unaware of future speedups, overestimate run time, and therefore mistakenly extend the deadline — causing significant unfairness.
• Figure 2 — Themis (reactive) vs. Shockwave (proactive). A real trace job doubles batch size three times, from 32 to 256, boosting training speed by up to 1.7×. Themis updates throughput immediately after each scaling event and recomputes estimated finish time; that changed estimate makes Themis detect under-service and try to prioritize the job later — but it has already suffered under-prioritization and misses the fairness deadline by 2.07×. Purely agnostic scheduling is worse: FTF ρ = 3.07.
• Agnostic/reactive scheduling also degrades efficiency. Makespan-minimizing algorithms (MILP, Longest Processing Time / LPT) and JCT-minimizing algorithms (SRPT, AlloX) rely on exact job run time or run-time ordering. Dynamic adaptation changes throughput on the fly, so run time can shrink (batch size up) or grow (batch size down); estimates from initial or current throughput are valid only at that instant.
• Figure 4 result. For MILP makespan minimization, being reactive yields 22.3% worse makespan and 28% worse cluster utilization than proactive scheduling; being fully agnostic is worse at 30% worse makespan. Mechanism: reactive scheduling treats J1 and J2 as long-running from their initial throughput and prioritizes them; adaptation makes J1 and J2 shorter than J3 in their second epoch, too late to re-prioritize J3. This motivates a scheduler that models future dynamic adaptation and accounts for its uncertainty.

2.3 Supporting User-defined Dynamic Adaptation

• Argument against auto-scaling. Improper batch size changes hurt convergence and accuracy. Unlike Pollux, which automatically modifies batch size, the authors argue schedulers should support user-defined schedules, because no adaptive scaling technique works consistently across all datasets and optimizers. Named policies: linear scaling rule, Accordion, Gradient Noise Scale (GNS), SimiGrad, Hessian eigenspectrum.
• Figure 3 — Pollux autoscaling (ResNet18 / CIFAR-10, 2 GPUs, initial batch size 32). Pollux reduces end-to-end training time by 5×, scaling batch size 32 → 64 at epoch 1, → 314 at epoch 2, → 690 at epoch 30, → 1682 at epoch 70 until completion — but causes a 2–3% accuracy loss. Plotting statistical efficiency (as defined in Pollux) shows large batch sizes in the first 30 epochs cause the degradation; correspondence with Pollux's authors indicates the degradation depends on the initial batch size (32 here) and thus varies across jobs.
• Expert heuristic comparison. The authors tested an expert heuristic for ResNet18/CIFAR-10: scale up when the gradient norm has insignificant (< 50%) changes, and do not scale during the initial 20 epochs nor the 10 epochs before and after each learning-rate decay. Result: minimal accuracy loss and 3× faster than vanilla training. Such heuristics do not transfer — for ResNet-50/ImageNet the experts scale batch size by 10× at the 30th, 60th, and 80th epoch. Shockwave therefore assumes no preference for any technique.
• Summary. Automatic adaptation risks accuracy degradation; Shockwave observes and forecasts future scaling events but treats dynamic adaptation as part of the user's program that cannot be modified.

3. Overview

• Market theory for efficiency and fairness. Prior schedulers also used market theory, but on static models assuming resource requests don't change. Those guarantees do not hold when jobs dynamically change, so Shockwave extends to a discrete-time dynamic market.
• Predicting dynamic adaptation. A dynamic market alone presumes perfect knowledge of when and how much throughput changes; ML training is stochastic, so Shockwave forecasts the trajectory and feeds it in.
• Scalable system implementation. Shockwave is a centralized, round-based scheduler (following Gavel) with tractable approximations, maintaining low overhead while scheduling every 120 seconds and scaling to 900 active jobs on 256 GPUs.

4. Dynamic Market Theory Formulation

4.1 Volatile Fisher Market (VFM)

• Why Fisher markets. The equilibrium of a Fisher Market, solved by maximizing Nash Social Welfare (NSW), is a strong condition implying all fairness guarantees used in prior systems; under equal endowment it implies Pareto Optimality (PO), Envy-freeness (EF), and Proportionality (PR) — the properties adopted by systems like DRF. Efficiency is defined via utility: a function mapping allocated resources to job progress. Fisher market equilibrium has also been shown to maximize efficiency.
• From static to dynamic. Classic Fisher Market assumes time-invariant utility; a recent study shows guarantees can be violated under time-variant utilities. Prior dynamic-market work studies settings where goods arrive online; this paper's setting differs — buyers have time-variant utilities over goods. The extension is named Volatile Fisher Market (VFM).
• The paper proves maximizing Nash Social Welfare Over Time (NSW_OT, Equation 1) solves the VFM equilibrium and establishes long-term properties such as Proportionality Over Time (PR_OT), with strong implications for finish time fairness and sharing incentive.
• Mechanics. Discrete intervals t = 1…T; a central seller (the scheduler) sells resources (GPUs and/or CPUs) to buyers (jobs). All resources are volatile — resources bought at t₀ cannot be carried to t > t₀. Job i's utility is a sequence of time-variant functions u_it (e.g., u₀ at batch size 16 doubling to u₁ = 2u₀ when the batch size doubles at t = 1). Time-varying utility ⇒ time-varying demand ⇒ time-variant equilibrium price. Each job has an initial budget reflecting purchasing power; different budgets encode scheduling priority.
• Equilibrium conditions. (a) Optimal Spending — each job's accrued utility Σ_{t=1..T} u_it is maximized under its budget; (b) Work-conserving — no leftover resources if the price is non-zero.

4.2 Equilibrium Properties

Cluster-level performance — NSW_OT (Equation 1):

NSW_OT(U₁(X₁), …, U_N(X_N)) = ∏_i U_i(X_i)^(B_i / Σ_i B_i), where U_i(X_i) = Σ_t u_it(x_it)

• U_i(X_i) = utility (e.g., epoch progress) accrued over rounds t = 1…T; X_i = the sequence of per-round allocations x_i1…x_iT; B_i = the job's budget. Maximized NSW_OT maximizes the (weighted) geometric mean of job progress over a T-round horizon, so cluster-wide utility is maximized and utilization improves.
• Pareto Optimality Over Time (PO_OT). Maximized NSW_OT implies PO_OT: each job has no surplus resources at each instant; one job's progress cannot increase without depriving another.
• FTF over time — Corollary 4.0.1:

The equilibrium of the Volatile Fisher Market with linear or Leontief utility at each instant (a) minimizes the product of FTF (ρ) across all jobs, i.e. ∏_i ρ_i; (b) when the budgets assigned to jobs are equal, the equilibrium provably guarantees Sharing Incentive (SI), i.e., all jobs' FTF ρ are no greater than 1, i.e., ρ_i ≤ 1, ∀i.

4.3 Handling Uncertainty

• VFM assumes perfect knowledge of when throughput changes, but adaptation is non-deterministically triggered by stochastic gradient values varying across models and datasets. §5 develops a predictor; because predictions are random variables, the formulation is extended to a VFM handling uncertainty in future demands, guaranteeing Maximized Nash Social Welfare Over Time in Expectation (MNSW_OTE) (Appendix F).

5. Predicting Dynamic Adaptation

• Key insight. Leverage knowledge about the techniques used for batch size scaling to restrict the search space of possible batch size changes.
• Regimes and trajectories. A regime is a tuple R = (c, f): c = job configuration (e.g., batch size), f = duration as a fraction of total epochs. Example: a 100-epoch job starting at BS₃₂ for epochs 1–20 has c₁ = BS₃₂, f₁ = 0.2. A trajectory is a sequence of regimes: if the job scales to BS₆₄ for epochs 21–80 and back to BS₃₂ for epochs 81–100, the trajectory is (c₁=BS₃₂, f₁=0.2) → (c₂=BS₆₄, f₂=0.6) → (c₃=BS₃₂, f₃=0.2). For a new job each (c_i, f_i) is a tuple of random variables.
• Domain knowledge (deterministic scaling patterns). (a) Accordion alternates only between two configurations c₁ (small batch) and c₂ (large batch): scaling up c₁ → c₂ when gradient values change slowly (below threshold), and back c₂ → c₁ when they change rapidly. (b) GNS only scales up, to a pre-specified limit, never down — gradient noise tends to grow throughout training; the paper's simple GNS model doubles the batch size as gradient noise grows above a relative threshold.
• Accordion and GNS were chosen as representative because they are used in prior systems (KungFu, Pollux) and their decisions are entirely determined by gradient states (norms and noises), which encode back-propagation stochasticity. Most other dynamic batch sizing policies also adapt to gradient states.
• Prior for regime transition. Since configuration transitions are deterministic, the only random variable is a regime's duration. For a job with K regimes, define P(f₁,…,f_K); epoch fractions must sum to 1, with no stationarity assumption. Approach: define a prior over regime duration, update the posterior in real time as training progresses.
• The restatement posterior update rule. Uses the commonly-used Dirichlet prior Dir(n₁,…,n_K). The standard Bayesian update assumes epoch samples of individual regimes are drawn independently and randomly — false, because epochs of the k-th regime can only emerge once the (k−1)-th finishes (temporal dependence). The restatement rule updates only the prior parameters corresponding to completed epochs, while continuing to believe ongoing and future regimes will evenly split the remaining epochs. For at most K regimes the prior is Dir(N/K,…,N/K); when the k-th regime (k = 1…K−1) finishes with observed epochs m₁,…,m_k:

Dir(m₁, …, m_k, S_k, …, S_k), where S_k = (N − Σ_k m_k) / (K − k)

• Figure 5 shows the restatement rule has lower interpolation error than the standard Bayesian update; error is averaged over 200 jobs randomly drawn from the Gavel workload trace, each with an Accordion- or GNS-imposed batch size scaling schedule.
• Predicting job remaining time. Sum individual regimes' expected durations for total runtime; subtract cumulative past run time (T_j) for remaining time. Necessary for estimating FTF.
• Computational tractability. The cluster-level trajectory space is combinatorially large, so the scheduler considers a single regime transition trajectory per job — the mean (expectation) of its posterior.
• Prediction accuracy (Figure 5). Compared against (1) the standard Bayesian posterior update and (2) a greedy approach forecasting run time using only the most up-to-date throughput — what all reactive schedulers use. Evaluated on 200 Accordion and GNS jobs with real adaptation trajectories, the restatement rule converges to the oracle job run time and oracle trajectory faster than both baselines. Regime-duration modeling error averages 6%, yielding on average 84% accuracy in run time prediction. The predictor needs no prior training — it only observes job progress across epochs.

6. Shockwave Design

System flow (Figure 6):

  (1) new job arrives
        |
        v
  +--------------------------+       (2) epoch completion / batch-size scaling
  |   Bayesian Predictor     |  <----------------------------------------------+
  |   Dirichlet prior; adds  |                                                 |
  |   job to active pool     |                                                 |
  +--------------------------+                                                 |
        |  (3) posterior update via restatement rule                           |
        v                                                                      |
  +--------------------------+                                                 |
  | Dirichlet Posterior      |--- forecast future batch-size schedule -----+   |
  | Model                    |--- predict (remaining) run time ---------+  |   |
  +--------------------------+                                          |  |   |
        (4) Long-term EFFICIENCY estimator -> makespan lower bound H  <--+  |   |
        (5) Long-term FAIRNESS  estimator -> FTF rho-hat per job      <--+  |   |
                                |                                           |   |
                                v                                           v   |
  +-----------------------------------------------------------------------------+
  | (6) SCHEDULE SOLVER : generalized Nash social welfare                        |
  |     weights = FTF^k   |   regulariser = makespan estimate H                  |
  |     output: N x T binary schedule matrix X  -->  Cluster Manager launches    |
  +-----------------------------------------------------------------------------+

• (1) On arrival the Bayesian predictor builds a prior for the job's batch size scaling schedule and adds the job to the active pool.
• (2) On epoch completion or a triggered batch size scaling, the event is reported. (3) The Dirichlet posterior is updated with the restatement rule; it forecasts the future batch size schedule for the solver and predicts remaining run time for the estimators.
• (4) A long-term efficiency estimator estimates makespan (time to finish all active jobs). (5) A long-term fairness estimator estimates FTFs for all active jobs.
• (6) The solver converts predicted batch size schedules into per-job utility and synthesizes a generalized Nash social welfare function using FTF estimates as weights and the makespan estimate as a regularizer. Output: a schedule for the next T rounds, used by the cluster manager to launch jobs.

6.1 Schedule Solver

• Output. Plans for a configurable number of future rounds T (default in §6.1: 20 two-minute rounds; Appendix G states default T: 30 two-minute rounds — both figures appear in the paper). Output is an N × T binary matrix X; X[j,t] = 1 schedules job J_j in round t, X[j,t] = 0 deschedules it.
• Inputs. Per-job batch size schedules (→ utility UTIL_j), estimated FTFs ρ̂_j, estimated makespan H.

Objective (Equation 2):

Maximize over X: ( Σ_{j=1..N} ρ̂(j)^k · log Σ_t UTIL_j(X[j,t]) ) / (N·M) − (λ · H(X)) / Z₀

• Σ_t UTIL_j(X[j,t]) is the summed utility of active jobs; utility rises when a job is scheduled for more rounds in the window, and the sum of log-utilities across jobs is the Nash social welfare.
• The k-th power of FTF values ρ̂_j (default k = 5) acts as weights, prioritizing jobs at risk of violating FTF (e.g., long-queued jobs). The regularizer penalizes schedules that could increase the makespan estimate H(X): λ (default 1e−3) controls its magnitude, Z₀ normalizes so the regularizer is insensitive to the scale of H(X), and M is the total number of cluster GPUs.
• Hyperparameter sensitivity. Tuned over a large range; performance is consistent around the defaults with k in [1, 10] and λ in [1e−4, 1e−2]. Exceedingly large or small values let one term dominate the other and push Shockwave off the fairness/efficiency Pareto frontier.
• Re-solving and regime decomposition. Like Themis/Gavel/Pollux, the solver recomputes when the planned rounds elapse or when jobs arrive or complete. If adaptation is predicted within the window, the job's schedule is decomposed into regimes, each with fixed batch size and throughput; generalized NSW is implemented at the regime level, a job's utility being the sum over its regimes.

6.2 Long-term Fairness and Efficiency Estimators

• FTF estimator. Job J_j's ρ̂(j) = predicted job completion time (attained service time + waiting time + predicted remaining run time) ÷ predicted total run time; predicted runtime is tied to the predicted batch size scaling schedule. FTF ρ values are plugged into the social welfare function as weights, which act as the budgets in the volatile Fisher market: a job predicted to be unfairly scheduled long-term (large ρ) receives a higher budget and is proactively prioritized in the planning window.
• Makespan estimator. Estimates makespan to complete all active jobs and penalizes schedules that increase it. Since true makespan is hard to estimate, Shockwave uses a lower bound (from Coffman/Garey/Johnson bin-packing) as a proxy and penalizes increasing that bound.

7. Implementation

• Scheduler and worker. Time-sharing via round-based scheduling; each round is a fixed interval (default 2 minutes). Each round the scheduler selects jobs from the active pool; the lease manager translates the schedule into job leases and instructs workers to launch, suspend, or resume. Each worker binds to a single GPU device.
• Placement engine. Adopted from Gavel: tightly packs a job's workers onto machines to minimize fragmentation, and prefers previously executed machines to maximize locality.
• Lease lifecycle. Not running in round T but scheduled for T+1 → new lease, job dispatched before the round starts, workers launch at the round boundary. Running in T and scheduled for T+1 → lease extension signal, job stays on the same workers. Running in T but suspended in T+1 → workers stop it as the lease is not renewed.
• Restart penalization. Shockwave penalizes frequent restarts (model/dataset dispatch overhead): the solver prefers continuous rounds and penalizes scattering a job's execution across rounds; the placement engine prefers previously allocated workers.
• Dynamic adaptation support. A job notifies the solver on batch size scaling. Two configurable modes: reactive mode (invalidate the schedule and immediately re-solve — default) and lazy mode (continue and postpone re-solving to the next interval).
• Prototype. Python atop the Gavel ML cluster manager, adding a schedule solver, meta-data collector, and schedule translator (schedule → leases). Users get an interface to monitor gradients and trigger batch size scaling; requests are sent over gRPC. Solver implemented with Gurobi. Checkpoints on Linux NFS; checkpointing overhead < 3%.

8. Evaluation

8.1 Experiment Setup

Workload (Table 2):

• Trace generation. Two workloads are used. Default: Gavel's workload generator for synthetic distributed training workloads with diversity in job sizes, model types, and arrival patterns. Jobs range 0.2 to 5 hours with 1, 2, 4, or 8 workers; arrivals follow a Poisson process with inter-arrival rate λ ∈ [0.1, 0.2]. Total batch size is increased by raising the per-GPU batch size while preserving worker count. A production trace of real job durations and arrival timestamps used by Pollux is also evaluated (Appendix J). Each job is configured as Static, Accordion, or GNS.

8.2 Baseline Schedulers

• The paper says it compares against "six schedulers" and then names seven: OSSP (Open Shop Scheduling), AlloX, Themis, Gavel, MST (Max-Sum-Throughput), Gandiva-Fair, and Pollux.
• All baselines except Pollux keep worker count fixed; Pollux dynamically tunes both worker count and batch size. For a fair comparison the Shockwave prototype performs only time-sharing with fixed worker counts, even though the market formulation can be re-parameterized to support worker scaling. Pollux is compared separately in §8.7.

• Performance metrics. Efficiency = makespan and utilization. Fairness = (1) fraction of jobs with FTF ρ > 1.0 and (2) worst-case FTF ρ (worst-case slowdown from unfair scheduling); lower is better for both, indicating better preservation of sharing incentive. Responsiveness = average JCT.

8.3 Evaluating Efficiency and Fairness — Physical, 32 GPUs, 120 Jobs

• Efficiency. Makespan on average 1.3× less than Themis, Gavel, and AlloX; 37% makespan improvement over MST; makespan similar to OSSP (which has no fairness constraint). Cluster utilization 28% better on average than Themis, Gavel, AlloX.
• Finish time fairness. Shockwave's worst-case FTF ρ = 1.82, beating Themis, Gavel, AlloX by 2× on average. OSSP and MST severely break FTF: worst-case ρ reaches 5.79 and 5.2. Shockwave's unfair-job fraction beats Themis/Gavel/AlloX by 2.7× on average; OSSP unfairly schedules 70.8% of jobs, MST 25%.
• Average JCT. Shockwave is similar to Themis, Gavel, MST. AlloX is better by aggressively prioritizing short jobs (delaying long jobs); OSSP is worst, aggressively prioritizing long jobs for tight packing.

Figure 7 — relative values versus Shockwave (Shockwave = 1.0):

• Mechanism. Jobs are opportunistically prioritized to improve long-term efficiency when doing so does not affect FTF. The solver also improves fairness by smart arbitrating: "rich" jobs (low chance of violating FTF) yield resources to "poor" jobs (high chance).

8.4 A Closer Look at Shockwave's Schedule (50 jobs)

Jobs are categorized by GPU-time into (X)Large, Medium, Small, (X)Small.

• AlloX prioritizes small jobs — in the first 100 rounds most scheduled jobs are XSmall. Its filter prevents starvation of medium/large jobs but does not prioritize them: large jobs trail until round 230.
• Gavel's max-min fair scheduling prioritizes least-performant jobs; all sizes evenly partition GPUs. Instantaneous fairness hurts long-term efficiency: large jobs run on a mostly idle cluster from round 170 to round 220.
• Shockwave opportunistically schedules (X)Large jobs across rounds without hurting small/medium jobs' sharing incentive; large jobs are scheduled between rounds 0–50 and 50–120, tightly packing the cluster → low makespan. Responsiveness is preserved: most XSmall jobs finish before round 50, small jobs before round 110 — comparable to AlloX.
• OSSP over-prioritizes (X)Large and medium jobs and significantly delays XSmall completion, breaking sharing incentive and undermining responsiveness.
• Fairness (Figure 8b, FTF ρ CDF). Shockwave's worst-case FTF ρ for this 50-job batch is 1.23 with a low unfair fraction. AlloX's and Gavel's CDFs grow faster for ρ ≤ 1, but more than 20% of their jobs have ρ > 1 — they over-prioritize some jobs past the sharing incentive threshold. Shockwave avoids over-prioritization and improves fairness by predicting adaptation for a more accurate FTF deadline estimate.

8.5 Scaling to Large Clusters

Simulation fidelity (Table 3) — difference between simulator and physical cluster:

• The physical cluster implementation and the simulator share the same scheduling code base and solver engine; overall difference ≈ 5%.
• Configurations: 64 GPUs with over 220 jobs, 128 GPUs with over 460 jobs, 256 GPUs with over 900 jobs, with the contention factor held at roughly three to keep contention constant regardless of scale.

Efficiency at scale (Figure 9):

• Fairness at scale. Worst-case FTF ρ averages 1.32, outperforming Themis, Gavel, AlloX, and Gandiva-Fair by 2.5×, 2.4×, 3.1×, and 3.9× respectively. Unfair-job fraction (ρ > 1) averages 4%, outperforming other fair-scheduling baselines by 6×.
• Responsiveness at scale. Similar average JCT to fair schedulers, except Gandiva-Fair prolongs average JCT by 16–22% — its stride scheduling gives a job tickets equal to job size (worker count), so large jobs get a higher proportional share and delay small jobs.

8.6 Benefits of Proactive Scheduling (varying static/dynamic job mix)

• All-static case (isolates the social-welfare-maximization win): all fair policies (Shockwave, Themis, Gavel, AlloX) keep the unfair fraction relatively low (< 18%), but Shockwave limits it to < 5%. Shockwave shows an 18% average makespan improvement over Themis, Gavel, and AlloX with no loss in average JCT.
• Increasing the dynamic fraction: Shockwave's makespan speedup over Gavel, Themis, and AlloX rises to 1.3× as the dynamic-job fraction grows from 0.4 to 1.0. Reactive schedulers degrade in fairness as dynamism grows: with all jobs dynamic, Themis schedules 28% of jobs unfairly, AlloX 22%, while Shockwave is at 9%.

8.7 Shockwave versus Pollux

• Setup. Both run the same workload trace provided by Pollux. The Pollux simulator is run first to collect the batch size schedule observed at runtime, which is fed as input to the Shockwave simulator, so both see the same jobs and same batch size schedule — job processing times match even with dynamic scaling.
• JCT. Pollux achieves a 3× improvement in average JCT because it scales the number of workers per job, reducing contention: Pollux reduces requested GPU hours per job by 2.4× versus the original trace. Shockwave's prototype does not change worker counts, so it preserves the trace's contention level (2.4× larger than Pollux) and has inferior responsiveness. The paper notes Shockwave has comparable JCTs to other baselines (Figure 7) and that the Pollux paper itself reports a 3× speedup over its baselines.
• Finish time fairness. Shockwave significantly outperforms Pollux. Pollux targets instantaneous fairness per allocation: its p-norm formulation penalizes allocations giving low instantaneous throughput but does not preserve long-term fairness across rounds. Shockwave's dynamic market provably guarantees long-term fairness.
• Makespan. Shockwave has a similar makespan to Pollux despite not changing worker counts, because it optimizes long-term efficiency.
• Accuracy caveat. Pollux's automatic tuning of batch size and worker count can cause accuracy loss — 2% for ResNet18 and up to 4% for DeepSpeech — which, with poor fairness, the authors argue makes Pollux less attractive for practical deployments.

8.8 Varying Cluster Contention and Workload

• The contention factor is varied and all policies compared on a smaller 14-GPU physical cluster. Shockwave's fairness and efficiency win increases as contention grows and decreases as it drops (Appendix I). Pollux-trace arrival patterns are also evaluated (Appendix J).

8.9 Solver Overhead

• A timeout knob (default 15 s) limits solving overhead. On a 256-GPU cluster, solver quality improves with diminishing returns as timeout goes from 1 s to 15 s; quality is measured by the bound gap (distance from optimal at timeout).

• Gurobi's recommended criterion is 0.1%; the 2000-job case exceeds it, but results show limited impact on efficiency and fairness. The solver runs in a separate thread and is proactively invoked mid-round, so its overhead is hidden when it is less than half a round duration.

8.10 Resilience to Prediction Error

• Random noise (± p%) is injected into the interpolated job run time under dynamic adaptation. Settings match Figure 10 with all jobs dynamic ((S, D) = (0, 1.0)).

Figure 13 — relative values (Oracle = 1.0):

• Worst-case FTF ρ and unfair fraction inflate slowly as injected error grows; average JCT shows a similarly steady trend. The authors attribute this robustness to the design principle of Nash social welfare, which emphasizes common ownership and fair sharing: the penalty for skewed training progress is huge, making the scheduler conservative about schedule slacks predicated on biased FTF estimates.
• Scheduling efficiency does drop: 100% injected noise lowers scheduling efficiency by over 30% by corrupting job-length estimates (Shockwave opportunistically prioritizes long-running jobs to improve makespan). Even so, the degraded efficiency is on par with the baselines (Themis, Gavel, AlloX).

9. Related Work

• The detailed comparison against Gandiva, Optimus, DRF, REF, Themis, AlloX, Tiresias, and Gandiva-Fair appears in §2. Two contributions are spotlighted: (1) Shockwave is built on Nash social welfare, a theoretically grounded approach co-optimizing long-term rather than instantaneous fairness and efficiency; (2) Shockwave proactively plans schedules for dynamic adaptation, while most existing schedulers only react to it.
• AFS (Apathetic Future Share) is another elastic sharing mechanism proactive to system dynamics — but its dynamism refers to job arrival and time-variant cluster contention, with jobs themselves unchanging. Shockwave's focus differs: jobs' resource demands and efficiency change due to batch size scaling. AFS also primarily targets average JCT, while Shockwave maximizes social welfare over time.

10. Conclusion

• Shockwave is a market-theory-based efficient and fair scheduling framework for DNN training. Existing schedulers fail to preserve fairness and degrade efficiency by being reactive to dynamic adaptation. Shockwave's proactive approach uses dynamic markets and Bayesian statistics, improving efficiency and fairness over state-of-the-art schedulers.

Appendices

Appendix A — Dynamic Batch Scaling Degrades Accuracy

• A.1 — When scaling degrades accuracy (the "generalization gap", whose underlying reasons the paper says are still not well understood): (a) scaling batch size by k× reduces iterations per epoch by k×, so for a fixed epoch budget total back-propagation iterations fall k× and accuracy loss stems from the reduced number of model updates; (b) larger batches reduce gradient-estimate noise, but noise regularizes training and helps escape local minima; (c) larger batches drive convergence to sharp minima, making outputs sensitive to small input perturbations.
• Heuristics and adaptive techniques (Gradient Norm, GNS, Hessian eigenspectrum) mitigate the gap, but no single technique handles all models, datasets, and optimizers. Pollux adopts GNS, and recent work points out limitations of GNS for batch size scaling.
• A.2 — Pollux autoscaling on NeuMF/NCF-ml-1m. Statistical efficiency degrades minimally when scaling batch size from 256 to 32768, even in early epochs, so Pollux immediately scales 256 → 32768 at epoch 1. This yields inferior validation accuracy — lower HR (Hit Rate) and NDCG (Normalized Discounted Cumulative Gain) — than vanilla training with scaling disabled. An expert-set schedule that scales to 32768 at epoch 3 matches vanilla accuracy. The authors also found Pollux's statistical efficiency metric can be incorrect for Neural-MF models.

Appendix B — Static Filters Degrade Efficiency and Fairness

• Figure 15 visualizes the schedules behind Table 1 on the same 4-GPU / 3-job setting as Figure 1: (a) Themis with f = 1/3, (b) Themis with f = 1.0, (c) Shockwave with a dynamic filter f that varies per round (e.g. 2/3 on some GPUs, 1/3 on others).

Appendix C — Volatile Fisher Market Formulation

• VFM runs over rounds t = 1…T, each a fixed interval (e.g., 120 s). A central seller sells multiple resource types (GPUs and/or CPUs) to buyer jobs; all resources volatile, no carry-over. Each resource type has a dynamic price per round; each job has an initial budget spent across rounds, endowment reflecting priority. VFM assumes divisible resources.
• Formal components: (a) N buyer jobs competing for J resource types; (b) x_ijt = job i's purchase of resource j in round t (provision normalized to one unit), X_i = the J × T allocation matrix; (c) budget B_i, price p_jt, accrued payment Σ_{j,t} p_jt · x_ijt, price matrix P (J × T); (d) utility U_it(x_it) maps received resources to performance gain (e.g., epoch progress), varying across rounds to model adaptation.
• Performance functions are limited to the CES family — Themis and Gavel use linear utility, DRF uses Leontief, REF uses Cobb-Douglas, all CES. VFM supports multi-resource allocation, but the paper's evaluation covers only GPU allocation.
• C.2 Equilibrium conditions. (a) Optimal spending: X*i = argmax{X_i} U_i(X_i) s.t. Σ_t Σ_j p_jt · x_ijt ≤ B_i, ∀i. (b) Work-conserving / market clearing: if p_jt > 0 then Σ_i x_ijt = 1, ∀j,t.

Theorem C.1:

For Volatile Fisher Market with linear or Leontief (e.g., DRF) utility, the solution of (3) captures the optimal allocation in the market equilibrium and the Lagrangian dual to capacity constraints (i.e., Σ_i x_ijt ≤ 1, ∀j,t) captures the equilibrium price.

• Equation (3) is an Eisenberg-Gale-styled program: Maximize Σ_i B_i · log U_i(X_i) s.t. U_i(X_i) = Σ_t u_it(x_it), with u_it linear (Σ_j u_ijt x_ijt) or Leontief (min_j x_ijt / a_ijt), Σ_i x_ijt ≤ 1, x_ijt ≥ 0. Note: even if instantaneous utility is Leontief, the summed utility over time is not Leontief in general.

Appendix D — Proof of Theorem C.1

• D.1 Linear utility. VFM with linear utilities reduces to a special case of the static Fisher market by treating each (resource, time) pair (j, t) as a unique resource type k; program (4) is then the classic Eisenberg-Gale program already proven to capture static equilibrium.
• D.2 Leontief utility. No direct link to the static market exists, so the proof characterizes the Karush–Kuhn–Tucker (KKT) conditions of the EG program rewritten in standard convex form (5a–5e), with Lagrangian multipliers β_i, λ_ijt, p_jt, η_ijt. First-order conditions give β_i = B_i / U_i(X_i) and β_i = Σ_j λ_ijt; multiplier nonnegativity gives p_jt · a_ijt ≥ λ_ijt, leading to U_i(X_i) = B_i / min_{t'}{ Σ_j p_jt' a_ijt' }.
• Interpretation: each job's utility is achieved by purchasing resources only in periods guaranteeing MBB (Maximal Bang-Per-Buck), where Σ_j p_jt a_ijt is the unit cost of one unit of utility. Complementary slackness gives p_jt > 0 ⇒ Σ_i x_ijt = 1, proving Market Clearing (MC); maximizing the budget-weighted geometric mean leaves no money unspent, proving Budget Clearing (BC). MBB + MC + BC establish equilibrium.

Appendix E — Proof of Corollary 4.0.1

• (a) ∏_i ρ_i equals ∏_i U_i(C/N) · NSW_OT^(−1); since ∏_i U_i(C/N) is a constant independent of X_i, the VFM equilibrium that maximizes NSW_OT equivalently minimizes ∏_i ρ_i.
• (b) At equilibrium each job has maximized utility under budget. With equal budgets job i cannot prefer job j's allocation, since i could afford to buy it: U_i(X_i) ≥ U_i(X_j), ∀i,j. Because the market clears, not all jobs can have share strictly below C/N, so some job k has share ≥ C/N, giving U_i(X_j) ≥ U_i(X_k) ≥ U_i(C/N) — establishing finish time fairness.

Appendix F — Stochastic Dynamic Program (Efficiency and Fairness in Expectation)

• Components: (a) State — each job has a private, finite state set; for batch size scaling a state is the tuple (BatchSize, Epoch). (b) Policy — π(s_t, x_t) = probability of allocation x_t conditional on job states s_t in round t; the paper limits π to deterministic policies. (c) Transition probability — P_i(s_it+1 | s_it, x_it). (d) Utility — U_i(s_t, ·, s_t+1) = performance gain on transition.
• Equation (6) is a linear program searching for the optimal policy maximizing NSW in expectation: π* = argmax_π Σ_i B_i · log E_π[U_i], subject to a definition of expected cumulative utility, per-round allocation not exceeding provision with non-negativity, and valid probability transitions. Maximized NSW_OTE co-optimizes efficiency and fairness in the expectation sense.

Appendix G — Shockwave Design Details

• Planning window default stated here: T = 30 two-minute rounds; re-solve on window elapse, arrival, or completion.
• Regime decomposition example. A job has two regimes; it is currently in regime 1 at epoch 5, and regime 2 is predicted to start at epoch 15. The planning window is 30 minutes; epoch durations are 2 minutes (regime 1) and 1 minute (regime 2). Adaptation can start as early as the 20th minute in the window, and a 2× change in throughput must be accounted for. Each regime becomes a micro-job with static throughput (epochs 5–14 = micro-job 1, epoch 15 onward = micro-job 2). A K × T binary matrix Y_j[k,t] represents job J_j's K regimes in the window; partial order constraints preserve regime order.

G.1 — Implementing NSW over time (Equations 7, 8):

UTIL_j(Y_j[·,·]) = F_j / E_j + Σ_{t=1..T} Σ_{k=1..K} ( Y_j[k,t] · D · TH(j,k) ) / ( Q_j · E_j )

WELFARE(Y[·,·,·]) = Σ_{j=1..N} log UTIL_j(Y_j[·,·])

• A job's utility = current epoch progress percentage (finished epochs F_j ÷ total epochs E_j) plus the epoch progress percentage under the allocation, summed across regimes and rounds. Per-round epoch progress for regime k = round duration (D_j) × whether the regime is scheduled (Y[k,t]), divided by epoch duration Q(j)/THPT(j,k). Maximizing NSW_OT yields the equilibrium and its guarantees.

G.2 — Estimators for long-term effects. Maximizing welfare over an infinite horizon is infeasible (compute cost, limited predictability, online arrivals forcing replanning), so Shockwave plans a finite window (e.g. 30–60 minutes) plus estimators.

ρ̂(j) = ( L_j + W_j + R̂(j) · N_avg(j) ) / ( P̂(j) · N_avg(j) ) (Equation 9)

H(Y[·,·,·]) = max{ ( Σ_j R(Y_j[·,·]) ) / M , max_j R(Y_j[·,·]) } (Equation 10)

• L_j = attained service time; W_j = waiting time; R̂(j) = interpolated remaining run time; P̂(j) = predicted total run time under isolated resources (from the Bayesian posterior), with R̂(j) = P̂(j) − L_j. Isolated run time is linearly scaled by a contention factor N_avg(j) — within a fixed time range, the ratio between jobs requesting GPUs and total GPUs provisioned, counting only the range in which the job is queued or running. The k-th power of ρ is the weight (the market budget).
• The makespan lower bound is the maximum of (sum of remaining run times ÷ cluster GPU count M) and (longest remaining job run time) — the max of "longest job remaining" and "makespan if all remaining jobs were spread evenly across the cluster."
• λ controls regularization strength; the appendix states Shockwave yields similar makespan and fairness for different workloads when λ is between 1e−1 and 1e1 (§6.1 instead reports a default of 1e−3 and a good range of [1e−4, 1e−2]; both figures appear in the paper).

G.3 — End-to-end schedule optimizer (Equation 11):

Maximize over Y₁,…,Y_N: (1 / (N·M)) · Σ_{j=1..N} ρ(j)^k · log[ UTIL_j(Y_j[·,·]) ] − (λ / Z₀) · H(Y₁[·,·], …, Y_N[·,·])

• Z₀ is a normalization coefficient — the sum of the interpolated run time across all jobs. The solver output is a schedule per regime; the per-round job schedule is translated from it.
• Dynamic job arrival. Like Themis, Tiresias, Pollux, and Gavel, Shockwave periodically adds newly arriving jobs to the solver; the fairness objective automatically arbitrates between newly-arrived short jobs and long-queued jobs by their pressure on breaking FTF.

Appendix H — Constraints of Program 11

1. Preserving the order of regimes — no regime may run before its precedent regimes complete.
2. Work-conserving (market clearing) — idle resources not allowed when ready jobs exist.
3. Capacity limits — GPUs assigned to jobs must not exceed total provision.

Appendix I — Varying Contention Factor (14-GPU physical cluster)

• Contention factor (CF) = ratio of jobs requesting GPUs to total GPUs provisioned in a fixed time range; the default assumed throughout is 3. Shockwave's efficiency win shrinks as slack grows:

• Fairness for all policies improves as CF decreases, but Shockwave still leads: the average fraction of unfairly scheduled jobs across contention factors is 8.67%, outperforming baselines by 2.85×. At CF = 2 Shockwave maintains worst-case FTF ρ of 1.2, outperforming Themis, Gavel, AlloX by 1.27×. At CF = 1.5 Shockwave and all baselines approach worst-case FTF ≈ 1 and the difference is insignificant.

Appendix J — Varying the Cluster Trace (Pollux trace, 32 GPUs)

• Evaluation repeated with real DNN training traces from Pollux (job duration and arrival timestamps, extracted from a prior workload analysis). Trends match earlier sections, but the makespan win over Themis, Gavel, and AlloX drops from 30–35% to 20%.
• Explanation: the synthetic traces have 2× greater job-duration diversity than the Pollux trace, so long-running jobs have a larger impact on final makespan and utilization, and opportunistically prioritizing them yields greater improvement when diversity is high.

Limitations

• Worker count held fixed. The evaluated prototype performs only time-sharing and keeps a job's worker count constant for its lifetime. The paper states the market formulation can be re-parameterized to support worker scaling, but this is neither implemented nor measured; the direct consequence is a 3× worse average JCT than Pollux (§8.7).
• Only two adaptation policies modeled. The predictor's domain knowledge covers Accordion and GNS only; the authors state they "plan to add support for more policies in the future" (§5).
• Single trajectory per job. To avoid combinatorial explosion, only the posterior mean trajectory is considered — alternative trajectories are discarded (§5).
• Batch-size dynamism only. Dynamic adaptation is scoped to batch size scaling; other forms (e.g., model-structure changes such as the lottery ticket hypothesis mentioned in the abstract) are not modeled.
• Efficiency degrades under prediction error. 100% injected noise lowers scheduling efficiency by over 30% (§8.10).
• Efficiency win is contention- and trace-dependent. The makespan win shrinks from 35% at CF = 3 to 8% at CF = 1.5 (Appendix I), and from 30–35% to 20% on the less duration-diverse Pollux trace (Appendix J).
• Solver quality degrades at very large job counts. At 2000 active jobs the 15 s bound gap is 0.44%, exceeding Gurobi's recommended 0.1% (§8.9).
• Slightly worse than the pure-efficiency baseline. Shockwave's makespan is 5–9% worse than OSSP at scale (§8.5).
• Internal inconsistency in reported defaults. The planning window default is 20 rounds in §6.1 and 30 rounds in Appendix G; the good range for λ is [1e−4, 1e−2] in §6.1 and [1e−1, 1e1] in Appendix G.2.

Open Problems Identified by the Paper

1. Support for more dynamic adaptation policies. The authors explicitly plan to extend the predictor beyond Accordion and GNS to other gradient-state-driven batch sizing policies (§5).
2. Worker-count elasticity within the market. Re-parameterizing VFM to also allocate worker counts (not just time slices) is stated as possible but left unimplemented (§8.2).
3. Other fairness metrics. The market can support weighted proportional fairness by encoding priorities in budgets, but only FTF is evaluated (§2.1).
4. Multi-resource allocation. VFM formally supports multiple resource types (GPUs and CPUs), yet evaluation covers only GPU allocation (Appendix C).
5. Trustworthy adaptation signals. The authors report that Pollux's statistical efficiency metric can be incorrect for Neural-MF models, leaving open the question of a reliable signal for deciding when to adapt (§2.3 footnote, Appendix A.2).