Alltoall

Alltoall is a collective communication operation used in parallel computing, in which every process starts with a block of data for each process in the communicator and ends with a block of data for every process. Specifically, each process sends a distinct data block to every other process and receives a distinct data block from every other process. After the operation, each process has a concatenation of the blocks received from all processes, resulting in data that has been redistributed across the processes.

In the Message Passing Interface (MPI), the standard alltoall operation is MPI_Alltoall. When all processes participate, each process provides a send buffer partitioned into p blocks (one per destination) of equal size and a receive buffer partitioned similarly. The version MPI_Alltoall with uniform counts requires the same number of elements sent to each destination; MPI_Alltoallv supports varying send counts and displacements per destination. The operation is synchronous in the sense that the call completes after the data have been transferred and copied into the receive buffers on all processes.

Common use cases include matrix transposition, data redistribution after a decomposition, or shuffling data for parallel sorting or graph algorithms, where a global reorganization of distributed data is required.

Performance depends on the network and implementation; the total data exchanged is proportional to p*(p-1) blocks, and latency and bandwidth dominate. Many MPI implementations optimize via pipelining and data-transfer strategies, but alltoall can be bandwidth-intensive and may become a bottleneck at large scale.

See also: alltoallv.