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.