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

一种数据并行中的群通信优化策略 王珏, 胡长军, 张纪林，李建江 （北京科技大学信息工程学院 北京 100083） 摘 要: 群通信是影响大规模数据并行系统效率的关键因素,其主要发生在程序不同阶段间的数组重分布与循环划分后的数组重映射这两种情况.在一次通信中显著影响群通信效率常被忽视的因素是消息冲突和消息长度的不一致.因为它们会导致进程间大量的空闲等待时间.然而以前的研究要么不能完全避免消息冲突,要么针对某些特殊情况.对此,提出了在数组分布为Block_Cyclic（k）情况下的一种更具有普遍适用性的通信调度策略CSS. 通过证明表明该策略能使一个通信步内的消息互不冲突且消息长度尽量相等.从而最小化通信调度生成时间和实际通信时间.最后的测试结果也表明,与传统的通信优化算法和MPI_Alltoallv实现相比,CSS策略使得通信效率得以明显提高. 关键词: 并行编译;数据并行;组通信;数组重分布;分布内存 引言 当前大多数并行应用系统都是采用基于分布式内存的数据并行范例.群通信在数据并行程序中普遍存在并且是影响其执行效率的关键因素.群通信主要发生在以下两种情况:程序的不同阶段间的数组重分布和循环划分后的数组重映射.许多数据并行编程语言,例如HPF[1]、Vienna Fortran[2]和p-HPF[3]等,都是通过在分布内存下提供数组分布指导支持全局命名空间（global name space）.在这些语言中,程序员通过指导语句来指定数组在处理器间的分布模式.根据“拥有者计算”原则,编译器利用这些分布信息和循环中数组赋值语句来产生通信集.许多时候由于通信代价过高而导致并行效率很低,甚至出现负加速比.针对这些典型问题,越来越多的研究者将通信优化的研究重点放在如何最小化通信集生成的时间[4][5]、重叠通信与计算[6]以及重分布数组上,不过他们却忽略了由于结点间消息冲突和一次通信中消息长度不一样所带来的大量通信开销。另外,通过对消息进行调度减轻通信代价的研究有:Park等人[7]在考虑数据传输、通信调度和索引计算的基础上提出了一个针对某些特例减少通信总时间的算法,不过它只是针对某些特例.Desprez等人[8]给出了一个最小化消息冲突的算法,但该算法仍然不能避免通信冲突.X. Yuan等人[9][10]提供了一个基于MPI_Alltoallv实现的通信调度算法, 但是其运行时的开销很大. M. Guo等人在以前工作的基础上[11]给出了关于一维数组的重分布通信调度策略,其中目标数组在发送处理器组Q和接收处理器组P上具有不同分布形式[12],然而该研究只是着眼于并行程序不同阶段之间数组的重分布问题,并不能解决循环划分之后的数组重映射问题.与以往的研究相比,本文的主要贡献有以下三点: 本文提出的策略首次解决了循环划分后在数组重映射时出现的消息冲突问题.其避免了数组重映射时结点间的消息冲突,同时也最小化了每步通信所花费的时间. 本文提出的策略更具有普遍性,也适用于不同阶段的数组重分布. 本文提出的策略引入关于通信表的周期性理论,大幅度减低通信调度生成的时间.因此有利于该通信调度算法在编译阶段实现,不会带来额外的运行时开销. real A（0:（n-1））,B（0:（n-1）） ！processor P（0:（n-1）） ！processor Q（0:（n-1）） ！distribute A（cyclic（x））onto P ！distribute B（cyclic（y））onto Q FORALL（i = 0:（n-1）） A（1*i+b1）= F（B（2*i+b2）） 综上所述,本文给出了一种不仅具有普遍适用性,而且空间和时间花费很小,可以用于编译时完成的通信调度策略CSS（Communication Scheduling Strategy）. 为了更好地描述问题,文中使用通信表COM（COMmunication）table和调度表CS（Communication Scheduling）table(表的定义在第二部分给出)来分别描述处理器间的消息交互模式和消息的调度情况.首先引入通信表的周期性理论来缩短通信调度表的生成时间,然后给出与通信表内元素递推关系相关的定理和推论的证明.在以上定理和推论的基础上,构造出有效的调度算法使调度表的每一列变成接收处理器序号的枚举,并尽量把长度相近的消息放到同一个通信步内.CSS策略既避免了处理器间的通信冲突,同时也最小化了调度表的生成时间和实际通信的总时间.为了便于算法描述,本文主要是以一维数组为例进行说明,该策略很容易扩展到多维数组的情况. 本文余下部分的组织如下:第二部分介绍所要解决的问题并举例进行说明;第三部分是本文的核心内容,论述了处理器间的通信调度策略;第四