Ring & Tree Algorithms — infra.bea.ai

Knowing what AllReduce does is table stakes. Knowing how it’s implemented — ring vs tree, latency vs bandwidth — is what lets you predict whether adding more GPUs will actually help.

1. The Naive Approach: Why It Doesn’t Scale

Simplest AllReduce: every GPU sends its data to GPU 0, GPU 0 sums everything, GPU 0 broadcasts the result.

Step 1: All → GPU 0    (P-1 messages of N bytes = N(P-1) bytes into GPU 0)
Step 2: GPU 0 reduces  (compute)
Step 3: GPU 0 → All    (P-1 messages of N bytes)

Problem: GPU 0’s network link is the bottleneck — it must receive/send $N(P-1)$ bytes. With 1000 GPUs and 1 GB gradients: GPU 0 must handle 999 GB of traffic. Meanwhile, all other GPUs sit idle during Steps 1 and 3.

Time: $O(N \times P)$ — gets slower with more GPUs. Completely useless.

2. Ring AllReduce: Bandwidth-Optimal

The Idea

Ring AllReduce

Arrange $P$ GPUs in a ring. Each GPU only communicates with its two neighbors. The algorithm has two phases:

Phase 1: ReduceScatter (P-1 steps)

Divide each GPU’s data into $P$ chunks
Each step: every GPU sends one chunk to the right neighbor, receives one from the left, and reduces (sums) the received chunk with its own
After $P-1$ steps: each GPU holds one fully-reduced chunk

Phase 2: AllGather (P-1 steps)

Each step: every GPU sends its reduced chunk to the right, receives the next reduced chunk from the left
After $P-1$ steps: every GPU has all $P$ reduced chunks = the complete AllReduce result

Communication Volume

Each GPU sends $\frac{N}{P}$ bytes per step, for $2(P-1)$ steps total:

\text{Per-GPU volume} = 2 \times \frac{N}{P} \times (P-1) = \frac{2N(P-1)}{P}

For large $P$ : $\approx 2N$ — independent of GPU count.

This is bandwidth-optimal — you can’t do AllReduce with less total data movement (proven lower bound).

Why It Works

The key insight: every GPU is simultaneously sending and receiving every step. No GPU is ever idle. The ring’s aggregate bandwidth is $P \times B$ (where $B$ is per-link bandwidth), and the algorithm uses all of it.

Limitation: Latency

Ring AllReduce takes $2(P-1)$ steps. Each step has a startup latency $\alpha$ (establishing communication). Total latency: $2(P-1)\alpha$ .

For 1000 GPUs: 1998 steps × ~5μs/step = ~10ms of pure latency overhead — even before counting data transfer. For small messages (e.g., a single scalar), this latency dominates.

3. Tree Reduction: Latency-Optimal

The Idea

Ring AllReduce

Organize GPUs in a binary tree. Reduce up the tree (log₂P steps), then broadcast down.

            GPU0 (root, has final sum)
           /    \
        GPU0    GPU2
       /    \  /    \
     GPU0 GPU1 GPU2 GPU3

Steps: $2 \log_2 P$ (reduce up + broadcast down)

Latency

$2 \log_2 P \times \alpha$ — for 1000 GPUs: $2 \times 10 \times 5μs = 100μs$ . That’s 100× less than ring’s 10ms.

Bandwidth

Each step sends $N$ bytes through a single link. Total: $N \times 2\log_2 P$ bytes through the root link — not bandwidth-optimal for large messages.

4. When to Use Which

Algorithm	Best for	Latency	Bandwidth
Ring	Large messages (gradients, parameters)	$O(P)$ — high	Optimal: $\frac{2N(P-1)}{P}$
Tree	Small messages (scalars, control)	$O(\log P)$ — low	Suboptimal: $O(N \log P)$
Recursive halving-doubling	Medium messages	$O(\log P)$	Near-optimal

NCCL’s Strategy

NCCL doesn’t use a single algorithm — it switches based on message size:

Small messages (< ~256 KB): Tree algorithm (latency matters more)
Large messages (> ~256 KB): Ring algorithm (bandwidth matters more)
Very large messages: Chunked ring with pipelining

This adaptive strategy is one reason NCCL outperforms manual implementations.

5. The Communication Time Model

Total time for a collective:

T = \alpha + \frac{N}{B} \times f(P)

Where:

$\alpha$ = startup latency per message (~5-10 μs)
$N$ = message size in bytes
$B$ = per-link bandwidth (e.g., 450 GB/s for one NVLink direction)
$f(P)$ = algorithm-dependent scaling factor

Algorithm	$\alpha$ term	Bandwidth term
Ring AllReduce	$2(P-1) \times \alpha$	$\frac{2N(P-1)}{P \times B}$
Tree AllReduce	$2\log_2 P \times \alpha$	$\frac{2N \log_2 P}{B}$

Crossover: Ring wins when $N > \frac{P \times \alpha \times B}{\log_2 P}$ . For typical values: ring wins for messages > ~100 KB.

Practical Example

AllReduce of 1 GB gradients across 8 H100s on NVLink (450 GB/s per direction):

Ring: $T = 2 \times 7 \times 5\mu s + \frac{2 \times 10^9 \times 7}{8 \times 450 \times 10^9} = 70\mu s + 3.9ms = 3.97ms$

Tree: $T = 2 \times 3 \times 5\mu s + \frac{2 \times 10^9 \times 3}{450 \times 10^9} = 30\mu s + 13.3ms = 13.3ms$

Ring is 3.3× faster for this large message. Tree’s advantage only appears for tiny messages.

6. Overlapping Communication with Computation

In practice, AllReduce doesn’t have to wait until backward completes. Gradient bucketing starts AllReduce for early layers while later layers are still computing:

Backward:     [Layer 32] [Layer 31] [Layer 30] ... [Layer 1]
AllReduce:                [Bucket 8] [Bucket 7] ... [Bucket 1]
                          ↑ starts as soon as bucket is ready

PyTorch DDP does this automatically — gradients are grouped into “buckets” (default 25 MB), and AllReduce starts for each bucket as soon as its gradients are computed.

Ideal: AllReduce is completely hidden behind backward computation. Reality: for the last few buckets, AllReduce must wait (no more computation to overlap with). The overhead is the tail — the AllReduce time for the last bucket.

Self-Check

Explain why naive AllReduce is O(N×P) and doesn’t scale
Draw the ring AllReduce algorithm (ReduceScatter + AllGather phases)
Prove that ring AllReduce per-GPU volume is $2N(P-1)/P$
Explain why tree is better for small messages and ring for large
Calculate AllReduce time for given N, P, B using the time model
Explain gradient bucketing and how it overlaps AllReduce with backward