Pith. sign in

REVIEW 3 major objections 5 minor 3 cited by

Trivance completes AllReduce in the theoretical minimum of log₃ n steps on bidirectional rings and tori, with one-third the congestion of Bruck's algorithm.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-02 22:17 UTC pith:6MWTZEUI

load-bearing objection New AllReduce pattern that hits log_3 n with 3x lower congestion than Bruck, but the arbitrary-n generalization is unproven and inconsistent, and the evaluation relies on it. the 3 major comments →

arxiv 2602.17254 v2 pith:6MWTZEUI submitted 2026-02-19 cs.DC cs.NI

Trivance: Latency-Optimal AllReduce by Shortcutting Multiport Networks

Anton Juerss , Vamsi Addanki , Stefan Schmid This is my paper
classification cs.DC cs.NI
keywords AllReducecollective communicationlatency-optimal algorithmbidirectional ringtorus networkcongestionReduce-ScatterAllGather
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

Trivance is an AllReduce algorithm—the collective operation that sums data, such as gradients, across all nodes of a cluster—designed for torus and ring topologies where each node has two bidirectional ports. The paper's central claim is that Trivance completes AllReduce in ⌈log₃ n⌉ communication steps, the theoretical lower bound, while incurring roughly one-third the link congestion of Bruck's algorithm, the only other latency-optimal scheme. The trick is to use both ports in every step: each node sends and receives simultaneously to peers at tripling distances (1, 3, 9, …) and merges both incoming streams before forwarding. If the claim holds, latency-optimal AllReduce no longer requires the one-directional, congestion-heavy routing of Bruck; the same step count is reached with even link utilization. The paper proves the step bound for ring sizes that are powers of three, gives a construction for other sizes, extends the pattern to multidimensional tori, and reports packet-level simulations showing 5–30% faster completion for small and intermediate message sizes.

Core claim

The discovery is a communication pattern in which, at step k, every node exchanges data with partners at distance 3^k in both ring directions, so the set of nodes any single node has heard from triples in radius each step. Because both ports are used and the two incoming messages are reduced together before the result is forwarded, the pattern covers all n nodes in ⌈log₃ n⌉ steps, matching the known lower bound for bidirectional two-port networks. The paper proves this for n=3^s and reports that the latency-optimal variant has congestion Θ(n/2) against Bruck's Θ(3n/2); the bandwidth-optimal variant (a Reduce-Scatter followed by AllGather) transmits the minimal m(1−1/n) bytes per node per pha

What carries the argument

The mechanism is the simultaneous bidirectional peer exchange with distance ρ(k)=3^k: each node's partners are π(r,k,n)=(r−3^k mod n, r+3^k mod n), and the two arriving streams are jointly reduced before being forwarded. The latency proof rests on the disjoint-range lemma: after step k a node holds data from a contiguous radius R_k=Σ_{i=0}^k 3^i=(3^{k+1}−1)/2, and the two partners' known ranges partition the ring interval between them without overlap, so the radius triples each step. This joint reduction distinguishes Trivance from mirroring approaches that run two independent collectives in opposite directions, and the uniform reach in both directions is what cuts congestion by a factor of

Load-bearing premise

The proof that each node's known-data range triples every step depends on the two communication partners holding disjoint, complementary subsets of the nodes between them—a property established only for ring sizes that are exact powers of three, and merely asserted for other sizes.

What would settle it

On a ring of 7 nodes (a non-power-of-three size the paper itself uses in Figure 4), trace Trivance's latency-optimal pattern for two steps: node 0's final-step peers are at distance 2 per the figure, but §4.4's formula ⌈(3^2−7)/2⌉=1 per the text. Simulate or hand-trace the block-propagation recursion to see whether every node actually obtains all 7 blocks after ⌈log₃ 7⌉=2 steps; any node missing a block falsifies the general latency-optimality claim for arbitrary n.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • On ring sizes that are powers of three, Trivance reaches the log₃ n step lower bound with Θ(n/2) congestion, one third of Bruck's, so latency-bound AllReduce completes faster at equal offered load.
  • The bandwidth-optimal variant finishes Reduce-Scatter and AllGather in 2·log₃ n steps while moving the minimal m(1−1/n) bytes per phase, giving Δ=1 and Λ=2.
  • On D-dimensional tori, running D concurrent Trivance collectives preserves the log₃ n step count while transmission-delay optimality approaches the ideal mβ/D; the paper's closed-form factors are 1.33 for D=2, 1.08 for D=3, and 1.02 for D=4.
  • Simulated completion times improve 5–30% for message sizes up to 8 MiB on 2D tori, up to 32 MiB in high-bandwidth networks, and up to 128 MiB on 3D tori, with Trivance the best latency-optimal algorithm in every configuration.
  • Because the pattern maps onto standard asynchronous MPI primitives (Isend, Irecv, Waitall), it can be dropped into existing communication libraries without special hardware.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same two-port joint-reduction pattern should generalize to other collectives (AllGather, Reduce, Broadcast) and to any regular topology with at least two ports per node, not just tori; if the disjoint-range property holds there, the log₃ n latency bound would follow more broadly.
  • The arbitrary-n construction is the fragile point: the latency proof is only for powers of three, and the final-step distance formula in §4.4 appears inconsistent with the n=7 example in Figure 4 (the text says distance 2 while the formula gives 1). A reader should verify the pattern on small non-power-of-three rings before relying on the general ⌈log₃ n⌉ claim.
  • The congestion analysis is an average over links; in a real switch with flow control, the simultaneous tripling of distances each step might create transient hotspots even though average utilization is uniform. That is an empirical question the packet-level simulation starts to address but does not fully settle.
  • Since the advantage is largest when messages are small and links are fast, combining Trivance with in-network aggregation or with congestion-aware scheduling could extend its gains into larger-message regimes; that combination is not explored in the paper.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. Trivance proposes a bidirectional AllReduce algorithm for ring and torus topologies that claims to achieve the latency-optimal log_3 n step bound while reducing congestion relative to Bruck. The algorithm uses both ports in every step, communicating at distances 3^k and performing joint reductions on both incoming messages. The paper derives analytical step, bandwidth, and transmission-delay bounds, gives a proof of latency-optimality for powers of three, extends the pattern to multidimensional tori, and validates the claims with packet-level SST simulations on rings, 2D tori, and 3D tori. The central stated contribution is a latency-optimal AllReduce that preserves bandwidth-optimality and improves congestion by a factor of three over Bruck.

Significance. If the general-size claims can be established, this is a meaningful contribution: a latency-optimal bidirectional AllReduce pattern with congestion Θ=n/2 in the power-of-three case, versus 3n/2 for Bruck, together with a natural multidimensional extension. The paper has no fitted parameters: the analytical bounds follow from the communication pattern under the standard Hockney-style congestion-aware model, and the SST simulation is an independent empirical check. The power-of-three proof is essentially sound (modulo an arithmetic typo in the appendix), and the multidimensional transmission-delay tables are a useful reference. The main risk is the arbitrary-size extension, which is currently unproven and, as stated, inconsistent with the paper's own n=7 example.

major comments (3)
  1. [§4.4 / Appendix A / Theorem 4.3] The latency-optimality proof covers only n=3^s. Appendix A's induction is valid for that case, but Theorem 4.3 is stated for arbitrary n, and the paper's evaluations use power-of-two sizes. For n=7 the extension is not merely unproven: with the proposed final-step distance d=1, node 0's step-0 peers are 1 and 6, so after the first step it knows blocks {0,1,6}; the second exchange at distance 1 again contacts 1 and 6, whose post-step-0 knowledge adds only blocks {2,5}, leaving blocks 3 and 4 unreceived. A corrected coverage proof for all n, or an explicit restriction of the theorem to n=3^s, is required.
  2. [§4.4, final-step formula and Figure 4] The arbitrary-size rule is internally inconsistent. The text and Figure 4 require final distance 2 for n=7, but the displayed formula ⌈(3^{⌈log_3 7⌉}−7)/2⌉ = ⌈(9−7)/2⌉ = 1. The preceding sentence, which says the distance increases by one for each two nodes exceeding 3^{⌊log_3 n⌋}, would give 2, but the formula does not. Since the simulation section evaluates n=8, 64, 32×32, and 16×16×16 — all non-powers of three — the implemented rule must be specified precisely and proven; otherwise the empirical results cannot be attributed to the described algorithm.
  3. [Table 1 and §6 power-of-two evaluation] The headline congestion comparison Θ=n/2 for Trivance(L) versus 3n/2 for Bruck(L) is derived from the geometric sum for n=3^s. For the evaluated power-of-two sizes, no derivation is given, and the value depends on the unproven arbitrary-n extension. The abstract's '50% improvement' step claim and the factor-three congestion reduction are therefore overstated as general claims. Please provide a proof for arbitrary n, or clearly re-state all such claims as applying to n=3^s and re-evaluate the power-of-two cases accordingly.
minor comments (5)
  1. [Appendix A] In the contradiction step, R_{s-1} is written as 3^{s-1}/2; the correct value is (3^s−1)/2, matching the diameter of the n=3^s ring.
  2. [§6.1, §6.2] Figure references are inconsistent: the text refers to 'Fig. 8' for ring results and 'Fig. 6.2' for bandwidth impact, while the actual figures are numbered differently. Please align all cross-references.
  3. [References] There are duplicate references: [1] and [16] are the same SST simulator paper, and [19], [20], [21] are the same TPUv4 paper. Please consolidate.
  4. [Abstract and §4.4] The text often says 'log_3 n steps' when for arbitrary n it should be '⌈log_3 n⌉ steps' (and for n=3^s exactly log_3 n). The notation in §4.4 uses both floor and ceiling; please make the step-count convention uniform.
  5. [Algorithm 1] The recursive BlockPropagation function with a for-loop over k from step to ⌈log_3 n⌉−1 is hard to follow; the base case returns if step ≥ ⌈log_3 n⌉, and the recursive calls use k+1. Please rewrite with a clearer base/recursion structure or inline the expansion.

Circularity Check

0 steps flagged

No circularity: Trivance's latency and congestion bounds are analytically derived from its explicit communication pattern; the arbitrary-n proof gap is a correctness issue, not a circular one.

full rationale

I walked the derivation chain. The central claims are: (i) the log_3 n step count, justified by Lemma 4.2/Theorem 4.3 plus Appendix A; (ii) congestion Theta = n/2 vs Bruck's 3n/2, computed from per-step congestion 3^k and geometric sums; (iii) bandwidth-optimality from m(1 - 3^{-s}) per phase. None of these reduce to fitted parameters or to definitions of the target quantities. The lower bound log_{2D+1} n and log_3 n are imported from external prior work (Chan et al. [8]; Bruck et al. [5]), not from the authors' own prior results. There are no load-bearing self-citations, no ansatz smuggled via an author citation, and no renamed empirical pattern: the communication pattern is specified explicitly as peers at distance 3^k in both directions with joint reduction. The SST simulations are an independent packet-level validation and do not feed fitted constants back into the analysis. The genuine weakness in this paper is not circularity. Appendix A proves Theorem 4.3 only for n = 3^s (the contradiction step uses R_{s-1} = (n-1)/2 as the ring diameter), and Section 4.4's arbitrary-n final-distance rule is internally inconsistent: for n=7 the formula gives ceil((3^2-7)/2)=1, while the text and Figure 4 specify a final distance of 2. This is an unproven generalization and a potential correctness gap for the power-of-two sizes used in the evaluation, but it is not a case where the prediction is equivalent to the input by construction. Therefore the circularity score is 0.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 0 invented entities

No fitted parameters. The algorithm's step count and congestion are derived from the communication pattern; the only inputs are network size n and standard Hockney constants. The axioms are standard hardware and mathematical assumptions.

axioms (4)
  • domain assumption Each node can send and receive one message per port per step (2 ports on a ring, 2D ports on a D-dimensional torus).
    Used throughout §4; required for simultaneous left/right communication. This is a hardware capability assumption.
  • domain assumption The Hockney cost model C(m)=α + m·β applies and per-step startup latency α is additive.
    Eq. (1) in §2.1 forms the basis of all analytical comparisons.
  • standard math The lower bound of ⌈log_{2D+1} n⌉ steps for AllReduce on D-dimensional tori (Chan et al.) is accepted as the optimal latency.
    Used in §2.3 to define latency-optimality and to claim Trivance is optimal.
  • standard math Reduction operations are associative and commutative, so partial reductions can be combined and forwarded.
    Needed for the joint reductions in §4.2; not stated explicitly but assumed throughout.

pith-pipeline@v1.3.0-alltime-deepseek · 20843 in / 22035 out tokens · 184068 ms · 2026-08-02T22:17:15.900697+00:00 · methodology

0 comments
read the original abstract

AllReduce is a fundamental collective communication operation in distributed computing and a key performance bottleneck for large-scale training and inference. Its completion time is determined by the number of communication steps, which dominate latency-sensitive workloads, and the communication distance affecting both latency- and bandwidth-bound regimes. Direct-connect topologies, such as Google's TPUv4 tori, are particularly prone to large communication distances due to limited bisection bandwidth. In this paper, we present Trivance, a novel AllReduce algorithm that completes within $\log_3 n$ steps - a 50% improvement in comparison to Swing and Recursive Doubling, while reducing congestion compared to Bruck's algorithm by a factor of three and preserving bandwidth-optimality. Trivance exploits both transmission ports of a bidirectional ring within each step to triple the communication distance along both directions simultaneously. By performing joint reductions, Trivance improves both the number of steps and network congestion. We further show that Trivance extends naturally to multidimensional torus networks, retaining its latency advantage while achieving performance comparable to bandwidth-optimal algorithms for large AllReduce sizes. Our packet-level SST simulation shows that Trivance improves state-of-the-art approaches by 5-30% for AllReduce sizes up to 8 MiB, in high-bandwidth settings up to 32 MiB and for 3D tori up to 128 MiB. Throughout the evaluation, Trivance remains the best-performing latency-optimal algorithm.

Figures

Figures reproduced from arXiv: 2602.17254 by Anton Juerss, Stefan Schmid, Vamsi Addanki.

Figure 1
Figure 1. Figure 1: Compared to Recursive Doubling, Trivance completes in log3 𝑛 steps by leveraging both ports for joint reductions and tripled communication distance per step. Congestion is reduced by factor three compared to Bruck. Doubling takes three steps and incurs congestion from four overlapping transmissions in its final step. In comparison, Bruck’s algorithm completes in two communication steps, but induces more li… view at source ↗
Figure 2
Figure 2. Figure 2: Progression of received blocks at node 𝑟 from step 𝑘 to step 𝑘 + 1, acquiring the blocks of nodes 𝑝 and 𝑞 along with their neighbors, tripling the known data. step and reducing the communication distance by a factor of three. By the end of this phase, every node holds the complete global reduction result. 4.2 Latency-Optimal Algorithm By following the same communication pattern as the bandwidth-optimal ver… view at source ↗
Figure 3
Figure 3. Figure 3: Progression of received blocks for each node on [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: First two steps of Trivance AllReduce for a square torus of size 𝑛 = 81. Green arrows show the original collective; purple the mirrored collective. for 9 nodes. For 7 nodes, two steps are also required despite the smaller network size. The communication distance in the final step is only two (shorter than in the 9-node case) which leads to less communication collisions. Additionally, fewer blocks are trans… view at source ↗
Figure 4
Figure 4. Figure 4: Trivance AllReduce for networks of size 7 (left) and 9 (right) [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 6
Figure 6. Figure 6: AllReduce completion time comparison of state [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: , where the latency improvement of Trivance for small messages is similar to [PITH_FULL_IMAGE:figures/full_fig_p010_7.png] view at source ↗
Figure 6
Figure 6. Figure 6: illustrates the relative completion time of the best [PITH_FULL_IMAGE:figures/full_fig_p011_6.png] view at source ↗
Figure 8
Figure 8. Figure 8: AllReduce completion on a 32 × 32 torus with varying network bandwidth from 200 Gb/s to 3.2Tb/s. Each graph compares for a specific bandwidth, Trivance to the best performing algorithm. At lower bandwidths, transmission delay constitutes a larger fraction of the overall completion time, causing bandwidth optimized approaches to surpass Trivance at approximately 4 MiB. As bandwidth increases, the relative i… view at source ↗
Figure 10
Figure 10. Figure 10: AllReduce completion on a 16 × 16 × 16 torus of Bucket and Bruck compared to Trivance. 6.4 Summary Overall, our evaluation shows that Trivance consistently de￾livers the best performance in latency-bound regimes across rings and multidimensional torus networks, achieving an im￾provement of 5-30% for small and moderate message sizes. This advantage persists as network dimensionality increases, with the tra… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings

    cs.NI 2026-05 conditional novelty 7.0

    Bridge reduces All-to-All completion time by typically 3x to 10x and improves AllReduce by up to 6.6x over Ring by reusing optical subrings across multiple steps in reconfigurable networks.

  2. Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks

    cs.DC 2026-05 unverdicted novelty 5.0

    ReTri achieves all-to-all in ⌈log₃ n⌉ phases for ORNs by co-designing bidirectional exchanges and reconfiguration strategy, with simulations showing up to 10× improvement over static and 2.1× over prior reconfigurable Bruck.

  3. Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks

    cs.DC 2026-05 conditional novelty 5.0

    ReTri completes All-to-All on optical reconfigurable networks in ceil(log3 n) phases via balanced ternary block propagation and amortizes reconfiguration delay, claiming up to 10x faster completion than pairwise All-to-All.

Reference graph

Works this paper leans on

44 extracted references · 3 linked inside Pith · cited by 2 Pith papers

  1. [1]

    Evensky, Joseph P

    Helgi Adalsteinsson, Scott Cranford, David A. Evensky, Joseph P. Kenny, Jackson Mayo, Ali Pinar, and Curtis L. Janssen. A simulator for large-scale parallel computer architectures.Int. J. Distrib. Syst. Technol., 1(2):57–73, April 2010

    2010

  2. [2]

    Adiga and G

    N.R. Adiga and G. Almasi. An overview of the bluegene/l supercom- puter. InSC ’02: Proceedings of the 2002 ACM/IEEE Conference on Supercomputing, pages 60–60, 2002

    2002

  3. [3]

    Chris Erway, José E

    GeorgeAlmási,PhilipHeidelberger,CharlesJ.Archer,XavierMartorell, C. Chris Erway, José E. Moreira, B. Steinmacher-Burow, and Yili Zheng. Optimization of mpi collective communication on bluegene/l systems. InProceedings of the 19th Annual International Conference onSupercomputing,ICS’05,page253–262.AssociationforComputing Machinery, 2005

    2005

  4. [4]

    Language models are few-shot learners

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry,AmandaAskell,SandhiniAgarwal,ArielHerbert-Voss,Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Ben...

    1901

  5. [5]

    Efficient algorithms for all-to-all communications in multi-port message-passing systems

    Jehoshua Bruck, Ching-Tien Ho, Shlomo Kipnis, and Derrick Weath- ersby. Efficient algorithms for all-to-all communications in multi-port message-passing systems. InProceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’94, page 298–309, New York, NY, USA, 1994. Association for Computing Machinery

    1994

  6. [6]

    Synthesizing optimal collective algorithms

    Zixian Cai, Zhengyang Liu, Saeed Maleki, Madanlal Musuvathi, Todd Mytkowicz, Jacob Nelson, and Olli Saarikivi. Synthesizing optimal collective algorithms. InProceedings of the 26th ACM SIGPLAN SymposiumonPrinciplesandPracticeofParallelProgramming,PPoPP ’21, page 62–75. Association for Computing Machinery, 2021

    2021

  7. [7]

    Syccl: Exploiting symmetry for efficient collective communication scheduling

    Jiamin Cao, Shangfeng Shi, Jiaqi Gao, Weisen Liu, Yifan Yang, Yichi Xu, Zhilong Zheng, Yu Guan, Kun Qian, Ying Liu, Mingwei Xu, Tianshu Wang, Ning Wang, Jianbo Dong, Binzhang Fu, Dennis Cai, and Ennan Zhai. Syccl: Exploiting symmetry for efficient collective communication scheduling. InProceedings of the ACM SIGCOMM 2025Conference,SIGCOMM’25,page645–662,N...

  8. [8]

    Collective communication on architectures that support simultaneous communication over multiple links

    Ernie Chan, Robert van de Geijn, William Gropp, and Rajeev Thakur. Collective communication on architectures that support simultaneous communication over multiple links. InProceedings of the Eleventh ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’06, page 2–11, New York, NY, USA, 2006. Association for Computing Machinery

    2006

  9. [9]

    InSC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 386–400, 2018

    SudheerChunduri,ScottParker,PavanBalaji,KevinHarms,andKalyan Kumaran.Characterizationofmpiusageonaproductionsupercomputer. InSC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pages 386–400, 2018

    2018

  10. [10]

    Canary: Congestion-aware in-network allreduce using dynamic trees.Future Generation Computer Systems, 152:70–82, 2024

    DanieleDeSensi,EdgarCostaMolero,SalvatoreDiGirolamo,Laurent Vanbever, and Torsten Hoefler. Canary: Congestion-aware in-network allreduce using dynamic trees.Future Generation Computer Systems, 152:70–82, 2024

    2024

  11. [11]

    InProceedings of the 36th ACM International Conference on Supercomputing, ICS ’22

    GuangnanFeng,DezunDong,andYutongLu.Optimizedmpicollective algorithms for dragonfly topology. InProceedings of the 36th ACM International Conference on Supercomputing, ICS ’22. Association for Computing Machinery, 2022

    2022

  12. [12]

    Distributed training of large language models on aws trainium

    Xinwei Fu, Zhen Zhang, Haozheng Fan, Guangtai Huang, Mohammad El-Shabani, Randy Huang, Rahul Solanki, Fei Wu, Ron Diamant, and Yida Wang. Distributed training of large language models on aws trainium. InProceedings of the 2024 ACM Symposium on Cloud Computing, pages 961–976, 2024

    2024

  13. [13]

    Roger W. Hockney. The communication challenge for mpp: Intel paragon and meiko cs-2.Parallel Computing, 20(3):389–398, 1994

    1994

  14. [14]

    Hammingmesh: A network topology for large-scale deep learning.Commun

    TorstenHoefler,TommasoBonato,DanieleDeSensi,SalvatoreDiGiro- lamo, Shigang Li, Marco Heddes, Deepak Goel, Miguel Castro, and Steve Scott. Hammingmesh: A network topology for large-scale deep learning.Commun. ACM, 67(12):97–105, November 2024

    2024

  15. [15]

    Optimal bucket algorithms for large mpicollectivesontorusinterconnects

    Nikhil Jain and Yogish Sabharwal. Optimal bucket algorithms for large mpicollectivesontorusinterconnects. InProceedingsofthe24thACM International Conference on Supercomputing, ICS ’10, page 27–36. Association for Computing Machinery, 2010

    2010

  16. [16]

    A simulator for large-scale parallel computer architectures.International Journal of Distributed Systems and Technologies (IJDST), 1(2):57–73, 2010

    Curtis L Janssen, Helgi Adalsteinsson, Scott Cranford, Joseph P Kenny, Ali Pinar, David A Evensky, and Jackson Mayo. A simulator for large-scale parallel computer architectures.International Journal of Distributed Systems and Technologies (IJDST), 1(2):57–73, 2010

    2010

  17. [17]

    Pat: a new algorithm for all-gather and reduce-scatter operations at scale, 2025

    Sylvain Jeaugey. Pat: a new algorithm for all-gather and reduce-scatter operations at scale, 2025

    2025

  18. [18]

    An optimisation of allreduce communication in message-passing systems.Parallel Computing, 107:102812, 2021

    Andreas Jocksch, Noé Ohana, Emmanuel Lanti, Eirini Koutsaniti, Vasileios Karakasis, and Laurent Villard. An optimisation of allreduce communication in message-passing systems.Parallel Computing, 107:102812, 2021

    2021

  19. [19]

    Tpuv4:Anopticallyreconfigurablesupercomputerforma- chine learning with hardware support for embeddings

    Norm Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles,etal. Tpuv4:Anopticallyreconfigurablesupercomputerforma- chine learning with hardware support for embeddings. InProceedings of the 50th annual international symposium on computer architecture, pages 1–14, 2023

    2023

  20. [21]

    Tpuv4:Anopticallyreconfigurablesupercomputerformachine learning with hardware support for embeddings

    Norm Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles, Clifford Young, Xiang Zhou, Zongwei Zhou, and David A Pat- terson. Tpuv4:Anopticallyreconfigurablesupercomputerformachine learning with hardware support for embeddings. InProceedings of the 50thAnnualInternationalSympo...

    2023

  21. [22]

    An in-networkarchitectureforacceleratingshared-memorymultiprocessor collectives

    Benjamin Klenk, Nan Jiang, Greg Thorson, and Larry Dennison. An in-networkarchitectureforacceleratingshared-memorymultiprocessor collectives. In2020 ACM/IEEE 47th Annual International Symposium on Computer Architecture (ISCA), pages 996–1009, 2020

    2020

  22. [23]

    DmitryKolmakovandXuecangZhang.Ageneralizationoftheallreduce operation.arXiv preprint arXiv:2004.09362, 2020

    Pith/arXiv arXiv 2004

  23. [24]

    Understanding com- munication characteristics of distributed training

    Wenxue Li, Xiangzhou Liu, Yuxuan Li, Yilun Jin, Han Tian, Zhizhen Zhong, Guyue Liu, Ying Zhang, and Kai Chen. Understanding com- munication characteristics of distributed training. InProceedings of the 8th Asia-Pacific Workshop on Networking, APNet ’24, page 1–8. Association for Computing Machinery, 2024

    2024

  24. [25]

    Resccl: Resource- efficient scheduling for collective communication

    Tongrui Liu, Chenyang Hei, Fuliang Li, Chengxi Gao, Jiamin Cao, Tianshu Wang, Ennan Zhai, and Xingwei Wang. Resccl: Resource- efficient scheduling for collective communication. InProceedings of the ACM SIGCOMM 2025 Conference, SIGCOMM ’25, page 55–70, New York, NY, USA, 2025. Association for Computing Machinery

    2025

  25. [26]

    Rethinking machine learning collective communication as a multi- commodityflowproblem

    XutingLiu,BehnazArzani,SivaKesavaReddyKakarla,LiangyuZhao, Vincent Liu, Miguel Castro, Srikanth Kandula, and Luke Marshall. Rethinking machine learning collective communication as a multi- commodityflowproblem. InProceedingsoftheACMSIGCOMM2024 Conference, ACM SIGCOMM ’24, page 16–37, New York, NY, USA,

  26. [27]

    Paard: Proximity-aware all-reduce communication for dragonfly networks

    Junchao Ma, Dezun Dong, Cunlu Li, Ke Wu, and Liquan Xiao. Paard: Proximity-aware all-reduce communication for dragonfly networks. In2021 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking (ISPA/BDCloud/So- cialCom/SustainCom), pages 255–262, 2021

    2021

  27. [28]

    Efficient large-scale language model training on gpu clusters using megatron-lm

    DeepakNarayanan,MohammadShoeybi,JaredCasper,PatrickLeGres- ley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. Efficient large-scale language model training on gpu clusters using megatron-lm. InProceedings of the International ConferenceforHighPerformanceComp...

    2021

  28. [29]

    Bandwidthoptimalall-reducealgorithms for clusters of workstations.Journal of Parallel and Distributed Computing, 69:117–124, 02 2009

    PitchPatarasukandXinYuan. Bandwidthoptimalall-reducealgorithms for clusters of workstations.Journal of Parallel and Distributed Computing, 69:117–124, 02 2009

    2009

  29. [30]

    Automatic mpi counter profiling of all users: First results on a cray t3e 900-512

    Rolf Rabenseifner. Automatic mpi counter profiling of all users: First results on a cray t3e 900-512

  30. [31]

    Optimization of collective reduction operations

    Rolf Rabenseifner. Optimization of collective reduction operations. In Marian Bubak, Geert Dick van Albada, Peter M. A. Sloot, and Jack Dongarra, editors,Computational Science - ICCS 2004, pages 1–9. Springer Berlin Heidelberg, 2004

    2004

  31. [32]

    Rico-Gallego, Juan C

    Juan A. Rico-Gallego, Juan C. Díaz-Martín, Ravi Reddy Manumachu, and Alexey L. Lastovetsky. A survey of communication performance models for high-performance computing.ACM Comput. Surv., 51(6), January 2019

    2019

  32. [33]

    Generalisation of recursive doubling for allreduce: Now with simulation.Parallel Computing, 69:24–44, 2017

    Martin Ruefenacht, Mark Bull, and Stephen Booth. Generalisation of recursive doubling for allreduce: Now with simulation.Parallel Computing, 69:24–44, 2017

    2017

  33. [34]

    Collective algorithms for multiported torus networks.ACM Trans

    Paul Sack and William Gropp. Collective algorithms for multiported torus networks.ACM Trans. Parallel Comput., 1(2), February 2015

    2015

  34. [35]

    Swing: Short-cutting rings for higher bandwidth allreduce

    Daniele De Sensi, Tommaso Bonato, David Saam, and Torsten Hoefler. Swing: Short-cutting rings for higher bandwidth allreduce. In21st USENIXSymposiumonNetworkedSystemsDesignandImplementation (NSDI 24), pages 1445–1462. USENIX Association, April 2024

    2024

  35. [36]

    TACCL: Guiding collective algorithm synthesis using communication sketches

    Aashaka Shah, Vijay Chidambaram, Meghan Cowan, Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Jacob Nelson, Olli Saarikivi, and Rachee Singh. TACCL: Guiding collective algorithm synthesis using communication sketches. In20th USENIX Symposium on Net- workedSystemsDesignandImplementation(NSDI23),pages593–612. USENIX Association, April 2023

    2023

  36. [37]

    Megatron-lm: Training multi- billion parameter language models using model parallelism.arXiv preprint arXiv:1909.08053, 2019

    Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-lm: Training multi- billion parameter language models using model parallelism.arXiv preprint arXiv:1909.08053, 2019

    Pith/arXiv arXiv 1909

  37. [38]

    Lamda: Language models for dialog applications.arXiv preprint arXiv:2201.08239, 2022

    RomalThoppilan,DanielDeFreitas,JamieHall,NoamShazeer,Apoorv Kulshreshtha, Heng-Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications.arXiv preprint arXiv:2201.08239, 2022

    Pith/arXiv arXiv 2022

  38. [39]

    Decomposing mpi collectives for exploiting multi-lane communication

    Jesper Larsson Träff and Sascha Hunold. Decomposing mpi collectives for exploiting multi-lane communication. In2020 IEEE International Conference on Cluster Computing (CLUSTER), pages 270–280, 2020

    2020

  39. [40]

    Enabling next-generation ai work- loads: Announcing tpu v5p and ai hypercomputer.Google Cloud, December, 6, 2023

    Amin Vahdat and Mark Lohmeyer. Enabling next-generation ai work- loads: Announcing tpu v5p and ai hypercomputer.Google Cloud, December, 6, 2023

    2023

  40. [41]

    TopoOpt: Co-optimizing network topology and parallelization strategy for distributed training jobs

    Weiyang Wang, Moein Khazraee, Zhizhen Zhong, Manya Ghobadi, Zhihao Jia, Dheevatsa Mudigere, Ying Zhang, and Anthony Kewitsch. TopoOpt: Co-optimizing network topology and parallelization strategy for distributed training jobs. In20th USENIX Symposium on Net- workedSystemsDesignandImplementation(NSDI23),pages739–767. USENIX Association, April 2023

    2023

  41. [42]

    Efficient direct-connect topologies for collective communications, 2025

    LiangyuZhao,SiddharthPal,TapanChugh,WeiyangWang,JasonFantl, Prithwish Basu, Joud Khoury, and Arvind Krishnamurthy. Efficient direct-connect topologies for collective communications, 2025

    2025

  42. [43]

    Resiliencyatscale:Managinggoogle’stpuv4machine learning supercomputer

    YazhouZu,AlirezaGhaffarkhah,Hoang-VuDang,BrianTowles,Steven Hand,SafeenHuda,AdekunleBello,AlexanderKolbasov,ArashRezaei, DayouDu,etal. Resiliencyatscale:Managinggoogle’stpuv4machine learning supercomputer. In21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24), pages 761–774, 2024. A Latency-Optimality Proof forTrivance We have e...

    2024

  43. [46]

    Bruck’s data transmission follows the same pattern asTrivance, but in step𝑘 the communication distances are 3𝑘 and 2·3 𝑘, resulting in a total congestion of3·3 𝑘 per step

    Over 2·log 3𝑛 steps, this equals an optimality of2 3·log 3𝑛. Bruck’s data transmission follows the same pattern asTrivance, but in step𝑘 the communication distances are 3𝑘 and 2·3 𝑘, resulting in a total congestion of3·3 𝑘 per step. Consequently, the transmission delay of Bruck’s algorithm is exactly three times that ofTrivance, for both the latency-optim...

  44. [2024]

    Association for Computing Machinery