Implementation and Performance Analysis of a New MPI Allgather Algorithm on Terascale Linux Clusters
Jing Chen · Chinese Journal of Computers · 2006
Message Passing Interface(MPI) is one of the most important parallel programming environment. The MPI library provides point-to-point and collective communication functions, among which MPI Allgather is one of the most frequently used functions. Three kinds of algorithm are implemented for MPI Allgather in the latest versions of MPICH, i.e., the ring, the recursive doubling and the Bruck algorithms. In order to minimize the TCP traffic and congestion over Fast Ethernet, the authors propose a new MPI Allgather algorithm, namely the neighbor exchange. In the neighbor exchange algorithm, a property of pair-wise communication is incorporated and a process always exchanges data with its logical neighbor processes. A new concept, the Average Logical Communication Distance(ALCD), is proposed to measure the algorithmic communication locality. Analysis on the ALCD for the four algorithms reveals that the neighbor exchange and the ring algorithms have the best communication locality property among the four MPI Allgather algorithms. Numerical experiments on terascale Linux clusters DeepComp 6800 and DAWNING 4000A show that the neighbor exchange algorithm performs the best for long messages but is suboptimal for short and medium sized ones. For medium-size messages, the ring algorithm performs the best and for short messages, the recursive doubling algorithm performs the best.