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

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

作　　者：刘刚[1] 顾乃杰[1] 任开新[1] 熊焰[1] 

机构地区：[1]中国科学技术大学计算机科学技术系,安徽合肥230027

出　　处：《电子学报》2005年第9期1723-1728,共6页Acta Electronica Sinica

基　　金：安徽省自然科学基金(No.03042210)

摘　　要：全交换在并行计算领域中有着大量而且重要的应用,例如FFT和矩阵运算等.本文提出了一种适合环网结构的全交换算法.算法中采用了新的网络划分技术及通信模式,使高维环网上全交换算法的通信量的主项达到了理论下限,这是已知的其他相关算法未能达到的,且其启动次数与通信量均优于现有的其他同类算法.本文所述的算法并不要求环网每一维上的处理器结点数目是2的方幂或某一个数的平方.最后,该算法简单规范,易于硬件高效实现.All-to-all personalized communication,also known as complete exchange,is at the heart of nmnerons applications in paralld 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-counected 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 wansmission 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.

关 键 词：全交换 全对全私人化通信 并行算法 环网 虫蚀路由 集体通信 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]