Collective Communication

Definition

A collective is a communication operation involving all ranks in a group (vs. point-to-point). These six primitives are the complete vocabulary of distributed training: broadcast, reduce, all-reduce, reduce-scatter, all-gather, all-to-all. Every parallelism strategy — DP, ZeRO/FSDP, TP, EP — is built from them and bounded by the interconnect they run on. NCCL is the standard NVIDIA implementation.

Key math / How it works

Notation: $N$ ranks; $\oplus$ = associative reduction (usually sum); “chunk $j$” = the $j$-th $1/N$ slice of a buffer.

Primitive	Before → After (rank $r$)	Definition
Broadcast	root has $x$ → all have $x$	copy one rank’s buffer to all
Reduce	$x_r$ → root has ${⨁}_r{x}_r$	reduce, result on one root
All-Reduce	$x_r$ → all have ${⨁}_r{x}_r$	reduce, result on every rank
Reduce-Scatter	vector in $N$ chunks → rank $r$ keeps ${⨁}_s{x}_s[r]$	reduce, but scatter — each keeps its chunk
All-Gather	chunk $y_r$ → all have $[y_0,\dots ,y_{N-1}]$	concatenate every rank’s chunk
All-to-All	$[z_r^0,\dots ,z_r^{N-1}]$ → $[z_0^r,\dots ,z_{N-1}^r]$	transpose: send chunk $j$ to rank $j$

The two identities that drive everything:
$\boxed{\text{All-Reduce}=\text{Reduce-Scatter}+\text{All-Gather}}$
All-gather is the inverse of reduce-scatter (with the sum dropped). This decomposition is the lens behind ring all-reduce and ZeRO/FSDP (all-gather sharded weights before a layer, reduce-scatter grads after). All-to-all is the primitive behind MoE expert parallelism and sequence parallelism.

Ring all-reduce cost. Split each rank’s $M$-byte buffer into $N$ chunks. Reduce-scatter = $N-1$ ring steps sending $M/N$ each; all-gather = another $N-1$ steps. Bytes sent per GPU:
${\text{data}}_{\text{ring}}=2(N-1)\cdot \frac{M}{N}=2\frac{N-1}{N}M$
Under the $\alpha$–$\beta$ model (message of $n$ bytes = $\alpha +n\beta$):
$T_{\text{ring}}=\underset{\text{latency}}{\underbrace{2(N-1)\alpha }}+\underset{\text{bandwidth}}{\underbrace{2\frac{N-1}{N}M\beta }}$
As $N\to \infty$ the bandwidth term $\to 2M\beta$ — constant, independent of $N$, and provably bandwidth-optimal (Patarasuk & Yuan 2009). This is why ring all-reduce backs large-scale DP. But the latency term grows linearly in $N$, so for small messages at large $N$ a tree (or double-binary-tree) all-reduce wins with $\sim 2\lceil {\log }_{2}N\rceil \alpha$ latency. In-network reduction (NVLink SHARP / IB SHARP) halves ring volume toward $\frac{N-1}{N}M$ by summing in the switch ASIC.

Contrast the naive baselines: reduce-to-root ($(N-1)M$ on one hot link, scales with $N$) and all-pairs ($N\times$ too much data). The ring beats both by using every link equally with no hot spot.

Why it matters

The cost model’s $\beta =1/\text{bandwidth}$ means the fabric sets the constant: NVLink (~900 GB/s) is ~18× NDR InfiniBand (~50 GB/s/GPU). Placing each collective on the right link — chatty TP all-reduces on NVLink, once-per-step DP syncs across nodes on IB — is the central design lever of N-D parallelism.

Taught in

• 08-data-parallelism-and-collectives — §4 primitives, §5 ring all-reduce derivation.

See also

• nccl — topology-aware implementation
• data-parallelism — all-reduce as the gradient sync
• zero / fsdp — RS + AG decomposition in action
• tensor-parallelism — per-layer all-reduce
• expert-parallelism — all-to-all dispatch/combine
• gpu-systems-for-llms