K元N立方体网络均匀跨步通信模式的性能分析与优化

卢宏生等

摘要：K元N立方体网络是高性能计算机常用的一种网络结构.均匀跨步通信是高性能计算最重要的通信模式之一.针对K元N立方体网络均匀跨步通信模式，推导出其性能下限的理论公式，采用自行开发的网络模拟器模拟了多种结构、多种跨步值和多种消息长度的传输性能.最后针对节点重映射和消息分割两种优化措施进行了模拟和分析.模拟结果显示，4元N立方体网络具有良好的Alltoall性能，接近Alltoall性能最好的K元N树网络.

关键词：K元N立方体；Alltoall通信；均匀跨步通信；节点重映射；消息分割

中图分类号：TP301 文献标识码：A

对于很多重要应用而言，比如快速傅里叶变换等[1]，Alltoall通信都是非常重要的通信模式，是影响性能的关键所在[2].许多网络设计的目标就是获得良好的Alltoall性能.标准的Alltoall通信可参考图1所示的MPI_AlltoAll的定义[3]，每个进程都向其他所有进程发送数据，这意味着每个进程也同时接收来自其他进程的数据.由于标准的Alltoall通信可能存在大量竞争，包括网络的竞争，目标的竞争，从而导致性能大幅下降.

假设共计N个进程{P0， P1， …， PN-1}.一种常用的优化手段是将Alltoall通信过程分解成N-1个阶段.阶段i，i=[1， …， N-1]，每个进程Pk只向进程P（k+i）%N发送数据，这意味着每个进程Pk同时在接收P（k+N-i）%N发送的数据.这种方式有序化了Alltoall通信，降低了可能的阻塞，提升了整体Alltoall性能.上述每个阶段的通信都属于均匀跨步模式.所谓均匀跨步模式就是参与通信的所有进程对，其目标进程号和源发送进程号差值都相同.这种均匀跨步模式是许多重要应用中的通信基础模式，是超级计算机网络结构设计中的重要参考指标.图2是一个4进程Alltoall通信的阶段划分示意图.

在高性能计算中，每种通信模式的性能都和网络拓扑结构有着重要的关系.其中K元N立方体结构一直是网络结构研究的热点，是高性能计算机常用的一种拓扑结构.典型的系统包括IBM Blue Gene，Cray Gemini等.本文重点研究K元N立方体网络均匀跨步模式的性能及其优化.

1均匀跨步通信性能分析

Alltoall通信由于涉及很多因素，其性能的理论分析是十分复杂的.IBM的Kumar等人基于Bluegene/L系统3D环网结构提出了一个针对多维环网的Alltoall通信模型性能公式[4].假设三维环网中每一维的处理器数量分别为Px，Py，Pz，系统中处理器的总数量为P=Px*Py*Pz，最长维处理器数量M=max（Px，Py，Pz），每个处理器发送m字节数据到其他处理器，单个字节在网络中的传输时间为β，则在Alltoall通信模式下，网络所传输的数据总量为P*P*m.每个包在最长维的平均步长为M/4，该维的链路总数为2P，因此完成Alltoall通信的时间T=P2*m*M/4*b/（2P）=P*（M/8）*m*β.该公式反映了Alltoall模式下3D环网的最好性能.如引言中所述，Alltoall通信可分解成若干步均匀跨步通信，因此分析均匀跨步通信模式的性能具有重要意义.

Kumar以IBM BlueGene系统为参考，给出了3D环网Alltoall性能的上限评估公式.但事实上，在设计高性能计算机网络系统时，我们更关注其Alltoall性能的下限.因为应用与算法是多种多样的，知道了网络可能的性能下限，才能针对重大应用选择适应性更好的网络架构.下面从理论上初步分析均匀跨步的性能下限.K元N立方体网络，共有KN个节点，网络直径为N*K/2，链路总数为N*2*KN条.对于均匀跨步消息，网络链路冲突最大的情况是任一对通信节点间的步长均等于网络直径.所以理想情况下，需要的链路数为N*（K/2）*KN.所以我们得到系统链路吞吐率的下限公式为：

这是一个十分有趣的公式.它显示，对于K元N立方体而言，均匀跨步通信的吞吐率下限与维数无关，仅和每一维的长度相关.当K≤8时，均匀跨步通信吞吐率超过50%；特别当长度K=4时，即4元N立方体在进行均匀跨步模式通信时，吞吐率可以达到100%.了解一种网络结构Alltoall性能的下限对于网络结构的设计、各种网络参数的选取具有重要的参考意义.由上述公式可见，在Alltoall通信性能方面，4元N立方体性能接近K元N树性能.当然上述情况的分析都是基于理想情况.后面将用模拟器检查我们的分析是否准确.

2均匀跨步通信性能模拟

2.1网络模拟器

为了更好地模拟网络通信的性能，我们开发了一款采用C++编写的节拍级网络模拟器netsim.该模拟器支持K元N立方体、K元N树等多种网络结构.我们重点模拟了K元2立方体网络，即2D环网.该2D环网基于5端口路由器实现.路由器采用从输入缓冲经交叉开关到输出缓冲的传统的路由器结构.之所以没有采用目前比较主流的高阶路由器结构，主要是考虑构建2D环网所需路由器的端口比较少，同时这种结构的差异对我们研究的影响很小.我们研究的重点在于消息长度、通信模式和网络拓扑间的关系上.

2.2性能模拟

我们分别对4×4 2D环网和8×8 2D环网进行了模拟.针对4×4 2D环网的16个节点，我们分别模拟长度为512 B，1 kB，2 kB，4 kB，8 kB，16 kB，32 kB，64 kB，128 kB，256 kB，512 kB，1 MB的Alltoall消息.每个Alltoall消息被划分为15个阶段完成.

图5是 8×8 2D环网执行不同长度的Alltoall通信在63个阶段的吞吐率.其中系列i，i=[1..12]，分别对应长度为512*2i-1 B的消息.每个阶段p，p=[1..63]，坐标（X，Y）的节点向坐标（（X+dx）%8，（Y+dy）%8）的节点发送消息，dx=p%8， dy=p/8.结果显示，各个阶段的吞吐率有很大的差别.部分阶段，无论消息长度，吞吐率均达到100%，这主要得益于上述阶段不存在链路冲突；还有部分阶段吞吐率很低，最低的仅为14%，远低于我们预测的8×8 环网50%的吞吐率下限.这主要是因为我们的预测中仅从链路数量需求方面考虑了冲突的情况，但实际上作为环网，采用确定性维序路由算法后，链路之间存在依赖关系.这种依赖关系使得链路冲突率进一步加大.对于K元N立方体网络，K越大，影响越大.第2节中预测的最低值更接近最低值的上限或Alltoall通信阶段的平均值.

在很多应用中，Alltoall性能都是性能的关键.优化Alltoall通信性能也一直是研究的热点.将Alltoall通信分解为N-1个均匀跨步过程是一种比较常见的优化方法.在前面的分析和模拟中，我们发现均匀跨步的性能和网络的结构有很大的依赖关系，而应用程序看到的跨步通常是逻辑上的概念.比如进程号，它并不等同代表网络中物理位置的物理号.真正影响通信性能的是物理号.是否可以通过变换逻辑和物理的映射关系改变均匀跨步的性能，从而提升Alltoall通信性能呢？

为此，我们编写了一个模拟程序，选择8X8 2D环网进行模拟，用A，B，C，D 4个矩阵分别记录X+，Y+，X-，Y- 4个方向的链路，一个完整的Alltoall消息被分解为63个阶段，分别记录每个阶段所有链路的使用情况.

图7（a）代表了一个逻辑节点号到物理节点号的映射关系.图7（b）中的4个图分别表示在阶段9即p[i]进程向p[（i+9）%64]进程（i=[0..63]）通信时X+，Y+，X-，Y-4个方向共计256条链路的使用情况.图7（c）中的4个图则分别表示在阶段31即p[i]进程向p[（i+31）%64]进程（i=[0..63]）通信时X+，Y+，X-，Y- 4个方向共计256条链路的使用情况.很容易发现，2个阶段的链路情况并不相同，这和我们前面的分析是吻合的.一个有趣的现象是：完成完整的Alltoall通信后，所有X+，Y+，X-，Y- 4个方向共计256条链路，每条链路均被使用了64次.多次更换映射关系，现象依旧.实际上，由于我们面对K*K 2D环网是一个对称网络，无论逻辑节点号和物理节点号如何映射，对于完整的Alltoall通信而言，都是每个节点都和其他所有节点完成一次通信.而我们采用的是均衡的先X后Y确定性维序路由算法，因此无论如何映射，每条链路使用的次数是固定的，只在每个阶段有一定的差异.由于网络的对称性，每条链路最终使用的次数都是相同的.但这并不意味着重新映射逻辑节点号与物理节点号无助于提升Alltoall通信性能.事实上，由于映射关系的不同，每种映射下每个阶段的链路冲突率是不同的，最终所有阶段叠加的结果就是Alltoall通信性能并不相同.

如图8所示，（a），（b）分别对应4×4 2D环结构下两种逻辑处理器号和物理处理器号的映射关系.16个处理器的2D环网的Alltoall通信划分成15个均匀跨步通信阶段.（a.1），（a.2），（a.3），（a.4）表示映射关系1时阶段1的X+，Y+，X-，Y- 4个方向链路的使用情况.（b.1），（b.2），（b.3），（b.4） 表示映射关系2时阶段1的X+，Y+，X-，Y-4个方向链路的使用情况.定义一条链路的权值W为同一个阶段传输的消息数量.可以发现，映射关系1在阶段1时最大链路权值为1，即意味着在此阶段通信的16个消息没有链路冲突，消息以满带宽传输.而映射关系2在阶段1时最大链路权值为2，即意味这在此阶段通信16个消息中有2个消息共享（1，1）到（2，1）号链路.因此消息性能将为峰值性能的一半.阶段i的最大权值记为Wi.W=∑Wi/15（i∈[0..15]）是Alltoall通信各阶段平均最大链路权值.结果显示，在映射关系1下，W1=1.在映射关系2下，W2=1.87.即4×4 2D 环网在映射关系1下Alltoall消息带宽可以达到链路峰值，而在映射关系2下，Alltoall消息带宽仅为链路峰值带宽的1/W2=53%.

针对Alltoall通信，也有一些研究人员尝试将长消息分割成小消息，通过对小消息的调度降低网络的冲突，从而提升性能[5].比如在InfiniBand 16元2树网络中通过将128 kB长消息拆分成16 kB小消息，Alltoall性能提升10%.但事实上，InfiniBand网络采用的是确定性路由，排除消息非常短的情况，无论消息长度多长，链路的使用情况是相同的.之所以通过将长消息拆分成短消息性能有所提升，主要是由InfiniBand HCA的消息发送机制造成的.HCA在发送消息时以时间片为单位，在一个时间片内连续调度同一个QP上的数据包，导致消息发射的频率并不恒定，从而导致网络拥塞.同时由于在Alltoall通信的各阶段间没有高效的同步机制，也容易造成目标节点的冲突，从而增加性能随消息长度浮动的变数.

总体来说，在理想情况下，这里的理想条件包括合理的消息发送机制、合理的NI，ROUTER均衡的缓冲配置、均衡的路由算法、足量的VC数量，决定Alltoall通信性能的关键首先是网络固有的属性即网络拓扑.良好的映射关系将有助于减少网络链路的冲突率，从而提升Alltoall通信的性能.因此在作业分配时，合理地配置节点资源或者在算法设计时紧耦合网络拓扑状况将大大提升Alltoall通信的性能.由于K元N树网络能够保证所有源和目标间的一一映射均不存在链路冲突[6]，因此其任意均匀跨步模式的通信性能均可达到链路有效性能的100%，即等同于点到点通信性能.因此树型网络作为支持Alltoall通信的理想拓扑结构，是K元N立方体网络在Alltoall通信性能方面优化的重要标尺.

4结束语

Alltoall性能的理论分析十分复杂.将Alltoall通信拆分成多个阶段的均匀跨步通信是一种提升性能的简单高效的方法.这种方法避免了目标的冲突.本文给出了一种K元N立方体网络中均匀跨步通信模式最低性能的估计值，这对高性能计算机网络结构的设计具有一定的参考价值.本文的公式显示其性能和一维的长度成反比.特别是当K=4时，4元N立方体网络有比较好的Alltoall性能.但最好的性能仍然属于完全无冲突的K元N树网络.在Alltoall通信方面，网络拓扑结构仍然是影响性能的第一要素.经过模拟与分析，也指出通过节点重映射手段可提升K元N立方体网络的Alltoall通信性能，而消息分割只在某些特定的系统中有效，并不具备普适性.

参考文献

[1]YOGISH Sabharwal， SAURABH K Garg， RAHUL Garg， et al. Optimization of fast fourier transforms on the blue Gene/L supercomputer[C] // Proc of 15th International Conference on High Performance Computing.Bangalore， India， 2008： 309-322.

[2]Alltoallcommunication[EB/OL]. [2014-4-9].http：//en.wikepedia.org/wiki/Alltoall_communication.

[3]MPI_Alltoall[EB/OL]. [2014-4-9].http：//www.mpich.org/static/docs/v3.1/www3/MPI_Alltoall.html.

[4]SAMEER Kumar， YOGISH Sabharwal， RAHUL Garg， et al. Optimization of Alltoall communication on the blue Gene/L supercomputer[C] // Proc of 37th International Conference on Parallel Processing， Portland， Oregon， 2008： 320-329.

[5]陈淑平， 卢德平， 陈忠平. InfiniBand网络中Alltoall通信性能优化[J]. 高性能计算发展与应用， 2012（2）： 69-74.

CHEN Shuping， LU Deping， CHEN Zhongping. Optimization of Alltoall performance in InfiniBand network[J]. Development and Application of High Performance Computing， 2012（2）：69-74.（In Chinese）

[6]SABINE R hring， MAXIMILIAN Ibel， SAJAL K Das， et al. On generalized fat trees[C] // Proc of the 9th International Parallel Processing Symposium.Santa Barbara， California， 1995： 37-44.