MPI All-to-All
All-to-all is the total exchange in which every process sends a distinct message to every other process, transposing data across the group.
The total exchange
In MPI_Alltoall, each of P processes holds P blocks; block j on rank i is destined for rank j. After the call, rank j holds the j-th block from every rank. Viewed as a matrix whose rows are processes and columns are destinations, all-to-all is a distributed transpose. The variable-size MPI_Alltoallv lets each pair exchange a different amount.
Why it is expensive
All-to-all moves the most data of any standard collective: every process talks to every other, so total traffic scales as O(P^2) messages if done naively. It is the communication bottleneck in algorithms that need a global data redistribution, most famously the parallel FFT, where a transpose between decomposition directions is unavoidable, and in histogram or sorting steps that reshuffle keys by owner.
- Each rank sends a unique message to every other rank.
- It is the dominant cost in distributed FFTs and parallel sorts.
- Network bisection bandwidth is the limiting hardware resource.
- Alltoallv handles uneven per-destination message sizes.
Algorithms and hardware
For small messages, a Bruck-style logarithmic algorithm reduces the number of communication steps at the cost of extra local copying. For large messages, a direct pairwise schedule that carefully orders partners avoids network hot spots. Because all-to-all stresses the network's bisection bandwidth, the fat-tree or dragonfly topology of the interconnect strongly affects its speed.
Design implication
Because all-to-all scales poorly, algorithm designers work to avoid or minimize it. A spectral solver for plasma fields may accept a slightly less efficient decomposition to cut the number of transposes per step, trading local arithmetic for reduced global exchange. Recognizing an all-to-all as the scaling wall is often the first step in redesigning a communication-heavy kernel.