【摘要】 给出一个新的MPIAllgather算法———邻居交换算法(neighborexchange).提出的平均逻辑通信距离的概念和计算公式,可以有效地衡量通信的局部性.通过分析,发现在4种MPIAllgather算法中,邻居交换和环算法均具有最优的通信局部性.在万亿次机群深腾6800和曙光4000A上对4个MPIAllgather算法进行的性能测试和分析结果表明,邻居交换算法的长消息通信性能最优,中长消息通信性能不稳定,短消息通信性能次于递归倍增和Bruck算法.更多还原

【Abstract】 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.更多还原