Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings
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 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. 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.Where the paper says it
Where the paper says it
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 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] 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]. 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].Where the paper says it
Where the paper says it
Where the paper says it
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 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, 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Optimal Scheduling and Amortization
The paper derives optimal reconfiguration schedules for All-to-All (Section 3.3), Reduce-Scatter (Section 3. p. 1 • We characterize the optimal reconfiguration schedules for All-to-All (Section 3. 3), Reduce-Scatter (Section 3. 3), Reduce-Scatter (Section 3. 4), and AllGather (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. □
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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 For AllReduce, Bridge uniformly outperforms existing reconfiguration strategies, delivers up to 1. 5× speedup,
and exceeds the bandwidth-optimal Ring algorithm by 1. 5× speedup,
and exceeds the bandwidth-optimal Ring algorithm by 1. 6× on low to moderate-sized workloads. 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.Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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). 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).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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
𝑅
. 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
𝑅
. 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
𝑅
. 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
𝑅
. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 , 𝑥𝑠−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, 𝐴), . In step 𝑘 ∈ {0, . , 𝑠 − 1}, each node 𝑢
communicates with node 𝑢 + 2
𝑘 mod 𝑛, that is, with a peer
at ring distance 2
𝑘
. , 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 paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. delays above 1 ms. The benefit of Bridge also becomes consistent in larger networks, particularly from 128 nodes onward.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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]. 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]. 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].Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 • 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. 6× compared to static
baselines on low to moderate-sized workloads. 6× compared to static
baselines on low to moderate-sized workloads. Bridge improves All-to-All over existing approaches by up to 10. Bridge improves All-to-All over existing approaches by up to 10. 4×
compared to the static baseline and by 1. 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). 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. For AllReduce, Bridge uniformly outperforms existing reconfiguration strategies, delivers up to 1. 5× speedup,
and exceeds the bandwidth-optimal Ring algorithm by 1. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
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
-
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.
-
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.
-
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.
-
Implement a strategy that constructs subrings consisting of active communication pairs, which
preserve reachability to peers in subsequent steps.
-
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. -
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.
-
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.
-
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
- Predicting Networks Before They Happen: Experimentation on a Real-Time V2X Digital Twin
- MultiMoQ: Multi-Access Media-Over-QUIC for Robust Immersive Video Streaming
- HiFiNet: Hierarchical Fault Identification in Wireless Sensor Networks via Edge-Based Classification and Graph Aggregation
- Flux: Optimal Scheduling of Optical Circuit Switches for LLM Training
- Tutorial on Closed-Loop and Application-Aware Digital Twins for Future Wireless Networks
- Claude Code Complete User Handbook