小型微型计算机系统JournalofChineseComputerSystems2007年5月第5期Vol128No.52007机群系统中的高效全交换算法刘刚1,顾乃杰1,陶耀东1,2,任开新11(中国科学技术大学计算机科学技术系,安徽合肥230027)2(中国科学院沈阳计算技术研究所,辽宁沈阳110004)E2mail:liugang@mail.ustc.edu.cn;gunj@ustc.edu.cn摘要:全交换在并行计算领域中有着大量而重要的应用,例如FFT和矩阵运算等.本文在由以太网交换机分层级联而成的机群系统上,提出了高性能的全交换算法DCE和算法MCCE.这两个算法充分利用了网络中瓶颈链路的带宽,达到了通信量的理论下限,并且运用多种策略来避免通信过程中的网络冲突,从而提高了机群的通信性能.实验结果表明,本文所述的算法在消息长度较长时,明显优于MPICH和LAMƒMPI中实现的MPI-Alltoall算法.最后,该算法简单规范,易于实现.关键词:全交换;全队全私人化通信;MPI;机群;集体通信中图分类号:TP311文献标识码:A文章编号:100021220(2007)0520861206EfficientAlgorithmsforCompleteExchangeonEthernetSwitchedClustersLIUGang1,GUNai2jie1,TAOYao2dong1,2,RENKai2xin11(DepartmentofComputerScience&Technology,UniversityofScienceandTechnologyofChina,Hefei230027,China)2(ShenyangInstituteofComputingTechnology,ChineseAcademyofSciences,Shenyang110004,China)Abstract:Completeexchange,alsoknownasall2to2allpersonalizedcommunication,occursinnumerousnumericalandscientificapplications,suchasFFTandmatrixtranspose.ThepaperproposestwonewalgorithmsforcompleteexchangeonclustersconnectedbyEthernetswitchedhierarchicalnetwork.Thenewalgorithmsfullyutilizethebandwidthinthebottlenecklinksandtheoreticallyachievethelowerboundsonmessagetransmission.ExperimentalresultsshowthattheproposedalgorithmssignificantlyoutperformotherMPI-AlltoallalgorithmsincludedinMPICHandLAMƒMPI,onEthernetswitchedclusterswithhierarchicalnetworktopologieswhenthemessagesizeislong.Finally,thealgorithmsareconceptuallysimpleandeasilyimple2mented.Keywords:completeexchange;all2to2allpersonalizedcommunication;MPI;cluster;collectivecommunication1引言机群系统具有性价比高、可扩展性好和可用性高等特点,已经成为商业应用和科学计算领域广泛采用的计算平台.在最新发布的世界超级计算机Top500排行榜中,机群占到72%.通信性能对机群计算效率有重要影响,提高机群的通信性能成为机群计算领域主要的研究热点.机群通信系统包括通信网络和通信软件两个部分.通信网络是机群节点之间数据交换和协同工作的基础,其性能很大程度上影响着整个系统的性能.机群广泛使用以太网、Myrinet和InfiniBand等高速通信网络,其中以太网目前应用最广泛,虽然其网络带宽和延迟不如专用网络,但是它在节点间通信负载不是非常大的应用环境中得到了广泛应用,其优点是易于搭建且成本低廉.MPI(MessagePassingInterface)是目前应用最广的一种基于消息传递模型的并行编程接口,它几乎被所有并行计算环境和流行的多进程操作系统所支持.MPI不仅支持点对点通信,还支持集体通信.MPI中最重要的集体通信操作之一是MPI-Alltoall,即全交换.所谓全交换是指系统中的每个处理器节点给其它节点均发送一份内容不同但长度相同的消息.目前,有关全交换操作的研究成果已有很多,其中很多通信算法是为并行机中的专有网络设计的,例如hypercube[1]、mesh[2]、torus[3]和胖树[4]等.机群系统上的研究成果也不少.Thakur[5]提出了与网络拓扑结构无关的通用全交换算法.Liu[6]在不规则拓扑结构上提出了启发式的全交换算法.在用一台以太网交换机连接而成的机群上,Tam[7]提出了高效的全交换调度算法.在用多台以太网交换机连接而成的机群上,Faraj[8]提出了一种通信量达到理论下限的全交换算法.但是该算法非常复杂,不易实现.Faraj[9]介绍了一种实用的经验方法,该方法针对某个计算平台,通过对多个全交换算法进行性能测试,从而为该平台选择性能最佳的算法来进行全交换操作.全交换算法分为直接通信算法和间接通信算法(又称消息合...