机群系统中的高效全交换算法

Efficient Algorithms for Complete Exchange on Ethernet Switched Clusters

全交换在并行计算领域中有着大量而重要的应用,例如FFT和矩阵运算等.本文在由以太网交换机分层级联而成的机群系统上,提出了高性能的全交换算法DCE和算法MCCE.这两个算法充分利用了网络中瓶颈链路的带宽,达到了通信量的理论下限,并且运用多种策略来避免通信过程中的网络冲突,从而提高了机群的通信性能.实验结果表明,本文所述的算法在消息长度较长时,明显优于MPICH和LAM/MPI中实现的MPI-Alltoall算法.最后,该算法简单规范,易于实现.

Complete exchange, also known as all-to-all personalized communication, occurs in numerous numerical and scientific applieations, such as FFT and matrix transpose. The paper proposes two new algorithms for complete exchange on clusters connected by Ethernet switched hierarchical network. The new algorithms fully utilize the bandwidth in the bottleneck links and theoretically achieve the lower bounds on message transmission. Experimental results show that the proposed algorithms significantly outperform other MPI_Alltoall algorithms included in MPICH and LAM/MPI, on Ethernet switched clusters with hierarchical network topologies when the message size is long. Finally, the algorithms are conceptually simple and easily implemented.