《论文_一种数据并行中的群通信优化策略(定稿)》

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

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

2、突且消息长度尽量相等.从而最小化通信调度生成时间和实际通信时间.最后的测试结果也衣明,与传统的通信优化算法和MPI_Alltoallv实现相比,CSS策略使得通佶效率得以明显提岛.关键词:并行编译;数据并行;组通信;数组重分布;分布内存1引言当前大多数并行应用系统都是采用棊于分布式内存的数据并行范例•群通信在数据并行程序中普遍存在并且是影响其执行效率的关键因素.群通信主要发生在以下两种情况:程序的不同阶段间的数组重分和和循环划分后的数组重映射.许多数据并行编程语言，例如HPFIlViennaFortran121和p-HPF⑶等,都是通过在分布内存

3、下提供数组分布指导支持全局命名空间(globalnamespace).在这些语言中，程序员通过指导语句来指定数组在处理器间的分布模式.根据“拥有者计算”原则,编译器利用这些分布信息和循环中数组赋值语句來产生通信集.许多时候山于通信代价过高而导致并行效率很低，其至出现负加速比•针对这些典型问题，越来越多的研究者将通信优化的研究亜点放在如何最小化通信集牛成的时间⑷⑸、重叠通信与计算⑹以及亜分布数组上，不过他们却忽略了由于结点间消息冲突和一次通信中消息长度不一样所帶来的大最通信开销。另外，通过对消息进行调度减轻通信代价的研究有:Park等人⑺在考虑数据传

4、输、通信调度和索引计算的基础上提出了一个针对某些特例减少通信总时间的算法，不过它只是针对某些特例.Dcsprcz等人園给出了一个最小化消息冲突的算法，但该算法仍然不能避免通信冲突XYuan等人⑼何提供了一个基于MPI_Alltoallv实现的通信调度算法，但是其运行时的开销很大.M.Guo等人在以前工作的基础上I⑴给出了关于一维数组的重分布通信调度策略，其中H标数组在发送处理器组Q和接收处理器组P上具有不同分布形式旧，然而该研究只是着眼于并行程序不同阶段之间数组的重分布问题,并不能解决循环划分之后的数组重映射问题.与以往的研究相比，本文的主要贡献有

5、以下三点：(1)本文提出的策略首次解决了循环划分后在数组亜映射时出现的消息冲突问题.其避免了数组亜映射时结点间的消息冲突,同时也最小化了每步通信所花费的时间.(1)本文提出的策略更具有普遍性,也适用于不同阶段的数组重分布.(2)本文提出的策略引入关于通信表的周期性理论，大輛度减低通信调度牛成的时间.因此有利于该通信调度算法在编译阶段实现，不会带来额外的运行时开销.综上所述，本文给出了一种不仅具有普遍适用性，而且空间和时间花费很小，可以用于编译时完成的通信调度策略CSS(CommunicationSchedulingStrategy).为了更好地描述

6、问题,文中使用通信表COM(COMmunication)table和调度表CS(CommunicationScheduling)table(表的定义在第二部分给出)来分別描述处理器间的消息交互模式和消息的调度情况.首先引入通信表的周期性理论来缩短通信调度表的生成时间，然后给出■通信表内元素递推关系相关的定理和推论的证明•在以上定理和推论的棊础上,构造出有效的调度算法使调度表的每一列变成接收处理器序号的枚举，并尽量//、、//、、1.realA(0:(na-1)),B(0:(nb-1))把长度相近的消息放到同一个通信步内.css12.!process

7、orP(0:(np-l))策略既避免了处理器间的通信冲突，同时也z/、、3.!processorQ(0:(nq-1))最小化了调度表的牛成时间和实际通信的总z/、、4.!distributeA(cyclic(x))ontoP时间.为了便于算法描述，本文主要是以一维,//、、5.!distributeB(cyclic(y))ontoQ数组为例进行说明，该策略很容易扩展到多、、6.FORALL(is=0:(ns-1))维数组的情况.A(al*is+bl)=F(B(a2*is+b2))本文余下部分的组织如下:第二部分介绍所要解决的问题并举例进行说明;第三

8、部分是本文的核心内容，论述了处理器间的通信调度策略;第四部分给出在分布式内存机群上的测试结果并进行分析;最后是结论及进一步