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

arXiv:2605.12766 · cs.NI · Submitted 2026-05-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings".

Jane: Here's the gist of the paper. 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.

Tom: The central question is therefore when reconfiguration is worth its cost.

Jane: The Problem Addressed Collective communication primitives specify communication objectives among a group of GPUs, such as AllReduce, Reduce-Scatter, AllGather and All-to-All.

Tom: These collectives can be implemented with a variety of algorithms

8, 16, 27, 29: .

Title and authors: Jane: So what exactly is Bridge proposing? It sounds like they aren't just picking one way to reconfigure, but a whole strategy that keeps things efficient across multiple steps >

Lu: They are exploiting the structure of Bruck’s communication pattern to support what they call sparse reconfiguration, which is a big idea because it means you don't have to constantly tear down and rebuild the entire network >

Meng: So if I'm thinking about deployment, what does this mean for my team that has to worry about latency spikes during reconfigurations? >

Tom: It suggests they reduce propagation and transmission delay by directly connecting immediate communication partners while still keeping a path to later peers through connected subrings >

Jane: That subring idea sounds smart because it lets them amortize the high reconfiguration overhead across multiple steps, which is a crucial benefit when you have many steps in the collective operation >

Lalam: Exactly. Bridge constructs these subrings, which are groups of active communication pairs that keep reachability to peers alive for subsequent steps >

Tom: So it's about making sure the links you need next are already set up or easily reachable because of how you structured those initial connections >

The paper's summary: Jane: Okay, so summarizing what they found, the authors derived optimal reconfiguration schedules for AlltoAll, Reduce-Scatter, and AllGather for any fixed number of reconfigurations >

Lu: For AlltoAll specifically, the optimal schedules are periodic; they find that reconfiguration should happen every log2 n R plus one steps to minimize latency >

Tom: And they quantified the total cost of this using a formula C A2A R which shows how the cost balances communication and those reconfigurations >

Meng: That formula looks complicated, but what does it tell us about when we should actually bother changing the network? Is there a simple rule? >

Jane: Well, for AlltoAll, the optimal number of reconfigurations is determined by minimizing that total cost over all possible values of R in polynomial time >

Lalam: For Reduce-Scatter in the transmission-optimal case, they give you an interval formulation of Theorem three point three to find the asymptotically optimal placement of those reconfigurations > <ref:2605.12766#pg1>

Tom: It seems like they've formalized the tradeoff between how often you change things and how much total communication delay it causes >

The paper's improvements: Jane: So what are the actual performance results? I want to know if this is actually faster than what we have now, or just theoretically better on paper >

Tom: In our evaluation, Bridge consistently reduces AllReduce completion time against existing reconfiguration strategies with speedups of up to one point five times > <ref:2605.12766#pg1>

Lu: And it exceeds the bandwidth-optimal Ring algorithm by one point five times to six point six times on low to moderate-sized workloads >

Meng: That's a lot for a collective operation; what about larger message sizes or when the delay between reconfigurations is small, like in milliseconds? >

Tom: Bridge improves AlltoAll completion time over static solutions by typically up to ten times at low reconfiguration delays and even up to five times when those delays are in the millisecond scale >

Jane: That's significant, especially that five times when the delay is small, because it means this strategy can actually be used practically in real systems >

Lalam: The largest gains over both baselines happen when only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps >

Conclusion: Tom: So, to wrap up, the main point of this paper is that Bridge delivers substantial performance improvements over all static baselines with speedups typically ranging from one point five times up to six point six times >

Jane: It seems like Bridge is most effective in network settings where only sparse reconfigurations are feasible and it can use those reusable links to cut down communication and spread out the reconfiguration cost over several steps >

Lu: The results show that Bridge outperforms static algorithms across nearly the entire parameter space except for settings with small networks, small messages, and high reconfiguration delay >

Meng: So if I'm looking at deployment today, it seems like this is a strong contender for when you need those sparse reconfigurations because it handles the cost trade-off better than just sticking to one static configuration >

Lalam: Bridge is most effective for Reduce-Scatter in latency-sensitive settings and it’s also noted that the optimal number of reconfigurations for AllGather depends on balancing latency and transmission optimization >

Tom: We're looking at this paper, "Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings," as a way to understand how to make those dynamic network changes actually work without killing our performance.

Weizenbaum Institute · TU Berlin

cs.NI

Submitted: 2026-05-12

Updated: 2026-11-10

License: http://creativecommons.org/licenses/by-nc-nd/4.0/

Importance score: 77/100

The gist: Optical circuit-switched networks have emerged as an appealing alternative to electrical fabrics as they can reconfigure the network topology at runtime…

Key concepts

Collective Communication Primitives
These are specific communication tasks among a group of devices, such as AllReduce or All-to-All. The paper focuses on how these tasks can be efficiently implemented in optical networks by adapting the network connections dynamically at runtime to minimize communication delays and costs.
Bridge Strategy
This is the core method that exploits Bruck’s communication pattern to create efficient sparse reconfiguration. It builds subrings of active communication pairs that ensure nodes remain reachable for subsequent steps, allowing reconfiguration overheads to be reused across multiple operations.
Optimal Scheduling and Amortization
The paper derives optimal timing for when and how often to reconfigure the network based on the specific collective operation. For All-to-All, this involves periodic reconfigurations every log2 n R+1 steps, which mathematically minimizes total communication cost by balancing reconfiguration expense against transmission delay.
Reusable Subrings
These are minimal connected groups of active communication pairs formed during the process. By constructing these subrings based on Bruck's pattern, the Bridge strategy ensures that links used in one step can be reused or efficiently repurposed for future steps, which is key to amortizing reconfiguration costs.

Terminology

Summary

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. p. 0

Where the paper says it

Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings Anton Juerss Weizenbaum Institute & TU Berlin Germany Stefan Schmid TU Berlin & Weizenbaum Institute Germany 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. p. 0
Where the paper says it

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.

The Problem Addressed

Collective communication primitives specify communication objectives among a group of GPUs, such as AllReduce, Reduce-Scatter, AllGather and All-to-All. These collectives can be implemented with a variety of algorithms [8, 16, 27, 29]. p. 1

Where the paper says it

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]

Optical Reconfigurable Networks (ORNs) offer an opportunity to address this bandwidth overhead by adapting connectivity at runtime. p. 2
Where the paper says it

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].

A common choice to implement All-to-All is to complete the operation in n − 1 parallel point-to-point exchanges offering no opportunity to reconfigure the network to reduce particularly costly traffic [25, 29]. p. 2
Where the paper says it

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].

The Bridge Strategy

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. p. 0

Where the paper says it

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.

This enables high reconfiguration overheads to be amortized across multiple steps, increasing its benefit. p. 1
Where the paper says it

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 in a subring. This enables high reconfiguration overheads to be amortized across multiple steps, increasing its benefit.

Bridge constructs subrings, consisting of active communication pairs, which preserve reachability to peers in subsequent steps. p. 1
Where the paper says it

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.

Optimal Scheduling and Amortization

The paper derives optimal reconfiguration schedules for All-to-All (Section 3.3), Reduce-Scatter (Section 3. p. 1

Where the paper says it

• We characterize the optimal reconfiguration schedules for All-to-All (Section 3. 3), Reduce-Scatter (Section 3.

4), and AllGather (Section 3. p. 1
Where the paper says it

3), Reduce-Scatter (Section 3. 4), and AllGather (Section 3.

5) for any fixed number of reconfigurations. p. 1
Where the paper says it

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.

For All-to-All, the optimal reconfiguration schedules are periodic: reconfiguration should occur every log2 n R+1 steps. p. 5
Where the paper says it

□ Under the simplifying assumption that 𝑅 + 1 divides 𝑠, all optimal segments have the same length 𝑟1 = 𝑟2 = · · · = 𝑟𝑅+1 = 𝑠 𝑅+1 . Given a network of 𝑛 nodes and 𝑅 reconfigurations, the optimal All-to-All schedule for Bruck is periodic: reconfiguration should occur every log2 𝑛 𝑅+1 steps.

This results in a total cost becoming CA2A(R) = salphas + (R +1)c n(1/(R+1)) - 1 + Rdelta, c = alphah + beta m squared. p. 9
Where the paper says it

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.

Performance Evaluation

In our evaluation, Bridge reduces AllReduce completion time consistently against existing reconfiguration strategies with speedups of up to 1.5× and exceeds the bandwidth-optimal Ring algorithm by 1. p. 0

Where the paper says it

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. p. 0
Where the paper says it

5× speedup, and exceeds the bandwidth-optimal Ring algorithm by 1. 6× on low to moderate-sized 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. p. 1
Where the paper says it

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.

Conclusion

Overall, Bridge delivers substantial performance improvements over all static baselines with speedups of typically 1.5 × to 6.6 ×. The largest gains over both baselines arise in settings where only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps. p. 9

Where the paper says it

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.

p. 9
Where the paper says it

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.

The most effective approach is Bridge in network settings where sparse reconfigurations are beneficial. p. 1
Where the paper says it

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).

p. 1
Where the paper says it

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).

Pruning redundant reasoning tokens

The paper explores the design space of network reconfiguration during collective operations. The optimal number of reconfigurations is determined by minimizing the total cost over all feasible values of R, which is possible to compute in polynomial time. p. 7

Where the paper says it

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 = arg min 0≤𝑅≤𝑠 𝐶 A2A 𝑅 .

p. 7
Where the paper says it

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 = arg min 0≤𝑅≤𝑠 𝐶 A2A 𝑅 .

The optimal number of reconfigurations for All-to-All is arg min 0≤R≤s C A2A(R). p. 7
Where the paper says it

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 = arg min 0≤𝑅≤𝑠 𝐶 A2A 𝑅 .

p. 7
Where the paper says it

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 = arg min 0≤𝑅≤𝑠 𝐶 A2A 𝑅 .

The optimal number of reconfigurations for Reduce-Scatter in the transmission-optimal case is given by the interval formulation of Theorem 3. p. 7
Where the paper says it

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.

p. 7
Where the paper says it

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.

How the training signal is built

The paper formalizes the formation of minimal connected subrings which can be directly derived from Bruck’s communication pattern. For each subring i in step k, we define S(k)i as S(k)i:= ∪ u ∈ 0. p. 4

Where the paper says it

, 𝑥𝑠−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, 𝐴), .

.. n − 1 u ≡ i (mod 2k). p. 3
Where the paper says it

In step 𝑘 ∈ {0, . , 𝑠 − 1}, each node 𝑢 communicates with node 𝑢 + 2 𝑘 mod 𝑛, that is, with a peer at ring distance 2 𝑘 .

This shows that Bridge forms minimal subrings in which reconfigurable links can be reused to reach future peers. p. 4
Where the paper says it

, 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.

Where the gains come from

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. For Reduce-Scatter, reconfigurations become beneficial when they reduce per-hop latency without incurring too much reconfiguration overhead. p. 6

Where the paper says it

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.

The 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. p. 8
Where the paper says it

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.

p. 8
Where the paper says it

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.

The largest improvements over both baselines arise in configurations where only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps. p. 9
Where the paper says it

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.

p. 9
Where the paper says it

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.

p. 9
Where the paper says it

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.

The paper presents a framework for identifying optimal schedules for Bruck’s algorithm, and formalized this tradeoff for AllReduce and All-to-All. The results show that Bridge outperforms Ring most clearly for small to medium message sizes, where shortcutting communication paths substantially reduces latency, yielding speedups of up to 6. p. 9

Where the paper says it

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.

6×. Bridge outperforms R-HD by up to 1. p. 0
Where the paper says it

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× in settings where only one or two reconfigurations are beneficial. p. 8
Where the paper says it

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.

The benefit of Bridge also becomes consistent in larger networks, particularly from 128 nodes onward. p. 9
Where the paper says it

delays above 1 ms. The benefit of Bridge also becomes consistent in larger networks, particularly from 128 nodes onward.

The largest gains over both baselines arise in settings where only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps.

The paper extends Bridge to reconfigurable multidimensional networks such as tori [14], where each node would have an OCS degree greater than two. Since Bruck’s communication pattern is cyclic, it naturally enables multiport capabilities in reconfigurable networks, as each link is used in only one direction. p. 2

Where the paper says it

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.

p. 2
Where the paper says it

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.

p. 2
Where the paper says it

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.

A mirrored collective can be performed in parallel for the architecture considered in this work. p. 2
Where the paper says it

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].

p. 2
Where the paper says it

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].

p. 2
Where the paper says it

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].

The paper evaluates Bridge for All-to-All and AllReduce compared to state-of-the-art reconfigurable algorithms and static baselines for networks between 16 and 256 nodes. The evaluation demonstrates that dynamic reconfigurations with Bridge during collective operations reduce AllReduce completion time compared to reconfigurable approaches consistently by up to 1. p. 7

Where the paper says it

• 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. p. 7
Where the paper says it

5× and by 1. 6× compared to static baselines on low to moderate-sized workloads.

Bridge improves All-to-All over existing approaches by up to 10. p. 7
Where the paper says it

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. p. 7
Where the paper says it

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. p. 1
Where the paper says it

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).

The largest gains over both baselines are observed at 128 MB with δ = 5 ms, where it achieves 2. p. 8
Where the paper says it

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) Bridge ) are observed at 128 MB with 𝛿 = 5 ms, where it achieves 2.

1× speedup. p. 0
Where the paper says it

For AllReduce, Bridge uniformly outperforms existing reconfiguration strategies, delivers up to 1. 5× speedup, and exceeds the bandwidth-optimal Ring algorithm by 1.

Bridge outperforms S-Bruck by up to 10. p. 9
Where the paper says it

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.

4× for message sizes above 1 MB. p. 1
Where the paper says it

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.

Bridge outperforms Ring most clearly for small to medium message sizes, where shortcutting communication paths substantially reduces latency, yielding speedups of up to 8. p. 9
Where the paper says it

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.

5×. The 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. The most effective approach is Bridge in network settings where sparse reconfigurations are beneficial.

The paper presents a framework for identifying optimal schedules for Bruck’s algorithm, and formalized this tradeoff for AllReduce and All-to-All. The 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. p. 9

Where the paper says it

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.

p. 9
Where the paper says it

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. p. 9
Where the paper says it

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.

p. 9
Where the paper says it

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.

The largest improvements over both baselines arise in configurations where only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps.

The paper extends Bridge to reconfigurable multidimensional networks such as tori [14], where each node would have an OCS degree greater than two. Since Bruck’s communication pattern is cyclic, it naturally enables multiport capabilities in reconfigurable networks, as each link is used in only one direction. A mirrored collective can be performed in parallel for the architecture considered in this work. The model could be extended to capture computation–reconfiguration overlap. p. 2

Where the paper says it

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.

p. 2
Where the paper says it

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.

The paper explores the design space of network reconfiguration during collective operations. The optimal number of reconfigurations is determined by minimizing the total cost over all feasible values of R, which is possible to compute in polynomial time. The optimal number of reconfigurations for All-to-All is arg min 0≤R≤s C A2A(R). The optimal number of reconfigurations for Reduce-Scatter in the transmission-optimal case is given by the interval formulation of Theorem 3.3. The optimal number of reconfigurations for AllGather is determined by balancing latency and transmission optimization. p. 7

Where the paper says it

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.

The paper presents a framework for identifying optimal schedules for Bruck’s algorithm, and formalized this tradeoff for AllReduce and All-to-All. The 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. In most settings, Bridge achieves speedups of roughly 2× to 3× over the static baseline. The largest improvements over both baselines arise in configurations where only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps.

The paper extends Bridge to reconfigurable multidimensional networks such as tori [14], where each node would have an OCS degree greater than two. Since Bruck’s communication pattern is cyclic, it naturally enables multiport capabilities in reconfigurable networks, as each link is used in only one direction. A mirrored collective can be performed in parallel for the architecture considered in this work. The model could be extended to capture computation–reconfiguration overlap. The paper concludes by stating that Bridge is most effective for Reduce-Scatter in latency-sensitive settings. p. 7

Where the paper says it

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 𝑅 ★ A2A for the latency-dominated setting. 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.

It is also noted that the optimal number of reconfigurations for AllGather is determined by balancing latency and transmission optimization. p. 7
Where the paper says it

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.

The largest gains over both baselines arise in configurations where only sparse reconfigurations are feasible and Bridge can exploit reusable links to reduce communication and amortize the reconfiguration overhead across multiple steps. p. 9
Where the paper says it

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.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Amortize reconfiguration overhead by reusing optical links across multiple subsequent steps to reduce communication cost over time, allowing the benefit of reconfiguration to amortize beyond a single step.

  2. Achieve All-to-All completion times typically 3x to 10x faster than static baselines, and up to 5x even when reconfiguration delays are in the millisecond scale.

  3. Outperform existing reconfiguration strategies for AllReduce by delivering up to 1.5x speedup and exceeding the bandwidth-optimal Ring algorithm by 1.5x to 6.6x on low to moderate-sized workloads.

  4. Implement a strategy that constructs subrings consisting of active communication pairs, which preserve reachability to peers in subsequent steps.

  5. Optimize All-to-All schedules by deriving optimal periodic reconfigurations based on Bruck's pattern, where reconfiguration should occur every log2 n R+1 steps for latency optimization.

  6. For Reduce-Scatter, determine the optimal reconfiguration schedule by minimizing the sum of transmission delay using an interval formulation of an Integer Linear Program to find the asymptotically optimal placement of reconfigurations.

  7. Implement a strategy for AllGather that places reconfigurations late relative to Reduce-Scatter, optimizing for transmission delay by reversing the optimal schedule and ensuring AllGather places them late to optimize for transmission delay.

  8. Extend the framework to networks with fewer than 2n optical ports by using hierarchically connected static blocks that share reconfigurable optical links, forming a hierarchical ring.

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 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, the opportunity to reuse optical links to optimize multiple steps remains largely unexplored. In this paper, we present Bridge, a reconfiguration strategy for frequently used collective communication primitives, 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 3x to 10x over static baselines and is effective even with millisecond-scale reconfiguration delays; for AllReduce up to 1.5x against existing reconfiguration strategies, and by 1.5x to 6.6x against the Ring algorithm on low to moderate-sized workloads.

Sources

Related papers