mpi collective communication
**MPI Collective Communication** encompasses the **coordinated communication operations where all processes in a communicator group participate — including broadcast, scatter, gather, reduce, and allreduce — that form the backbone of distributed parallel programming, where the collective algorithm's efficiency (tree, ring, recursive halving/doubling) determines whether communication or computation is the bottleneck at scale**.
**Why Collectives Dominate MPI Performance**
In practice, 60-90% of MPI communication time is spent in collective operations, not point-to-point messages. A single MPI_Allreduce in a 10,000-process distributed training job synchronizes gradients across all processes — if this takes 10 ms, the 100 ms compute step effectively becomes 110 ms, a 10% overhead. Optimizing collectives is the single highest-leverage communication optimization.
**Core Collective Operations**
| Operation | Description | Pattern |
|-----------|-------------|--------|
| **Broadcast** | Root sends data to all processes | One-to-all |
| **Scatter** | Root distributes different data chunks to each process | One-to-all (partitioned) |
| **Gather** | All processes send data to root | All-to-one |
| **Allgather** | Gather + Broadcast — every process gets all data | All-to-all |
| **Reduce** | Combine (sum/max/min) all processes' data at root | All-to-one (with computation) |
| **Allreduce** | Reduce + Broadcast — every process gets the reduced result | All-to-all (with computation) |
| **Reduce-Scatter** | Reduce, then scatter result chunks | All-to-all (partitioned reduce) |
| **All-to-All** | Each process sends unique data to every other process | All-to-all (personalized) |
**Collective Algorithms**
- **Binomial Tree**: O(log P) steps. Process 0 sends to 1, then both send to 2 and 3, etc. Optimal for small messages (latency-bound).
- **Ring (Bucket/Pipeline)**: Data circulates around a ring in P-1 steps. Each process sends/receives 1/(P-1) of the data per step. Optimal for large messages (bandwidth-bound). Bandwidth cost: 2(P-1)/P × N — approaches 2N regardless of P.
- **Recursive Halving-Doubling**: Processes exchange data with partners at doubling distances (1, 2, 4, 8...). O(log P) steps with both latency and bandwidth optimality for medium-sized messages.
- **NCCL (NVIDIA)**: Hardware-aware collective library that exploits NVLink topology, NVSwitch, and InfiniBand for GPU-to-GPU collectives. Uses ring, tree, and NVSwitch all-reduce algorithms selected based on message size and GPU topology.
**Latency-Bandwidth Model**
Collective time is modeled as: T = α × log(P) + β × N × f(P), where α = latency per message, β = transfer time per byte, N = data size, P = processes, and f(P) depends on the algorithm. The choice between tree (latency-optimal) and ring (bandwidth-optimal) crossover point depends on message size.
**Overlap and Pipelining**
Non-blocking collectives (MPI_Iallreduce) enable computation-communication overlap. The collective executes in the background while the process computes on independent data. For deep learning, layer-wise gradient allreduce overlaps with backward pass computation of earlier layers.
MPI Collective Communication is **the synchronization heartbeat of distributed parallel computing** — the operations that every process must complete together, making their performance the ultimate determinant of parallel scaling efficiency.