Optimal, Non-pipelined Reduce-scatter and Allreduce Algorithms with an Application to All-to-all Communication

Abstract

The reduce-scatter collective operation in which p processors in a network of processors collectively reduce p input vectors into a result vector which is partitioned into p blocks over the processors is important both in its own right and as building block for other collective operations. We present a surprisingly simple, but non-trivial algorithm for solving this problem optimally in ⌈log 2p⌉ communication rounds with each processor sending, receiving and reducing exactly p − 1 blocks of vector elements, provided that the binary reduction operator is commutative. We combine this with a similarly simple, well-known allgather algorithm to get a volume optimal algorithm for the allreduce collective operation where the result vector is replicated on all processors. The communication pattern is a simple, ⌈log 2p⌉-regular, circulant graph also used elsewhere. A simple requirement on the skip sequence of the circulant graph gives freedom in the choice of communication pattern which may be valuable for practical implementation. The algorithms can readily be implemented and used for the collective operations MPI_Reduce_scatter_block, MPI_Reduce_scatter_block and MPI_Allreduce as specified in the MPI standard. For completeness, we also give a ⌈log 2p⌉ communication round optimal allreduce algorithm that can be used to implement MPI_Allreduce and is suited for smaller input vectors. Finally, we observe that the reduce-scatter algorithm can be used as a template for round-optimal all-to-all communication with smaller communication volume, for some p, than the well-known algorithm by Bruck et al. (1997) to implement the collective MPI_Alltoall operation. We provide experimental evidence on a small cluster that the algorithms can perform better than or comparably to other implemented MPI library algorithms.