Revisiting a Classic: Bruck algorithm for non-uniform all-to-all communication
Sidharth Kumar, University of Alabama at Birmingham

Abstract:  As supercomputers enter the exascale era, scientific applications that rely heavily on collective communication operations in Message Passing Interface (MPI) for data exchange and global synchronization find their communication costs increasingly dominating. Among all the MPI collective operations, MPI_Alltoall and MPI_Alltoallv play especially important roles in allowing all the processes involved in communication to exchange data with each other. MPI_Alltoallv is a generalization of MPI_Alltoall, supporting the exchange of non-uniform distributions of data. However, the latency of the standard MPI_Alltoallv implementations is in O(P ) (linear in the number of processes), whereas MPI_Alltoall is O(log P ). Such linear-complexity performs poorly when applications are deployed on thousands of processes, especially for short-message communication which is dominated by latency.

In this talk, I will present variants of the Bruck algorithm, a classic uniform all-to-all communication algorithm with logarithmic latency in P. I will then present two techniques: padded bruck and two-phase bruck, that efficiently generalizes Bruck to non-uniform all-to-all data exchange. The techniques make it possible to perform non-uniform all-to-all data exchanges with logarithmic latency. We empirically validate the techniques on three supercomputers: Theta, Cori and Stampede, using both microbenchmarks and two real-world applications: graph mining and program analysis. We perform both weak and strong scaling studies for a range of average message sizes, degree of imbalances, and distribution schemes, and demonstrate that our techniques outperform vendor optimized Cray’s MPI_Alltoallv by as much as 50% for different workloads and scale.