Butterfly-like Algorithms for GASPI Split Phase Allreduce

Abstract

Collective communication routines pose a significant bottleneck of highly parallel programs. Research on different algorithms for disseminating information among all participat- ing processes in a collective communication has brought forth many different algorithms, some of which have a butterfly- like communication scheme. While these algorithms have been abandoned from usage in collective communication routines with larger messages, due to the congestion that arises from their use, these algorithms have ideal properties for split-phase allreduce routines: all processes are involved in the computation of the result in each communication round and they have few communication rounds. This article will present several different algorithms with a butterfly-like communication scheme and examine their usability for a GASPI allreduce library routine. The library routines will be compared to state-of-the-art MPI implementations and also to a tree-based allreduce algorithm.