Dynamic Scheduling of MPI-based Distributed Deep Learning Training Jobs

Iqbal Mohomed; Mete Kemertas; Tim Capes; Vishal Raheja

REVIEW 3 major objections 5 minor 12 references

Dynamic Scheduling of MPI-based Distributed Deep Learning Training Jobs

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Ring-architecture deep learning jobs can be stopped, resized, and restarted cheaply enough that dynamic scheduling more than halves average job completion time in simulation.

desk verdict Direct resizing measurements are credible, but the headline simulated scheduler gain is an in-sample artifact and should be read as a hypothesis. read the letter →

arxiv 1908.08082 v1 pith:ZUNPFERZ submitted 2019-08-21 cs.LG cs.DCstat.ML

Tim Capes , Vishal Raheja , Mete Kemertas , Iqbal Mohomed This is my paper · ORCID

classification cs.LGcs.DCstat.ML

keywords dynamicschedulingringall-reduceGPUclustercheckpointandrestartdoublingheuristicresourceallocationdistributeddeeplearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Deep learning jobs on GPU clusters are usually trained with a fixed number of GPUs, but clusters are shared and demand shifts. This paper tries to establish that ring-architecture training jobs—the all-reduce alternative to parameter servers—can be dynamically resized: stopped, checkpointed, and restarted with more or fewer GPUs without a meaningful penalty. To support this, it derives a resource-to-speed model for ring all-reduce algorithms, formulates the allocation problem as a non-convex, NP-hard integer program, and introduces a doubling heuristic that assigns workers in powers of two to escape local optima. Experiments on ResNet-110 with CIFAR-10 show stop-restart time near 10 seconds and 94.5% scaling efficiency from 4 to 8 GPUs; a scheduler simulation reports average job time more than halved under moderate contention. If correct, the same cluster can finish more training jobs in the same wall-clock time by shifting GPUs between jobs as contention changes.

What carries the argument

The carrying mechanism is the resource-to-speed model of Eq. 5, $f(w) = (\theta_0 (m/w) + \theta_1 (w-1) + \theta_2 (w-1)(n/w) + \theta_3)^{-1}$, where $w$ is the number of workers, $m$ is the minibatch size per worker, $n$ is the model size, and the $\theta$'s are non-negative coefficients learned for each job. This single functional form can represent ring, doubling-halving, and binary-block all-reduce algorithms with different coefficient behaviors. The scheduling problem is a non-convex, non-linear, NP-hard integer program minimizing the sum of job completion times subject to total GPU capacity; the doubling heuristic solves it by starting every job at one GPU and repeatedly adding $w_j$ workers to the job maximizing $(Q_j/f(w_j) - Q_j/f(2w_j))/w_j$, the average per-GPU reduction in remaining time. Doubling matters because increasing from 8 to 9 GPUs can look worse than increasing from 8 to 16 GPUs, so a unit-step greedy heuristic can get stuck in a local optimum. The learning-rate rescaling rule $lr_{new} = (w_{new}/w_{last}) \cdot lr_{last}$ is what makes checkpointed resumes on more GPUs preserve convergence.

What would settle it

Run the proposed scheduler on a real cluster with jobs whose speed and convergence were not used to fit the model, and compare predicted vs. actual completion times and final accuracies; the claim fails if, for instance, a ResNet-110 run resumed from a 4-GPU checkpoint onto 8 GPUs with the Eq. 7 learning-rate doubling reaches markedly lower test accuracy than an uninterrupted 8-GPU run, or if measured stop/restart overhead on a loaded cluster is far above the simulated 10 seconds.

Watch

Extended reading notes

Core claim

The central discovery is twofold: ring-architecture jobs have low stop-and-restart cost and near-linear scaling, so dynamic resizing is practically viable; and a doubling-based heuristic can allocate GPUs to jobs in a way that respects the non-monotonic performance of ring all-reduce. The authors model time per minibatch as a combination of forward/backward propagation and all-reduce communication, fit a speed-per-worker function $f(w)$ to each job by non-negative least squares, and solve the scheduling problem by repeatedly giving a job enough extra workers to double its allocation, selecting the job with the largest average marginal time improvement per GPU. On a single 8-GPU node with ResNet-110 on CIFAR-10, resuming from a 4-GPU checkpoint onto 8 GPUs saved about 32% of training time when stopped at 51 epochs and about 23% when stopped at 102 epochs, with roughly 10 seconds of checkpoint/stop/restart overhead. In simulation on a 64-GPU cluster with Poisson job arrivals, the precompute scheduling strategy more than halved average job completion time relative to fixed 8-GPU allocations under moderate contention.

Load-bearing premise

The simulation's promised halving of average job time assumes that the per-job speed and convergence models learned from previously completed runs predict new jobs of the same kind, and that resuming from a checkpoint with the doubled learning rate reaches the same model quality as uninterrupted training; neither assumption is tested on held-out jobs or measured accuracy.

Editorial extensions

If this is right

On a 64-GPU cluster with Poisson arrivals and moderate contention, the precompute scheduler more than halves average job completion time compared with fixed 8-GPU allocations.
Rescaling a job from 4 to 8 GPUs at 51 epochs saves roughly 32% of wall-clock time; stopping at 102 epochs still saves about 23%, with stop/restart overhead around 10 seconds.
The doubling heuristic lets the scheduler reach 16-GPU allocations that a unit-increment greedy heuristic would miss, because the 8-to-9 step looks unprofitable while the 8-to-16 step is not.
Because placement is simpler in ring architectures (there are no parameter servers to place), the scheduling gains can be realized without adding placement complexity.
Exploratory scheduling—giving new jobs 8 GPUs briefly to sample speeds at 1, 2, 4, and 8 GPUs—performs well under moderate contention but poorly under extreme contention, where the 7.5 minutes of exploration is too costly.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A next step the authors leave implicit: deploy the precompute scheduler on a live cluster and compare measured completion times to the simulated halving, which would also test whether the fitted speed model generalizes to new jobs.
The same doubling heuristic could in principle be applied to parameter-server jobs, since the speed model's functional form covers both architectures and the heuristic is what avoids local-optimum stalls.
The checkpoint-resume results suggest dynamic scheduling could double as preemption: suspend a low-priority job, admit a short high-priority job, then resume the suspended job on a different worker count with minimal penalty.
For models sensitive to learning-rate changes, the Eq. 7 rescaling rule may not preserve accuracy; if so, the scheduler would need a short warm-up or a different adaptation rule before reallocating GPUs.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Here's my take on arXiv:1908.08082. The paper's direct measurements are the real contribution: checkpointing and restarting a Horovod job from 4 to 8 GPUs costs about 10 seconds, scaling efficiency is 94.5%, and resizing saves 23–32% wall-clock time. Those numbers support the feasibility claim that dynamic scheduling of ring-architecture jobs is practical. The doubling heuristic is a sensible addition to Optimus, because it avoids getting stuck on bad intermediate allocations (8→9 vs 8→16). That part is worth reading.

The soft spot is the scheduler simulation. Table 3's 'more than halving' comes from a simulator that predicts convergence using the same fitted model (Eq. 5) and 'data from previously completed runs' — effectively every simulated job is a copy of the ResNet-110 runs used to fit the model. There's no held-out workload, no second model/dataset, no error bars, and no code released. So the >2x improvement is not yet evidence about real workloads; it's an in-sample demonstration that the fitted curves favor the precompute/exploratory strategies. The paper itself hints at this in Section 9, saying future work will use 'real workloads with a simulated schedule rather than a simulated schedule with simulated workloads.' That's an honest acknowledgment that the current simulation is not a measured result.

Second issue: Table 2 reports steps and total epochs but not final validation accuracy. The learning-rate rescaling of Eq. 7 follows Goyal et al., but without accuracy numbers we can't tell if a resized run converges to the same quality. If the 4→8 runs finish at a worse optimum, 'faster completion' isn't apples-to-apples.

These concerns are not fatal. The direct feasibility evidence stands on its own. The simulation is an engineering extrapolation, not a measured claim. For a cluster-scheduling audience, this is a useful extension of Optimus to ring architectures with some concrete numbers. I'd bring it to a reading group. A serious referee should engage with it, but the burden should be on the authors to validate the scheduler on held-out workloads or with a real implementation. My recommendation: accept with major revision, not desk reject.

Referee Report

3 major / 5 minor

Summary. The paper argues that dynamic (elastic) scheduling of distributed deep learning jobs is feasible for ring-allreduce architectures, not just parameter-server architectures. It derives a resource-to-speed model f(w) in Eq. (5) and a convergence-in-epochs model in Eq. (1), formulates resource allocation as an NP-hard integer program, and proposes a doubling heuristic. Experiments with Horovod/ResNet-110 on CIFAR-10 measure 94.5% scaling efficiency from 4 to 8 GPUs and roughly 10 seconds of checkpoint/restart overhead. Using those runs, a scheduler simulation in Section 7 reports more than a halving of average job completion time under moderate contention relative to fixed 8-GPU scheduling. The direct experimental measurements support feasibility; the headline scheduling gain rests on an in-sample simulation that has not been validated on held-out workloads.

Significance. If the claims held, the paper would provide a useful feasibility result for dynamic resizing of ring-architecture training jobs and a concrete scheduling heuristic. The direct measurements—94.5% scaling efficiency and about 10 seconds of restart overhead—are credible and valuable on their own. The proposed model and doubling heuristic are well motivated by the communication structure of all-reduce. However, the central quantitative claim (more than halving of average job time) currently comes from a simulator that is fitted and evaluated on the same ResNet-110/CIFAR-10 workload, with no held-out jobs, no prediction-error analysis, and no report of final model accuracy. The paper therefore establishes feasibility but does not yet establish the magnitude of the scheduling benefit for new workloads; it is a solid basis for a major revision rather than an accept.

major comments (3)

[§7, Table 3] The more-than-halving claim is computed in-sample. The simulation predicts each job's convergence 'based on data from previously completed runs,' and those runs are the same ResNet-110/CIFAR-10 jobs used to fit the convergence model in Eq. (1) and the resource model in Eq. (5). With no held-out workload, no second model/dataset, and no reported prediction error, the comparison between Precompute and Eight may simply reflect the fitted curves rather than a general property of ring-architecture scheduling. Please validate the simulator on held-out jobs or at least report cross-validated prediction errors and error bars on the Table 3 entries.
[§6, Table 2] The resizing experiments do not report the quality of the converged model. Table 2 lists steps, epochs, and wall-clock time but no final validation accuracy or loss for the uninterrupted baselines or the checkpoint/resume runs. Since Eq. (7) changes the global batch size and learning rate at resume time, 'faster completion' is only an apples-to-apples comparison if the resumed runs reach the same final accuracy as the baselines. Please report the final validation accuracy for every row of Table 2, or explicitly state the convergence criterion used.
[§4.2, Eq. (6)] The doubling heuristic's motivating premise—that non-power-of-two allocations such as 9 GPUs have disproportionately worse per-GPU performance and can trap the Optimus greedy heuristic—is asserted but never measured in the paper. Table 1 profiles only 1, 2, 4, and 8 GPUs, and no experimental data are presented for w = 3, 5, 6, 7, etc. Consequently, the claimed advantage of the doubling heuristic over the Optimus greedy heuristic is not demonstrated by the evidence in this manuscript; at minimum, a sensitivity analysis or direct measurements for a few non-power-of-two configurations would be needed.

minor comments (5)

[§6, Table 2] The text says the 5k-stop experiment saves 'close to 50 min (~32%)' and the 10k-stop experiment saves 'close to 36 min (~23%)', but Table 2 gives 126 min for the 4-GPU baseline and 104 and 113 min for the resized runs, i.e., differences of 22 and 13 minutes. Please reconcile these numbers or correct the computation.
[Table 2] The header of Table 2 contains spacing and column-label errors ('# GP U sinit stepsstop #GP U snew stepstot epochs Ttot'), which make the table harder to read; please reformat the column names.
[§3.2, Eq. (5)] The sentence 'In all cases, we can fit a NNLS model for each value of w' is unclear: Eq. (5) is presented as a single functional form with coefficients θ0..θ3 learned from (w, f(w)) data points. Please clarify whether the θ coefficients are global or fitted separately for each w.
[§7] The description of the exploratory strategy ('gives a new job 8 GPUs for the first ten minutes to run for 2.5 minutes at each of 1, 2, 4 and 8 GPUs') is ambiguous about whether these are sequential or parallel runs and about how the measured speeds are aggregated. Please clarify.
[§5, Table 1] The paper reports a single profiling run per configuration and no variance or confidence intervals for the scaling efficiency or for the ~10 second restart overhead; adding repeat measurements would strengthen the direct feasibility claim.

Circularity Check

1 steps flagged · score 6.0 of 10

Simulated >2x scheduling gain is computed in-sample from the fitted speed/convergence models, so the headline result reduces to the fit; direct checkpoint measurements are non-circular.

fitted input called prediction [Section 7 (Scheduler simulation), Table 3; builds on Section 3.2 Eq. 5, Section 3.1 Eq. 1, and Section 4.1 t_j=Q_j/f(w_j)]
"Using data from the experimental runs we developed a simulation of a scheduler which allocates GPUs to jobs according to a scheduling strategy and predicts the convergence of those runs based on data from previously completed runs. ... f (w) is our resource model where θ’s are positive coefficients to be learned for each job. ... To learn the values of θ’s, we collect data points of the form (w, f (w))."

Section 4.1 defines every job's completion time as t_j = Q_j / f(w_j), where Q_j comes from the NNLS fit of Eq. 1 to the loss curve and f(w) comes from the NNLS fit of Eq. 5 to the measured (w, f(w)) points from the ResNet-110/CIFAR-10 runs. The Section 7 simulator then generates the simulated jobs' convergence and speed from the same previously completed runs, so the scheduler's model and the simulated ground truth are the same fitted functions by construction. Table 3's average completion times—including the claimed more than halving for Precompute over Eight under moderate contention—are therefore evaluations of the fitted curves, not predictions tested against held-out jobs or an independent workload model. The simulated gain is the model's own marginal gain optimized by Eq.

full rationale

The direct experimental results in Section 6 are self-contained and non-circular: Table 1 measures per-GPU forward/backward times, the paper reports 94.5% scaling efficiency from 4 to 8 GPUs, and Table 2 directly measures checkpoint-stop-restart times averaging ~10 seconds and completion-time savings of ~32% and ~23% when resuming with 8 GPUs. Those are real measurements, not derived from the fitted model. The circularity is confined to the load-bearing simulation claim in the abstract and Section 7: Eq. 5 is a parametric resource model fitted by NNLS to the same experimental runs used in the simulation, Eq. 1 is fitted to the same jobs' loss curves, and Section 4.1 computes completion times as Q_j/f(w_j). Because the simulator's 'actual' job behavior is generated from those same fitted equations, Table 3's more-than-halving result is in-sample by construction: the scheduler is evaluated against its own predictive model, with no held-out job set, no second workload, and no reported final validation accuracy to verify that Eq. 7's learning-rate rescaling preserves model quality. This is a partial circularity of the headline simulated gain, not of the paper's measured feasibility claims. There is no self-citation chain, no imported uniqueness theorem, and no renaming of a known result; the doubling heuristic and the scheduling formulation remain independent algorithmic content. The score is 6 because the central 'more than halving' claim reduces to the fitted inputs, while the direct measurements and the scheduling problem formulation still carry independent value.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central scheduler claim rests on a fitted speed model rather than a parameter-free derivation. The optimization takes the fitted f(w) as ground truth, and the simulation uses previously completed runs to predict completion, so the headline gain is conditional on the calibration generalizing. No new physical entities are introduced.

free parameters (2)

θ0, θ1, θ2, θ3 = not reported; fit per job with NNLS
Eq. 5's speed model f(w) is calibrated to measured run times. The scheduler objective and simulation treat these fitted coefficients as ground truth, so the headline gains are partly artifacts of the fit.
β0, β1, β2 = not reported; fit with NNLS, β0 > 0
Eq. 1 predicts remaining epochs Qj. No held-out error or comparison to actual convergence is reported.

assumptions (4)

domain assumption SGD loss converges as O(1/k), so the loss curve in Eq. 1 with NNLS-fitted β0, β1, β2 models remaining epochs to convergence Qj.
Section 3.1 relies on this functional form to predict when a job will finish; no validation on held-out jobs is shown.
domain assumption The all-reduce time equations for ring, doubling-halving, and binary blocks (Eqs. 2-4), taken from Rabenseifner and Thakur, apply to Horovod/NCCL/OpenMPI on the test cluster.
Eq. 5 collapses these equations into f(w); if the imported communication model is wrong for this stack, the fitted coefficients absorb the error but the scheduling conclusions may not transfer.
domain assumption Stopping, checkpointing, and restarting with more GPUs and the Eq. 7 learning-rate scaling preserves final model quality.
Section 6 reports epoch counts and wall-clock times but no final accuracies, so convergence equivalence is asserted rather than measured.
domain assumption Job arrivals follow a Poisson process and the simulated jobs resemble real DL cluster workloads.
Section 7 uses exponential inter-arrival times on a synthetic workload; the moderate-contention conclusion depends on this arrival model.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Dynamic Scheduling of MPI-based Distributed Deep Learning Training Jobs." pith.science (2026). https://pith.science/paper/ZUNPFERZ

@misc{pith2026190808082,
  author       = {Pith},
  title        = {Pith review of: Dynamic Scheduling of MPI-based Distributed Deep Learning Training Jobs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZUNPFERZ}},
  note         = {Machine review of arXiv:1908.08082}
}

read the original abstract

There is a general trend towards solving problems suited to deep learning with more complex deep learning architectures trained on larger training sets. This requires longer compute times and greater data parallelization or model parallelization. Both data and model parallelism have been historically faster in parameter server architectures, but data parallelism is starting to be faster in ring architectures due to algorithmic improvements. In this paper, we analyze the math behind ring architectures and make an informed adaptation of dynamic scheduling to ring architectures. To do so, we formulate a non-convex, non-linear, NP-hard integer programming problem and a new efficient doubling heuristic for its solution. We build upon Horovod: an open source ring architecture framework over TensorFlow. We show that Horovod jobs have a low cost to stop and restart and that stopping and restarting ring architecture jobs leads to faster completion times. These two facts make dynamic scheduling of ring architecture jobs feasible. Lastly, we simulate a scheduler using these runs and show a more than halving of average job time on some workload patterns.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[1]

write newline

" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...

work page
[2]

Abadi, P

M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Imple...

work page 2016
[3]

Goyal, P

P. Goyal, P. Doll \' a r, R. B. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR , abs/1706.02677, 2017, 1706.02677 http://arxiv.org/abs/1706.02677 . ://arxiv.org/abs/1706.02677

arXiv 2017
[4]

K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition (CVPR), 2016 , 2016

work page 2016
[5]

K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. ECCV , 2016, 1603.05027 http://arxiv.org/abs/1603.05027 . ://arxiv.org/abs/1603.05027

arXiv 2016
[6]

Krizhevsky

A. Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto , 05 2012

work page 2012
[7]

Nvidia collective communications library v2

Nvidia. Nvidia collective communications library v2. https://developer.nvidia.com/nccl, 2017

work page 2017
[8]

Open source high performance computing

OpenMPI. Open source high performance computing. https://www.open-mpi.org/, 2017

work page 2017

Show all 12 references

[9]

Y. Peng, Y. Bao, Y. Chen, C. Wu, and C. Guo. Optimus: an efficient dynamic resource scheduler for deep learning clusters. In Eurosys 2018, Proceedings of the 13th EuroSys Conference , 2018

2018
[10]

Rabenseifner

R. Rabenseifner. Optimization of collective reduction operations. International Conference on Computation Science , 2004

2004
[11]

Sergeev and M

A. Sergeev and M. D. Balso. Horovod: fast and easy distributed deep learning in tensorflow. CoRR , abs/1802.05799, 2018, 1802.05799 http://arxiv.org/abs/1802.05799 . ://arxiv.org/abs/1802.05799

2018 arXiv
[12]

Thakur and R

R. Thakur and R. Rabenseifner. Optimization of collective communication operations in mpich, 2005

2005

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

write newline

" write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...

work page

[2] [2]

Abadi, P

M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur, J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner, P. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu, and X. Zheng. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Imple...

work page 2016

[3] [3]

Goyal, P

P. Goyal, P. Doll \' a r, R. B. Girshick, P. Noordhuis, L. Wesolowski, A. Kyrola, A. Tulloch, Y. Jia, and K. He. Accurate, large minibatch SGD: training imagenet in 1 hour. CoRR , abs/1706.02677, 2017, 1706.02677 http://arxiv.org/abs/1706.02677 . ://arxiv.org/abs/1706.02677

arXiv 2017

[4] [4]

K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Computer Vision and Pattern Recognition (CVPR), 2016 , 2016

work page 2016

[5] [5]

K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. ECCV , 2016, 1603.05027 http://arxiv.org/abs/1603.05027 . ://arxiv.org/abs/1603.05027

arXiv 2016

[6] [6]

Krizhevsky

A. Krizhevsky. Learning multiple layers of features from tiny images. University of Toronto , 05 2012

work page 2012

[7] [7]

Nvidia collective communications library v2

Nvidia. Nvidia collective communications library v2. https://developer.nvidia.com/nccl, 2017

work page 2017

[8] [8]

Open source high performance computing

OpenMPI. Open source high performance computing. https://www.open-mpi.org/, 2017

work page 2017