Tuning Collective Patterns to Alleviate Congestion in Shared AI Clusters

Motivation

• Shared-cluster tenants lack control over other jobs and infrastructure, while congestion in even one flow can slow a synchronized communication phase and increase training time.Communication may account for 10-90% of an epoch’s duration.Source: §1 · p. 1

Approach

• REACT tunes the recurring communication pattern at the application layer, changing flow endpoints while preserving the required information exchange and requiring no network support.It is designed for unilateral deployment by an individual tenant and makes no assumptions about underlying network protocols.Source: §1 · pp. 1–2

Design

• REACT detects potentially congested flows by comparing their completion times with similar flows and across epochs, then prioritizes critical-path flows for semantically safe node swaps.It also prunes swaps unlikely to alleviate congestion and uses an analytical model to estimate performance impact, allowing multiple transforms to be considered within an epoch.Source: §1 · p. 2

Scope

• REACT targets congestion lasting a few epochs and is best-effort: it cannot respond to congestion that dissipates within an epoch or guarantee that all congestion is eliminated.The stated target duration is a few hundreds of milliseconds.Source: §1 · p. 2

Evaluation

• 13%-38% improvement in communication time on a shared academic GPU cluster, with up to 75% improvement in algorithm bandwidth in simulations across congestion scenarios.The evaluation covers dual binary tree AllReduce, Ring AllReduce, and AllGather with recursive doubling.Source: §1 · p. 2

Repeated rounds of information exchange

• Repeated epochs provide a useful time granularity for a reactive feedback loop because the same high-level information exchange recurs as training proceeds.Each epoch combines local computation with communication that exchanges gradients or updated weights among nodes.Source: §2 · pp. 2–3

Information exchange specified via collective operations

• Application libraries use collective communication libraries such as NCCL, Gloo, or OpenMPI to execute communication requirements expressed through collective operations.The application libraries generate and schedule computation and communication tasks across devices.Source: §2 · p. 3

Collective operations realized via collective patterns

• A collective pattern is the concrete series of message exchanges implementing a collective operation, and different patterns can realize the same required exchange.AllReduce can use a tree or ring; AllGather can use broadcast by each node or recursive doubling.Source: §2 · p. 3
• The collective communication library sets up the pattern’s source-destination exchanges over intra-host or inter-host transports, and this work focuses on the inter-host component.Collectives typically handle intra-host exchange before inter-host exchange.Source: §2 · p. 3

3.1 Computing Collective Patterns

• NCCL maintains fixed patterns per collective and selects the lowest-cost option using message size, node/device counts, and pairwise link bandwidth and latency; solver approaches model network and workload characteristics to reduce communication time.Solver approaches are computationally expensive to run repeatedly and require complete knowledge of link characteristics and all workloads in the cluster.Source: §3.1 · p. 3
• Plink probes paths to choose AllReduce tree roots and leaves, while AutoCCL tunes predefined NCCL parameters without changing the intrinsic communication pattern.REACT instead aims to react more generally to congestion for a given pattern.Source: §3.1 · p. 3
• REACT can take infrequently generated collective patterns from AdapCC as inputs and minimally tweak them, enabling an order-of-magnitude faster reaction to congestion.Source: §3.1 · p. 4
• AdapCC periodically probes paths and recomputes patterns with a solver at coarse timescales; REACT can tweak its patterns at an order of magnitude faster reaction timescale.REACT can use infrequently generated AdapCC patterns as inputs.Source: §3.1 · pp. 3–4

3.2 Minimizing Network Delays in Distributed Training

• Routing and coordinated scheduling approaches rely on infrastructure support or control over all jobs, while application-integrated overlap, compression, or packet dropping require tighter application integration.REACT works at the collective-library layer without modifying the overlying application or underlying transport and infrastructure.Source: §3.2 · p. 4

4.1 Key Design Considerations

• REACT targets shared clusters with varied topologies and protocols, where tenants cannot assume network support, global job information, or control over infrastructure.It uses CCL-available flow statistics and simple heuristics to make low-overhead, minimal changes to a given pattern.Source: §4.1 · pp. 4–5

4.2 REACT in a nutshell

• At the end of each epoch, nodes report flow completion times to a leader, which analyzes them after a batch of epochs and disseminates a modified pattern for the next batch.The implementation uses batches of six epochs and repeats until congestion is no longer detected or changes stop improving performance; transforms preserve communication semantics.Source: §4.2 · p. 5

4.3 Illustrative Example

• Congestion at node 3 delays aggregation and can cascade to higher tree layers because later nodes must wait for its input.The example assumes 16 nodes connected to one switch and uses NCCL’s two-tree AllReduce pattern.Source: §4.3 · p. 5
• In the example, REACT swaps congested node 3 with a viable node to reduce flows into node 3 while preserving AllReduce semantics; the figure shows chunks redirected away from the congested link.The approach can also reposition congested nodes in other trees and optimize the reverse broadcast path for outgoing congestion.Source: §4.3 · pp. 5–6, Figure 1 · p. 5
• 14% improvement restores the reduce phase to 576µs despite congestion, matching its 576µs no-congestion time in the illustrative Tree-AllReduce example.The example uses α = 4µs, β = 1/(100Gbps), s = 2MB, and p = 2.Source: Figure 1 · p. 5, §4.3 · p. 6

5.1 Preliminaries and Notations

• REACT represents collective patterns as time-expanded networks, with vertices for ranks at logical steps and edges for flows between ranks.It discusses dual-tree AllReduce, Ring AllReduce, and Recursive Doubling AllGather as case studies while describing the system as applicable to other patterns.Source: §5.1 · p. 6

5.2 Detecting congestion

• Congestion detection compares a flow’s throughput with similar-degree flows; low throughput across epochs indicates steady congestion, while high variation flags erratic congestion.The steady-congestion test uses the 90th-percentile throughput and a 20% threshold in the experiments; erratic congestion is detected using normalized standard deviation.Source: §5.2 · p. 6

5.3.1 Finding semantically viable swaps

• REACT uses global, chunk-local, and position-equivalent swaps to change flows while preserving collective semantics, favoring finer-grained swaps when available.Position-equivalent swaps are found by checking candidate pairs against the collective’s information-exchange requirements.Source: §5.3.1 · p. 7

5.3.2 Pruning the Swap Space

• REACT prunes candidate swaps by rejecting those that increase a rank’s degree at any timestep, then prioritizes swaps that reduce congested-node degree.It randomly selects among equally prioritized viable swaps.Source: §5.3.2 · pp. 7–8

5.3.3 Applying transforms on collectives

• Transform usefulness depends on collective structure and congestion type: tree AllReduce supports all three transforms, while Ring AllReduce and Recursive Doubling support narrower subsets.Ring AllReduce primarily benefits from global permutation; Recursive Doubling supports global permutation and position-equivalent swaps.Source: §5.3.3 · p. 8

5.4.1 After a single batch of epochs

• After each epoch batch, REACT considers congested nodes on per-epoch or average critical paths, prioritizes steady congestion, and estimates whether candidate swaps improve path times.It accepts an update only if estimated mean critical-path time is at least 5% lower, using observed flow times and estimates for unseen flows.Source: §5.4.1 · pp. 8–9

5.4.2 Over multiple batches of epochs

• Across batches, REACT compares observed communication time with the prior pattern, reverts a worse update, and periodically explores new patterns.In the experiments, it allows five exploratory rounds of six epochs each and discards flow data older than 60 epochs.Source: §5.4.2 · p. 9

6.1 RCollective library

• RCollective implements collective patterns through PyTorch peer-to-peer APIs, posting asynchronous GPU operations on separate streams for chunk subgraphs.The prototype also incurs overhead from setting up new NCCL communicators and missing NCCL buffer-management optimizations; tighter NCCL integration could reduce prototype overheads.Source: §6.1 · p. 9, §6 · p. 9

6.2 REACT Tuner

• RTuner runs on a separate CPU thread, gathers flow-completion times after each epoch batch, computes updated patterns, and shares them with participating nodes.A leader collects worker measurements and broadcasts the updated graph; the tuner uses additional CPU resources.Source: §6.2 · p. 10

6.3 Prototype on a shared cloud

• The prototype ran on a shared academic cluster with four A100 GPUs per server and a 200-Gbps Slingshot data interface; RTuner used a separate management interface.The job continued for five epochs with the older pattern while the tuner completed consensus.Source: §6.3 · p. 10

7 Evaluation

• The evaluation overview covers a shared-cluster testbed and larger-scale ns-3 simulations under different scenarios.The methodology evaluated Tree AllReduce, Ring, and Recursive Doubling collectives across several topologies.Source: §7 · p. 10, §7.1 · p. 10

7.2 Testbed Evaluation

• 13%-38% speedup under congestion was reported for Tree AllReduce on the GPU cluster.Table 2 reports baseline-to-REACT completion-time ratios across node counts and congestion degrees.Source: Table 2 · p. 10, §7.2 · p. 11

7.1 Evaluation Methodology

• Evaluation compared collective completion time and algorithm bandwidth against a baseline across congestion scenarios, using both a shared-cluster testbed and simulations.The methodology included external flows, overlapping jobs, and jobs sharing network paths without sharing nodes.Source: §7.1 · p. 10, §7 · p. 10

7.2 Testbed Evaluation

• Under no congestion, REACT caused a < 4% performance drop compared with the baseline.The passage attributes the cost to exploration and setting up new connections when there is no external congestion to alleviate.Source: §7.2 · p. 11

7.3.1 Congestion due to varying number of external flows

• Up to 60-95% improvement was reported under high congestion, with mean improvements of 35% for tree and 15% for recursive doubling.In low congestion (p = 1), REACT improved performance by up to 20% in the worst-case configuration.Source: §7.3.1 · p. 11, Figure 5 · p. 11
• Multiple ECMP path choices reduced congestion, but REACT continued to improve performance across routing configurations.The authors note this can reduce the need for more ECMP ports or RDMA queue-pair connections, lowering NIC memory load.Source: §7.3.1 · p. 11

7.3.3 Multiple Jobs.

• When REACT was enabled only for Job 1, both jobs improved under network-only contention; enabling it for both jobs still improved performance but yielded dips versus the one-job case.The two jobs shared network paths but not nodes, and independent tuning could leave them in a bad configuration.Source: §7.3.3 · p. 12, Figure 7 · p. 12

7.3.4 REACT under Network Failures

• With partial link failures in a 3-layer Clos, REACT improved Tree AllReduce algorithm bandwidth by up to 20% in the worst case.The simulations reduced randomly selected link bandwidths to 30, 50, or 80 Gbps and retained 4-way ECMP.Source: §7.3.4 · p. 12, Figure 8 · p. 12

Hierarchical Collectives

• REACT can treat each level of a hierarchical collective as an independent job, separately from other collective calls in the larger job.The paper mentions 3D parallelism and dividing communication into macro steps as examples.Source: §8 · p. 12

Congestion Scenarios

• Swapping nodes can explore unknown network paths only when congestion affects a limited number of nodes; if most links are congested, tuning cannot avoid it.Source: §8 · p. 12

Intra-host congestion and collectives

• Straggler handling, intra-server congestion, and additional collective operations are proposed extensions, but this work does not evaluate them.Reducing RDMA connection-establishment overhead is also left to future implementation work, potentially leveraging prior work.Source: §8 · p. 12

9 Conclusion

• REACT changes flow sources and destinations by swapping nodes in collective graphs, preserving semantic correctness and using end-host observations without network support or global coordination.Source: §9 · p. 12
• 13–35% improvements in algorithm bandwidth on a shared cluster and up to 75% gains in simulation across diverse congestion scenarios are reported for REACT.Source: §9 · p. 13

A.1 Communication Collective patterns

• Ring AllReduce uses O(N) steps and is bandwidth-optimal, while Tree AllReduce uses O(logN) steps and scales better; Recursive Doubling AllGather also uses logN steps.Ring AllReduce performs reduce-scatter followed by AllGather; Tree AllReduce reduces at the root, then broadcasts down the reverse tree.Source: §A.1 · p. 18

A.2 Applying Transforms on Collectives

• For Ring AllReduce, global node swaps can alleviate Spine-ToR congestion, but not Server-TOR congestion; recursive-doubling swaps can shift lower-cost flows to later, larger-message timesteps.Swaps within a ring chunk graph can increase node degree and are not helpful there.Source: §A.2 · p. 18

A.3 Analyzing Position-equivalent Swaps

• The brute-force swap-safety check has complexity O(|V|2(|V| + |E|)), reaching O(N7) generally and O((NlogN)3) for popular collectives.It simulates the collective on one-hot bitvectors and checks whether the final vectors satisfy the operation’s semantic conditions.Source: §A.3 · p. 18

A.4 Summarizing REACT Parameters

• Table 3 summarizes the parameters used by REACT.Source: §A.4 · p. 18, Table 3 · p. 18

A.5 Feedback Loop Algorithm

• The feedback algorithm finds critical paths and congestion, ranks congested nodes, tests swaps against expected performance, and updates the critical paths when a swap is accepted.Its inputs include the TEN graph, flow completion times, prior flow times, and the device’s local rank.Source: §A.5 · p. 19

B Implementation Details

• The cluster topology connects four A100 GPUs per server with NVLink, and the Slingshot ToRs are fully connected.Each server’s high-speed interface connects to exactly one ToR.Source: B Implementation Details · p. 19
• Experiments enable GPU Direct RDMA and adaptive routing, with congestion modeled by an injected flow.Source: B Implementation Details · p. 19
• Switches may reroute a congested flow through another ToR, but REACT neither modifies nor controls that routing decision.The paper states REACT works regardless of this load-balancing scheme.Source: B Implementation Details · p. 19

B.1 Implementation of CTCollective

• For each collective edge, the implementation posts GPU sends or receives and blocks the corresponding streams; aggregation is posted when the edge condition applies.Source: §B.1 · p. 19
• CTCollective’s implementation is presented as a function for implementing any custom graph, with inputs including the TEN graph and local device rank.The function creates streams based on the maximum degree and constructs a local graph.Source: §B.1 · p. 19
• Figure 11 presents the CDF of TreeAllReduce epoch times measured on the shared GPU cluster.The caption identifies the plotted metric and setting but gives no specific comparison or outcome.Source: Figure 11 · p. 20

• With REACT, epoch times come very near the no-congestion baseline in the plotted runs.The section compares epoch-time CDFs for baseline RCollective and RCollective+REACT.Source: §C.1 · p. 20
• External congestion affects NCCL, while RCollective without REACT performs worse than NCCL in most cases.Source: §C.1 · p. 20
• Under p=2, RCollective+REACT performs better than NCCL under congestion for a majority of epochs.Source: §C.1 · p. 20

C.2 Results on Star Topology

• Star-topology Tree AllReduce simulations show higher improvements than fattree simulations, attributed to fixed paths enabling better decisions.Figure 12 covers an 8-node Tree Allreduce with 20MB messages.Source: §C.2 · p. 20, Figure 12 · p. 20

C.3 Tail Latency and effects of ECMP.

• REACT improves p95 epoch-time performance across congestion scenarios regardless of the underlying routing configuration.Figure 13 compares ECMP configurations and collective tuning in the fattree topology.Source: §C.3 · p. 20, Figure 13 · p. 21
• With short switch-queue thresholds, messages ≤100KB are not significantly affected at lower congestion levels, but REACT still improves performance at higher levels.Source: §C.3 · p. 20