高维环网上的一种可扩展的全交换算法

全交换在并行计算领域中有着大量而且重要的应用,例如FFT和矩阵运算等.本文提出了一种适合环网结构的全交换算法.算法中采用了新的网络划分技术及通信模式,使高维环网上全交换算法的通信量的主项达到了理论下限,这是已知的其他相关算法未能达到的,且其启动次数与通信量均优于现有的其他同类算法.本文所述的算法并不要求环网每一维上的处理器结点数目是2的方幂或某一个数的平方.最后,该算法简单规范,易于硬件高效实现.

Efficient and Scalable Algorithms for All-to-All Personalized Communication on Multidimensional Tori

All-to-all personalized communication,also known as complete exchange,is at the heart of numerous applications in parallel computing environment,such as FFT and matrix transpose.This paper presents new efficient algorithms for all-to-all personalized communication in ring and multidimensional torus.In this paper,we adopt new network-partitioning technique and communication pattern to improve the performance of all-to-all personalized communication for multidimensional torus-connected multiprocessors,and the number of nodes in each dimension needs not be a power of two and square of some number.The main item of the transmission time of the algorithms reaches the lower bound in theory,which can not be obtained in existing indirect algorithms proposed in the literature.Finally,the algorithms are conceptually simple and easily implemented in hardware.