Allreduce (and the rest) from scratch
This post is a whirlwind tour of collective operations — allreduce, allgather, reduce-scatter, broadcast, all-to-all. Every modern parallelism strategy is a particular sequence of these.
Every collective is a schedule of just two primitives: a point-to-point send and a point-to-point recv. To make this concrete, I handrolled each collective from these primitives. The code (implementations, tests, and benchmark) is in this GitHub repo.
The alpha-beta cost model
The Hockney model: sending a message of $M$ bytes from one rank to another costs
\[T_{\text{p2p}} = \alpha + \beta M\]where $\alpha$ is the fixed per-message latency (including, e.g., the handshake) and $\beta$ is the time per byte. $\alpha$ and $\beta$ are physical properties of the interconnect you’re working with.
Messages on different links travel concurrently, so a collective’s wall time is roughly
\[T = (\text{messages on the critical path}) \cdot \alpha + (\text{bytes on the busiest link}) \cdot \beta.\]So, every collective gets a coefficient on $\alpha$ (how many sequential rounds it takes) and a coefficient on $\beta M$. With $N$ ranks and a total message of size $M$, the scorecard for every collective in this post is:
| collective | pattern | $\alpha$ coef | $\beta M$ coef | notes |
|---|---|---|---|---|
broadcast_flat |
flat from root | $N-1$ | $N-1$ | baseline |
broadcast_tree |
binomial tree | $\log N$ | $\log N$ | latency-optimal |
scatter |
flat from root | $N-1$ | $(N-1)/N$ | |
gather |
flat to root | $N-1$ | $(N-1)/N$ | |
reduce_flat |
flat to root | $N-1$ | $N-1$ | baseline |
reduce_tree |
binomial tree | $\log N$ | $\log N$ | latency-optimal |
allgather |
ring | $N-1$ | $(N-1)/N$ | bandwidth-optimal |
reduce_scatter |
ring | $N-1$ | $(N-1)/N$ | bandwidth-optimal |
allreduce_ring |
RS + AG | $2(N-1)$ | $2(N-1)/N$ | bandwidth-optimal |
allreduce_tree |
reduce + bcast | $2\log N$ | $2\log N$ | latency-optimal |
all_to_all |
pairwise | $N-1$ | $(N-1)/N$ | bandwidth-optimal |
So, there are two ways an algorithm could be efficient: it could minimize rounds, the $\alpha$ coefficient, or bytes per link, the $\beta M$ coefficient. The rest of this post shows that, broadly, tree algorithms minimize rounds, and ring algorithms minimize bytes per link. So, rings win with massive message sizes where the $\beta M$ term dominates (bandwidth-bound), and trees win when messages are small and the $\alpha$ term dominates (latency-bound).
Rooted collectives
One rank in charge — a root — that talks to every other rank in a star.
broadcast_flat
The root sends the full message to each of the $N-1$ other ranks, one at a time.
def broadcast_flat(rank, world_size, data, root=0):
if rank == root:
for peer in range(world_size):
if peer != root:
dist.send(data, dst=peer)
else:
dist.recv(data, src=root)
scatter
The root sends chunk $i$ from the message to rank $i$. $N-1$ sequential sends from the root, but each only $M/N$ bytes, so the $\beta M$ coefficient drops to $(N-1)/N$, which tends to $1$ as network size increases.
def scatter(rank, world_size, data, root=0):
# Require data size divisibility by world size. Otherwise, chunks may have
# uneven lengths, and we'd need either two sendrecvs instead of one (one
# for chunk size to allocate an appropriately-sized buffer, and one for the raw
# data itself) or padding.
assert data.numel() % world_size == 0, "data size must be divisible by world_size"
chunk_size = data.numel() // world_size
if rank == root:
chunks = data.chunk(world_size)
for peer in range(world_size):
if peer != root:
dist.send(chunks[peer], dst=peer)
return chunks[root].clone()
else:
buf = torch.empty(chunk_size, dtype=data.dtype)
dist.recv(buf, src=root)
return buf
gather
The inverse of scatter: every rank sends its $M/N$-size chunk to the root.
def gather(rank, world_size, data, root=0):
if rank == root:
chunks = [torch.empty_like(data) for _ in range(world_size)]
chunks[root] = data
for peer in range(world_size):
if peer != root:
dist.recv(chunks[peer], src=peer)
return torch.cat(chunks)
else:
dist.send(data, dst=root)
return None
reduce_flat
Each peer sends its full $M$ bytes and the root accumulates.
def reduce_flat(rank, world_size, data, root=0):
if rank == root:
result = data.clone()
buf = torch.empty_like(data)
for peer in range(world_size):
if peer != root:
dist.recv(buf, src=peer)
result += buf
return result
else:
dist.send(data, dst=root)
return None
In all four of these collectives, the root performs $N-1$ messages back to back, so latency scales as $N-1$. A tree fixes this by letting children which have received the data start propagating it.
The tree
Having the root do all $N-1$ messages sequentially idles NIC capacity at the other ranks. If, instead, each rank that’s already received the data starts passing it on by the next round, the number of holders doubles each round. So, after $\lceil \log_2 N \rceil$ rounds every rank has it.
broadcast_tree
def broadcast_tree(rank, world_size, data):
n_rounds = (world_size - 1).bit_length()
for k in range(n_rounds - 1, -1, -1):
distance = 1 << k
# A rank's lowest set bit is its round of arrival -- the round where it
# receives the data and joins the holder set. Once it arrives, it
# remains active for all rounds with smaller k, where it serves as a
# sender to grow its own subtree.
# This check: if any lower bit set, rank doesn't receive data yet; skip
# for a later (smaller-k) round.
if rank & (distance - 1):
continue
# If rank's lowest set bit is k, receive and join the holder set.
if rank & distance:
dist.recv(data, src=rank - distance)
# Data flows from bit-k-clear rank to its bit-k-set peer at rank + 2^k.
else:
peer = rank + distance
if peer < world_size:
dist.send(data, dst=peer)
reduce_tree
def reduce_tree(rank, world_size, data):
acc = data.clone()
buf = torch.empty_like(data)
n_rounds = (world_size - 1).bit_length()
for k in range(n_rounds):
# 1 << k = 2^k. At round 0 you pair with your distance-1 neighbor, round
# 1 with distance-2, round 2 with distance-4, etc.
distance = 1 << k
# Rank with k-th bit set sends.
if rank & distance:
# Send our running sum to the peer, then drop out.
dist.send(acc, dst=rank - distance)
return None
peer = rank + distance
if peer < world_size:
dist.recv(buf, src=peer)
acc += buf
# Rank 0 has all bits zero, so it never enters the send branch and is the
# only rank to reach this return with the full sum.
return acc
The ring
The ring’s core observation is that you need never move more than $M/N$ bytes at a time, and it reduces the $\beta M$ coefficient to a constant.
allgather
Imagine the ranks arranged in a circle. On each step, every rank sends the chunk it currently holds to its right neighbor and receives a new chunk from its left. After $N-1$ steps, every chunk has visited every rank.
def allgather(rank, world_size, data):
left = (rank - 1) % world_size
right = (rank + 1) % world_size
chunks = [torch.empty_like(data) for _ in range(world_size)]
chunks[rank] = data.clone()
send_idx = rank
for _ in range(world_size - 1):
recv_idx = (send_idx - 1) % world_size
# Even ranks send first, odd ranks recv first
if rank % 2 == 0:
dist.send(chunks[send_idx], dst=right)
dist.recv(chunks[recv_idx], src=left)
else:
dist.recv(chunks[recv_idx], src=left)
dist.send(chunks[send_idx], dst=right)
send_idx = recv_idx
return torch.cat(chunks)
Each step moves only $M/N$ bytes per link, and there are $N-1$ steps, so there is a total of $M(N-1)/N$ bytes per link passed during the collective. This is bandwidth-optimal: to end up holding everyone else’s data, each rank must receive at least $M(N-1)/N$ bytes (every chunk but its own). The ring hits this lower bound exactly.
reduce_scatter
The mirror of allgather: same ring rotation.
def reduce_scatter(rank, world_size, data):
assert data.numel() % world_size == 0, "data size must be divisible by world_size"
left = (rank - 1) % world_size
right = (rank + 1) % world_size
chunks = [chunk.clone() for chunk in data.chunk(world_size)]
buf = torch.empty_like(chunks[0])
send_idx = (rank - 1) % world_size
for _ in range(world_size - 1):
recv_idx = (send_idx - 1) % world_size
if rank % 2 == 0:
dist.send(chunks[send_idx], dst=right)
dist.recv(buf, src=left)
else:
dist.recv(buf, src=left)
dist.send(chunks[send_idx], dst=right)
chunks[recv_idx] += buf
send_idx = recv_idx
return chunks[rank]
Allreduce, and why ZeRO-2 is free
Allreduce leaves every rank holding the sum of each rank’s initial value. It’s notably used in data-parallel training: each rank computes gradients for its slice of the batch, and an allreduce averages them across ranks so that every rank can take the same optimizer step.
allreduce_ring
A reduce-scatter followed by an allgather:
def allreduce_ring(rank, world_size, data):
reduced_chunk = reduce_scatter(rank, world_size, data)
return allgather(rank, world_size, reduced_chunk)
allreduce_tree
A reduce followed by a broadcast:
def allreduce_tree(rank, world_size, data):
reduced = reduce_tree(rank, world_size, data)
out = reduced if rank == 0 else torch.empty_like(data)
broadcast_tree(rank, world_size, out)
return out
allreduce = reduce-scatter + allgather, so ZeRO-2 is a free lunch. In plain data parallel (DDP), every rank stores a full copy of the parameters, the gradients, and the optimizer states. For Adam in mixed precision, the optimizer states are three times the size of the parameters themselves.
ZeRO shards these between ranks and reduces the memory pressure per rank: ZeRO-1 shards the optimizer states, ZeRO-2 additionally the gradients, ZeRO-3 additionally the parameters. In particular, ZeRO-2 handles training with sharded optimizer state and gradients by doing this:
reduce_scatterthe gradients, so rank $r$ holds the summed gradient for its shard $r$;- rank $r$ updates its shard of the parameters using its shard of the optimizer state;
allgatherthe updated parameter shards, so that every rank has the full parameters for the next forward pass.
DDP allreduces gradients, which is a reduce-scatter plus an allgather under the hood. Parameters and gradients are the same size, so ZeRO-2’s explicit reduce-scatter followed by allgather moves the same number of bytes as DDP. This is an $N$-fold reduction in gradient and optimizer-state memory for no additional communication cost.
(The free lunch ends at ZeRO-3. Sharded parameters have to be allgather-ed back, pushing total communication to roughly 1.5x. ZeRO-3 trades communication for the ability to fit the very largest models at all.)
Why deep learning picks the ring over the tree
The tree wins when $\alpha$ dominates (small messages) and the ring wins when $\beta M$ dominates (large messages). To reproduce the crossover for myself, I benchmarked both handrolled allreduces against gloo’s built-in dist.all_reduce on 8 CPU ranks, sweeping message size. Log-scaled-y and linear-scaled-y views:


Tree leads through 1 MB, the curves cross somewhere between 1 and 4 MB, and ring wins from 4 MB up (at 64 MB, ring averages about 0.48 s against tree’s 0.53 s). (On NCCL, the crossover point lands in the same order of magnitude.) Expectedly, gloo’s C implementation beats both of my Python-loop versions almost everywhere — orchestrating sends and receives from a Python loop incurs overhead.
Gradient buffers are big — for concreteness, a 7-billion-parameter model in bf16 has a 14 GB gradient tensor — so even though DDP buckets the gradients, firing allreduce on every ~25 MB bucket as it fills to overlap communication with the backward pass, a single bucket is already one to two orders of magnitude past the crossover. Deep learning is firmly bandwidth-bound.
This is why, though NCCL keeps a tree algorithm (a clever double binary tree) around for the small-message, latency-bound regime, for averaging gradients it’s rings; the tree’s $\log N$ latency edge matters little when every message is MBs to GBs.
All-to-all, the MoE collective
all_to_all
The final collective is the most symmetric of all: all_to_all is a matrix transpose. Each rank holds $N$ chunks, and chunk $j$ on rank $i$ goes to rank $j$.
The subtlety is scheduling: if every rank walks its partners in the same order $0, 1, 2, \dots$, they all pile onto the same partner and gloo’s sends block, waiting for a matching recv. Pairing instead by $\text{peer} = \text{rank} \oplus k$ for $k = 1, \dots, N-1$ (when $N$ is a power of two) keeps every rank busy with a distinct partner on every step.
This butterfly pattern makes much more sense when visualized in a higher dimension: a hypercube.
def all_to_all(rank, world_size, data):
assert data.numel() % world_size == 0, "data size must be divisible by world_size"
chunks = list(data.chunk(world_size))
# Diagonal of the transpose: my own j=rank chunk stays put.
out = [torch.empty_like(chunks[0]) for _ in range(world_size)]
out[rank] = chunks[rank].clone()
ws_is_pow2 = world_size & (world_size - 1) == 0
for k in range(1, world_size):
# XOR schedule when N is a power of 2, otherwise the plain linear peer
# order. XOR-by-k is a fixed-point-free (nobody is paired with
# themselves) involution (applying it twice gets you back where you
# started, so the pairing is mutual -- both sides are partners this
# step). This results in a "perfect matching": every node is paired with
# exactly one other node, and no node appears in two pairs, i.e., every
# step cleanly splits all N ranks into N/2 disjoint pairs.
#
# In linear peer order, you get a star centered on a single hub instead
# of a matching, resulting in serialization.
peer = rank ^ k if ws_is_pow2 else k
# This guard fires only on the non-pow2 branch since XOR-by-k is
# fixed-point-free.
if peer == rank:
continue
# Lower rank sends first to break the symmetry.
if rank < peer:
dist.send(chunks[peer], dst=peer)
dist.recv(out[peer], src=peer)
else:
dist.recv(out[peer], src=peer)
dist.send(chunks[peer], dst=peer)
return torch.cat(out)
A transpose-shaped communication pattern shows up most canonically in MoE layers. Dispatching the right tokens to the right experts is an all_to_all, and gathering the experts’ outputs back to the tokens’ home ranks is another.