一种数据并行中的群通信优化策略

《一种数据并行中的群通信优化策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种数据并行中的群通信优化策略王珏，期长军,张纪林，李建江(北京科技人学信息工程学院北京10()083)摘要：群通信是影响人规模数据并行系统效率的关键因索，其主要发生在程序不同阶段间的数组遼分布与循环划分后的数纟II重映射这两种悄况•在一次通信屮显箸影响群通信效率常被忽视的因素是消息冲突和消息长度的不一致.因为它们会导致进程间人屋的空闲等待时间.然而以前的研究耍么不能完全避免消息冲突，要么针对某些特殊情况.对此提出了在数组分布为Block_Cyclic(k)情况下的-种更具有普遍适川性的通信调度策略CSS.通过证明表明该策略能使一个通信步内的消息互不冲突消息长度尽量相等.从而最

2、小化通信调度生成时间和实际通信时间.最后的测试结果也表明，与传统的通信优化算法和MPI.Alltoallv实现相比,CSS策略使得通信效率得以明显提高.关键词：并行编译;数据并行;组通佶；数组重分布;分布内存1引言当前大多数并行应用系统都是采用基于分布式内存的数据并行范例•群通信在数据并行程序中普遍存在并□是影响英执行效率的关键因素.群通信主要发生在以下两种情况:程序的不同阶段间的数组重分布和循环划分后的数组重映射.许多数据并行编程语言，例如hpfm、ViennaFortran⑵和p-HPF［3］等，都是通过在分布内存下提供数组分布指导支持全局命名空间(globalnamesp

3、ace).在这些语言中，程序员通过指导语旬来指定数组在处理器间的分布模式.根据“拥有者计算”原则，编译器利用这些分布信息和循环小数组赋值语句來产生通信集.许多时候由于通信代价过高而导致并行效率很低，英至出现负加速比.针对这些典型问题，越來越多的研究者将通信优化的研究重点放在如何最小化通信集生成的时间⑷⑸、重叠通信与计算⑹以及重分布数组上，不过他们却忽略了由于结点间消息冲突和一次通信中消息长度不一样所带来的大量通信开销。另外，通过对消息进行调度减轻通信代价的研究冇:Park等人⑺在考虑数据传输、通信调度和索引计算的基础上提出了一个针对某些特例减少通信总时间的算法，不过它只是针対某

4、些特例.Desprez等人冈给出了一个最小化消息冲突的算法，但该算法仍然不能避免通信冲突XYuan等人何⑼提供了一个棊于MPl_Alltoallv实现的通信调度算法，但是其运行时的开销很人.M.Guo等人在以前工作的基础上［⑴给出了关于一维数组的重分布通信调度策略，英中冃标数组在发送处理器组Q和接收处理器组P上具冇不同分布形式2撚而该研究只是着眼于并行程序不同阶段Z间数组的重分布问题，并不能解决循环划分之后的数组重映射问题•与以往的研究相比，本文的主要贡献有以下三点：(1)本文提出的策略首次解决了循环划分后在数组重映射时出现的消息冲突问题•其避免了数组重映射时结点间的消息冲突,

5、同时也最小化了每步通信所花费的时间.(2)本文捉出的策略更具有普遍性，也适用于不同阶段的数组重分彳IJ.(3)本文提出的策略引入关于通信表的周期性理论，人幅度减低通信调度生成的时I'可•因此有利于该通信调度算法在编译阶段实现，不会带来额外的运行时开销.本文研究得到国家高技术研究发展计划863(No.2006AA01Z105)、国家自然科学基金(No.60373008)和教育部重点基金(No.106019)资助.作者简介住珏，男，1981年生，博士研究生，主要研究方向：并行计算与并行编译技术.胡长军，男，1963年生，博士，教授，博士生导师，主要研究方向：并行计算与并行编译技术，

6、并行软件工程、网络存储体系结构、数据工程与软件工程.张纪林，男，1980年生，博上研究生，主要研究方向:并行计算与并行算法.李建江，男，1971年生，博上，副教授，主耍研究方向：并行计算、并行编译与多线程技术.本文联系人:王珏,电话:(010)62334522,13520541361,E-mail:ncepu5@163.com,联系地址:北京市学院路30号北京科技大学信息工程学院135信箱王珏邮编:100083综上所述,本文给出了一种不仅具冇普遍适用性，而仇空间和时间花费很小，可以用于编译时完成的通信调度策略CSS(CommunicationSchedulingStrategy

7、).为了更好地描述问题,文中使用通信表COM(COMmunication)table和调度表CS(CommunicationScheduling)table(表的定义在第二部分给出)来分别描述处理器间的消息交互模式和消息的调度情况.首先引入通信表的周期性理论来缩短通信调度表的生成时间，然示给出与通信表内元素递推关系相关的定理和推论的证明•在以上定理和推论的基础上,构造出有效的调度算法使调度表的每一列变成接收处理器序号的枚举，并尽虽把长度相近的消息放到同一个通信步内.CSS策略既避免了处理器间