Enhanced collective communication functions using factorization and pairwise-exchange communication

This paper proposes new algorithms to enhance the collective communication functions, and reports the analysis and experimental results of them. The new algorithms use factorization and pairwise-exchange dissemination methods in broadcast, allgather and allreduce. They demand at most log₂P stages, and deliver better performance than the previous algorithms such as ring, recursive doubling and dissemination algorithms. Experimental results show the improvement of 50% or so over MPICH version 1.2.6 on a Linux cluster using TCP over fast Ethernet and gigabit Ethernet. The algorithms are being extended to other communication functions such as all-to-all broadcast and reduce-scatter.