Adaptive Recursive Doubling Algorithm for Collective Communication

Process arrival times at MPI collective operations differ significantly. Addressing this fact with special handling for popular collective communication algorithms can yield performance improvements. The recursive doubling algorithm is one of the most efficient techniques for implementing collectives in MPI, especially for short messages and when the number of participating processes is a power of two. In the recursive doubling algorithm, all the processes must complete a given step before the algorithm continues to the next step. In this paper, we present a recursive doubling algorithm that makes use of available data and removes the requirement for each process to arrive at each step before proceeding. Our approach makes use of the multicast feature of the underlying network and progress tagging of messages, describing the currently available partial results. Our approach could be implemented in any parallel execution environment that supports multicasting. Our prototype implementation is based upon a network interface card with an FPGA, the Net FPGA. The Net FPGA provides hardware level programmability to offload processing, precise and controlled timing for accounting for packet and algorithm behavior, allowing classification of skew scenarios. Our algorithm provides up to 10% saving in synchronization delay in the presence of skew and up to 37% saving in number of messages generated, and up to 32% saving in reduction operations performed in MPI Allreduce.