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

小 型 微 型 计 算 机 系 统Jou rnal of Ch inese Compu ter System s2007 年 5 月 第 5 期V o l128 N o. 5 2007机群系统中的高效全交换算法刘刚1 , 顾乃杰1 , 陶耀东1, 2 , 任开新11(中国科学技术大学 计算机科学技术系, 安徽 合肥 230027)2(中国科学院 沈阳计算技术研究所, 辽宁 沈阳 110004)E2m ail: liugangm ail. ustc. edu. cn; gunj ustc. edu. cn摘 要: 全交换在并行计算领域中有着大量而重要的应用, 例如 FFT 和矩阵运算等. 本文在由以太网交换机分层级联而成的 机群系统上, 提出了高性能的全交换算法DCE 和算法M CCE. 这两个算法充分利用了网络中瓶颈链路的带宽, 达到了通信量的 理论下限, 并且运用多种策略来避免通信过程中的网络冲突, 从而提高了机群的通信性能. 实验结果表明, 本文所述的算法在消 息长度较长时, 明显优于M P ICH 和LAM M P I 中实现的M P I- A lltoall 算法. 最后, 该算法简单规范, 易于实现.关 键 词: 全交换; 全队全私人化通信;M P I; 机群; 集体通信中图分类号: T P 311文献标识码: A文 章 编 号: 100021220 (2007) 0520861206Eff ic ien t A lgor ithm s for Com plete Exchange on Ethernet Sw itched ClustersL IU Gang1 , GU N ai2jie1 , TAO Yao 2do ng1, 2 , R EN Kai2x in11(D ep artm ent of C om p u ter S cience & T echnology , U niversity of S cience and T echnology of China, H ef ei 230027, China)2(S heny ang Institu te of C om p u ting T echnology , Chinese A cad em y of S ciences, S heny ang 110004, China)Abstract: Comp lete exchange, also know n as all2to 2a ll personalized comm un icat io n, occu rs in num erou s num erical and scien t if ic app licat io n s, such as FFT and m atrix t ran spo se. T he paper p ropo ses tw o new algo rithm s fo r comp lete exchange on clu sters connected by E thernet sw itched h ierarch ical netw o rk. T he new algo rithm s fu lly u t ilize the bandw idth in the bo t t leneck link s and theo retically ach ieve the low er bounds on m essage t ran sm issio n. Exper im en tal resu lts show that the p ropo sed algo rithm s sign if ican t ly ou tperfo rm o ther M P I- A lltoall algo rithm s included in M P ICH and LAM M P I, on E thernet sw itched clu sters w ith h ierarch ical netw o rk topo logiesw hen the m essage size is long. F inally, the algo rithm s are concep tually sim p le and easily im p le2 m en ted.Key words: comp lete exchange; all2to 2a ll personalized comm un icat io n; M P I; clu ster; co llective comm un icat io n1引言机群系统具有性价比高、可扩展性好和可用性高等特点, 已经成为商业应用和科学计算领域广泛采用的计算平台. 在 最新发布的世界超级计算机 Top 500 排行榜中, 机群占到 72%. 通信性能对机群计算效率有重要影响, 提高机群的通信 性能成为机群计算领域主要的研究热点.机群通信系统包括通信网络和通信软件两个部分. 通信 网络是机群节点之间数据交换和协同工作的基础, 其性能很 大程度上影响着整个系统的性 能. 机群广泛使用以太 网、 M yrinet 和 Infin iB and 等高速通信网络, 其中以太网目前应用 最广泛, 虽然其网络带宽和延迟不如专用网络, 但是它在节点 间通信负载不是非常大的应用环境中得到了广泛应用, 其优 点是易于搭建且成本低廉.M P I(M essage Passing In terface) 是目前应用最广的一种 基于消息传递模型的并行编程接口, 它几乎被所有并行计算 环境和流行的多进程操作系统所支持. M P I 不仅支持点对点通信, 还支持集体通信. M P I 中最重要的集体通信操作之一 是M P I- A lltoall, 即全交换. 所谓全交换是指系统中的每个处 理器节点给其它节点均发送一份内容不同但长度相同的消 息. 目前, 有关全交换操作的研究成果已有很多, 其中很多通 信算法是为并行机中的专有网络设计的, 例如 hypercube 1 、 m esh 2 、to ru s 3 和胖树 4 等. 机群系统上的研究成果也不少.T haku r 5 提出了与网络拓扑结构无关的通用全交换算法. L iu 6 在不规则拓扑结构上提出了启发式的全交换算法. 在用 一台以太网交换机连接而成的机群上, T am 7 提出了高效的 全交换调度算法. 在用多台以太网交换机连接而成的机群上, Faraj 8 提出了一种通信量达到理论下限的全交换算法. 但是 该算法非常复杂, 不易实现. Faraj 9 介绍了一种实用的经验 方法, 该方法针对某个计算平台, 通过对多个全交换算法进行 性能测试, 从而为该平台选择性能最佳的算法来进行全交换 操作.全交换算法分为直接通信算法和间接通信算法 (又称消 息合并算法). 直接通信算法是指每条消息仅在源节点和目的收稿日期: 2006203221 基金项目: 国家自然科学基金项目(60533020) 资助. 作者简介: 刘 刚, 男, 1978 年生, 博士研究生, 研究方向为并 行分布式系统; 顾乃杰, 男, 1961 年生, 博士生导师, 研究方向为并行分布式计算; 陶耀东, 男, 1981 年生, 博士研究生, 研究方向为数字控制系统; 任开新, 女, 1977 年生, 讲师, 研究方向为多级互连网络.862小 型 微 型 计 算 机 系 统2007 年节点之间直接传送, 它适合于消息比较长的情况. 间接通信算 法是先将发往多个目的节点的多条消息合并为一条长消息, 发送给某个中间节点, 然后再由此节点负责将这些消息转发 到它们的目的节点. 间接通信算法减少了启动开销, 却增加了 网络中的通信负载, 它适合于消息比较短的情况.本文在由以太网交换机分层级联而成的机群系统上, 提 出了高性能的全交换算法DCE 和算法M CCE. 这两个算法运 用了多种策略来避免通信过程中的网络冲突, 并且充分利用 了网络中瓶颈链路的带宽资源. 与现有的其他算法相比, 本文 中的算法有如下主要优点: 1) 全交换算法DCE 和算法M CCE 都达到了通信量的理论下限; 2) 算法M CCE 无冲突地安排了 尽可能多的消息并发传递, 从而减少了消息启动开销和同步 开销, 提高了机群的通信性能.本文第二节介绍了与算法相关的系统通信模型. 第三节 具体描述了全交换算法DCE 和算法M CCE. 第四节给出实验 结果和性能分析. 第五节是结论.2 系统模型与基本术语目前, 由于交换机端口数目等因素的限制, 用多台以太网 交换机分层级联而成的大型机群系统很多都采用图 1 所示的 两层交换网络结构. 机群中的 N = a b 个计算节点可分为 a (a2) 个组, 每组有 b (b1) 个计算节点. 同一组中的计算节 点连接到同一台以太网交换机上, 然后 a 台交换机再连接到 主交换机. 于是我们可将这类机群系统模型化为“树”型拓扑 结构: 主交换机 ES 为树的根节点, 所有计算节点为叶节点. tx 表示以第 x (0x a ) 个下层交换机为根的子树, (x , i) 表示 第 x 棵子树中的第 i (0i b) 个计算节点, (x , i) (y , j ) 表 示节点 (x , i) 向节点 (y , j ) 发送消息.图 1 两层交换机互连拓扑结构图F ig. 1 F ig. 1 In terconnect io n topo logy of the tw o 2level sw itch h ierarchy本文中我们假定每个计算节点在一个通信步中可以同时 发送和接受消息; 每一条以太网链路均为双向链路; 所有的以 太网链路具有相等的带宽和速度. 由此可知, 与主交换机直接 相连的 a 条物理链路成为系统的通信瓶颈. 当 b= 1 时, 此通 信模型就简化为由一台以太网交换机连接所有计算节点的机 群系统. 若每棵子树中计算节点的数目略有不同时, 则可以通 过增加虚拟节点的方式来适用此模型.我们设定在两个计算节点之间发送一条消息所需的时间 开销为 T = ts + m siz etw , 其中 ts 为发送消息所需的启动时间, tw 为传输一个字节所需的通信时间, m siz e 是消息的长度(以字节为单位).定理 1. 对于如图 1 所示的两层交换机互连结构, 其中 a1 且 b1, 全交换操作的通信量的理论下限为 b2 (a- 1).证明: 因为每棵子树均有 b 个计算节点, 不失一般性, 我 们仅需考虑与主交换机相连的某一条瓶颈链路. 该链路的一边有 b 个节点, 另一边有 b (a - 1) 个节点, 那么至少应该有 b2 (a- 1) 条消息要单向经过该链路. 因此, 在两层交换网络结 构上全交换操作的通信量的理论下限为 b2 (a- 1).3 全交换算法在树型拓扑结构中, 与根节点相连的物理链路成为通信 瓶颈. 在子树之间传递的消息均需要经过这些瓶颈链路, 而在 每棵子树内传递的消息仅使用本子树内的链路和通信端口. 因此, 我们将消息分为局部消息和全局消息: 局部消息的源节 点与目的节点在同一棵子树中, 而全局消息的源节点与目的 节点隶属于不同的子树. 为了完全达到全交换操作通信量的 理论下限, 我们必须首先对这些经过瓶颈链路的全局消息进 行调度, 避免链路冲突且充分利用瓶颈链路带宽.表 1 通信阶段的环形排列T ab le 1 Phases from ring schedu ling P h a se 0P h a se 1P h a se a - 2 t0t1t0t2t0ta- 1t1t2t1t3t1t0ta- 2ta- 1ta- 2t0ta- 2ta- 3ta- 1t0ta- 1t1ta- 1ta- 2我们用著名的环形算法 ( ring algo rithm ) 7 来安排子树之 间的全局消息传递, 如表 1 所示, tx ty (x y ) 表示子树 tx 将 目的地址为子树 ty 中节点的 b2 条全局消息发送给 ty , 并且规 定所发送的这 b2 条全局消息必须在同一通信阶段内完成. 因 此, 整个通信过程分为 a - 1 个通信阶段, 每一棵子树在不同 的通信阶段依次向不同的子树发送全局消息. 例如对子树 t1 而言, 首先是 t1 t2 , 接下来依次是 t1 t3、t1 t4 , . 在第 p (1 p a ) 个通信阶段中, 每一棵子树 tk (0k a ) 在向子树 t (k+ p )moda 发送全局消息的同时, 也从子树 t (k- p )moda 接受全局消 息. 环形算法划定了每一条全局消息的通信阶段, 并确保在任 何两棵子树之间传递的全局消息不会与其他子树之间传递的 全局消息相冲突.3. 1 全交换算法DCE在用环形调度算法确定了全局消息的通信阶段之后, 我 们要具体实现每一棵子树内所有节点的通信模式. 首先我们 采用直接通信方式来实现全交换.子 树 tx 中有 b 个节点 (x , 0) , (x , 1) , , (x , b- 1) , 每个 节点都需要向子树 ty 中的所有节点各发送一条消息. 我们采 用广播策略 (b roadcast schem e) 来安排子树 tx 向子树 ty 发送5 期刘 刚 等: 机群系统中的高效全交换算法863b2 条全局消息: b2 条消息分 b 轮发送, 在每一轮中, tx 中的某 一个节点依次向 ty 中 b 个节点连续发送 b 条消息, 即 (x , 0) (y , 0) , , (x , 0) (y , b- 1) , (x , 1) (y , 0) , , (x , 1) (y ,b- 1) , , (x , b- 1) (y , 0) , , (x , b- 1) (y , b- 1). 因此, 每个通信阶段可分为 b2 步. 在每一步通信过程中, 子树 tx 中 至多有两个节点参与全局消息的发送与接收: 节点 (x , i) 向 ty 中的节点 (y , j ) 发送消息, 与此同时, 节点 (x , j ) 也从 tz 中的节 点 (z , i) 接收消息, 因此全局消息的传递没有冲突.在传递全局消息的同时, 子树 tx 中的 b 个节点还需要传 送本子树内的 b (b- 1) 条局部消息. 我们采用广播策略, 以错 排方式将这 b (b- 1) 条局部消息无冲突地安排在 b2 步通信过 程中. 若节点 (x , i) 是全局消息的发送者, 节点 (x , j ) 是全局消 息的接受者 ( ij ) , 则我们安排节点 (x , ( i+ 1)modb) 向同一 棵子树中的节点 (x , ( j + 1)modb) 发送局部消息, 这样就避免 了全局消息和局部消息产生冲突. 每一棵子树的内部节点在 第一个通信阶段就可以完成所有 b2 条局部消息的传递, 因此 在其他通信阶段, 就只需要传递全局消息.A lgor ithm DCEa2 BEG INFor p = 1 to a- 1For k = 0 to a- 1 Para- DoG roup T ransm it1 (k , (k + p )mod a) ; tk t (k+ p ) mod aENDA lgor ithm G roup T ransm it1 (x , y ) tx tyBEG INFor s= 0 to b2- 1 and Para- Do. (x sb ) (y , s mod b) ;. if (y - x ) mod a= 1 and sb s mod bthen (x , ( sb + 1) mod b) (x , (s+ 1) mod b) ;END图 2 全交换算法DCE 的具体描述F ig. 2 D escr ip t io n of comp lete exchange algo rithm DCE(y , j )(y , j )图 2 是算法的正式描述: M (x , i) 表示从源节点 (x , i) 发送 到目 的 节 点 ( y , j ) 的 一 条 消 息, 而 M (x , 3 ) 表 示 消 息 集 合段, 每个通信阶段有 b2 步, 因此全交换算法DCE 的时间复杂 度是 T = b2 (a - 1) ts + b2 (a - 1) m siz etw , 其通信量完全达 到理论下限 b2 (a- 1).结论 1. 全交换算法DCE 在通信过程中没有任何链路冲突.证明: 环形算法确保在任何两棵子树之间传递的全局消 息不会与其他子树之间传递的全局消息产生冲突, 并且广播策略也保证在每一步通信过程中, 子树 tx 内仅有一个节点发 送全局消息, 仅有一个节点接受其他子树发送的全局消息, 因 此任何两条全局消息之间不存在冲突. 在不同子树内传递的 局部消息彼此不会产生冲突, 而且在算法的每一步, 一棵子树 内至多有一条局部消息在传递, 因此冲突唯一可能存在于某 棵子树中的全局消息和局部消息之间, 而错排方式有效地避 免了这种冲突. 所以全交换算法DCE 在通信过程中理论上没 有链路冲突.3. 2 全交换算法M CCE在全交换算法DCE 的每一步通信过程中, 每棵子树至多 有 4 个节点参与消息的传递, 很多节点闲置, 这造成了链路和 端口带宽的浪费. 于是, 我们又提出了一个新的全交换算法 M CCE. 该算法沿用环形算法, 将整个通信过程分为个 a - 1 通信阶段. 与算法DCE 不同之处在于, 在每个通信阶段中, 新 算法采用消息合并方式来重新设计全局消息的通信模式, 这 样可以大幅度减少消息个数、通信次数以及同步开销, 从而提 高机群系统的通信性能.全交换算法M CCE 在两棵子树之间传递全局消息 ( tx ty ) 有两种通信模式: 其一, 在第一个通信阶段中, 子树 tx 中的 每个节点 (x , i) 将目的地址为子树 tx + 1 中节点的 b 条消息合并 为一条长消息发送给节点 (x + 1, (b- 1) - i) , 然后在第二个 通信阶段中, 再由节点 (x + 1, (b- 1) - i) 将消息拆分、散发给 tx + 1 中的其他节点; 其二, 子树 tx 中的所有节点在第 p - 1 (p2) 个通信阶段中, 先将目的地址为 (y , j ) 的 b 条消息收集到 树内节点 (x , (b- 1) - j ) 中, 然后在第 p 个通信阶段中, 再由 节点 (x , (b- 1) - j ) 将这 b 条消息合并为一条长消息并直接 发送到这些消息的目的节点 (y , j ). 因此所有的全局消息都需 要两次通信才能达到目的节点, 而局部消息只需本子树内的M (x , 0)(x , 1)(x , b- 1)(y , j ) , M (y , j ) , M (y , j ) . 该算法总共有 a - 1 个通信阶一次通信即可到达目的节点.表 2 子树 tx 中 6 个节点的通信模式T ab le 2 A n examp le fo r comm un icat io n pattern of sub2tree tx1(x , 0) (x , 1)(x , 1) (x , 2)(x , 2) (x , 3)(x , 3) (x , 4)(x , 4) (x , 5)(x , 5) (x , 0)2(x , 0) (x , 2)(x , 1) (x , 3)(x , 2) (x , 4)(x , 3) (x , 5)(x , 4) (x , 1)(x , 5) (x , 0)3(x , 0) (x , 3)(x , 1) (x , 4)(x , 2) (x , 5)(x , 3) (x , 2)(x , 4) (x , 0)(x , 5) (x , 1)4(x , 0) (x , 4)(x , 1) (x , 5)(x , 2) (x , 3)(x , 3) (x , 0)(x , 4) (x , 1)(x , 5) (x , 2)5(x , 0) (x , 5)(x , 1) (x , 4)(x , 2) (x , 0)(x , 3) (x , 1)(x , 4) (x , 2)(x , 5) (x , 3) 6(x , 0) (x , 5)(x , 1) (x , 0)(x , 2) (x , 1)(x , 3) (x , 2)(x , 4) (x , 3)( x , 5) (x , 4) 在全交换算法M CCE 的每一个通信阶段中, 子树 tx 中的 每个节点需要为下一个通信阶段收集全局消息; 其中在第二 个通信阶段, 子树 tx 中的每个节点还要负责将其在第一个通信阶段中接受的全局消息拆分, 再散发给本子树内其他节点; 在最后一个通信阶段, 子树 tx 中的节点要完成本子树内的 “局部”消息传递. 这就等同于要求子树内的 b 个节点进行“局864小 型 微 型 计 算 机 系 统2007 年部”全交换操作. 子树 tx 中的 b 个节点共需要 b 次通信才能将A lgor ithm DCEa3 BEG INFor p = 1 to a- 1For k = 0 to a- 1 Para- DoG roup T ransm it2 (k , (k + p )mod a) ; tk t (k+ p ) mod aENDA lgor ithm G roup T ransm it2 (x , y ) tx tyBEG INFor s= 1 to bFor i= 0 to b- 1 Para- DoGMif i= b- s, then (x , i) - (y , s- 1)LMelse (x , i) - (x , j ) , w here j = ( i+ s) mod (b+ 1) ;M (x , i)(y , 3 ) , if (y - x ) mod a= 1M x , 3W here GM =y , x - 1, otherw iseb 条合并后的长消息都发送到 ty 中的相应节点. 因此,“局部” 全交换操作也需要在b步之内完成. 我们提出了一种拓展的 环形算法, 该算法充分利用了子树中除发送合并消息的节点 的出端口以及接受合并消息的节点的入端口之外所有的端口 和空闲链路, 在每一步都无冲突地安排了 b- 1 条消息在本子 树内同时传递. b 步之后, 子树中的每个节点都给其他 b- 1 节点各发送了一条内容不同的消息. 表 2 举例描述了子树 tx 中 6 个节点的通信模式, 其中的深色区域表示在不同子树之 间的消息传递.图 3 是算法M CCE 的正式描述, 该算法分为 a - 1 个通 信阶段, 每个通信阶段又分为 b 步. 因此全交换算法M CCE 的时间复杂度是 T = b (a - 1) ts + b2 (a - 1) m siz etw , 其 通信量完全达到理论下限 b2 (a- 1).结论 2. 全交换算法M CCE 在通信过程中没有链路冲突.证明: 由结论 1 可知, 任何两棵子树之间传递的全局消息M ( (x - 1)mod (1, i)(x , i)LM =(x , j )+ M ( (y + 1)moda, (b- 1) - j ) , if (y - x )moda= 2M (x , i)( (y + 1) mod a, b- 1) - j ) ,otherw iseEND图 3全交换算法M CCE 的具体描述传递的消息彼此也不会产生冲突, 因此冲突只可能存在于某棵子树之中. 由拓展的环形调度算法可知, 在任何一个通信阶 段的第步 s 1. . b 中, 子树 tx 中的节点 (x , i) ( ib- s) 向节F ig. 3 D escr ip t io n of comp lete exchange algo rithm M CCE点 (x , j ) 发送了一条消息, 当 i b- s时, j = ( i+ s) - (b+ 1) 0. . s- 2 . 当i= b- s时,M (x , i)(x , j ) , if (y - x ) mod a= a- 1,不会与其他子树之间传递的全局消息产生冲突, 不同子树内图 4 节点 (0, 3) 的 18 步通信过程F ig. 4 A n ex amp le f or com m unication p a tterns of the nod e (0, 3)(x , b- s) (y , s- 1) , 因此子树 tx 中的任何两个节点不可能 同时向一个目的节点发送消息. 因此, 全交换算法M CCE 在通信过程中没有任何链路冲突. 下面举例说明在全交换算法的通信过程中, 节点发送和5 期刘 刚 等: 机群系统中的高效全交换算法865接收消息的具体过程. 若在 a = 4 且 b= 6 的树型网络拓扑结 构上实现全交换操作, 则节点 (0, 3) 的 18 步通信过程如图 4所示. 在通信开始之前, 节点 (0, 3) 有 24 条不同的消息要发送 给机群中的节点, 其中包括一条留给自己的假消息. 消息的初 始分布如图 4 (a) 所示, 其中“ab, cd ”表示一条源节点为 (a, b) 且目的节点为 (c, d ) 的消息; 节点 (0, 3) 目前准备要发送的消 息用黑框标示; 节点 (0, 3) 在前一步中刚收到的消息用阴影标示. 在完成最后一步通信之后, 节点 (0, 3) 要将所收到的消息 排列整齐, 最后的结果如图 4 ( t) 所示.4算法性能评价下面将本文提出的全交换算法 DCE 和算法M CCE, 与LAM M P I 6. 5. 9 10 和最新版本的M P ICH 1. 2. 6 5 中实现的M P I- A lltoall 进行性能对比. 在M P ICH 1. 2. 6 中, M P I- A ll2 toall 是由四个不同算法共同实现的, 系统根据不同的消息长 度而选用不同的算法. 当消息长度小于 256 字节时, M P ICH 调用B ruck 算法以减少消息发送次数和进程同步开销; 当消 息长度介于 256 字节与 32K 字节之间时, 调用简单的 irecv2 isend 算法; 当消息长度大于 32K 字节且进程数目为 2 的方幂 时,M P ICH 调用成对交换 (pairw ise2exchange) 算法, 当进程 数目不是 2 的方幂时, M P ICH 调用环形 ( ring) 算法. LAM M P I 仅使用简单的 irecv2isend 算法来实现M P I - A lltoa ll.测试环境为具有 24 个节点的 PC 机群系统. 每台 PC 节 点有 P 4 2. 4GH 处理器, 256M 内存、一个百兆位网卡和 40G 硬盘, 操作系统为 D eb ian GNU L inux (内核版本是 2. 6. 9). 节点之间通过百兆位快速以太网互连, 交换设备由一台 3COM 3C 17302 交换机和 4 台 T P- L ink TL - SF 1024 交换机 组成.图 5 实验所用的网络拓扑结构F ig. 5 E thernet topo logies u sed in the exper im en ts实验所用的网络拓扑结构如图 5 所示. 其中图 5 (a) 表示 由一台交换机连接 24 个节点的 PC 机群; 图 5 (b) 表示由各连 接 8 个节点的三台交换机和一台主交换机组成的 PC 机群; 图 5 (c) 表示由各连接 6 个节点的四台交换机和一台主交换 机组成的 PC 机群. 这三种拓扑结构分别简称为拓扑 (a)、拓 扑 (b) 和拓扑 (c). 图 6 给出了我们测试M P I- A lltoall 性能的 代码片断. 我们调用LAM M P I 的点对点通信原语来具体实 现算法DCE 和算法M CCE.图 7 (a)、(b) 和 (c) 分别显示了 4 种算法在 3 种不同的网 络拓扑结构上的性能比较结果. 可以看出, 不同的拓扑结构所M P I- Barrier (M P I- COMM - WORLD )start= M P I- W t im e () ;fo r (count= 0; count IT ER - NUM ; count+ + ) M P I- A lltoall( )elap sed- t im e= M P I- W t im e- start;comp let ion- t im e= elap sed- t im eIT ER - NUM ;图 6 测试M P I- A lltoall 性能的代码片断F ig. 6 Code segm en t fo r m easu ring M P I- alltoall perfo rm ance对应的通信完成时间也大不相同, 这是因为不同的拓扑结构 决定了瓶颈链路上不同的通信负载. 理论上, 由一台交换机连图 7 通信完成时间与消息长度关系图F ig. 7 Perfo rm ance of comp lete exchange algo rithm s接所有计算节点的机群具有最优的通信性能. 对拓扑 (a) 而 言, 即当 b= 1 时, 我们的算法M CCE 就等同于算法 DCE, 它866小 型 微 型 计 算 机 系 统2007 年们与M P ICH 中的环形算法也非常相似. 因此当消息长度大 于 32KB 时, 这两个算法的运行时间与M P ICH 相差不大, 之 间的差距可能是由于采用了不同的同步策略. 当消息长度较 小时,M P ICH 和LAM 选用简单的 irecv2isend 算法就可以获 得较好的性能, 这是因为短消息导致交换机内部冲突的可能 性较小, 环形算法需要引入同步来减少网络冲突, 所以同步开 销的增大反而导致通信性能的下降.如图 7 (b) 和 (c) 所示, 我们提出的算法DCE 和算法M C2 CE 明显优于M P ICH 和 LAM , 尤其是在消息较长时, 算法 M CCE 一般比 LAM 快 15% 到 31%. 例如, 当消息长度为 128K 时, 在拓扑 (b) 中, 算法M CCE 比 LAM 快 31. 2% , 比 M P ICH 快 4 7. 9 % ; 在 拓 扑 ( c ) 中 , 算 法M CCE 比LAM 快 21. 3% , 比M P ICH 快 43. 4%. 这是因为拓扑 (b) 和拓扑 (c) 在两层交换机之间存在瓶颈链路, 而隶属于同一交换机中的 所有节点要共享一条瓶颈链路, 所以在瓶颈链路上发生链路 冲突的可能性就比较大. 算法 DCE 和算法M CCE 将整个通 信过程划分为多个无冲突的通信步, 在两个通信步之间插入 同步机制, 这样就大大减少了网络冲突的可能性, 从而提高了 全交换操作的通信性能.需要指出的是, 实验结果显示M P ICH 版本的M P I- A ll2 toall 整体性能比 LAM 版本的差, 但是这并不能说明在其他 计算平台上也依然如此. 有很多系统参数, 例如交换机中的缓 存容量、网络拓扑结构、操作系统上下文切换的开销以及网络 与处理器之间的速率比等, 都会明显地影响全交换操作的通 信性能 11 . 一般来说, 一个全交换算法不可能在所有的平台 上都取得较高的通信性能. 为了在不同的平台上都能获得较高的通信性能, 就必须让M P I- A lltoall 融合不同的算法以供 系统根据自身的特点选择调用, 这也是本文的研究目的.5 总 结制约机群发展的关键问题是负责数据传输的网络通信开 销. 本文在由以太网交换机分层级联而成的机群系统上, 提出 了高性能的全交换算法DCE 和算法M CCE. 这两个算法运用 了多种策略来避免通信过程中的网络冲突, 并且充分利用了 网络中瓶颈链路的带宽资源, 从而达到了提高机群通信性能 的目的. 实验结果表明, 本文所述的全交换算法在消息长度较 长时, 明显优于M P ICH 和 LAM M P I 中实现的M P I- A ll2 toall 算法.References: 1 Sco t t D S. Efficient all2to 2a ll comm unicat ion patterns in hyper2 cube and m esh topo logiesC . In: P roceedings of 6th D istributed M emo ry Computing Conference , Po rtland, U SA , 1991, 3982 403. 2 Sundar N S, Jayasim ha D N , et a l. H ybrid algo rithm s fo r com 2 p lete exchange in 2D m eshesJ . IEEE T ran s. Parallel and D is2 tributed System s, 2001, 12 (12) : 120121218. 3 L iu Gang, Gu N ai2jie, et a l. Efficient and scalable algo rithm s fo r all2to 2a ll personalized comm unicat ion on m ultid im ensiona l to riJ . T ien T zu H sue