Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings Anton Juerss
Weizenbaum Institute & TU Berlin Germany
arXiv:2605.12766v1 [cs.NI] 12 May 2026
Abstract Optical circuit-switched networks have emerged as an appealing alternative to electrical fabrics as they can reconfigure the network topology at runtime, reducing communication cost and improving bandwidth utilization. Yet exploiting optical reconfigurable networks for collective communication comes with a fundamental trade-off: each reconfiguration incurs non-negligible delay, communication must pause while the fabric reconfigures, and the benefit of a new topology depends on future traffic. The central question is therefore when reconfiguration is worth its cost. While prior work has demonstrated the benefits of reconfiguration, existing strategies use optical links only to optimize the current step, without reusing them for future steps. In this paper, we present Bridge, a reconfiguration strategy for important collective communication primitives used in AI/ML and HPC applications, namely All-to-All, AllReduce, Reduce-Scatter, and AllGather. Bridge exploits the structure of Bruck’s communication pattern to support efficient sparse reconfiguration. The key idea is to reduce propagation and transmission delay by directly connecting immediate communication partners and preserve efficient reachability to future peers through connected subrings. As a result, optical links can be reused across multiple subsequent steps, allowing the benefit of reconfiguration to amortize beyond a single step. Our evaluation shows that Bridge reduces All-to-All completion time by typically 3× to 10× over static baselines even with millisecond-scale reconfiguration delays. For AllReduce, Bridge uniformly outperforms existing reconfiguration strategies, delivers up to 1.5× speedup, and exceeds the bandwidth-optimal Ring algorithm by 1.5× to 6.6× on low to moderate-sized workloads.
1
Introduction
The rapid growth of deep learning models and datasets has made both training and inference increasingly dependent on large-scale distributed infrastructure. To meet these demands, the four leading US hyperscalers have reportedly announced plans to invest $650 billion in AI infrastructure in 2026 alone [26]. A considerable share will go into GPU- and TPU-powered datacenters, where performance
Stefan Schmid
TU Berlin & Weizenbaum Institute Germany depends critically on collective communication among accelerators. Inter-node communication becomes increasingly important, making network interconnects a major bottleneck for communication-intensive collectives such as AllReduce and All-to-All [17]. The design of datacenter interconnect fabrics therefore plays a central role in the scalability and efficiency of largescale ML systems [10, 14, 24]. Whereas electrically switched networks are power-intensive and may lead to performance bottlenecks, optical networks have emerged as a promising opportunity to reconfigure network topology at runtime, enabling direct-connect topologies that significantly improve both performance and efficiency [10, 18]. Optical circuit switches (OCSs) establish optical paths between pairs of GPUs by steering light from input to output ports [10]. As these paths can be reconfigured, the network topology can be aligned with the communication traffic of the active workload. [2, 5, 10]. Collective communication is particularly compatible with optical reconfigurable networks (ORNs): it largely follows one-to-one data exchanges, the communication pattern for which the topology can be optimized is known in advance, and collectives proceed in synchronized phases, between which the network can be reconfigured [10, 11, 18, 30]. This motivates low-degree topologies such as rings, which preserve end-to-end connectivity among all nodes at degree two using 2𝑛 optical ports [10, 12]. More generally, the topology must not remain a single ring throughout the collective, but may instead evolve into multiple connected subrings. Many algorithms exist to solve collectives for static photonic topologies that deliberately avoid reconfiguration, but these inevitably suffer from congestion caused by multi-hop forwarding between GPUs. Conversely, a dynamically reconfigurable topology can, in principle, eliminate congestion by establishing direct optical paths between communicating GPUs, but only at the cost of reconfiguration delay. Balancing this fundamental tradeoff becomes essential to realize the practical benefits in reconfigurable networks.
Prior work on collective communication for ORNs explored different directions: one approach, typically considering no or negligibly low reconfiguration delay [3, 4], concludes that every-step topology adaptations are beneficial. These schedules are commonly derived from Birkhoff–von Neumann (BvN) decompositions [6] of aggregate traffic matrices [2, 17, 18], which express the overall communication demand as a weighted sum of per-step matchings. Second, systems such as TopoOpt [14, 30] assume that adapting the network during collective operations incurs prohibitive overhead due to high reconfiguration delay. Consequently, the network can be reconfigured only once before model training begins. A third line explicitly trades off reconfiguration delay against completion time gains obtained by ORNs [2, 7]. However, existing reconfigurable strategies are often constrained by the underlying communication algorithm. Figure 1 visualizes this for 64 nodes by comparing the completion time of state-of-the-art algorithms, Halving-Doubling (HD) and Bruck [8]. For HD all schedules have identical cost until reconfigurations start, whereas Bruck reconfigures earlier and reuses reconfigurable links to form subrings which reduce costs for subsequent steps significantly.
Completion Time
Halving Doubling R=0 R=1 R=2
in a subring. This enables high reconfiguration overheads to be amortized across multiple steps, increasing its benefit. In our evaluation, Bridge reduces AllReduce completion time consistently against existing reconfiguration strategies with speedups of up to 1.5× and exceeds the bandwidthoptimal Ring algorithm by 1.5× to 6.6× on low to moderatesized workloads. Bridge improves All-to-All completion time over static solutions by typically up to 10× at low reconfiguration delays, and even by up to 5× when reconfiguration delays are in the milliseconds. Compared to BvN-based Bruck schedules, Bridge achieves speedups of up to 2.6× for configurations with 1 ms reconfiguration delay. Our key contributions are: • We introduce Bridge, a novel approach that leverages the communication pattern of the state-of-the-art algorithm by Bruck to realize AllReduce and All-to-All by reusing optical links, thereby enabling sparse, infrequent or even single reconfigurations (Section 3). • We characterize the optimal reconfiguration schedules for All-to-All (Section 3.3), Reduce-Scatter (Section 3.4), and AllGather (Section 3.5) for any fixed number of reconfigurations and extend the approach to networks with fewer than 2𝑛 optical ports (Section 3.7). • We conduct large-scale simulations in Astra-Sim [31] using ns-3 [1] as the network backend, comparing Bridge for AllReduce (Section 4.3) and All-to-All (Section 4.2) against existing reconfiguration strategies for Bruck and Halving-Doubling, as well as against static baselines. Our evaluation spans message sizes from 1 KB to 256 MB, realistic reconfiguration delays from 1 𝜇s to 5 ms, and a wide range of network sizes and per-hop delays. • To support reproducibility and facilitate follow-up work, we will release our simulation code and experimental artifacts as open source together with this paper.
Bruck R=0 R=1 R=2
Steps
Steps
Figure 1: Cumulative AllReduce communication cost of Bruck compared to HD for 𝑛 = 64 with 𝑅 = 0, 1, 2 reconfigurations (reconfiguration delay is not considered). This paper is motivated by the observation that existing reconfiguration algorithms are myopic and miss an important optimization opportunity: optical links can be reused and reconfiguration overhead amortized for future steps. By lowering cost relative to static structures over multiple steps, the benefit of a reconfiguration is no longer limited to a single step; instead, reconfiguration overhead can be spread and amortized as reconfigured links provide a Bridge to subsequent steps. We propose Bridge, a reconfiguration strategy that constructs subrings, consisting of active communication pairs, which preserve reachability to peers in subsequent steps. Based on Bruck’s algorithm, we derive optimal reconfiguration schedules for AllReduce and All-to-All. As a result, once the communication of a reconfigured step is completed, the same topology can be reused across future steps without further reconfiguration, while peers are placed closer together
2
Motivation
Collective communication primitives specify communication objectives among a group of GPUs, such as AllReduce, Reduce-Scatter, AllGather and All-to-All [11, 29]. Collective algorithms realize these primitives by following a predefined communication pattern [24]. They are typically organized as a sequence of communication steps, in each of which a GPU sends data to exactly one other GPU [27, 29]. In AllReduce, each node contributes data to a global reduction whose result is returned to all nodes, often via a Reduce-Scatter followed by an AllGather [29]. In All-to-All, each GPU sends a distinct message to every other GPU. These collectives can be implemented with a variety of algorithms [8, 16, 27, 29]
𝑇 (𝑚, 𝐴) = 𝜎 (𝐴) · 𝛼𝑠 +
𝜎 (𝐴) ∑︁−1 𝑘=0
ℎ𝑘 · 𝛼 ℎ +
𝜎 (𝐴) ∑︁−1
𝑚𝑘 · 𝑐 𝑘 · 𝛽 + 𝑅 · 𝛿
𝑘=0
where, in each step 𝑘 of total 𝜎 (𝐴) steps, the algorithm 𝐴 incurs a startup latency 𝛼𝑠 (e.g., data preparation), per-hop
Cost Components:
Cost Distribution
and place substantial demands on the network, especially All-to-All. Optical Reconfigurable Networks (ORNs) offer an opportunity to address this bandwidth overhead by adapting connectivity at runtime [2, 4, 14, 17]. Unlike packet-switched electrical fabrics, however, an OCS provides only a one-toone circuits at any moment of time [10, 20], which naturally leads to low-degree topologies. Ring-like fabrics are therefore a practical and common design for OCS-based distributed ML systems [2, 10, 18]. Recent work exploits the rail structure of scale-out systems—fixed groups of links or nodes that communicate within the same parallel communication lane— by replacing packet switches within a rail with OCSs [10]. This realizes direct-connect rings that preserve connectivity at low node degree while enabling reconfiguration across communication phases. Beginning with TPUv4 [14] and continuing in later large-scale TPU systems such as Ironwood [15], hierarchical accelerator designs combine local electrical connectivity with a reconfigurable optical layer, motivating models that account for shared optical resources and explicit reconfiguration overheads. A common choice to implement All-to-All is to complete the operation in 𝑛 − 1 parallel point-to-point exchanges offering no opportunity to reconfigure the network to reduce particularly costly traffic [25, 29]. For AllReduce, HalvingDoubling (HD) is a common latency-optimal implementation where in step 𝑘 each node 𝑢 communicates to 𝑣 = 𝑢 ⊕ 2𝑘 (recursively halves/doubles distance) for log2 𝑛 steps, whereas Ring is bandwidth-optimal [13] and performs 𝑛 − 1 clockwise single blocks transmissions [29]. Bruck provides a promising All-to-All and also AllReduce algorithm for ORNs [8], where each node, given a step 𝑘, communicates to its peer at offset 2𝑘 . This completes All-to-All or AllReduce in log2 𝑛 steps. On static fabrics, Bruck matches the cost of HD, but replaces its pairwise exchanges with a cyclic communication pattern which naturally forms connected subrings. To assess the performance of collective communication algorithms, the Hockney 𝛼 − 𝛽 cost model is commonly used. In line with related work [2, 16, 27, 28, 31], we extend this cost model to be topology-aware and consider a congestion factor 𝑐 (overlapping flows per link), decompose network latency into a per-hop latency 𝛼ℎ (propagation delay and per-hop message processing) and a per-step latency 𝛼𝑠 . We further model network reconfiguration overheads with 𝛿 as follows:
100%
0,2 ms
Per-Step
Per-Hop
AllReduce
0,5 ms
0,1 ms
Bandwidth
Congestion
All-to-All
1,1 ms
0,1 ms 10,1 ms
32KB 32MB 32KB 32MB Ring Ring Bruck Bruck
32KB 32MB Bruck Bruck
66% 33% 0%
Figure 2: Cost distribution and completion time of state-of-the-art algorithms for AllReduce and All-toAll. The opportunity for improvement through ORNs is greater for All-to-All, whereas for AllReduce it is more limited for large workloads. delay 𝛼ℎ for each hop ℎ𝑘 required to reach its destination, a transmission delay of 𝛽 · 𝑚𝑘 · 𝑐𝑘 (𝑚𝑘 is the chunk size transmitted in step 𝑘, 𝛽 the network cost per byte — inverse of bandwidth 𝑏) and a reconfiguration overhead 𝛿 for the number of reconfigurations 𝑅. We ommit computation costs, as these are similar among collective algorithms. [29]. Although recent static approaches for rings and tori use topology-aware scheduling or mirroring to reduce congestion and path length [16, 27], they cannot remove the fundamental costs imposed by the topology itself. Figure 2 shows the completion time distribution of Ring and Bruck in Astra-Sim [31] for AllReduce and All-to-All on a static ring topology. ORNs directly connect peers, reducing the number of hops and congestion on each link. For All-to-All, per-hop delay dominates at small workloads and congestion at large ones, making direct connections through OCSs desirable. For AllReduce, Bruck shows a similar trend, but the bandwidthoptimal Ring highlights a key limitation: for large workloads, completion time is dominated by unavoidable transmission cost (𝑚 · 𝛽) rather than congestion overhead. Consequently, the potential of reconfiguration is larger for All-to-All, while for AllReduce it is strongest for small workloads and more constrained for large ones. Prior work on leveraging ORNs for All-to-All largely follows two directions: either the topology is reconfigured greedily at every step when reconfiguration delay is assumed negligible [3, 4, 23], or it is configured once before the collective begins and then kept static throughout execution when reconfiguration delay is high [14, 15, 30]. Beyond these extremes, and a broadening range of options, the design space of dynamic reconfiguration during collective communication has remained largely unexplored. For AllReduce, the same two baselines exist, together with prior work on dynamic reconfiguration [2] for HD, which we refer to as R-HD. However, R-HD remains fundamentally limited because each reconfiguration primarily benefits only the current step and
does not preserve connectivity for subsequent ones. The RHD reconfiguration strategy initially operates on a ring until the first reconfiguration is scheduled which then directly connects peers. Each node can reach only its current peer and these connections are not useful in later steps. As a result, the topology must be reconfigured again to proceed [2]. Each reconfiguration therefore benefits only a single step and must justify the delay of each reconfiguration. According to our evaluation (Section 4), the gain from one shortcut is often too small to amortize the cost of reconfiguration. The main challenge in reconfigurable optical networks is that the communication-optimal strategy—directly reconnecting active pairs in every step—quickly becomes impractical when reconfiguration delay is non-negligible [2, 14, 15, 20]. Reconfiguration schedules must therefore be selfsustaining, in the sense that instead of disrupting the remaining communication pattern, they should at minimum preserve and ideally improve it. Therefore, we posit that a single, efficient reconfiguration needs to satisfy three conditions: Condition 1: Minimize communication costs in the current step Condition 2: Preserve reachability to peers of subsequent steps Condition 3: Reduce costs for subsequent steps by established, reusable reconfigurable links without further reconfiguration To minimize communication cost in the current step, a necessary condition is that reconfigurations directly connect active communication pairs [2, 30]. R-HD satisfies this condition, but remains limited because the resulting topology is useful only for the current step and must be reconfigured in the next step. The second condition addresses the key requirement for sparse reconfiguration: beyond optimizing the current step, a reconfiguration must preserve sufficient reachability for the remaining communication pattern so that the collective can continue without immediate further reconfiguration. Condition 3 strengthens this requirement further. Preserving reachability alone allows the collective to proceed, but an effective and self-sustained reconfiguration should also reduce the cost of subsequent steps by reusing established reconfigurable links useful beyond the current exchange. This enables the cost of a single reconfiguration to be amortized across multiple subsequent steps, thereby substantially reducing communication costs and strengthening the case for reconfiguration. More precisely, as optical ports are limited in number, ring-like topologies are the natural design structure [10]. Satisfying Conditions 1–3 therefore requires reconfiguration schedules that form connected Subrings: they must directly connect the active communication pairs, while at
the same time creating a Bridge to future peers through reusable reconfigurable links. In this way, future peers are brought closer and the cost of later steps is reduced. Such subrings should remain as small as possible, containing only the current peers and the minimum set of future peers needed to preserve reachability without further reconfiguration.
3
BRIDGE
In this section, we introduce Bridge: a reconfiguration strategy based on Bruck’s communication pattern. First, we establish in Section 3.1 the reconfiguration strategy of Bridge for All-to-All and AllReduce. We then show in Section 3.2 how Bruck can be leveraged to address the fundamental challenges of reconfiguration scheduling. Building on this, we derive and prove the optimal reconfiguration schedules of Bridge for All-to-All (Section 3.3) and Reduce-Scatter (Section 3.4), which translate to optimal schedules for AllGather (Section 3.5). In Section 3.6, we outline how to determine the optimal number of reconfigurations. Finally, Section 3.7 extends the model to settings with fewer than 2𝑛 optical ports.
3.1
Approach: Reusable Subrings with Bruck
We consider a scale-up network of 𝑛 nodes (power-of-two) interconnected by a programmable OCS fabric initially arranged as a ring [10, 18]. The fabric provides 2𝑛 optical ports, so that each node maintains one incoming and one outgoing optical connection and thus communicates with exactly one peer at a time [10]. Our approach builds on Bruck’s communication pattern [8], which is particularly well suited to reconfigurable networks. For All-to-All and Reduce-Scatter under a singleport communication model [27, 29], Bruck completes in 𝑠 := ⌈log2 𝑛⌉ steps. In step 𝑘 ∈ {0, . . . , 𝑠 − 1}, each node 𝑢 communicates with node 𝑢 + 2𝑘 mod 𝑛, that is, with a peer at ring distance 2𝑘 . For All-to-All, every step transmits the same amount of data, namely 𝑚2 . For Reduce-Scatter, the same communication pattern can be used, while the transmitted data is determined by the standard block propagation algorithm [16, 27, 29]. On static fabrics, Bruck exhibits the same number of steps and the same aggregate hop count, congestion, and transmitted data as HD, but follows a cyclic rather than pairwise communication pattern. For arbitrary 𝑛, the algorithm progresses identically except for the last step: if 2𝑠 −1 < 𝑛 < 2𝑠 , then each node sends only (𝑚/𝑛) (𝑛 − 2𝑠 −1 ) data in step 𝑠 − 1. In multiport networks with 𝑝 local ports per node, several independent communication offsets can be scheduled in parallel within one step, effectively collapsing Bruck in log𝑝+1 𝑛 steps.
7
0
1
6
7 2
5
4 k=0
3
0
1
6
7
0
1
2 6 5
4 k=1
3
2 5
4 k=2
3
Figure 3: Bruck’s communication pattern for 8 nodes separated in 3 steps. Reconfigurations in each step would result in the displayed topology. The OCS is omitted for clarity. Figure 3 visualizes the key property of Bruck’s communication pattern across consecutive steps: transitivity. If node 𝑢 communicates with node 𝑣 in step 𝑘, and node 𝑣 communicates with node 𝑤 in the same step, then node 𝑢 communicates with node 𝑤 in step 𝑘 + 1, since 2𝑘+1 = 2𝑘 + 2𝑘 . Thus, placing peers of the current step close together also keeps future peers close. Furthermore, these peer connections form a closed subring of size 2𝑛𝑘 , containing both all active peers and all future peers reachable from them. This directly addresses the three requirements from Section 2: it enables minimal cost in the current step, preserves reachability for subsequent steps, and reduces their cost as well through reusable links. To formalize this process, let x = (𝑥 0, . . . , 𝑥𝑠 −1 ) ∈ {0, 1}𝑠 denote a reconfiguration schedule, where 𝑥𝑘 = 1 indicates that the topology is reconfigured immediately before step 𝑘, and 𝑥𝑘 = 0 means that the topology from the previous step is reused. The total number of reconfigurations is then Í −1 𝑅 := 𝑠𝑘=0 𝑥𝑘 and a schedule with 𝑅 reconfigurations is denoted as xR . Algorithm 1 summarizes Bridge, where in each communication step 𝑘, the schedule x determines whether the OCS is reconfigured to the subring associated with offset 2𝑘 or whether the previously established topology is reused. Algorithm 1 Bridge: Reusable OCS Subrings with Bruck Input: 𝑛 = 2𝑠 nodes, reconfiguration schedule x = (𝑥 0, . . . , 𝑥𝑠 −1 ) 1: 𝑠 ← log2 𝑛 2: for each step 𝑘 ∈ {0, . . . , 𝑠 − 1} do 3: if 𝑥𝑘 = 1 then 4: Construct subring 𝑆𝑘 for offset 2𝑘 5: for each node 𝑢 do 6: Set optical link (𝑢, 𝑢 + 2𝑘 mod 𝑛) 7: end for 8: else 9: Reuse the topology from step 𝑘 − 1 10: end if 11: Perform step 𝑘 of Bruck on the current topology 12: end for
For a given reconfiguration schedule x and a collective algorithm 𝐴, we further define the stepwise improvement over the static fabric as Δ(x, 𝐴) = Δ0 (x, 𝐴), . . . , Δ𝑠 −1 (x, 𝐴) where Δ𝑘 (x, 𝐴) denotes the reduction in communication time of step 𝑘 relative to the static algorithm 𝐴, while 𝑅 · 𝛿 captures its overhead.
3.2
Minimal Connected Subrings
To ensure that reconfiguration preserves both locality and connectivity, we next formalize the formation of minimal connected subrings which can be directly derived from Bruck’s communication pattern. Such subrings contain exactly the nodes that must remain reachable after a reconfiguration step. Formally, for each subring 𝑖 ∈ {0, . . . , 2𝑘 − 1} in step 𝑘, we define 𝑆𝑖(𝑘 ) as 𝑆𝑖(𝑘 ) := { 𝑢 ∈ {0, . . . , 𝑛 − 1} | 𝑢 ≡ 𝑖
(mod 2𝑘 ) }.
Thus, the network is partitioned into 2𝑘 subrings of size 2𝑛𝑘 , and each node 𝑢 is connected to 𝑢 + 2𝑘 mod 𝑛 (to which it sends data) and 𝑢 − 2𝑘 mod 𝑛 (from which it receives data). Hence, the current communication peer 𝑢 + 2𝑘 mod 𝑛 is directly adjacent, while future Bruck peers remain reachable within the same subring. Lemma. For step 𝑘, the subring 𝑆𝑖(𝑘 ) is minimal: it contains exactly the current peer, all future peers, and peers of peers reachable under Bruck from step 𝑘 onward. Proof. In step 𝑘, node 𝑢 communicates with 𝑢 + 2𝑘 , so its current peer lies in the same residue class modulo 2𝑘 . In every subsequent step 𝑗 > 𝑘, the communication offset is 2 𝑗 = 2 𝑗 −𝑘 · 2𝑘 , i.e., again a multiple of 2𝑘 . Therefore, every future peer of 𝑢, and recursively every peer of such a peer, remains in the same residue class modulo 2𝑘 , namely in 𝑆𝑖(𝑘 ) . Since this residue class contains exactly 2𝑛𝑘 nodes, and every node in it is reachable by repeated communication steps of size 2𝑘 , 2𝑘+1, . . ., the subring contains exactly the nodes needed to preserve current and future reachability, and no more. □ This shows that Bridge forms minimal subrings in which reconfigurable links can be reused to reach future peers. Consequently, for a reconfiguration schedule x, the cost of a topology reconfiguration can be amortized across multiple steps: whenever 𝑥𝑘 = 1, the reconfiguration at step 𝑘 reduces not only the cost of that step, but also that of subsequent ones, i.e., Δ𝑖 (x, Bruck) > 0 for 𝑖 > 𝑘. Figure 4 illustrates the subring formation for 𝑅 = 1 and 𝑛 = 16. In this example, Bruck is reconfigured at step 𝑘 = 2, leading to 22 = 4 subrings of size 4. As a result, each node, for example node 0, reaches its communication peer node 4 in a single hop at step 𝑘 = 2, while requiring only two hops at step
𝑘 = 3 to node 8. By contrast, R-HD benefits from reconfiguration only at step 𝑘 = 3, since directly connecting peers earlier does not preserve the connectivity required for subsequent steps. Thus, for R-HD only Δ3 (x𝑅=1, R-HD) > 0, whereas for Bridge both Δ2 (x𝑅=1, Bridge) > 0 and Δ3 (x𝑅=1, Bridge) > 0. As we show in Section 4, this enables Bridge to outperform R-HD by up to 1.5× in completion time leading to Δ(xR, Bridge) ≥ Δ(xR, R-HD) for 𝑅 ∈ {0, ..., log2 𝑛}.
3.3
Proof by Contradiction. Define the marginal cost of extending a segment from length 𝑟 − 1 to length 𝑟 as 𝐷 (𝑟 ) := 𝐶 seg (𝑟 ) − 𝐶 seg (𝑟 − 1) = 𝛼𝑠 + 𝑐 2𝑟 −1 .
where 𝑐 := 𝛼ℎ + 𝛽 𝑚2 . Hence the total cost of a schedule is 𝐶𝐴2𝐴 (𝑟 1, . . . , 𝑟 𝑝 ) =
𝑝 ∑︁
𝐶 seg (𝑟 𝑗 )+𝑅𝛿 = 𝑠𝛼𝑠 +𝑐
R-HD
12 10 9 8
k=3
7 6
(2𝑟 𝑗 −1)+𝑅𝛿.
𝑗=1
𝑗=1
14 15 0 01 2
𝑝 ∑︁
Bruck
3
13
4
12
5
11
14 15 0 01 2
Subrings 3 4
10 9 8
7 6
5
0
4
1
5
= 122
8 6
9 3
13 7
10 15
11
14
Since 2𝑟 −1 is strictly increasing, 𝐷 (𝑟 ) is strictly increasing in 𝑟 . Segments of the same size incur the same cost. Assume an optimal schedule contains two segment lengths 𝑟 𝑎 and 𝑟𝑏 with 𝑟 𝑎 ≥ 𝑟𝑏 + 2. In this case, we can move one step from the longer segment to the shorter one, i.e., 𝑟 𝑎′ = 𝑟 𝑎 − 1 and 𝑟𝑏′ = 𝑟𝑏 + 1. The total number of steps remains unchanged. The corresponding change in cost is: 𝐶 seg (𝑟 𝑎 )+𝐶 seg (𝑟𝑏 ) − 𝐶 seg (𝑟 𝑎 −1)+𝐶 seg (𝑟𝑏 +1) = 𝐷 (𝑟 𝑎 )−𝐷 (𝑟𝑏 +1). Because 𝑟 𝑎 ≥ 𝑟𝑏 + 2, we have 𝑟 𝑎 > 𝑟𝑏 + 1, and since 𝐷 (𝑟 ) is strictly increasing 𝐷 (𝑟 𝑎 ) > 𝐷 (𝑟𝑏 + 1). Therefore 𝐶 seg (𝑟 𝑎 ) + 𝐶 seg (𝑟𝑏 ) > 𝐶 seg (𝑟 𝑎 − 1) + 𝐶 seg (𝑟𝑏 + 1), which contradicts optimality. Hence, no optimal schedule can contain two segments whose lengths differ by at least two, since they could be rearranged to balanced segment sizes. Therefore, in every optimum, |𝑟 𝑎 − 𝑟𝑏 | ≤ 1 for all 𝑎, 𝑏. □ Under the simplifying assumption that 𝑅 + 1 divides 𝑠, all optimal segments have the same length 𝑟 1 = 𝑟 2 = · · · = 𝑠 . 𝑟 𝑅+1 = 𝑅+1 Theorem 3.2. Given a network of 𝑛 nodes and 𝑅 reconfigurations, the optimal All-to-All schedule for Bruck is periodic: log2 𝑛 steps. reconfiguration should occur every 𝑅+1
𝑟 −1 ∑︁ 𝑚 𝑖 𝐶 seg (𝑟 ) = 𝛼𝑠 + 𝛼ℎ + 𝛽 2 = 𝑟𝛼𝑠 + 𝑐 (2𝑟 − 1), 2 𝑖=0
11
Lemma 3.1. For fixed 𝑅, every optimal All-to-All schedule has segment lengths that differ by at most one.
All-to-All: Periodic Reconfigurations
To minimize communication cost for Bruck, we first prove that periodic reconfigurations are optimal (Theorem 3.2) and then determine in Section 3.6 how many reconfigurations are worthwhile. We characterize the reconfiguration space of the algorithm across 𝑠 = log2 𝑛 steps, where the network may reconfigure at each step. We first find optimal reconfiguration schedules to reduce All-to-All completion time 𝐶𝐴2𝐴 with Bruck’s algorithm, where each node sends per step the same amount of data, 𝑚𝑘 = 𝑚2 . As congestion and communication distance in Bruck are identical, the cost contribution of step 𝑘 is (total costs are in Ω(𝑛)): 𝑚 𝛼𝑠 + 𝛼ℎ ℎ𝑘 + 𝛽𝑚𝑘 𝑐𝑘 = 𝛼𝑠 + 𝛼ℎ + 𝛽 ℎ𝑘 . 2 Consider a schedule with exactly 𝑅 reconfigurations, for Í𝑝 which the lengths of segments sum up to 𝑠 = 𝑗=1 𝑟 𝑗 . Each segment captures the progression of Bruck between topology reconfigurations. Within each segment, the communication distance in Bruck starts at 1 and doubles at every step, so a segment of length 𝑟 has cost
13
Since 𝑠𝛼𝑠 , 𝑐 and 𝑅𝛿 are fixed for a given 𝑅, minimizing the total cost is equivalent to minimizing Í𝑝 𝑟 𝑗 Í𝑝 𝑗=1 2 with subject to 𝑗=1 𝑟 𝑗 = 𝑠.
k=2
Figure 4: Network topologies for 𝑛 = 16 and 𝑅 = 1: RHD reconfigured at step 𝑘 = 3 (left), and Bridge at step 𝑘 = 2 (middle/right). For clarity, the OCS connecting the nodes is omitted. Subrings (right) are grouped from Bruck at 𝑘 = 2.
Thus, the resulting total cost becomes: 1 ★ 𝐶 A2A (𝑅) = 𝑠𝛼𝑠 + (𝑅 + 1)𝑐 𝑛 𝑅+1 − 1 + 𝑅𝛿,
𝑚 . 2 This concludes, 𝑅 periodic reconfigurations are optimal and reduce costs from Ω(𝑛) to 𝑂 (𝑅 · 𝑛 1/(𝑅+1) ).
3.4
𝑐 = 𝛼ℎ + 𝛽
Reduce-Scatter: Early Reconfigurations
We now search for optimal reconfiguration schedules to complete the AllReduce collective with Bruck. AllReduce is typically decomposed through the Rabenseifner decomposition [29] into a Reduce-Scatter phase followed by an AllGather phase. We first identify optimal schedules for ReduceScatter where Bruck’s algorithm transmits data starting at 𝑚 0 = 𝑚2 which halves in every subsequent step. The cost of step 𝑘 ∈ {0, . . . , 𝑠 − 1} is 𝑚 𝑚 𝛼𝑠 + 𝛼ℎ ℎ𝑘 + 𝛽𝑚𝑘 𝑐𝑘 = 𝛼𝑠 + 𝛼ℎ 2𝑘 + 𝛽 𝑘+1 2𝑘 = 𝛼𝑠 + 𝛼ℎ 2𝑘 + 𝛽 . 2 2
As established in Theorem 3.1, the optimal reconfiguration periods to reduce path lengths and latency for Bruck are periodic. In the following, we therefore focus on finding the optimal schedule to minimize transmission delay. Consider one reconfiguration period covering steps 𝑎, 𝑎 + 1, . . . , 𝑏 with 0 ≤ 𝑎 ≤ 𝑏 ≤ 𝑠 − 1. The transmission cost of step 𝑘 in this period is 𝑚 𝑚 𝛽𝑚𝑘 ℎ𝑘 = 𝛽 𝑘+1 2𝑘 −𝑎 = 𝛽 𝑎+1 , 2 2 Since 2 are constant across all schedules, they can be omitted. Minimizing the sum of all steps in the period yields the ILP: ∑︁ (𝑏 − 𝑎 + 1) 𝑧𝑎,𝑏 𝐶𝑅𝑅𝑆 = min 2𝑎 0≤𝑎≤𝑏 ≤𝑠 −1 Í with subject to = 1, 𝑡 ∈ {0, . . . , 𝑠 − 0≤𝑎≤𝑡 𝑧𝑎,𝑏 𝑡 ≤𝑏 ≤𝑠 −1 Í 1} and 𝑧𝑎,𝑏 = 𝑅 + 1, for 0 ≤ 𝑎 ≤ 𝑏 ≤ 𝑠 − 1 where 𝑧𝑎,𝑏 ∈ {0, 1} indicates whether the interval [𝑎, 𝑏] is chosen. Each chosen variable 𝑧𝑎,𝑏 = 1 represents one reconfiguration period covering exactly the steps 𝑎, . . . , 𝑏. The ILP returns the transmission-delay-optimal reconfiguration schedule and reveals the asymptotically optimal placement of reconfigurations, where resetting the distance is most valuable early in the algorithm. 𝑚𝛽
Theorem 3.3. Given a network of 𝑛 nodes, 𝑠 steps and 𝑅 reconfigurations, Bridge partitions 𝑠 in the optimal transmissiondelay schedule for Reduce-Scatter in 𝑅 + 1 periods minimizing 𝐶𝑅𝑅𝑆 . For every fixed number 𝑅 of reconfigurations, the optimal Reduce-Scatter schedule is different and is given by the ILP above. However, the reconfiguration schedules are independent of network parameters and therefore only need to be computed once. Finally, we observe that for small networks or for a large number of reconfigurations, the transmissionoptimal and latency-optimal Reduce-Scatter schedules coincide. Intuitively, as 𝑅 increases relative to the total number of steps 𝑠 = log2 𝑛, every period becomes very short, so the space of feasible schedules collapses to partitions consisting only of periods of length 1 and 2. In our evaluation (Section 4, the optimal schedules were computed within milliseconds for networks of up to 256. Further, the optimal reconfiguration points for Reduce-Scatter occur earlier than the periodic reconfigurations of All-to-All.
3.5
step is constant: 𝛽𝑚𝑘 ℎ𝑘 = 𝛽
𝑚 𝑚 𝑠 −1−𝑘 2 =𝛽 . 2 2 𝑠 −𝑘
Since AllGather reverses both the message-size evolution and the communication distances of Reduce-Scatter, the total transmission cost of an AllGather schedule is identical to that of the reversed Reduce-Scatter schedule [29]. Therefore, for any fixed number 𝑅 of reconfigurations, the transmission-optimal AllGather schedule is the reverse of the transmission-optimal Reduce-Scatter schedule. Consequently, whereas Reduce-Scatter places reconfigurations early, AllGather places them late to optimize for transmis★ ) is the transmission-optimal schedsion delay. If (𝑟 1★, . . . , 𝑟 𝑅+1 ★ , . . . , 𝑟 ★) is optimal for Allule for Reduce-Scatter, then (𝑟 𝑅+1 1 Gather. Regarding reconfiguration schedules for optimal latency, reconfiguration periods are balanced as in 3.3. Unlike Reduce-Scatter, subsequent communication partners are not reached naturally after a reset since communication distance is strictly decreasing. Before the collective starts, we construct the subring to preserve reachability until the next reconfiguration step 𝑘, effectively connecting communication peers of step 𝑘 − 1. Since the communication distance decreases, all nodes remain reachable until the next reconfiguration, while the cost is minimized at step 𝑘 −1. The optimization is also reversed compared to Reduce-Scatter: in Reduce-Scatter, we minimize the cost of the immediate next step and let it double thereafter, whereas in AllGather, we halve the cost at each step until it reaches its minimum just before the next reconfiguration. At step 𝑘, we reconfigure the topology according to Bruck for the next reconfiguration step, or into a ring if no further reconfiguration occurs. This leads Bridge to delay AllGather reconfigurations relative to a periodic schedule.
𝑥 𝑅=1 (BridgeAll−to−All ) 𝑥 𝑅=1 (BridgeReduce−Scatter ) 𝑥 𝑅=1 (BridgeAllGather ) 𝑥 𝑅=2 (BridgeAll−to−All ) 𝑥 𝑅=2 (BridgeReduce−Scatter ) 𝑥 𝑅=2 (BridgeAllGather )
𝑘 =0 0 0 0 0 0 0
1 0 0 0 0 1 0
2 0 1 0 1 0 0
3 1 0 0 0 1 1
4 0 0 1 1 0 0
5 0 0 0 0 0 1
Table 1: Reconfiguration schedules for Bridge with 𝑛 = 64 and 𝑅 = 1/𝑅 = 2, 𝑘 = 1 indicates reconfiguration before step 𝑘.
AllGather: Late Reconfigurations
AllGather is the reverse communication pattern of ReduceScatter [29]. In Bruck’s algorithm, the communication distance starts at ℎ𝑘 = 2𝑠 −1−𝑘 for 𝑘 = 0, . . . , 𝑠 − 1 while the transmitted data starts at 𝑚/𝑛 and doubles in every step [8]. Hence, as in Reduce-Scatter, the transmission cost of one
Table 1 compares the reconfiguration schedules computed by Bridge for 64 nodes. For All-to-All, the schedules are strictly periodic. For Reduce-Scatter, they shift one step earlier for both 𝑅 = 1 and 𝑅 = 2, whereas for AllGather they shift correspondingly later.
3.6
How often are Reconfigurations beneficial?
To determine how often the network should be reconfigured according to previous optimal schedules, the remaining optimization problem is to minimize the total cost over all feasible values of 𝑅, with 0 ≤ 𝑅 ≤ 𝑠, which is possible to compute in polynomial time. For All-to-All the optimal number of reconfigurations is A2A 𝑅★ A2A = arg min 𝐶𝑅 . 0≤𝑅 ≤𝑠
For Reduce-Scatter, the latency-optimal case is identical to All-to-All, so the optimal number of reconfigurations is again obtained by minimizing the cost for periodic schedules over 𝑅. For the transmission-optimal case, however, the schedule is not balanced and the exact optimum is given by the interval formulation of Theorem 3.3. The optimal number of reconfigurations is then RS 𝑅★ RS = arg min 𝐶𝑅 . 0≤𝑅 ≤𝑠
Since the optimal schedules for Reduce-Scatter diverge between latency- and bandwidth-constrained configurations, the relevant optimum is the minimum completion time across both cases, namely 𝑅★ RS for the bandwidth-dominated setting and 𝑅★ for the latency-dominated setting. A2A
3.7
Networks with less than 2𝑛 OCS ports
For settings in which the OCS provides fewer than 2𝑛 optical ports, we extend the model to hierarchically connected static blocks that share reconfigurable optical links in order to preserve a connected subring. Let 𝑧 denote the number of available optical ports. Then blocks of ⌈ 2𝑛 𝑧 ⌉ consecutive nodes share two optical ports, one in each direction, and together form a hierarchical ring. This abstraction is motivated by hierarchical systems such as Google’s TPUv4 [14], where blocks of chips communicate locally over an electrical fabric and access the optical layer only at the block boundary. Within each block, nodes communicate via static electrical links, while only the leftmost and rightmost nodes connect through the OCS to neighboring blocks. Reconfigurable links can still create shortcut paths that improve throughput, while the electrical substrate preserves connectivity to future communication partners without requiring frequent reconfigurations. Compared to our initial assumption of 2𝑛 OCS ports, reconfigurations with Bruck in the matched block cluster no longer reduce the effective communication distance to one hop, but only to 2𝑛 𝑧 . As a result, this strategy is beneficial in sufficiently large networks, where the communication distance in a given step exceeds the size of the matching cluster.
4
Evaluation
In order to complement our analytically derived reconfiguration schedules presented in Section 3, we assess in this section the performance of Bridge for All-to-All (Section 4.2) and AllReduce (Section 4.3) compared to state-of-the-art reconfigurable algorithms and static baselines for networks between 16 and 256 nodes. To this end, we conduct extensive simulations using Astra-Sim [31] with ns-3 [1] as the network backend. Within Astra-Sim, we implement the Bruck [8] collective algorithm together with an optical switch model that enables topology reconfiguration during collective operations. We structure our evaluation for AllReduce and All-to-All around the following research questions: • How do message size, per-hop delay, and network size influence Bridge’s performance gains? • Under what conditions are reconfigurations feasible? • To what extent does Bridge outperform existing approaches? Our evaluation demonstrates that dynamic reconfigurations with Bridge during collective operations reduce AllReduce completion time compared to reconfigurable approaches consistently by up to 1.5× and by 1.5× to 6.6× compared to static baselines on low to moderate-sized workloads. Bridge improves All-to-All over existing approaches by up to 10.4× compared to the static baseline and by 1.4× even for a reconfiguration delay of 5 ms.
4.1
Methodology
For this evaluation, we explore a broad parameter space, using DCQCN as a congestion control algorithm [32], link bandwidths of 200, 400, and 800 Gbps, and MTU sizes ranging from 1500 B (standard Ethernet) to 9000 B (jumbo frames), reflecting large-scale cluster deployments and capabilities of modern RNICs/DPUs [21]. Since our conclusions are consistent across this parameter space, we report results for the configuration that is most representative of current highperformance deployments: 800 Gbps links and a 4500 B MTU. In addition, we evaluate network sizes from 16 to 256 nodes, per-hop delays from 0.1 to 2 𝜇s [13], and message sizes from 1 KB to 256 MB [27]. We assume a per-step latency of 1.7 𝜇s [28], corresponding to typical InfiniBand-class fabrics. Simulations with varying per-step latency had no effect on Allto-All evaluations and only minor impact on comparisons with Ring; these results will be included in the full version of the paper. For reconfiguration delay, we base our settings on existing optical-switch prototypes, as summarized in Table 2. Practical optical network systems are primarily constrained by two factors: reconfiguration time and the number of available ports per switch. In general, designs that support larger port counts, and therefore larger network scales, tend to incur
higher reconfiguration delays [17]. We therefore evaluate both small-scale networks with low reconfiguration delay and larger-scale networks with delays in the millisecond range. Figures 8 and 12 rely on modern OCS technologies [20] with a reconfiguration speed of 10 𝜇s with 128 ports, which supports 64 nodes. OCS Technology
Reconfig. Time (ms)
#ports
SiP (Lightmatter) RotorNet (InFocus) 3D MEMS (Calient) Piezo (Polatis)
0.007 0.01 15 25
32 128 320 576
Table 2: Overview of OCS technologies. [9, 19, 20, 22] AllReduce is typically implemented via the Rabenseifner decomposition [29] as a Reduce-Scatter and AllGather phase. As shown in Section 3.5, AllGather exhibits identical cost under a reversed Reduce-Scatter reconfiguration schedule [16, 29]. Likewise, as discussed in Section 5, the latencyoptimal AllReduce schedules under Bridge can be derived directly from All-to-All. For this reason, we report results for All-to-All and Reduce-Scatter, which together also capture latency-optimal AllReduce and AllGather.
4.2
All-to-All
We compare the speedup in completion time achieved by Bridge for varying message size and reconfiguration delay against static Bruck (S-Bruck), which never reconfigures, and greedy Bruck (G-Bruck), which reconfigures each step based on a BvN decomposition (Figure 5). For varying message size, Bridge achieves speedups compared to S-Bruck of up to 10.4×, with gains generally increasing as reconfiguration delay decreases and message size grows (Figure 5a). Relative to both baselines in Figure 5b (the better result is underlined), Bridge performs best when message size and reconfiguration delay increase proportionally: at high reconfiguration delay and small message sizes, Bridge behaves similarly to S-Bruck, whereas at low reconfiguration delay it approaches G-Bruck. The largest gains over both ( min(G-Bruck,S-Bruck) ) are observed at 128 MB with 𝛿 = 5 ms, Bridge where it achieves 2.1× speedup. In Figure 6, we analyze Bridge under varying per-hop delay for representative small and large message sizes (the better baseline is underlined). Relative to S-Bruck, Bridge becomes increasingly beneficial as per-hop communication grows, since reconfiguration can avoid longer multi-hop paths. When per-hop delay is small, the gains remain limited and Bridge reconfigures less frequently. Compared to GBruck, the opposite holds. Relative to both baselines, Bridge achieves the largest gains again in settings, where only 𝑅 = 1 or 𝑅 = 2 reconfigurations are beneficial with speedups up to
2.3×. For 𝑚 = 16 MB (Figure 6b), per-hop delay has no effect on the results, with Bridge performing best at moderate 𝛼ℎ = 1 ms. To assess Bridge’s performance across different network sizes, Figure 7 reports the speedup for networks ranging from 16 to 256 nodes. We observe that Bridge achieves the largest gains in larger networks, particularly for large message sizes. As network size increases, Bridge remains beneficial even at higher reconfiguration delays, achieving at least 1.4× speedup for 256 nodes across all message sizes. We next evaluate Bridge across the full message-size range. In Figure 8, we compare the speedup of Bridge and G-Bruck over S-Bruck for 𝑛 = 64 and a reconfiguration delay of 10 𝜇s, corresponding to the RotorNet configuration with 128 optical ports. The main plot shows that Bridge improves over S-Bruck by 1.4× to 3× for small message sizes, with the speedup increasing to as much as 10× for large message sizes. For message sizes above 16 MB, however, G-Bruck performs identically, since reconfiguration at every step becomes beneficial in this regime. The inset plot highlights the advantage of Bridge over both baselines, showing that for this configuration Bridge achieves up to 2.1× speedup, first over S-Bruck and then over G-Bruck, for message sizes up to 4 MB. How do message size, per-hop delay, and network size influence Bridge’s performance gains? We observe that Bridge achieves the largest gains over S-Bruck for large message sizes, high per-hop delay, and large networks, as these increase communication cost and make topology reconfiguration more attractive. Compared to G-Bruck, Bridge performs best in configurations opposite to those that favor gains over S-Bruck, namely when the overhead of frequent reconfigurations outweigh its benefit. Under what conditions are reconfigurations feasible? In order to answer this question, we look at the comparison to S-Bruck. For message sizes above 1 MB, Bridge achieves speedups consistently of up to 10.4× over S-Bruck. For 1 MB, S-Bruck matches Bridge only at reconfiguration
(a) vs. S-Bruck
(b) vs. S-Bruck/G-Bruck
Figure 5: Speedup of Bridge compared to S-Bruck and G-Bruck for 800Gbps links and 𝛼ℎ = 1 𝜇s for varying 𝑚 and 𝛿.
(a) 32 KB
(b) 16 MB
Figure 6: Speedup of Bridge compared to S-Bruck and G-Bruck for 𝑛 = 64 with varying per-hop delay.
(a) 1 MB
(b) 32 MB
Figure 7: Speedup of Bridge compared to S-Bruck for 16 to 256 nodes with per hop delay 𝛼ℎ = 1 𝜇s.
To what extent does Bridge outperform existing approaches? Bridge outperforms S-Bruck, and G-Bruck in complementary regimes: when Bridge outperforms SBruck, it typically matches G-Bruck, and vice versa. When 𝛿 is high, Bridge matches S-Bruck at small message sizes and outperforms both baselines at larger sizes. At lower 𝛿, it outperforms both baselines at small message sizes and performs identical to G-Bruck at larger sizes. As a result, the largest improvements over both baselines arise in configurations, where only sparse reconfigurations are worthwhile and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps. Bridge outperforms G-Bruck by capturing most of the completion time reductions at substantially lower reconfiguration overhead, while also outperforming S-Bruck by trading the overhead of sparse reconfigurations for lower communication cost. Summary: Overall, these results show that Bridge outperforms static algorithms across nearly the entire parameter space, except in settings with small networks, small messages, and high reconfiguration delay, which are less representative of practical OCS deployments. In most settings, Bridge achieves speedups of roughly 2× to 3× over the static baseline, with gains increasing to 10× to 30× for larger networks, low reconfiguration delays, and large workloads. Relative to both baselines, G-Bruck and S-Bruck, Bridge achieves the largest improvements for settings where only sparse reconfigurations are feasible, with speedups of up to 2.4×.
4.3
Figure 8: Speedup of Bridge and G-Bruck against SBruck for 𝑛 = 64 with reconfiguration delay of 10 𝜇s. The inset plot describes the improvement of Bridge to both baselines. delays above 1 ms. The benefit of Bridge also becomes consistent in larger networks, particularly from 128 nodes onward. Even under very small per-hop delays, Bridge still achieves speedups of up to 5.4×, falling back to S-Bruck only for small messages and high reconfiguration delays. Since reconfiguration delay typically scales with network size, configurations combining small networks with large 𝛿 are of limited practical relevance. This shows that Bridge is beneficial whenever communication time exceeds the reconfiguration overhead and the network can be reconfigured with reasonably low delay.
Reduce-Scatter
In order to assess Bridge’s performance for AllReduce, we consider several baselines, including S-Bruck, static HD, G-Bruck, a reconfigurable Halving-Doubling strategy (RHD), and the Hamiltonian Ring algorithm. In principle, the subrings induced by Bruck could also be used to enable OCS-link reuse under HD, resulting in performance similar to Bruck. In the following, however, we consider R-HD as defined in prior work, i.e., starting from a ring topology and then applying BvN-based reconfigurations. Since Ring and R-HD outperform S-Bruck and G-Bruck for all workloads, we focus our comparison on the first two approaches. Ring serves as a strong baseline, as it avoids congestion and minimizes total data transmission, making it optimal for large message sizes. Figure 9a analyzes the speedup in completion time for varying message sizes against Ring and R-HD. Relative to Ring, Bridge achieves consistent speedups of up to 8.5× for small message sizes, whereas for large message sizes, this advantage diminishes: the speedup drops to around 1.3× at small reconfiguration delays, and for 𝛿 = 0.15 ms Ring begins
(a) vs. Ring
(b) vs. R-HD
Figure 9: Speedup of Bridge compared to Ring/R-HD for 𝛼ℎ = 1𝜇𝑠, 𝑏 = 800 Gbps and 𝑛 = 64 with varying message size.
(a) 32 KB
(b) 16 MB
Figure 10: Speedup of Bridge compared to Ring and R-HD for 𝑛 = 64 with varying per-hop and reconfiguration delay.
(a) 1 MB
(b) 32 MB
Figure 11: Speedup of Bridge compared to SBruck/Ring for networks of size 16 to 256 nodes with 𝛼ℎ = 1𝜇𝑠, 𝑏 = 800 Gbps. to outperform Bridge. At moderate message sizes, Bridge consistently outperforms R-HD by up to 1.4× in settings where one or two reconfigurations are beneficial. With varying per-hop delay, Figure 10 shows trends similar to All-to-All: higher per-hop delay makes reconfiguration more attractive. However, unlike All-to-All, the benefit is more limited because Ring remains highly competitive for large message sizes. As a result, for 16 MB and 𝛿 = 0.15 ms, Bridge outperforms existing approaches only when per-hop delay is above 1 𝜇s.
Figure 12: Speedup of all approaches compared to Ring for 𝑛 = 64 with 𝛿 = 10 𝜇𝑠, 𝛼ℎ = 1 𝜇s, 𝑏 = 800 Gbps. The inset plot shows Bridge’s improvement over the best baseline. Figure 11 evaluates network sizes from 16 to 256 nodes to analyze the feasibility of Bridge against static baselines (stronger baseline is underlined). For small message sizes, Bridge becomes beneficial either in larger networks or at small reconfiguration delays, improving over static baselines by up to 20×. For 32 MB, the benefit is reduced and concentrated in larger networks with low reconfiguration delay, where Bridge achieves speedups of 3.6×. In contrast, Ring outperforms Bridge for small networks with high reconfiguration delays. Figure 12 shows the consistent trend that Bridge achieves its largest gains for small to medium message sizes outperforming Ring for messages up to 64 MB, providing speedups of up to 5.0×. Further, Bridge outperforms all other baselines consistently and for larger message sizes performs similar to Ring. In the same setting, Bridge improves over all existing approaches by up to 1.3× for message sizes up to 16 MB. How do message size, per-hop delay, and network size influence Bridge’s performance gains? The gains of Bridge are strongest when communication cost is dominated by per-hop delay, namely up to medium message sizes, larger per-hop delays, and larger networks. As message size grows, Ring becomes increasingly competitive because it already minimizes congestion and data transmission. Likewise, higher per-hop delay and larger networks make reconfiguration more attractive, increasing the benefit of shortening multi-hop paths. Under what conditions are reconfigurations feasible? For Reduce-Scatter, reconfigurations become beneficial when they reduce per-hop latency without incurring too much reconfiguration overhead. This is the case primarily for small to medium message sizes and in networks where multi-hop communication is sufficiently expensive (high 𝛼ℎ and 𝑛). By contrast, for large message sizes or high reconfiguration delays, Ring often remains the better choice, especially in smaller networks.
To what extend does Bridge outperform existing approaches? Bridge outperforms Ring most clearly for small to medium message sizes, where shortcutting communication paths substantially reduces latency, yielding speedups of up to 6.6×. Relative to R-HD, the gains are smaller but Bridge performs consistently better while reaching 1.5× speedups in settings where only one or two reconfigurations are beneficial. This shows that similar to All-to-All, Bridge benefits over existing approaches where sparse reconfigurations are most effective because they reuse optical links to minimize latency cost and amortize reconfiguration overhead across multiple steps. Summary: Overall, these results show that Bridge is most effective for Reduce-Scatter in latency-sensitive settings, where it can substantially outperform Ring and R-HD by reducing communication distance through sparse, reusable reconfigurations. Its benefit grows with per-hop delay and network size, but decreases for large message sizes, where Bridge fails to outperform Ring due to its bandwidth efficiency. Since Ring is highly effective for AllReduce, the modest communication speedups for large workloads are insufficient to amortize even moderate reconfiguration delays. In contrast to All-to-All, where Bridge reports the greatest benefits for large workloads, here it is more effective for small workloads, covering a relevant, but smaller region of the parameter space.
5
Discussion and Future Work
Our results show that Bridge is the most effective approach in network settings where sparse reconfigurations are beneficial. We next discuss broader applications and possible extensions beyond the scope of this work and its evaluation. To extend Bridge to reconfigurable multidimensional networks such as tori [14], each node would have an OCS degree greater than two. Thereby, the network forms multiple subrings, which together form small subtori. However, high-port-count OCS technologies have significantly higher reconfiguration delays, therefor this approach is likely practical only for small networks [17]. Since Bruck’s communication pattern is cyclic, it naturally enables multiport capabilities in reconfigurable networks, as each link is used in only one direction. Since OCS connections are bidirectional, a mirrored collective can be performed in parallel, as proposed for static collective algorithms in prior work [16, 27]. For the architecture considered in this work, this yields a 2× speedup and applies equally to Ring, HD, S-Bruck, and G-Bruck. Many collectives also offer opportunities to overlap reconfiguration with computation, allowing GPUs to prepare data while the interconnect reconfigures [10]. In our setting, however, such computation introduces substantially
less overhead than the reconfiguration delays assumed in this work. Our model could be extended to capture computation– reconfiguration overlap, which would likely favor slightly more frequent reconfigurations at low 𝛿. For latency-optimal AllReduce, the reconfiguration schedules derived by Bridge for All-to-All can be directly applied to minimize completion time. In this setting, All-to-All’s optimization problem is identical to latency-optimal AllReduce, since both share the same communication pattern and transmit messages of constant size every step. It follows that optimizing communication distance also minimizes latency and congestion costs as shown in Section 3.3.
6
Conclusion
We explore the design space of network reconfiguration during collective operations. We show that reusing reconfigurable subrings across steps amortizes reconfiguration overhead, reducing completion time and enabling efficient sparse reconfigurations even with millisecond-scale costs. We presented a framework for identifying optimal schedules for Bruck’s algorithm, and formalized this tradeoff for AllReduce and All-to-All. Overall, Bridge delivers substantial performance improvements over all static baselines with speedups of typically 1.5 × to 6.6 ×. Compared to all static baselines, BvN schedules, and R-HD together, Bridge achieves improvements of up to 2.4× for All-to-All and 1.5× for AllReduce. An important direction for future work is to shift Bridge from offline schedule synthesis to an online runtime that adapts sparse reconfiguration to dynamic workloads. A natural next step would be to validate these gains in a hardware implementation with MPI that captures real control-plane and synchronization overheads.
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] Vamsi Addanki, Chen Avin, and Stefan Schmid. 2023. Mars: NearOptimal Throughput with Shallow Buffers in Reconfigurable Datacenter Networks. Proc. ACM Meas. Anal. Comput. Syst. 7, 1, Article 2 (March 2023), 43 pages. doi:10.1145/3579312 [4] Daniel Amir, Nitika Saran, Tegan Wilson, Robert Kleinberg, Vishal Shrivastav, and Hakim Weatherspoon. 2024. Shale: A Practical, Scalable Oblivious Reconfigurable Network. In Proceedings of the ACM SIGCOMM 2024 Conference (Sydney, NSW, Australia) (ACM SIGCOMM ’24). Association for Computing Machinery, New York, NY, USA, 449–464. doi:10.1145/3651890.3672248 [5] 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 [6] Garrett Birkhoff. 1946. Three observations on linear algebra. Univ. Nac. Tacuman, Rev. Ser. A 5 (1946), 147–151. [7] Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, and Pramod Viswanath. 2016. Costly Circuits, Submodular Schedules and Approximate Carathéodory Theorems. SIGMETRICS Perform. Eval. Rev. 44, 1 (June 2016), 75–88. doi:10.1145/2964791.2901479 [8] Jehoshua Bruck, Ching-Tien Ho, Shlomo Kipnis, and Derrick Weathersby. 1994. Efficient algorithms for all-to-all communications in multi-port message-passing systems. In Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA ’94). doi:10.1145/181014.181756 [9] 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. [10] Eric Ding, Chuhan Ouyang, and Rachee Singh. 2025. Photonic Rails in ML Datacenters. 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, 149–159. doi:10.1145/3772356.3772414 [11] Adithya Gangidi, Rui Miao, Shengbao Zheng, Sai Jayesh Bondu, Guilherme Goes, Hany Morsy, Rohit Puri, Mohammad Riftadi, Ashmitha Jeevaraj Shetty, Jingyi Yang, Shuqiang Zhang, Mikel Jimenez Fernandez, Shashidhar Gandham, and Hongyi Zeng. 2024. RDMA over Ethernet for Distributed Training at Meta Scale. In Proceedings of the ACM SIGCOMM 2024 Conference (Sydney, NSW, Australia) (ACM SIGCOMM ’24). Association for Computing Machinery, New York, NY, USA, 57–70. doi:10.1145/3651890.3672233 [12] Torsten Hoefler, William Gropp, Rajeev Thakur, and Jesper Larsson Träff. 2010. Toward performance models of MPI implementations for understanding application scaling issues. In European MPI Users’ Group Meeting. Springer, 21–30. [13] Zhiyi Hu, Siyuan Shen, Tommaso Bonato, Sylvain Jeaugey, Cedell Alexander, Eric Spada, James Dinan, Jeff Hammond, and Torsten Hoefler. 2025. Demystifying NCCL: An In-Depth Analysis of GPU Communication Protocols and Algorithms. In 2025 IEEE Symposium on High-Performance Interconnects (HOTI). 48–59. doi:10.1109/HOTI66940. 2025.00024 [14] 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 Patterson. 2023. TPU v4: An Optically Reconfigurable Supercomputer for Machine Learning with Hardware Support for Embeddings. In Proceedings of the 50th Annual International Symposium on Computer
Architecture (Orlando, FL, USA) (ISCA ’23). Association for Computing Machinery, New York, NY, USA, Article 82, 14 pages. doi:10.1145/ 3579371.3589350 [15] Norman P. Jouppi and Sridhar Lakshmanamurthy. 2025. Ironwood: Delivering Best in Class perf, perf/TCO and perf/Watt for Reasoning Model Training and Serving . In 2025 IEEE Hot Chips 37 Symposium (HCS). IEEE Computer Society, Los Alamitos, CA, USA, 1–26. doi:10. 1109/HCS66204.2025.11154400 [16] 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 [17] Mehrdad Khani, Manya Ghobadi, Mohammad Alizadeh, Ziyi Zhu, Madeleine Glick, Keren Bergman, Amin Vahdat, Benjamin Klenk, and Eiman Ebrahimi. 2021. SiP-ML: high-bandwidth optical network interconnects for machine learning training. In Proceedings of the 2021 ACM SIGCOMM 2021 Conference (Virtual Event, USA) (SIGCOMM ’21). Association for Computing Machinery, New York, NY, USA, 657–675. doi:10.1145/3452296.3472900 [18] Abhishek Vijaya Kumar, Arjun Devraj, Darius Bunandar, and Rachee Singh. 2024. A case for server-scale photonic connectivity. In Proceedings of the 23rd ACM Workshop on Hot Topics in Networks (Irvine, CA, USA) (HotNets ’24). Association for Computing Machinery, New York, NY, USA, 290–299. doi:10.1145/3696348.3696856 [19] Lightmatter, Inc. 2025. Passage Technology. https://lightmatter.co/ products/passage/ Accessed: 2025-07-03. [20] 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 [21] NVIDIA. [n. d.]. NVIDIA BlueField-4 DPU Datasheet. https://resources. nvidia.com/. Accessed: 2026-04-20. [22] Polatis (a HUBER+SUHNER company). n.d.. Series 7000 — 384×384port Software-Defined Optical Circuit Switch. https://www.polatis. com/ Accessed: 2025-07-01. [23] 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 [24] Kun Qian, Yongqing Xi, Jiamin Cao, Jiaqi Gao, Yichi Xu, Yu Guan, Binzhang Fu, Xuemei Shi, Fangbo Zhu, Rui Miao, Chao Wang, Peng Wang, Pengcheng Zhang, Xianlong Zeng, Eddie Ruan, Zhiping Yao, Ennan Zhai, and Dennis Cai. 2024. Alibaba HPN: A Data Center Network for Large Language Model Training. In Proceedings of the ACM SIGCOMM 2024 Conference (Sydney, NSW, Australia) (ACM SIGCOMM ’24). Association for Computing Machinery, New York, NY, USA, 691–706. doi:10.1145/3651890.3672265 [25] 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 [26] Reuters. 2026. Big Tech to invest about $650 billion in AI in 2026, Bridgewater says. Reuters (23 Feb. 2026). https://www.reuters.com/business/big-tech-invest-about-650billion-ai-2026-bridgewater-says-2026-02-23/ [27] 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. [28] 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. [29] Rajeev Thakur, Rolf Rabenseifner, and William Gropp. 2005. Optimization of Collective Communication Operations in MPICH. IJHPCA 19 (01 2005), 49–66. [30] 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. In 20th USENIX Symposium on
Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 739–767. https://www.usenix.org/conference/ nsdi23/presentation/wang-weiyang [31] 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. In 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 283–294. doi:10.1109/ISPASS57527.2023.00035 [32] Yibo Zhu, Haggai Eran, Daniel Firestone, Chuanxiong Guo, Marina Lipshteyn, Yehonatan Liron, Jitendra Padhye, Shachar Raindel, Mohamad Haj Yahia, and Ming Zhang. 2015. Congestion Control for Large-Scale RDMA Deployments. SIGCOMM Comput. Commun. Rev. 45, 4 (Aug. 2015), 523–536. doi:10.1145/2829988.2787484