Collective Communication Primitives are the fundamental parallel communication operations that coordinate data exchange among all processes (or GPUs) in a group — where allreduce, broadcast, allgather, reduce-scatter, and alltoall provide the building blocks for distributed training, scientific computing, and any parallel application, and where the choice of algorithm (ring, tree, recursive halving-doubling, hierarchical) determines the communication time that often dominates parallel scalability.

Core Collective Operations

• Broadcast: One process sends data to all others. Root → all. Data size: M bytes per node after completion.
• Reduce: All processes contribute data; one process receives the element-wise sum (or min/max). All → root. Used for: global sum, finding global maximum.
• Allreduce: Reduce + broadcast — every process gets the reduced result. The most critical collective for distributed training (gradient averaging). Cost: equivalent to reduce + broadcast but can be done in a single operation.
• Allgather: Each process contributes its piece; all processes receive the concatenation. All-to-all data exchange. Output size: P × input_size per process.
• Reduce-Scatter: Reduce + scatter — each process gets a different portion of the reduced result. Equivalent to allreduce but each process only keeps its 1/P share. Used in ZeRO optimizer state partitioning.
• Alltoall: Each process sends a different message to each other process. The most general (and most communication-intensive) collective. Used in FFT transpose, expert routing in MoE models.

Algorithm Implementations

Ring Allreduce:

• P processes arranged in a logical ring. Reduce-scatter phase: P-1 steps, each process sends and receives M/P bytes. Allgather phase: P-1 steps of the same form.
• Total data transferred per node: 2 × (P-1)/P × M ≈ 2M (bandwidth-optimal — independent of P!).
• Latency: 2(P-1) × α (where α is per-message latency). Latency-poor for large P.
• Used by: NCCL for intra-node GPU allreduce (NVLink), inter-node allreduce over IB.

Tree Allreduce:

• Binary tree reduction (log P steps) followed by broadcast (log P steps).
• Total data transferred per node: 2 × M × log P. Bandwidth-suboptimal (factor of log P worse than ring).
• Latency: 2 log P × α. Latency-optimal.
• Best for: small messages where latency dominates.

Recursive Halving-Doubling:

• Reduces in log P steps: at each step, pairs exchange and reduce half the data. Then doubles back.
• Both latency-optimal (log P steps) and bandwidth-optimal (2M total). The theoretically best algorithm.
• Requires P = power of 2 for simple implementation. Non-power-of-2 handling adds complexity.

NCCL (NVIDIA Collective Communications Library)

The standard for GPU-to-GPU collectives:

• Auto-detects topology (NVLink, NVSwitch, PCIe, InfiniBand) and selects optimal algorithm.
• Ring on NVLink (high bandwidth, few GPUs), tree across nodes (latency-optimized), double binary tree for hierarchical topologies.
• In-place allreduce: operates directly on GPU buffers with no intermediate copies.
• Overlaps communication with computation when used with CUDA streams.

Collective Communication Primitives are the data movement backbone of parallel computing — the operations whose bandwidth and latency scalability directly determine whether a distributed application achieves near-linear scaling or hits a communication wall.