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

summary

The gist

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

In short

The paper addresses communication overhead in optical circuit-switched networks by proposing a 'Bridge' strategy for collective operations like All-to-All. Bridge reconfigures network topology at runtime using reusable subrings based on Bruck’s pattern, allowing communication partners to be connected directly while maintaining reachability for future steps. This amortizes reconfiguration costs, leading to significant speedups over static and existing dynamic methods.

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 used across episodes

This episode discusses

The paper

Bridge: Optimizing Collective Communication Schedules in Reconfigurable Networks with Reusable Subrings · Read on arXiv

Weizenbaum Institute · TU Berlin

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.

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.

More episodes

← Home