Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks Anton Juerss
Weizenbaum Institute & TU Berlin Germany
arXiv:2605.26930v1 [cs.DC] 26 May 2026
Abstract All-to-All communication is a key performance bottleneck for distributed machine learning (ML) and high-performance computing (HPC) workloads, where dense traffic increasingly stresses scale-up interconnects. While these ML and HPC workloads have driven unprecedented infrastructure demand, optical reconfigurable networks (ORNs) offer a promising path forward. By adapting the physical topology to the active workload, they improve communication cost and bandwidth utilization. However, their benefit is critically contingent on whether the collective consists of structured phases that can be served by sparse and reusable topology states. In this paper, we revisit Bruck’s All-to-All implementation and demonstrate the benefits of topology optimization in which both communication pattern and reconfiguration strategy are co-designed. We present ReTri, a bidirectional All-to-All schedule for ORNs. ReTri uses balanced ternary block propagation to complete All-to-All in ⌈log3 𝑛⌉ phases. The induced reconfiguration strategy from ReTri’s pairwise bidirectional exchanges allow reconfiguration delays to be amortized across multiple phases. Preliminary simulations show that ReTri improves completion time by up to 10× over static All-to-All, even for millisecond-scale reconfiguration delays, and improving reconfigurable Bruck by up to 2.1×.
1
Introduction
To meet the increasing compute and memory demands of deep learning workloads, including recommendation systems and Mixture of Expert models, modern distributed systems connect thousands of accelerators in hyperscale datacenters [11, 16, 20, 27]. In these large-scale ML systems, efficient communication across accelerators is crucial for training and inference performance, since activations, embeddings, and tokens must be synchronized [16]. These synchronizations are typically realized through All-to-All collective communication, where each accelerator sends distinct data to every other accelerator [26]. Their impact on end-toend performance is substantial, accounting for up to 55% of MoE end-to-end training time [16]. The dense communication pattern of All-to-All makes it a major performance bottleneck and increasingly stresses scale-up interconnects [14]: every accelerator exchanges distinct data, raising serious
Stefan Schmid
TU Berlin & Weizenbaum Institute Germany concerns about congestion and requiring high network bandwidth [16, 20]. The design of datacenter interconnect fabrics therefore plays a central role in the scalability and efficiency of large-scale ML and HPC systems [7, 11, 20]. Whereas conventional, electrically switched networks are power-intensive and may lead to performance bottlenecks, optical reconfigurable networks (ORNs) have emerged as a promising alternative. ORNs establish bidirectional high-bandwidth optical links between endpoints, introducing the enhanced capability to adjust and optimize the physical topology [2, 4, 7]. However, direct optical connectivity incurs non-negligible reconfiguration delay, making it non-trivial to balance the resulting costs against against the benefit of adapting the topology to best meet the demands of the active communication phase [10, 19, 27]. In state-of-the-art GPU training systems, All-to-All is typically treated within scale-up domains as a destination-oriented redistribution primitive, for example in MoE token dispatch [16, 21]. Each node partitions its payload by destination and the communication layer sends each resulting block directly to its target endpoint. If the full traffic matrix is injected as one bulk operation in an ORN, the optical layer processes dense and unstructured traffic, withholding the opportunity to adapt the topology to a specific part of the workload [16, 27]. This paper is driven by three simple but powerful observations. First, even an optimal reconfiguration schedule cannot improve over a static topology if the collective algorithm does not match the constraints of ORNs. This motivates codesigning the All-to-All pattern around the port constraints of optical switches, such that communication is exposed as sparse phases. Multi-hop algorithms such as Bruck’s algorithm [5] decompose All-to-All into distinct, synchronized communication phases which are well-suited for ORNs. Second, optimization should account not merely for bandwidth utilization, but also to reduce the number of communication phases each of which require topology adjustments for optimal communication. Fewer structured phases reduce reconfiguration requirements, while still allowing the topology to be matched efficiently to the active traffic. Third, to fully exploit the potential of ORNs, bidirectional optical links should carry bidirectional traffic: if node 𝑢 sends data to node
Conference’17, July 2017, Washington, DC, USA
𝑣, then node 𝑣 should simultaneously send data to node 𝑢 over the same optical circuit. Based on these observations, we present a novel All-to-All communication pattern and reconfiguration strategy that addresses the described challenges: we propose ReTri, a bidirectional, sparse All-to-All communication pattern that synchronizes multiple pairwise exchanges to fully utilize each optical link. The induced reconfiguration schedule forms connected subrings that serve the active traffic while preserving persistent topology states for subsequent phases. By routing blocks over short paths and increasing the number of blocks per transmission, ReTri reduces the number of communication phases and thereby the associated number of reconfigurations. With two electrical-to-optical transceivers per accelerator, ReTri completes All-to-All in ⌈log3 𝑛⌉ phases, an effective reduction by 33% compared to Bruck’s All-to-All ORN-feasible implementation. Our preliminary results show that ReTri reduces All-to-All completion time by up to 90% for small reconfiguration delays of 1 𝜇s and consistently outperforms Bruck by up to 2.1×. Even for large reconfiguration delays, ReTri achieves speedups of 1.5× to 6.9× for 1 ms and showing improvements even for 50 ms delay for large workloads.
2
Motivation: Why All-to-All Changes Under Reconfiguration
Prior work has established that collective communication is particularly compatible with optical reconfigurable networks (ORNs) since the communication pattern is known in advance, and collectives proceed in synchronized phases, between which the network can be reconfigured [2, 3, 15]. Existing phased All-to-All algorithms, including Bruck’s algorithm, are typically designed for logical one-directional communication patterns and therefore, by design, do not fully exploit bidirectional optical links [5, 26]. A common approach to improve network utilization — used for ring-based collectives such as AllReduce — is to mirror the schedule by halving the workload and executing one half in each direction, improving bandwidth utilization by up to 2× [12, 23, 24]. In ORNs, however, optimizing for bandwidth utilization alone is insufficient: since reconfiguration is costly, each optimized topology state should carry as much All-to-All traffic as possible. The objective is therefore to minimize the number of topology adjustments while still transmitting over direct, optimal optical connections. For our reconfigurable architecture, we consider a scaleup domain, i.e., a tightly coupled group of 𝑛 accelerator endpoints within a single server or memory domain, connected
Anton Juerss and Stefan Schmid
Phase 0 0 7 1
Direct src-dest 6 All-to-All 5
7 Bruck
4 0
3 1
7 2
8 7 6
Phase 2
2
6 5
ReTri
Phase 1
4 0
5 4
0
1
6
7 2
3
5
1
8
2 3
7 6
4 0
5 4
3
0
1
6
2 5
4
3
1 2 3
Figure 1: Communication phases of Bruck, ReTri, and direct src-dest All-to-All (for clarity, only transmissions from node 0 are shown). ReTri completes in one fewer phase than Bruck with one additional node. to a programmable optical interconnect with 𝑝 endpointfacing optical ports. The interconnect establishes bidirectional optical circuits between endpoint ports and can reconfigure these circuits on demand, incurring a reconfiguration delay 𝛼𝑟 [8, 10, 16, 19]. If each node has only one transceiver, with 𝑝 = 𝑛, the interconnect can realize only a peer-to-peer matching in each configuration: every node can be connected to at most one other node [2, 17, 19]. Such a topology cannot be connected for 𝑛 > 2, and All-to-All must therefore be served by repeatedly reconfiguring direct pairings across phases. To maintain a persistent connected topology over all endpoints, each node must have a degree of at least two [7, 13]. Under this constraint, the minimal topology is a ring, which requires two electrical-to-optical transceiver per node and hence 𝑝 = 2𝑛 endpoint-facing ports at the optical-circuit switch (OCS) [7]. Direct destination-oriented All-to-All is a poor fit for reconfigurable networks, as this pattern misses structured phases for which the topology can adjust for (Figure 1). Each phase should expose only as many concurrent data transmissions as there are available ports — under the minimal assumption of two transceivers per node and 2𝑛 optical ports at the OCS, this corresponds to 2𝑛 simultaneous directed transmissions. Bruck’s algorithm with additional mirroring splits All-to-All in ⌈log2 𝑛⌉ phases, which together form connected subrings of size 2𝑛𝑘 in phase 𝑘 to ensure persistent topology states. These patterns are visualized in Figure 1. This raises the question: Can we achieve the same property with fewer phases? Theoretically, with two transceivers per node, All-to-All can be completed in ⌈log3 𝑛⌉ phases.
Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks
Assuming an initial logical ring, Bruck’s two-port pattern makes each node communicate with peers at offsets 3𝑘 and 2 · 3𝑘 . This achieves ⌈log3 𝑛⌉ phases in an ideal multi-port message-passing model, but it is not directly feasible for ORNs. Given the OCS has 2𝑛 ports, it can only establish 𝑛 bidirectional matching optical links, i.e., two incident links per node. Bruck’s pattern, however, uses established links only in one direction. This generally requires each node to send to two peers and receive from two different peers in the same phase; realizing these non-pairwise exchanges would require up to four incident optical links per node. Moreover, when Bruck is implemented over a ring, its traffic still progresses along one logical direction, increasing congestion and propagation delay. Thus, the effectiveness of reconfiguration schedules in ORNs is determined by the underlying All-to-All communication pattern. This opens the design space for an All-to-All schedule that completes in ⌈log3 𝑛⌉ phases. Such schedule must be bidirectional by design, using both directions of each optical link while preserving reusable connected topologies and balancing link utilization. In the next section, we present ReTri, an algorithm that addresses these requirements and explores the trade off between performance gains and reconfiguration overhead.
3
ReTri: Shortest Path All-to-All
We present ReTri, an efficient bidirectional All-to-All communication pattern tailored for ORNs, that establishes reusable subrings for sparse reconfiguration for 2𝑛 OCS ports completing in ⌈log3 𝑛⌉ phases.
3.1
Ternary Communication Pattern
In order to make optimal use of both available ports at each node for bidirectional communication, we use the Trivance approach by Juerss et al. [12]. Rather than forwarding data along a single logical direction, each node communicates in Trivance with two symmetric peers in every phase. Specifically, in phase 𝑘, each node 𝑟 in an 𝑛-node network communicates with two peers defined as: ( 𝜋left = 𝑟 − 3𝑘 mod 𝑛, 𝜋 (𝑟, 𝑘, 𝑛) = (𝜋 left, 𝜋right ) = 𝜋right = 𝑟 + 3𝑘 mod 𝑛, In AllReduce, Trivance exposes a latency–bandwidth tradeoff: it reduces the number of communication phases and shortens the paths lengths compared to a ring-based AllReduce. This improves completion time for small to medium message sizes. All-to-All exhibits a different set of constraints. Since transmitted blocks are distinct and cannot be reduced, every additional forwarding hop contributes directly to propagation delay, link occupancy, and congestion. By contrast, the bidirectional pattern underlying Trivance
Conference’17, July 2017, Washington, DC, USA
forwards blocks in both logical directions and thereby shortcuts the ring. When applied to All-to-All, this structure reduces the number of communication phases and decreases path lengths. As in Bruck’s two-port version, each node must receive both incoming transmissions of the current phase before it can advance to the next.
3.2
Block Propagation in All-to-All
The ternary pattern of Trivance reaches all nodes within 𝑠 = ⌈log3 𝑛⌉ communication phases. The resulting data movement, however, must be defined separately from AllReduce. In AllReduce, data blocks can be reduced between phases at each node, whereas in All-to-All every transmitted block is unique. In each phase of ReTri, the ternary structure partitions the remaining data into three groups: blocks that stay local, blocks propagated to the left, and blocks propagated to the right. Thus, for an initial message of 𝑚 bytes per node, each node transmits 𝑚3 bytes in each direction. Since every phase expands the set of reachable destinations by a factor of three, the canonical network size for ReTri is 𝑛 = 3𝑠 . We define the block propagation of ReTri analogously to Bruck’s radix-3 All-to-All [5], but using balanced ternary digits. We assume that 𝑛 = 3𝑠 and denote 𝐵 [𝑟, 𝑑] as the block initially stored at node 𝑟 and destined for node 𝑑. We define its signed offset as Δ𝑟,𝑑 = ucr𝑛 ((𝑑 − 𝑟 ) mod 𝑛) ∈ , . . . , 0, . . . , 𝑛−1 { − (𝑛−1) 2 2 }, where ucr𝑛 (·) maps a distance offset modulo 𝑛 to its unique centered representative. Since 𝑛 = 3𝑠 , every offset has a unique balanced ternary repreÍ −1 sentation Δ𝑟,𝑑 = 𝑠𝑘=0 𝜏𝑘 (𝑟, 𝑑)3𝑘 with 𝜏𝑘 (𝑟, 𝑑) ∈ {−1, 0, +1}. This representation defines how each block reaches its destination. In communication phase 𝑘, node 𝑖 sends all currently stored blocks with 𝜏𝑘 = +1 to (𝑖 + 3𝑘 ) mod 𝑛, with 𝜏𝑘 = −1 to (𝑖 − 3𝑘 ) mod 𝑛. Blocks with 𝜏𝑘 = 0 are not sent in phase 𝑘. Hence, the two outgoing messages of node 𝑖 in phase 𝑘 are Í (𝑘 ) 𝑀𝑖,+ = {𝐵 [𝑟, 𝑑] : 𝑖 = (𝑟 + ℓ<𝑘 𝜏ℓ (𝑟, 𝑑)3ℓ ) mod 𝑛, 𝜏𝑘 (𝑟, 𝑑) = (𝑘 ) +1}, send to (𝑖 + 3𝑘 ) mod 𝑛 and 𝑀𝑖,− = {𝐵 [𝑟, 𝑑] : 𝑖 = Í ℓ (𝑟 + ℓ<𝑘 𝜏ℓ (𝑟, 𝑑)3 ) mod 𝑛, 𝜏𝑘 (𝑟, 𝑑) = −1}. send to (𝑖 − 3𝑘 ) mod 𝑛. After all 𝑠 = log3 𝑛 phases, block 𝐵 [𝑟, 𝑑] has Í −1 moved by 𝑠𝑘=0 𝜏𝑘 (𝑟, 𝑑)3𝑘 = Δ𝑟,𝑑 positions and therefore reaches its destination 𝑑. The full correctness proof can be found in Appendix B.
3.3
Reconfiguration Strategy: Reusable Ternary Subrings
The ternary communication pattern of ReTri is similar to a shortest-path source-destination All-to-All which only requires a single communication phase. However, its main advantage is the algebraic structure of its phases from which we can directly derive our new topology states for each
Conference’17, July 2017, Washington, DC, USA
Anton Juerss and Stefan Schmid
Algorithm 1 ReTri: Reusable Ternary Subrings Require: 𝑛 = 3𝑠 nodes, reconf. schedule x = (𝑥 0, . . . , 𝑥𝑠 −1 ) 1: 𝑠 ← log3 𝑛
2: for each phase 𝑘 ∈ {0, . . . , 𝑠 − 1} do 3: if 𝑥𝑘 = 1 then 4: for each residue 𝑖 ∈ {0, . . . , 3𝑘 − 1} do 5: 6:
Construct subring 𝑆𝑖(𝑘 ) = {𝑢 | 𝑢 ≡ 𝑖 for each node 𝑢 ∈ 𝑆𝑖(𝑘 ) do
𝐶 𝐴 (𝑚) = (mod 3𝑘 )}
Set bidirectional optical links to 𝑢 − 3𝑘 mod 𝑛 and 𝑢 + 3𝑘 mod 𝑛 8: end for 9: end for 10: end if 11: end for 7:
reconfiguration. This structure makes the active communication pattern compatible with sparse, reusable optical topologies under the two-port constraint. Given the OCS has 2𝑛 ports, each node can establish exactly optical connections to two other nodes at any time. Hence, a feasible topology is a degree-two bidirectional graph: every node has two incident optical links, and the resulting topology is a collection of rings [7]. For ReTri, these rings are induced directly by the ternary communication pattern. Given a reconfiguration schedule x = (𝑥 0, . . . , 𝑥𝑠 −1 ), where 𝑥𝑘 = 1 denotes a reconfiguration before phase 𝑘, the ORN configures the edge set 𝐸𝑘 = {{𝑖, (𝑖 + 3𝑘 ) mod 𝑛} : 𝑖 ∈ {0, . . . , 𝑛 − 1}}. Equivalently, each node 𝑖 is connected to the two peers (𝑖 − 3𝑘 ) mod 𝑛 and (𝑖 +3𝑘 ) mod 𝑛. Algorithm 1 defines the edge-set construction of ReTri and the corresponding subrings induced per phase. While this reconfiguration schedule directly connects peers for the next phase, it also creates a new subring illustrated in Figure 1. For a reconfiguration before phase 𝑘, the topology is partitioned into 3𝑘 subrings. Each subring has size 3𝑛𝑘 . For each residue class 𝑖 ∈ {0, . . . , 3𝑘 − 1}, define 𝑆𝑖(𝑘 ) := { 𝑢 ∈ {0, . . . , 𝑛 − 1} | 𝑢 ≡ 𝑖
(mod 3𝑘 ) }.
Prior work showed that for OCSes with 2𝑛 ports, reconfiguration strategies that induce subrings reduce communication cost of the active phase while preserving reachability for subsequent phases [13, 22]. We prove in Lemma 1 in the Appendix A that the subrings induced by ReTri are minimal and include all nodes of future peers.
3.4
completion time, but each adjustment incurs a reconfiguration overhead 𝛿. We analyze this tradeoff for ReTri using an extended Hockney 𝛼-𝛽 cost model, following related work [2, 12, 25, 28]:
Performance Gains and Reconfiguration Costs
Reconfiguration during collective operations introduces a fundamental tradeoff: reconfigurations can adapt the topology to the next communication phase and thereby reduce
𝑠 · 𝛼𝑠 |{z}
+
𝑠 −1 ∑︁ 𝑘=0
per-phase delay
(ℎ𝑘 · 𝛼ℎ + 𝑚𝑘 · 𝑐𝑘 · 𝛽 ) + 𝑅 · 𝛿 | {z } | {z } |{z} per-hop delay
transmission delay
reconf. delay
where, in each phase 𝑘 of total 𝑠 phases, the algorithm 𝐴 incurs a startup latency 𝛼𝑠 (e.g., data preparation), per-hop delay 𝛼ℎ for each hop ℎ𝑘 , a transmission delay of 𝛽 · 𝑚𝑘 · 𝑐𝑘 with 𝑚𝑘 as the chunk size transmitted in phase 𝑘, 𝛽 = 𝑏1 the network cost per byte based on bandwidth 𝑏, 𝑐𝑘 maximum network congestion per directional link in phase 𝑘 and a reconfiguration overhead 𝛿 for the number of reconfigurations 𝑅. The total cost of ReTri to complete All-to-All in a static ring network of 𝑛 is as follows: 𝐶 ReTri (𝑚) = log3 𝑛 · 𝛼𝑠 + | {z } per-phase delay
log∑︁ 3 𝑛−1 𝑘=0
(3𝑘 · 𝛼ℎ + | {z } per-hop delay
𝑚 · 3𝑘 · 𝛽 ) 3 | {z } transmission delay
𝑚 𝑛 −1 = log3 𝑛 · 𝛼𝑠 + 𝛼ℎ + 𝛽 · . 3 2 Let x = (𝑥 0, . . . , 𝑥𝑠 −1 ) ∈ {0, 1}𝑠 denote a reconfiguration schedule, where 𝑥𝑘 = 1 indicates that the OCS is reconfigured before phase 𝑘, and 𝑥𝑘 = 0 that the previous topology is reused. If a topology is configured at phase 𝑘, then phase 𝑘 + 𝑡 can be served over the same subrings with hop distance 3𝑡 . Hence, a phase segment of length 𝑟 , where the topology is not reconfigured, has communication cost ReTri 𝐶 seg (𝑟 ) =
𝑟 −1 ∑︁ 𝑚 𝑡 3𝑟 − 1 𝛼 𝑠 + 𝛼ℎ + 𝛽 3 = 𝑟𝛼𝑠 + 𝑦 , 3 2 𝑡 =0
where 𝑦 := 𝛼ℎ + 𝛽 𝑚3 and each node transmits two message of size 𝑚3 in each direction. After a topology reconfiguration, the communication costs of the next phase is minimal: each node is directly connected to both its peers. Each additional phase without reconfiguration increases the communication distance, and therefore the congestion and propagation delay by a factor of three. Thus, the placement of reconfigurations determines how the 𝑠 = log3 𝑛 communication phases are partitioned into topology segments. Following prior work, the optimal schedule balances these segment lengths [13]: for a fixed number 𝑅 of reconfigurations, the resulting 𝑅 + 1 segments should differ in length by at most one [13]. In the aligned case where 𝑅 + 1 divides log3 𝑛, all segments have log3 𝑛 length 𝑅+1 , and the cost for R reconfigurations is 𝐶
ReTri
log3 𝑛
𝑚 3 𝑅+1 − 1 (𝑅) = log3 𝑛 · 𝛼𝑠 + (𝑅 + 1) · (𝛼ℎ + 𝛽 ) · + 𝑅𝛿. 3 2
Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks
If the ORN is reconfigured before every phase with 𝑅 = 𝑠 − 1 and therefore optimize the topology between each phase reducing the distance of communicating peers to 1. This leads to the optimal costs: 𝑚 𝐶 ReTri (log3 𝑛 − 1) = log3 𝑛 𝛼𝑠 + 𝛼ℎ + 𝛽 + (log3 𝑛 − 1)𝛿. 3 Given this, frequent reconfiguration between phases improves the performance and reduces the communication cost of All-to-All by 𝛼ℎ + 𝛽 𝑚3 𝑛−1 2 − log3 𝑛 at the cost of additional reconfiguration delay of (log3 𝑛 − 1)𝛿. In comparison, Bruck requires log2 𝑛 communication phases between which the topology may reconfigure, leading to maximal performance gains: 𝑚 𝐶 𝐵𝑟𝑢𝑐𝑘 (log2 𝑛 − 1) = log2 𝑛 𝛼𝑠 + 𝛼ℎ + 𝛽 + (log2 𝑛 − 1)𝛿. 4 log 𝑛
Bruck requires log2 𝑛 = log2 3 ≈ 1.58× as many phases as 3 ReTri. While transmission delay is for every-phase reconfiguration identical, Bruck incurs about 58% higher per-phase latency and per-hop latency. More importantly, achieving the same topology optimization inflicts also 58% more reconfiguration delay 𝛿. For large ORNs systems with millisecondscale reconfiguration delay, this difference can determine whether reconfigurations are even beneficial which gives ReTri with a significant advantage over Bruck. We analyzed the cost-optimal schedules for a fixed number of reconfigurations. This raises the questions of when and how often are reconfigurations beneficial for ReTri? Given the network parameters, the answer is obtained by evaluating the completion time for each feasible number of reconfigurations and selecting the lowest cost schedule. For ReTri, this corresponds to 𝑅★ = arg min0≤𝑅 ≤𝑠 −1 𝐶 ReTri (𝑅), where 𝑠 = log3 𝑛. The optimal value of 𝑅 depends on the relative cost of communication and reconfiguration. Reconfiguration between each phase is beneficial when the optimization in hop distance and congestion exceeds the reconfiguration overhead. This is more likely for large 𝑛, large message size 𝑚, low bandwidth, or high per-hop delay.
4
Preliminary Evaluation
Our analysis explores a clear tradeoff between performance gains by topology adjustments and reconfiguration overhead. The central questions to determine ReTri’s effectiveness are: under which network parameters do reconfigurations with ReTri improve static All-to-All completion time, and how does ReTri compare to existing All-to-All reconfiguration schedules? To answer these questions, we conduct preliminary simulations of ReTri using Astra-Sim [28] with ns-3 [1] as the network backend. We compare ReTri against two baselines. The first is the static shortest-path source-destination All-to-All, which operates on a static ring and second is the
Conference’17, July 2017, Washington, DC, USA
Figure 2: Heatmap showing All-to-All speedups of ReTri (𝑛 = 81) compared to static All-to-All (𝑛 = 64) with 𝑅 denoting the number of reconfigurations by ReTri. reconfigurable Bruck algorithm, namely Bridge [13]. We extend Bridge by employing a mirrored All-to-All with half the data 𝑚; thereby both logical directions are used to provide a fair comparison to ReTri. We model a scale-up system with 400 Gbps link bandwidth, a propagation delay of 1 𝜇s, and a per-phase delay of 1.7 𝜇s, following configurations used in related work [8, 16, 22, 25]. We evaluate workloads from 𝑚 = 1 KB to 256 MB and vary the reconfiguration delay 𝛿 over a broad range, from 1 𝜇s to 50 ms, to cover both fast optical interconnects with limited port number and architectures that provide more ports but incur higher reconfiguration delays [6, 9, 18]. Since ReTri is naturally aligned with powers of three, while Bruck with powers of two, we compare each algorithm at its favorable size. In Figures 2 and 3, Bruck operates on 64 nodes, whereas ReTri operates on 81 nodes, which favors Bruck — All-to-All completion time increases linearly with network size. Figure 2 reports the speedup of ReTri over static shortestpath All-to-All. For low reconfiguration delay, 𝛿 = 1 𝜇s, ReTri achieves speedups of up to 10×. In general, larger messages increase the completion time, so the proportional performance gains from reconfiguration grow and can outweigh the fixed overhead 𝛿. Reconfiguration remains beneficial up to 𝛿 = 10 𝜇s for small messages, up to 𝛿 = 1 ms for messages up to 8 MB, and even up to 𝛿 = 50 ms for 256 MB messages. Compared to Bruck in Figure 3, ReTri achieves consistent speedups of up to 2.1×, despite operating on 81 nodes compared to Bruck on 64 (26% larger network size). For small messages, ReTri benefits primarily from its lower phase count and shorter forwarding paths, yielding speedups of at least 1.6×. For larger messages, speedups range from 1.2× to 2.1×, where transmission delay dominates. For low 𝛿, frequent topology updates yield 5–10× speedups over the static baseline, while ReTri still maintains
Conference’17, July 2017, Washington, DC, USA
Figure 3: Heatmap showing All-to-All speedups of ReTri (𝑛 = 81) compared to Bridge, Bruck’s reconfiguration strategy (𝑛 = 64). gains of up to 1.5× at 8 MB and 1.1× even with 𝛿 = 50 ms at 256 MB. These results identify the regimes in which reconfigurations are beneficial: as message size and network size increase, the performances gains from optimizing the topology increasingly outweigh the reconfiguration overhead. Figures 4 and 5 in the appendix further show that, for larger networks, ReTri remains beneficial even at high reconfiguration delays, improving over the static baseline by 1.2× at 𝛿 = 150 ms for 256 MB messages, whereas Bruck no longer improves over static execution. This confirms that ReTri is most effective when communication is expensive: in these regimes, sparse or frequent reconfiguration substantially reduces hop distance and link congestion. Across the evaluated parameter space, ReTri also provides an effective reconfiguration strategy than Bruck.
5
Discussion, Challenges, and Research Agenda
We establish ReTri as a concrete step toward reconfigurationaware All-to-All in scale-up reconfigurable domains. We discuss the remaining challenges that shape a broader research agenda across algorithm design and systems integration. Non-power-of-three Networks: Our analysis focuses on the aligned case 𝑛 = 3𝑠 , where our ternary pattern induces nested reusable subrings. For arbitrary network sizes, ReTri establishes a ring under the identical pattern which performs identical to the next largest power-of-three size. While we outperform Bruck by operating on much larger networks, optimization for arbitrary sizes remains future work. Extension Beyond Rings: We can generalize ReTri beyond rings, with 𝑑 = 2𝑞 optical ports per node to balanced radix 𝑏 = 𝑑 + 1, where phase 𝑘 connects each node to the peers
Anton Juerss and Stefan Schmid
at offsets ±𝑎𝑏 𝑘 . The resulting topology then consists of a degree-𝑑 circular ring. We leave this for future work. Overlapping Computation with Reconfigurations: Reconfiguration delay does not necessarily lie on the critical path. In practical workloads, topology changes may overlap with computation or data preparation. For ReTri, this implies that the practical benefit of reconfiguration-aware schedules may be larger than suggested. Other Collectives: Although ReTri targets All-to-All, the same design principle may extend to other collectives with structured communication phases for ORNs, such as AllReduce. These collectives introduce additional dependencies as blocks may be reduced or replicated across phases. In particular, the ring algorithm completes AllReduce with minimal data transmission and congestion, so ReTri could be applied to primarily improve phase count and propagation delay. Synchronization Between Reconfigurations: Reconfiguration requires all nodes to complete the current phase before optical circuits can adjust. Barrier overhead, stragglers, and control-plane latency can reduce the benefit of frequent topology updates. While, we show that ReTri improves Allto-All for reconfiguration delays of 50 ms to 150 ms, future work may explore synchronization challenges further. Existing reconfiguration strategies: Existing reconfiguration strategies for collective workloads provide important insights for adapting optical topologies, but they can overcomplicate the problem by optimizing topology changes independently of the communication pattern. In many cases, the reconfiguration schedule can be derived directly from the communication pattern and is deterministic as the workload is known for All-to-All and AllReduce; when the pattern is constrained for ORNs, however, the remaining topology optimization is limited in performance and possibilities. In addition to the larger research avenues discussed, technical questions remain open. These include extending the evaluation of ReTri to hardware-level simulation with a concrete OCS model. More broadly, ReTri motivates a design space of reconfiguration-aware collectives in which the communication schedule and optical topology are co-designed rather than optimized independently.
6
Conclusion
By revisiting Bruck’s logarithmic phase structure under physical ORN constraints, we proposed ReTri, an All-to-All algorithm which achieves ⌈log3 𝑛⌉ communication phases while preserving pairwise bidirectional exchanges and inducing reusable subring topologies. This structure exposes a direct tradeoff between communication distance and reconfiguration overhead: frequent reconfiguration reduces hop count and congestion, while sparse reconfiguration amortizes topology changes across multiple phases. We showed
Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks
that reducing the number of communication phases directly improved completion time by up to 2.1× to Bruck. We believe this direction is particularly promising for future scale-up systems, where dense All-to-All traffic increasingly stresses electrical interconnects. By combining structured collective phases with reusable topologies, reconfigurable networks can move beyond direct peer matching and support communication patterns that are both phase-efficient and benefit over realistic reconfiguration delays.
Acknowledgments This work is part of a project that has received funding from the European Research Council (ERC), project FortifyNet (grant 101287293), 2026-2027 and by the German Federal Ministry of Research, Technology and Space (BMFTR) under grant 16DII131 “Weizenbaum Institut für die vernetzte Gesellschaft”.
References [1] [n. d.]. ns-3 Network Simulator. https://www.nsnam.org/. Accessed: 2026-03-26. [2] Vamsi Addanki. 2025. When Light Bends to the Collective Will: A Theory and Vision for Adaptive Photonic Scale-up Domains. In Proceedings of the 24th ACM Workshop on Hot Topics in Networks (UMD Campus, College Park, MD, USA) (HotNets ’25). Association for Computing Machinery, New York, NY, USA, 326–334. doi:10.1145/3772356.3772395 [3] Rukshani Athapathu and George Porter. 2025. Reconfigurability within Collective Communication Algorithms. In Proceedings of the 2nd Workshop on Networks for AI Computing (Coimbra, Portugal) (NAIC ’25). Association for Computing Machinery, New York, NY, USA, 43–49. doi:10.1145/3748273.3749203 [4] Chen Avin and Stefan Schmid. 2019. Toward demand-aware networking: a theory for self-adjusting networks. SIGCOMM Comput. Commun. Rev. 48, 5 (Jan. 2019), 31–40. doi:10.1145/3310165.3310170 [5] Jehoshua Bruck, Ching-Tien Ho, Shlomo Kipnis, and Derrick Weathersby. 1994. Efficient algorithms for all-to-all communications in multiport message-passing systems (SPAA ’94). doi:10.1145/181014.181756 [6] CALIENT Technologies, Inc. 2022. Calient’s Optical Circuit Switch (S-Series) Datasheet. https://www.calient.net/wp-content/uploads/ 2022/06/Datasheet_Calients-Optical-Circuit-Switches.pdf Accessed: 2025-07-03. [7] Eric Ding, Chuhan Ouyang, and Rachee Singh. 2025. Photonic Rails in ML Datacenters (HotNets ’25). Association for Computing Machinery, New York, NY, USA, 149–159. doi:10.1145/3772356.3772414 [8] Nathan Farrington, Alex Forencich, George Porter, P.-C. Sun, Joseph E. Ford, Yeshaiahu Fainman, George C. Papen, and Amin Vahdat. 2013. A Multiport Microsecond Optical Circuit Switch for Data Center Networking. IEEE Photonics Technology Letters 25, 16 (2013), 1589–1592. doi:10.1109/LPT.2013.2270462
Conference’17, July 2017, Washington, DC, USA
[9] Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. 2010. Helios: a hybrid electrical/optical switch architecture for modular data centers. SIGCOMM Comput. Commun. Rev. 40, 4 (Aug. 2010), 339–350. doi:10.1145/1851275. 1851223 [10] Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel Kilper. 2016. ProjecToR: Agile Reconfigurable Data Center Interconnect. In Proceedings of the 2016 ACM SIGCOMM Conference (Florianopolis, Brazil) (SIGCOMM ’16). Association for Computing Machinery, New York, NY, USA, 216–229. doi:10.1145/2934872.2934911 [11] Norm Jouppi, George Kurian, Sheng Li, et al. 2023. TPU v4: An Optically Reconfigurable Supercomputer for Machine Learning with Hardware Support for Embeddings (ISCA ’23). Association for Computing Machinery, New York, NY, USA, Article 82, 14 pages. doi:10.1145/ 3579371.3589350 [12] Anton Juerss, Vamsi Addanki, and Stefan Schmid. 2026. Trivance: Latency-Optimal AllReduce by Shortcutting Multiport Networks. arXiv:2602.17254 [cs.DC] https://arxiv.org/abs/2602.17254 [13] Anton Juerss and Stefan Schmid. 2026. Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings. arXiv:2605.12766 [cs.NI] https://arxiv.org/abs/2605.12766 [14] Mehrdad Khani, Manya Ghobadi, Mohammad Alizadeh, et al. 2021. SiP-ML: high-bandwidth optical network interconnects for machine learning training (SIGCOMM ’21). Association for Computing Machinery, New York, NY, USA, 657–675. doi:10.1145/3452296.3472900 [15] Abhishek Vijaya Kumar, Arjun Devraj, Darius Bunandar, and Rachee Singh. 2024. A case for server-scale photonic connectivity (HotNets ’24). Association for Computing Machinery, New York, NY, USA, 290–299. doi:10.1145/3696348.3696856 [16] Xudong Liao, Yijun Sun, Han Tian, Xinchen Wan, et al. 2025. MixNet: A Runtime Reconfigurable Optical-Electrical Fabric for Distributed Mixture-of-Experts Training. In Proceedings of the ACM SIGCOMM 2025 Conference (SIGCOMM ’25). Association for Computing Machinery, New York, NY, USA, 554–574. doi:10.1145/3718958.3750465 [17] William M. Mellette, Rob McGuinness, Arjun Roy, Alex Forencich, George Papen, Alex C. Snoeren, and George Porter. 2017. RotorNet: A Scalable, Low-complexity, Optical Datacenter Network. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication (Los Angeles, CA, USA) (SIGCOMM ’17). Association for Computing Machinery, New York, NY, USA, 267–280. https://doi.org/10.1145/3098822.3098838 [18] Polatis (a HUBER+SUHNER company). n.d.. Series 7000 — 384×384port Software-Defined Optical Circuit Switch. https://www.polatis. com/ Accessed: 2025-07-01. [19] George Porter, Richard Strong, Nathan Farrington, Alex Forencich, Pang Chen-Sun, Tajana Rosing, Yeshaiahu Fainman, George Papen, and Amin Vahdat. 2013. Integrating microsecond circuit switching into the data center. SIGCOMM Comput. Commun. Rev. 43, 4 (Aug. 2013), 447–458. doi:10.1145/2534169.2486007 [20] Kun Qian, Yongqing Xi, Jiamin Cao, Jiaqi Gao, et al. 2024. Alibaba HPN: A Data Center Network for Large Language Model Training (ACM SIGCOMM ’24). Association for Computing Machinery, New York, NY, USA, 691–706. doi:10.1145/3651890.3672265 [21] Le Qin, Junwei Cui, Weilin Cai, Meng Niu, Yan Yang, and Jiayi Huang. 2025. Optimizing All-to-All Collective Communication with Fault Tolerance on Torus Networks. In Proceedings of the 58th IEEE/ACM International Symposium on Microarchitecture (MICRO ’25). Association for Computing Machinery, New York, NY, USA, 659–674. doi:10.1145/ 3725843.3756057
Conference’17, July 2017, Washington, DC, USA
Anton Juerss and Stefan Schmid
[22] Mahir Rahman, Samuel Joseph, Nihar Kodkani, Behnaz Arzani, and Vamsi Addanki. 2026. Harvest: Adaptive Photonic Switching Schedules for Collective Communication in Scale-up Domains. arXiv:2602.09188 [cs.NI] https://arxiv.org/abs/2602.09188 [23] Paul Sack and William Gropp. 2015. Collective Algorithms for Multiported Torus Networks. ACM Trans. Parallel Comput. 1, 2, Article 12 (Feb. 2015), 33 pages. doi:10.1145/2686882 [24] Daniele De Sensi, Tommaso Bonato, David Saam, and Torsten Hoefler. 2024. Swing: Short-cutting Rings for Higher Bandwidth Allreduce. In 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI 24). USENIX Association, 1445–1462. [25] Aashaka Shah, Vijay Chidambaram, Meghan Cowan, Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Jacob Nelson, Olli Saarikivi, and Rachee Singh. 2023. TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, 593–612. [26] Rajeev Thakur, Rolf Rabenseifner, and William Gropp. 2005. Optimization of Collective Communication Operations in MPICH. IJHPCA 19 (01 2005), 49–66. [27] Weiyang Wang, Moein Khazraee, Zhizhen Zhong, Manya Ghobadi, Zhihao Jia, Dheevatsa Mudigere, Ying Zhang, and Anthony Kewitsch. 2023. TopoOpt: Co-optimizing Network Topology and Parallelization Strategy for Distributed Training Jobs. USENIX Association, Boston, MA, 739–767. https://www.usenix.org/conference/nsdi23/presentation/ wang-weiyang [28] William Won, Taekyung Heo, Saeed Rashidi, Srinivas Sridharan, Sudarshan Srinivasan, and Tushar Krishna. 2023. ASTRA-sim2.0: Modeling Hierarchical Networks and Disaggregated Systems for Large-model Training at Scale. 283–294. doi:10.1109/ISPASS57527.2023.00035
determines the action in phase 𝑘: the block is sent left if 𝜏𝑘 = −1, kept local if 𝜏𝑘 = 0, and sent right if 𝜏𝑘 = +1.
A
Proof. First, we show uniqueness. Assume for contradiction that two distinct vectors 𝑎, 𝑏 ∈ {−1, 0, +1}𝑠 repÍ −1 Í −1 𝑏𝑘 3𝑘 . Then resent the same offset, i.e., 𝑠𝑘=0 𝑎𝑘 3𝑘 = 𝑠𝑘=0 Í𝑠 −1 𝑘 𝑘=0 (𝑎𝑘 − 𝑏𝑘 )3 = 0, where each coefficient 𝑎𝑘 − 𝑏𝑘 lies in {−2, −1, 0, 1, 2}. Let 𝑗 be the largest index with 𝑎 𝑗 ≠ 𝑏 𝑗 . The leading term has absolute value at least 3 𝑗 , whereas all lower-order terms summed up can have at most absolute Í value 2 ℓ< 𝑗 3ℓ = 3 𝑗 − 1. Hence the leading term cannot be substituted, a contradiction which leads to a different destination. Thus the representation is deterministic. Since there are 3𝑠 = 𝑛 unique signed digit vectors and exactly 𝑛 centered offsets in {−(𝑛 − 1)/2, . . . , (𝑛 − 1)/2}, uniqueness Í −1 implies that the mapping (𝜏0, . . . , 𝜏𝑠 −1 ) ↦→ 𝑠𝑘=0 𝜏𝑘 3𝑘 is a bijection onto the centered offsets. Therefore, every destination node has exactly one signed base-3 path from every source node. It remains to show balance. Fix a phase 𝑘 and a node 𝑖. Before Í phase 𝑘, a block with digit vector 𝜏 is located at (𝑟 + ℓ<𝑘 𝜏ℓ 3ℓ ) mod 𝑛. For every digit vector 𝜏, there is exactly one source 𝑟 such that this node is 𝑖, namely Í 𝑟 ≡ 𝑖 − ℓ<𝑘 𝜏ℓ 3ℓ (mod 𝑛). Thus, the blocks stored at 𝑖 before phase 𝑘 are in one-to-one correspondence with all 3𝑠 = 𝑛 digit vectors. Among these vectors, exactly 3𝑠 −1 = 𝑛3 have 𝜏𝑘 = +1, exactly 𝑛3 have 𝜏𝑘 = −1, and exactly 𝑛3 have 𝜏𝑘 = 0. Hence, in phase 𝑘, node 𝑖 sends 𝑛3 blocks to the right, 𝑛3 blocks to the left, and keeps 𝑛3 blocks local. □
Proof of Minimal Subrings for ReTri
Lemma 1. For phase 𝑘, the subrings 𝑆𝑖(𝑘 ) are minimal under the 2𝑛 port constraint: they contain exactly the nodes that must remain mutually reachable for phase 𝑘 and all later phases, and the induced subring uses the minimum degree needed to support bidirectional communication at every node. Proof. Node 𝑢 communicates in phase 𝑘 with 𝑢 ± 3𝑘 , which lie in the same residue class modulo 3𝑘 . For every later phase 𝑗 > 𝑘, the offset is 3 𝑗 = 3 𝑗 −𝑘 · 3𝑘 , so all future peers of 𝑢 also lie in the same residue class. Therefore, any reusable topology established at phase 𝑘 must keep all nodes in 𝑆𝑖(𝑘 ) connected. Conversely, no node outside 𝑆𝑖(𝑘 ) is needed for any future offset, since all future offsets are multiples of 3𝑘 . Finally, every node must be able to communicate bidirectionally with its two phase neighbors; this requires degree two, which is exactly realized by the subring on 𝑆𝑖(𝑘 ) . Hence, the subring is minimal and includes all future peers. □
B
Ternary Block Propagation Proof
The propagation rule of ReTri relies on 𝑛 = 3𝑠 and every source-destination offset has a unique signed base-3 representation. For a block 𝐵 [𝑟, 𝑑], let Δ𝑟,𝑑 = ucr𝑛 ((𝑑 − 𝑟 ) mod 𝑛) be its centered offset. We represent this offset as Δ𝑟,𝑑 = Í𝑠 −1 𝑘 𝑘=0 𝜏𝑘 (𝑟, 𝑑)3 , where 𝜏𝑘 (𝑟, 𝑑) ∈ {−1, 0, +1}. The digit 𝜏𝑘
Lemma 2. Assume 𝑛 = 3𝑠 . For every source node 𝑟 and destination node 𝑑, the offset Δ𝑟,𝑑 has a unique representation Í −1 Δ𝑟,𝑑 = 𝑠𝑘=0 𝜏𝑘 (𝑟, 𝑑)3𝑘 with 𝜏𝑘 (𝑟, 𝑑) ∈ {−1, 0, +1}. Moreover, in every phase 𝑘, each node sends exactly 𝑛3 blocks to the left and exactly 𝑛3 blocks to the right.
Revisiting Bruck: Phase-Efficient All-to-All Communication in Reconfigurable Networks
C
Conference’17, July 2017, Washington, DC, USA
Additional Evaluation
Figure 4: Heatmap showing All-to-All speedups of ReTri (𝑛 = 9) compared to both reconfigurations with Bruck (B) (𝑛 = 8) and static All-to-All (S). The underlined speedup shows the better performing baseline.
Figure 5: Heatmap showing All-to-All speedups of ReTri (𝑛 = 243) compared to both reconfigurations with Bruck (B) (𝑛 = 256) and static All-to-All (S). The completion time is normalized by the number of nodes in the network, so that Bruck has no disadvantage by operating on a larger network.