Pith. sign in

REVIEW 3 major objections 5 minor 50 references

Prediction-Assisted Online Distributed Deep Learning Workload Scheduling in GPU Clusters

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

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

Pith's one-line read A prediction-assisted scheduler for mixed-parallelism deep learning jobs reduces total completion time by up to 92 percent by scheduling a virtual single machine with SRPT and using that order to place real jobs on GPUs.

desk verdict Plausible heuristic with strong experiments, but the Theorem 1 competitive-ratio proof has a real gap and should not be accepted as-is. read the letter →

arxiv 2501.05563 v1 pith:GA47CQIB submitted 2025-01-09 cs.DC cs.LG

Ziyue Luo , Jia Liu , Myungjin Lee , Ness B. Shroff This is my paper · ORCID
classification cs.DCcs.LG
keywords distributeddeeplearningGPUclusterschedulingmixedparallelismshortestremainingprocessingtimeonlineprediction-assistedgraphpartitioningrandomforestregression
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

The paper is trying to establish that a practical non-preemptive scheduler for distributed deep learning jobs with mixed parallelisms can be built by pretending the whole GPU cluster is a single machine. It argues that running preemptive SRPT on that virtual machine yields a sound ordering for placing real jobs onto GPUs, and that the resulting A-SRPT algorithm has a worst-case completion-time guarantee that degrades only linearly in the average training-iteration prediction error $\bar{\epsilon}$. If correct, this gives cluster schedulers a principled way to exploit the fact that most deep learning jobs recur, replacing user-supplied durations with learned predictions. The paper backs this with trace-driven testbed experiments and large-scale simulations reporting up to 92 percent reduction in total job completion time over existing schedulers.

What carries the argument

The argument is carried by four interacting pieces. Each job is modeled as a graph $\Omega=(V,E)$ whose vertices are stage replicas and whose edge weights are communication volumes, so placing a job becomes a graph-cut problem. Heavy-Edge is the greedy heuristic that co-locates the heaviest communicating replicas on the same server, favoring intra-server bandwidth. A random forest regression model predicts each job's training iterations $\tilde{n}_i$ from recurrent job metadata. The central reduction maps the cluster to a single machine: job $i$'s virtual duration is $(g_i/G)\tilde{n}_i\tilde{\alpha}_i^{\min}$, SRPT schedules that virtual instance preemptively, and the completion order guides real non-preemptive placements. The competitive-ratio proof, through Lemmas 1–3 and Theorem 1, connects the virtual optimum to the real optimum by bounding placement sensitivity with $\rho = \max_i \alpha_i^{\max}/\alpha_i^{\min}$ and prediction error with $\bar{\epsilon}$.

What would settle it

Run A-SRPT on a small cluster (say two GPUs) with a trace where the first pending job needs both GPUs while a queued single-GPU job could run, and count total idle GPU time. If the measured idle time exceeds the makespan term Lemma 2 allows, then the Theorem 1 bound is not supported for the algorithm as implemented, because the busy-GPU premise in Appendix B would be violated.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that the online non-preemptive DDLwMP scheduling problem can be approximated by a hypothetical single-machine preemptive instance in which each job's workload is scaled to $(g_i/G)\tilde{n}_i\tilde{\alpha}_i^{\min}$, scheduled by SRPT. The completion order of that virtual schedule is then used to dispatch real jobs onto GPUs, with communication-heavy jobs delayed and consolidated onto few servers while communication-light jobs are started immediately. Theorem 1 states that the resulting total completion time is within $(2+\tau+\rho G/(G-g_{\max}))\rho + 2\rho g_{\max}\bar{\rho}(1+\tau+(1+\rho)G/(G-g_{\max}))\bar{\epsilon}$ of optimal, so the guarantee degrades gracefully as average prediction error grows. The paper also claims its Heavy-Edge placement is near-optimal in practice, coming within 6 percent of an ILP solution while computing in milliseconds.

Load-bearing premise

The bound in Lemma 2 assumes that once jobs are placed, at least $G-g_{\max}$ GPUs stay continuously busy on those jobs, but Algorithm 1 can advance the clock without placing anything when the head job does not fit, so the proof's busy-GPU premise may not hold for the actual schedule.

Editorial extensions

If this is right

  • Cluster operators can use predicted training iterations from recurring jobs and still keep a provable worst-case bound that degrades only with average prediction error, not with the worst misprediction.
  • Communication-heavy jobs should be delayed until they can be consolidated onto few servers, while placement-insensitive jobs should be launched immediately to absorb fragmentation; A-SRPT encodes this split with a COMM_HEAVY threshold.
  • The reduction to a single-machine SRPT instance provides a template for adapting the scheduler to new parallelism types: only the graph model and the per-iteration time formula need to change.
  • In the paper's comparisons, the gap to a perfect-prediction version is small (7 percent in the testbed and 14 percent in simulation), indicating prediction quality is not the main bottleneck to realizing the reported gains.

Reading between the lines

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

  • Editorial inference: because the prediction model assigns zero iterations to unseen jobs, A-SRPT implicitly prioritizes first-time jobs; an ablation that reverses this choice would reveal how much of the reported gain comes from SRPT ordering versus this novelty bias.
  • Editorial inference: the competitive ratio depends on Heavy-Edge delivering placements close to $\tilde{\alpha}_i^{\min}$; replacing it with a weaker placement heuristic in the same experiments would quantify how much of the 92 percent gain comes from placement rather than scheduling order.
  • Editorial inference: the single-machine reduction suggests a direct extension to tensor and expert parallelism by re-weighting the graph edges for AllReduce and token-routing traffic, a direction the paper sketches but does not evaluate.
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.

Referee Report

3 major / 5 minor

Summary. The paper proposes A-SRPT, an online non-preemptive scheduler for distributed deep learning jobs with mixed parallelism (DDLwMP) in GPU clusters. It combines a graph-based placement heuristic (Heavy-Edge) with a random-forest predictor of training iterations, and maps the original cluster scheduling problem to a single-machine preemptive instance that is solved by SRPT. The central claims are a competitive-ratio bound (Theorem 1) that degrades with the average prediction error, and trace-driven experiments showing up to a 92% reduction in total job completion time over baselines.

Significance. If the competitive-ratio bound were established, this would be a useful addition to the DDL scheduling literature: it treats heterogeneous multi-GPU jobs with mixed parallelism, handles uncertain training durations through learned predictions, and separates placement (Heavy-Edge) from ordering (SRPT). The experimental study is reasonably thorough: a testbed using MIG, large-scale simulations over a 758k-job trace, comparison with five baselines, and a head-to-head evaluation of Heavy-Edge against ILP showing orders-of-magnitude speedup with only a small per-iteration training time penalty. The prediction model is evaluated on a held-out portion of the trace, and A-SRPT comes within 7% to 14% of a perfect-prediction variant. However, the main theoretical guarantee currently rests on an invalid proof step, and the workload trace is synthesized because model information is absent, so both the theoretical and the empirical claims need strengthening.

major comments (3)
  1. [Appendix B, Lemma 2] The proof of the makespan bound is invalid because it relies on the assertion that "with no further delays, we can ensure at least G−gmax GPUs are continuously busy for each job's training." Algorithm 1 does not enforce this invariant: line 25 advances time when the head of pending_queue cannot fit, so GPUs can remain idle even when later jobs in the queue could start, and a job running alone with g_i < G−gmax leaves more than gmax GPUs idle for its whole duration. Concretely, take G=100, gmax=50, τ=0, perfect predictions, and two jobs released at time 0: A with g=1, n=100000, αmax=1, and B with g=50, n=2000. In A1 both jobs have virtual processing time 1000; if ties are broken A before B, A-SRPT starts A at t=1000 and B at t=2000, so B finishes at 4000 and A at 101000. For i=B, the intermediate bound makespan_1 ≤ C_i(OPT_A1) + Σ_{j<i} g_j n_j αmax_j / (G−gmax) equals 2000 + 100000/50 = 4000, but the actual makespan of the first job is 101000. The final inequality of Lemma 2 is not violated in this instance, but the derivation of Eq. (12) is false, so Theorem 1 is not proven by the submitted argument.
  2. [Appendix C, Lemma 3 (Phase 2)] The exchange argument for underestimated jobs is under-specified. Inequality (14) compares total durations, but SRPT decisions depend on remaining processing times at the time of divergence, and the schedules may already have processed part of the jobs. After shortening ipred's duration, the SRPT schedule can change the entire subsequent order, so the statement that we "identify the subsequent time step t' ... and repeat" does not, by itself, establish the claimed decrease of at least Σ_{i∈U} (g_i/G) ϵ_i α~min_i in the objective. Since Lemma 3 is used in the proof of Theorem 1, this step needs a rigorous exchange argument or a direct citation to a lemma that already covers this transformation.
  3. [Section V-A-1-b and V-B] The trace-driven evaluation is synthetic in a way that materially limits the empirical claims. The two-month trace contains no DNN model information, so profiled models and their distributed configurations are randomly assigned to job groups, and the number of training iterations is obtained by dividing the trace duration by the estimated α~min_i. This procedure can create arbitrary correlations among iteration count, GPU demand, and communication pattern; the reported reductions (31% to 92% depending on setting) may therefore not transfer to actual DDLwMP workloads. The comparisons are internally fair because all algorithms see the same constructed workload, but the authors should at minimum report sensitivity to the random assignment (e.g., multiple seeds or an alternative model-to-group mapping) before claiming "real-world trace-driven" validation.
minor comments (5)
  1. [Theorem 1 proof] In the displayed algebra, the term I gmax αmax (1 + τ/G + (1+ρ)/(G−gmax)) ε should read I gmax αmax ((1+τ)/G + (1+ρ)/(G−gmax)) ε; the final bound in the next line uses the correct expression, so this is a typesetting error, but it makes the derivation hard to follow.
  2. [Algorithm 1 line 8 and Section IV-C-1] The condition in Algorithm 1 uses αmax_i / α~min_i ≥ COMM_HEAVY, while the text says the job is communication-heavy when the ratio "exceeds COMM_HEAVY (1.5)"; the threshold should be made consistent.
  3. [Section V-A-1-a] Because MIG vGPUs share the same PCIe interconnect, the testbed cannot exercise Heavy-Edge's placement decisions; the discussion should state more clearly that the testbed validates the SRPT ordering logic under a homogeneous interconnect, while placement benefits are supported only by the simulation study.
  4. [Section V-B-2-a] The large-scale simulation results are reported as single numbers without confidence intervals; since jobs are sampled from the trace, reporting the mean and spread over multiple random samples would make the comparisons more robust.
  5. [Fig. 4] The prediction-error histogram uses absolute iteration counts; adding a normalized (relative) error axis would make the accuracy of the random forest model more interpretable across jobs of very different lengths.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the competitive-ratio argument does not reduce to the prediction model or to a self-citation chain, so the derivation is self-contained for circularity purposes.

full rationale

The theoretical claim is not circular. Theorem 1 combines Lemmas 1-3 to bound the A-SRPT objective against the true optimal value O_PT_A plus an explicit additive term linear in the average prediction error. Lemma 1 is a scaling argument (each job in the virtual single-machine instance receives a fraction g_i/G of capacity); Lemma 3 is a standard perturbation argument that charges each prediction mistake by at most I*(g_i/G)*epsilon_i*alpha_min_i; and Lemma 2 attempts to bound the actual cluster makespan from the virtual SRPT completion order. None of these defines the predicted quantity as the output of the derivation, and the predictions enter only through the virtual durations, with the error term appearing as an independent cost: with perfect predictions the bound is already independent of the prediction model. The only self-cited building block is [20], used for pipeline-planning configurations and the analytic per-iteration time model; it is not used to force the scheduling result or to forbid alternatives. The reviewer's concern about Lemma 2 is a correctness gap: the bound assumes 'with no further delays, we can ensure at least G-gmax GPUs are continuously busy,' while Algorithm 1 can leave GPUs idle when the head-of-line job does not fit. However, a false or unsupported invariant is a proof gap, not an instance of input-output circularity, because the claimed bound is not equivalent to the model's fitted values by construction.

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

The central claim rests on modeling assumptions about pipeline training dynamics, a single-machine reduction that is not formally proven to preserve optimality, and an unstated continuous-busy premise in the competitive-ratio proof. The algorithm's own thresholds (COMM_HEAVY, tau) are free parameters but do not enter the main theoretical bound directly.

free parameters (2)
  • COMM_HEAVY threshold = 1.5
    Hand-chosen in Algorithm 1, Section IV-C-1, to split communication-heavy and non-communication-heavy jobs; no sensitivity analysis is provided.
  • delay factor tau = not specified for simulations; set to 0 in testbed
    Multiplier in the delay bound tau * gi/G * n-tilde_i * alpha-min_i (Algorithm 1, line 16). The value is not reported for simulations, and the testbed sets it to zero (Section V-A-1-a).
assumptions (5)
  • domain assumption Asynchronous pipeline per-iteration time equals the maximum per-stage computation-communication time (Eq. (7)).
    Adopted from PipeDream [9] and DAPPLE [25]; used throughout Section III-B to define alpha_i.
  • domain assumption Communication time formulas (4)-(6) for inter-stage and AllReduce operations are accurate.
    Standard analytical models from [20], [30], [31]; define the objective and the Heavy-Edge edge weights.
  • ad hoc to paper The single-machine instance A1 with job size gi/G * ni * alpha-min_i faithfully represents the cluster scheduling problem for ordering purposes.
    Introduced in Section IV-A; the mapping is a modeling choice, not a proven equivalence.
  • ad hoc to paper At least G-gmax GPUs are continuously busy in the schedule constructed from the A1-order.
    Assumed in Appendix B to bound the makespan of the first i-1 jobs; not enforced by Algorithm 1.
  • domain assumption Most DDL jobs recur and are predictable from group id and user id via random forest regression.
    Based on trace observations [6]; used to justify the prediction model in Section IV-C-3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Prediction-Assisted Online Distributed Deep Learning Workload Scheduling in GPU Clusters." pith.science (2026). https://pith.science/paper/GA47CQIB

@misc{pith2026250105563,
  author       = {Pith},
  title        = {Pith review of: Prediction-Assisted Online Distributed Deep Learning Workload Scheduling in GPU Clusters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GA47CQIB}},
  note         = {Machine review of arXiv:2501.05563}
}
read the original abstract

The recent explosive growth of deep learning (DL) models has necessitated a compelling need for efficient job scheduling for distributed deep learning training with mixed parallelisms (DDLwMP) in GPU clusters. This paper proposes an adaptive shortest-remaining-processing-time-first (A-SRPT) scheduling algorithm, a novel prediction-assisted online scheduling approach designed to mitigate the challenges associated with DL cluster scheduling. By modeling each job as a graph corresponding to heterogeneous Deep Neural Network (DNN) models and their associated distributed training configurations, A-SRPT strategically assigns jobs to the available GPUs, thereby minimizing inter-server communication overhead. Observing that most DDLwMP jobs recur, A-SRPT incorporates a random forest regression model to predict training iterations. Crucially, A-SRPT maps the complex scheduling problem into a single-machine instance, which is addressed optimally by a preemptive "shortest-remaining-processing-time-first" strategy. This optimized solution serves as a guide for actual job scheduling within the GPU clusters, leading to a theoretically provable competitive scheduling efficiency. We conduct extensive real-world testbed and simulation experiments to verify our proposed algorithms.

Figures

Figures reproduced from arXiv: 2501.05563 by the authors.

Figure 1
Figure 1. Three typical parallelisms for distributed DNN training. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. GPU mapping: An illustrative example. server may be occupied by existing jobs). We now map each stage replica of job i to a GPU, with the goal to reduce inter￾server communication to improve job training efficiency. Toward this end, we model each job i as a graph Ω = (V, E), where vertices V represent stage replicas and edges E denote data communication, with edge weights indicating communi￾cation data size. For int… view at source ↗
Figure 3
Figure 3. Algorithmic idea overview. single-machine preemptive online scheduling problem A1, sharing A’s job set. In A1, the number of training iterations for job i is scaled to gi G ni , while the arrival time ri is kept unchanged. As the actual per-iteration training time αi of a job can only be obtained after placement, to estimate the job’s GPU requirements and its minimum attainable per-iteration training time, we optimi… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Percentage of jobs: different prediction errors. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Testbed experiment performance. configuration. Otherwise, if the job group demands more than one GPU, we randomly select a model and one of its training configurations for the group. The number of job training iterations is computed by dividing the job duration in the …
Figure 6
Figure 6. Figure 6: Total job completion time comparisons with differ￾ent numbers of jobs. 0% 20% 40% 60% 80% Single-GPU Job Percentage 0 1 2 3 4 Total Job Completion Time (sec) 1e12 A-SRPT SPJF SPWF WCS-Duration WCS-Workload WCS-SubTime [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

50 extracted references · 43 canonical work pages

  1. [1]

    Language Models Are Few-Shot Learners,

    T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askellet al., “Language Models Are Few-Shot Learners,” arXiv preprint arXiv:2005.14165 , 2020

    arXiv 2005

  2. [2]

    Deep Residual Learning for Image Recognition,

    K. He, X. Zhang, S. Ren, and J. Sun, “Deep Residual Learning for Image Recognition,” in Proc. of IEEE CVPR , 2016

    work page 2016

  3. [3]

    AuTO: Scaling Deep Reinforcement Learning for Datacenter-Scale Automatic Traffic Opti- mization,

    L. Chen, J. Lingys, K. Chen, and F. Liu, “AuTO: Scaling Deep Reinforcement Learning for Datacenter-Scale Automatic Traffic Opti- mization,” in Proc. of ACM SIGCOMM , 2018

    work page 2018

  4. [4]

    Gandiva: Introspective Cluster Scheduling for Deep Learning,

    W. Xiao, R. Bhardwaj, R. Ramjee, M. Sivathanu, N. Kwatra, Z. Han, P. Patel, X. Peng, H. Zhao, Q. Zhang et al. , “Gandiva: Introspective Cluster Scheduling for Deep Learning,” in Proc. of USENIX OSDI, 2018

    work page 2018

  5. [5]

    Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning,

    A. Qiao, S. K. Choe, S. J. Subramanya, W. Neiswanger, Q. Ho, H. Zhang, G. R. Ganger, and E. P. Xing, “Pollux: Co-adaptive Cluster Scheduling for Goodput-Optimized Deep Learning,” in Proc. of USENIX OSDI, 2021

    work page 2021

  6. [6]

    MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters,

    Q. Weng, W. Xiao, Y . Yu, W. Wang, C. Wang, J. He, Y . Li, L. Zhang, W. Lin, and Y . Ding, “MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters,” in Proc. of USENIX NSDI , 2022

    work page 2022

  7. [7]

    Scaling Distributed Machine Learning with the Parameter Server,

    M. Li, D. G. Andersen, J. W. Park, A. J. Smola, A. Ahmed, V . Josifovski, J. Long, E. J. Shekita, and B.-Y . Su, “Scaling Distributed Machine Learning with the Parameter Server,” in Proc. of USENIX OSDI , 2014

    work page 2014

  8. [8]

    Megatron-LM: Training Multi-Billion Parameter Language Mod- els Using GPU Model Parallelism,

    M. Shoeybi, M. Patwary, R. Puri, P. LeGresley, J. Casper, and B. Catan- zaro, “Megatron-LM: Training Multi-Billion Parameter Language Mod- els Using GPU Model Parallelism,” arXiv preprint arXiv:1909.08053 , 2019

    arXiv 1909

Show all 50 references
  1. [9]

    PipeDream: Generalized Pipeline Parallelism for DNN Training,

    D. Narayanan, A. Harlap, A. Phanishayee, V . Seshadri, N. R. Devanur, G. R. Ganger, P. B. Gibbons, and M. Zaharia, “PipeDream: Generalized Pipeline Parallelism for DNN Training,” in Proc. of ACM SOSP , 2019

    2019

  2. [10]

    Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation,

    Z. Han, H. Tan, S. H.-C. Jiang, X. Fu, W. Cao, and F. C. Lau, “Scheduling Placement-Sensitive BSP Jobs with Inaccurate Execution Time Estimation,” in Proc. of IEEE INFOCOM . IEEE, 2020

    2020

  3. [11]

    Communication Contention Aware Scheduling of Multiple Deep Learning Training Jobs,

    Q. Wang, S. Shi, C. Wang, and X. Chu, “Communication Contention Aware Scheduling of Multiple Deep Learning Training Jobs,” arXiv preprint arXiv:2002.10105, 2020

    2002 arXiv

  4. [12]

    On Scheduling Ring-All-Reduce Learning Jobs in Multi-Tenant GPU Clusters with Communication Contention,

    M. Yu, B. Ji, H. Rajan, and J. Liu, “On Scheduling Ring-All-Reduce Learning Jobs in Multi-Tenant GPU Clusters with Communication Contention,” in Proc. of ACM MobiHoc , 2022

    2022

  5. [13]

    AutoML to Date and Beyond: Challenges and Opportunities,

    S. K. Karmaker, M. M. Hassan, M. J. Smith, L. Xu, C. Zhai, and K. Veeramachaneni, “AutoML to Date and Beyond: Challenges and Opportunities,” ACM Computing Surveys (CSUR) , vol. 54, no. 8, pp. 1–36, 2021

    2021

  6. [14]

    Tiresias: A GPU Cluster Manager for Distributed Deep Learning,

    J. Gu, M. Chowdhury, K. G. Shin, Y . Zhu, M. Jeon, J. Qian, H. Liu, and C. Guo, “Tiresias: A GPU Cluster Manager for Distributed Deep Learning,” in Proc. of USENIX NSDI , 2019

    2019

  7. [15]

    NVIDIA NVLink , https://www.nvidia.com/en-us/data-center/nvlink/

  8. [16]

    Random Forests,

    L. Breiman, “Random Forests,” Machine learning , vol. 45, pp. 5–32, 2001

    2001

  9. [17]

    Sequencing and Scheduling: Algorithms and Complexity,

    E. Lawler, J. Lenstra, A. R. Kan, and D. Shmoys, “Sequencing and Scheduling: Algorithms and Complexity,” Handbook in Operations Re- search and Management Science: Logistics of Production and Inventory , vol. 4, 1993

    1993

  10. [18]

    Goodfellow, Y

    I. Goodfellow, Y . Bengio, and A. Courville, Deep Learning. MIT press, 2016

    2016

  11. [19]

    GPipe: Efficient Training of Giant Neural Networks Using Pipeline Parallelism,

    Y . Huang, Y . Cheng, A. Bapna, O. Firat, D. Chen, M. Chen, H. Lee, J. Ngiam, Q. V . Le, Y . Wu et al. , “GPipe: Efficient Training of Giant Neural Networks Using Pipeline Parallelism,” in Proc. of NeurIPS, 2019

    2019

  12. [20]

    Efficient Pipeline Planning for Expedited Distributed DNN Training,

    Z. Luo, X. Yi, G. Long, S. Fan, C. Wu, J. Yang, and W. Lin, “Efficient Pipeline Planning for Expedited Distributed DNN Training,” in Proc. of IEEE INFOCOM . IEEE, 2022

    2022

  13. [21]

    Horovod: Fast and Easy Distributed Deep Learning in TensorFlow,

    A. Sergeev and M. Del Balso, “Horovod: Fast and Easy Distributed Deep Learning in TensorFlow,” arXiv preprint arXiv:1802.05799 , 2018

    2018 arXiv

  14. [22]

    Two-Tree Algorithms for Full Bandwidth Broadcast, Reduction And Scan,

    P. Sanders, J. Speck, and J. L. Traff, “Two-Tree Algorithms for Full Bandwidth Broadcast, Reduction And Scan,” Parallel Computing, vol. 35, no. 12, pp. 581–594, 2009

    2009

  15. [23]

    GADGET: Online Resource Optimization for Scheduling Ring-All-Reduce Learning Jobs,

    M. Yu, Y . Tian, B. Ji, C. Wu, H. Rajan, and J. Liu, “GADGET: Online Resource Optimization for Scheduling Ring-All-Reduce Learning Jobs,” in Proc. of IEEE INFOCOM . IEEE, 2022

    2022

  16. [24]

    Massively Scale Your Deep Learning Training with NCCL 2.4 , https://developer.nvidia.com/blog/ massively-scale-deep-learning-training-nccl-2-4/

  17. [25]

    DAPPLE: A Pipelined Data Parallel Approach for Training Large Models,

    S. Fan, Y . Rong, C. Meng, Z. Cao, S. Wang, Z. Zheng, C. Wu, G. Long, J. Yang, L. Xia et al., “DAPPLE: A Pipelined Data Parallel Approach for Training Large Models,” in Proc. of ACM PPoPP , 2021, pp. 431–445

    2021

  18. [26]

    Memory-Efficient Pipeline-Parallel DNN Training,

    D. Narayanan, A. Phanishayee, K. Shi, X. Chen, and M. Zaharia, “Memory-Efficient Pipeline-Parallel DNN Training,” in Proc. of ICML , 2021

    2021

  19. [27]

    Optimus: An Efficient Dynamic Resource Scheduler for Deep Learning Clusters,

    Y . Peng, Y . Bao, Y . Chen, C. Wu, and C. Guo, “Optimus: An Efficient Dynamic Resource Scheduler for Deep Learning Clusters,” in Proc. of EuroSys, 2018

    2018

  20. [28]

    When Will My ML Job Finish? Toward Providing Completion Time Es- timates through Predictability-Centric Scheduling,

    A. B. Faisal, N. Martin, H. M. Bashir, S. Lamelas, and F. R. Dogar, “When Will My ML Job Finish? Toward Providing Completion Time Es- timates through Predictability-Centric Scheduling,” in Proc. of USENIX OSDI, 2024

    2024

  21. [29]

    Scheduling with Untrusted Predictions,

    E. Bampis, K. Dogeas, A. V . Kononov, G. Lucarelli, and F. Pascual, “Scheduling with Untrusted Predictions,” in Proc. of IJCAI , 2022

    2022

  22. [30]

    Piper: Multidi- mensional Planner for DNN Parallelization,

    J. M. Tarnawski, D. Narayanan, and A. Phanishayee, “Piper: Multidi- mensional Planner for DNN Parallelization,” in Proc. of NeuIPS , 2021

    2021

  23. [31]

    Performance reported by NCCL tests , https://github.com/NVIDIA/ nccl-tests/blob/master/doc/PERFORMANCE.md

  24. [32]

    A Generic Communication Scheduler for Distributed DNN Training Acceleration,

    Y . Peng, Y . Zhu, Y . Chen, Y . Bao, B. Yi, C. Lan, C. Wu, and C. Guo, “A Generic Communication Scheduler for Distributed DNN Training Acceleration,” in Proc. of ACM SOSP , 2019, pp. 16–29

    2019

  25. [33]

    A Sum-Of-Ratios Multi-Dimensional- Knapsack Decomposition for DNN Resource Scheduling,

    M. Yu, C. Wu, B. Ji, and J. Liu, “A Sum-Of-Ratios Multi-Dimensional- Knapsack Decomposition for DNN Resource Scheduling,” in Proc. of IEEE INFOCOM , 2021

    2021

  26. [34]

    Approximate Algorithms for Scheduling Parallelizable Tasks,

    J. Turek, J. L. Wolf, and P. S. Yu, “Approximate Algorithms for Scheduling Parallelizable Tasks,” in Proc. of ACM SPAA , 1992

    1992

  27. [35]

    Balanced Graph Partitioning,

    K. Andreev and H. R ¨acke, “Balanced Graph Partitioning,” in Proc. of ACM Symposium on Parallelism in Algorithms and Architectures , 2004

    2004

  28. [36]

    Approximation Techniques for Average Completion Time Scheduling,

    C. Chekuri, R. Motwani, B. Natarajan, and C. Stein, “Approximation Techniques for Average Completion Time Scheduling,” SIAM Journal on Computing , vol. 31, no. 1, pp. 146–166, 2001

    2001

  29. [37]

    Pytorch: An Imperative Style, High-Performance Deep Learning Library,

    A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga et al. , “Pytorch: An Imperative Style, High-Performance Deep Learning Library,” in Proc. of NeurIPS , 2019

    2019

  30. [38]

    NVIDIA Multi-Instance GPU , https://www.nvidia.com/en-us/ technologies/multi-instance-gpu/

  31. [39]

    ImageNet: A Large-Scale Hierarchical Image Database,

    J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei, “ImageNet: A Large-Scale Hierarchical Image Database,” in Proc. of IEEE CVPR , 2009

    2009

  32. [40]

    Know What You Don’t Know: Unanswerable Questions for SQuAD,

    P. Rajpurkar, R. Jia, and P. Liang, “Know What You Don’t Know: Unanswerable Questions for SQuAD,” arXiv preprint arXiv:1806.03822, 2018

    2018 arXiv

  33. [41]

    Very Deep Convolutional Networks for Large-Scale Image Recognition,

    K. Simonyan and A. Zisserman, “Very Deep Convolutional Networks for Large-Scale Image Recognition,” arXiv preprint arXiv:1409.1556 , 2014

    2014 arXiv

  34. [42]

    Rethinking the Inception Architecture for Computer Vision,

    C. Szegedy, V . Vanhoucke, S. Ioffe, J. Shlens, and Z. Wojna, “Rethinking the Inception Architecture for Computer Vision,” in Proc. of IEEE CVPR, 2016

    2016

  35. [43]

    BERT: Pre-Training of Deep Bidirectional Transformers for Language Understanding,

    J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-Training of Deep Bidirectional Transformers for Language Understanding,” arXiv preprint arXiv:1810.04805, 2018

    2018 arXiv

  36. [44]

    XLNet: Generalized Autoregressive Pretraining for Language Understanding,

    Z. Yang, Z. Dai, Y . Yang, J. Carbonell, R. R. Salakhutdinov, and Q. V . Le, “XLNet: Generalized Autoregressive Pretraining for Language Understanding,” in Proc. of NeurIPS , 2019

    2019

  37. [45]

    Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer,

    C. Raffel, N. Shazeer, A. Roberts, K. Lee, S. Narang, M. Matena, Y . Zhou, W. Li, and P. J. Liu, “Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer,” The Journal of Machine Learning Research, vol. 21, no. 1, pp. 5485–5551, 2020

    2020

  38. [46]

    Exploiting Large System Dynamics for Designing Simple Data Center Schedulers,

    Y . Zheng, N. B. Shroff, R. Srikant, and P. Sinha, “Exploiting Large System Dynamics for Designing Simple Data Center Schedulers,” in Proc. of IEEE INFOCOM , 2015

    2015

  39. [47]

    Pipeline Parallelism for DNN Inference with Practical Performance Guarantees,

    A. Archer, M. Fahrbach, K. Liu, and P. Prabhu, “Pipeline Parallelism for DNN Inference with Practical Performance Guarantees,” arXiv preprint arXiv:2311.03703, 2023

    2023 arXiv

  40. [48]

    Gurobi Optimizer, https://www.gurobi.com/

  41. [49]

    Tutel: Adaptive Mixture-of-Experts at Scale,

    C. Hwang, W. Cui, Y . Xiong, Z. Yang, Z. Liu, H. Hu, Z. Wang, R. Salas, J. Jose, P. Ram et al. , “Tutel: Adaptive Mixture-of-Experts at Scale,” Proc. of MLSys , vol. 5, 2023

    2023

  42. [50]

    On the Opportunities and Risks of Foundation Models,

    R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill et al. , “On the Opportunities and Risks of Foundation Models,” arXiv preprint arXiv:2108.07258, 2021. APPENDIX A PROOF OF LEMMA 1 Proof. Let {c∗ i } be t...

    2021 arXiv

Pith tools

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