基于天河互连MPI聚合通信归约操作卸载优化 *

王 浩，张 伟，谢 旻，董 勇

(国防科技大学计算机学院，湖南 长沙 410073)

1 引言

在高性能计算领域，聚合通信在并行科学计算应用中扮演着非常重要的角色，许多并行应用程序使用聚合通信来满足一系列的通信请求，例如迭代数值求解器中剩余向量的大小、执行分布式数据归约、傅里叶变换。在许多基于MPI(Message Passing Interface)消息传递编程模型的并行科学计算应用中聚合通信占据大部分的通信时间消耗，对应用的运行性能和可扩展性有重要影响，并且影响程度随着应用规模的增加而增大[1]。MPI聚合通信接口中的归约操作MPI_Reduce和MPI_Allreduce被广泛应用于科学计算应用中，迭代求解器(如共轭梯度等)是许多科学模拟应用的重要组成部分，在每一次迭代过程中均使用多次归约来计算点积或范数[2]。Reduce操作是将所有进程提供的值进行归约计算后将计算结果发送到一个目的进程，Allreduce操作则是将归约计算结果发回所有进程。有研究表明，在一些MPI并行应用中，有超过40%的时间消耗在归约操作上[3]。一些科学应用程序和基准测试例如大规模原子分子并行模拟器[4]、Fluent[5]、OpenFOAM[6]在MPI_Allreduce操作上消耗的时间占比总的通信时间超过50%[7]。在当前软件层聚合通信实现中，Reduce操作的算法使用基于树形结构的归约算法实现，Allreduce操作的算法则是通过基于树形结构的归约/广播算法，或者是递归倍增算法实现[8]。Reduce和Allreduce操作的算法通常基于点对点通信操作实现，使用网络接口来执行结点间的消息通信，以及结点上的CPU来进行归约计算，可能受到操作系统噪声的影响[9,10]；而且当系统规模增大时，通信的计算步骤、计算量、进程距离将会相应增大，消息传输延迟带来很大的时间开销，且随着系统规模增加，这种时间开销增加是迅速的，使得软件实现的聚合通信可扩展性较差。

天河互连网络是国防科技大学自主研制的高性能计算机互连通信网络，由网络接口和互连交换2种专用芯片构成。网络接口在结点之间提供数据通信服务，互连交换芯片用于构造多种互连拓扑的交换网络架构。网络接口芯片支持PCIe 3.0x16接口，支持用户级通信来减少软件层开销，提供无连接模式的RDMA和短报文传输操作，并通过非阻塞通信模式来实现计算通信重叠执行[11 - 13]。互连交换芯片采用高阶路由结构降低互连网络跳步数，从而提高互连拓扑网络的带宽、可靠性和灵活性。面向聚合通信操作的性能优化和可扩展性问题，天河互连网络接口中设计了一种基于触发的通信卸载机制，其核心思想是将一些聚合通信操作卸载到互连网络中自主触发执行，减少主机处理器对聚合通信中数据通信过程的介入，实现计算与通信重叠执行，优化聚合通信的延迟和带宽。并且互连网络接口中还实现了计算逻辑部件，可以支持归约操作中的各种计算操作，从而消除聚合通信过程中将数据传输到主机处理器进行运算的过程，优化聚合通信的延迟。

目前已有一些针对聚合通信操作优化的研究工作，例如IBM的BG/L[14]集成有专门用来支持聚合通信操作的专用网络硬件，其功能专有，硬件复杂度高。Myrinet[15]网络接口包含嵌入处理器，支持特定聚合通信操作的卸载，但更新集合操作时需要更改网络接口上运行的控制程序。Mellanox开发的SHArP协议[16]在物理拓扑的基础上建立逻辑聚合通信树形结构，其设计的网络接口芯片与互连交换芯片硬件都具备数据聚合处理能力，共同构成逻辑树中的聚合结点，消息通信效率高，延迟低，但网络接口芯片与互连交换芯片硬件复杂度高，且要求构建的逻辑通信树与物理拓扑基本对应；类似的基于触发的通信卸载机制有可编程的网络接口API——Portals 4.0[17]，在网络接口加入Portals单元和DMA引擎来卸载聚合通信，但其加入的部件较多，增加了网络接口的硬件复杂性，且网络接口控制这些部件运行的程序存在额外开销；Fujistu设计的片上系统互连结构Tofu-2[18]，处理器芯片上集成了Tofu网络接口和Tofu同步接口，结点间采用会话模式的控制报文触发进行聚合通信操作的卸载，与天河互连网络通信卸载实现机制较为相似。不同的是天河互连网络仅在独立的网络接口芯片加入简单的硬件触发逻辑就能实现卸载功能，构造的通信卸载树形结构与物理拓扑独立，可灵活实现于多种拓扑结构中。

本文利用天河互连网络的触发操作特性，设计实现了归约操作的聚合通信卸载算法，并通过实验评估了基于不同树形结构的Allreduce和Reduce通信卸载算法的性能。

2 天河互连网络通信卸载技术

天河互连网络在网络接口中实现了虚拟端口(Virtual Port)的机制，这种机制支持硬件资源的虚拟化来灵活实现用户级通信，它为每个进程提供了独占使用通信硬件的编程视角[13]。当多个进程并发运行时，来自不同进程的通信操作相互独立，彼此不会产生干扰。每个虚拟端口是一组内存映射寄存器和一组相关的内存数据结构的组合，不同虚拟端口中的寄存器地址范围的间隔至少与物理页的长度相同。所有这些地址范围都可以映射到用户空间，这样就可以在用户空间中进行受保护的并发访问，过程如图1所示。

Figure 1 Process diagram of virtual ports realize user level communication图1 虚拟端口实现用户通信过程

内存数据结构包括：(1)通信请求描述符队列DQ(Descriptor Queue)，是物理地址连续的内存缓冲区。用户可以在DQ中构建一个通信请求，互连网络接口通过DQ来接受用户提交的通信操作请求，然后通知网络接口用DMA(Direct Memory Access)方式读取描述符到网络接口中并执行通信操作。用户还可以通过PIO(Programming Input/Output model)方式直接提交通信请求到网络接口的内部描述符队列中，但网络接口中的DQ的容量是有限的。(2)MP报文接收队列MPQ(Mini-Packet Queue)，一种用于双向通信的短报文机制。Mini-Packet以下简称MP报文，每个MP报文是128 B，其中前8 B是报文头，其余则是有效负载。网络接口向MPQ中顺序存储其它虚拟端口发送到本端口的MP报文，但MPQ的容量是有限的，如果MPQ满了，新到达的MP报文将被丢弃，因此必须有一个软件层协议来防止MPQ溢出。通常，MPQ也是在物理地址连续的内存中分配的，但也可以使用虚拟地址方式，利用网络接口中的地址转换表映射到用户空间。(3)事件状态队列EQ(Event Queue)，互连网络接口在其中记录用户提交的RDMA通信请求的执行状态，事件内容可以由用户控制。用户在初始化时可以对这些资源大小进行配置，对这些资源的访问操作是直接在用户地址空间上进行的。

为了加速聚合通信的执行，互连网络接口芯片基于现有的通信机制，设计实现了一种软硬件结合的触发机制，来进行聚合通信的通信卸载处理。在网络接口中加入一种特殊的硬件触发逻辑部件，该部件在满足触发条件时自动执行数据的复制、替换、接收或发送，不需要处理器的参与。用户设置一组通信请求描述符序列，在描述符序列头部定义对通信请求的控制操作，比如触发控制条件值、报文数据复制或替换的选项等。描述符序列被提交到虚拟端口中后，并不会立即执行，需要等待触发条件。在进行聚合通信操作时，当从网络接口接收到的数据报文设定了描述符序列的触发条件时，触发逻辑部件将会自动执行描述符序列，并根据描述符序列的设置选项完成复制、替换或转发等操作。这种触发机制由控制报文CP(Control Packet)处理，互连端口中有控制报文的计数器(CP Counter)，当网络接口接收到新的CP时，CP Counter计数加一，当达到计数阈值时，就立即触发描述符序列的执行，结点的触发原理如图2所示。

Figure 2 Schematic diagram of node trigger principle图2 结点触发原理示意图

该机制有多种优势：逻辑设计简单；可以构造多种树形拓扑结构的通信卸载算法，算法构造的拓扑与物理拓扑不一定完全对应，灵活性好；处理器不参与数据传输，受到系统噪声影响较小；数据传输由硬件自动完成，在结点规模增加时延迟增幅较小，可扩展性好；消息在网络接口中自行复制，减少跨PCIe的数据传输。为了支持归约操作，网络接口还加入了计算逻辑单元ALU，硬件支持最多同时对7个归约数据进行归约计算，可供支持的归约操作有浮点/整型求和、最大值、最小值，逻辑/位与、或、异或操作，通过计算卸载操作来进一步提高归约操作的通信性能。

3 基于触发机制的Reduce/Allreduce通信卸载算法

3.1 K-nomial与K-ary树形结构

Figure 3 2-nomial tree and 4-nomial tree for 16 nodes图3 16结点的2-nomial树和4-nomial树

Figure 4 2-ary tree and 4-ary tree for 16 nodes图4 16结点的2-ary树和4-ary树

以上构造树中的结点分为根结点(Root Node)、叶结点(Leaf Node)和中间结点(Inner Node) 3类，根结点最上层的1个结点；叶结点每条分支中最下层的结点；其余结点是中间结点。树中的边表示为父子关系，隶属于同一父结点的同一层子结点互为兄弟关系。结点间的通信只在父子结点之间进行，但每个结点上的通信操作则根据结点类型和子结点个数，而有所不同。

3.2 基于触发机制的Allreduce通信卸载算法

基于树形结构通信，不同类型的结点执行不同的通信原语操作。Allreduce的通信卸载算法如算法1所示。

算法1基于触发机制的Allreduce通信卸载算法

(1)根结点：①准备1个待触发的MP归约数据报文，目的地址为本结点，触发计数器值为子结点数目，触发条件为接收到所有子结点带有触发标志的归约数据报文；并将归约计算结果替换为报文数据发送到本结点的报文接收队列。

②准备1个待触发的MP归约结果数据报文序列，目的地址为所有子结点，触发计数器值为1，触发条件为接收到发送给本结点的归约计算结果报文；等待接收归约计算结果，并将接收到的数据替换为报文序列中的数据，发送到所有子结点的报文接收队列。

(2)中间结点：①准备1个待触发的MP归约数据报文，目的地址为父结点，触发计数器值为子结点数目，触发条件为接收到所有子结点带有触发标志的归约数据报文；并将归约计算结果替换为报文数据发送给父结点。

②准备1个待触发的MP归约结果数据报文序列，目的地址为所有子结点，触发计数器值为1，触发条件为接收到来自父结点的归约计算结果报文；等待接收归约计算结果，并将接收到的数据替换为报文序列中的数据，发送到所有子结点的报文接收队列。

(3)叶结点：准备1个MP归约数据报文，目的地址为父结点，立即发送给父结点；等待接收归约计算结果。

根结点和中间结点都准备2个描述符序列，一个是参与归约计算的数据报文，一个是将归约计算结果发给通信域中所有子节点的广播数据报文，叶结点只准备参与归约计算的数据报文。所有结点准备并提交报文到描述符队列后，先由叶结点启动通信序列发送报文并向上触发父结点的通信序列。根结点接收到所有子结点的报文后进行归约计算，并触发计算结果向下广播发送到所有子结点，直到所有的结点都接收到归约计算结果。算法执行的具体过程如下所示：根结点将待归约的数据打包为MP归约报文，等待接收到所有子结点的MP归约报文触发执行归约计算操作；并将归约计算结果广播报文发送给所有子结点，此报文的数据由自身的归约计算结果替换，由自身MP归约报文执行后触发执行。中间结点承担“向上归约”和“向下广播”的任务，准备2类MP交换报文，第1类是打包本结点待归约的数据为MP归约报文，等待接收子结点的归约数据报文，当接收到来自所有子结点的归约数据时，触发执行归约计算操作，并将归约计算结果向上发送给父结点参与下一轮归约计算；第2类的MP广播数据报文是用等待接收来自父结点的计算结果报文替换报文数据，并广播报文给所有子结点，由接收到父结点的计算结果报文触发执行。叶结点将本结点待归约的数据打包为MP归约报文，准备好后立即发送给父结点参与归约计算。所有结点准备好参与通信的报文，按照预定设置自动执行，结点各自提交所有报文的发送操作后，等待接收归约的计算结果，接收完毕后解析归约结果报文，将归约计算结果存入缓冲区。

3.3 基于触发机制的Reduce通信卸载算法

树形结构的Reduce通信卸载算法实现过程相比Allreduce的实现，减少了向下广播归约计算结果的过程，最终的归约计算结果只存在于根结点。基于触发机制的Reduce通信卸载算法如算法2所示。

算法2基于触发机制的Reduce通信卸载算法

(1)根结点：①准备1个待触发的MP归约数据报文，目的地址为本结点，触发计数器值为子结点数目，触发条件为接收到所有子结点带有触发标志的归约数据报文；并将归约计算结果替换为报文数据发送到本结点的报文接收队列。

②准备1个待触发的MP归约结果数据报文，目的地址为本结点，触发计数器值为1，触发条件为接收到发给本结点带触发标志的归约计算结果报文；等待接收归约计算结果，并将接收到的数据替换为归约结果报文中的数据，发送到本结点的报文接收队列。

(2)中间结点：准备1个待触发的MP归约数据报文，目的地址为父结点，触发计数器值为子结点数目，触发条件为接收所有子结点带有触发标志的归约数据报文，并将归约计算结果替换为报文数据发送给父结点。

(3)叶结点：准备1个MP归约数据报文，目的地址为父结点，立即发送给父结点。

根结点准备2个描述符，一个是参与归约计算的报文，一个是发送归约计算结果的报文，中间结点和叶结点只准备一个参与计算的报文。所有结点准备并提交报文到描述符队列后，先由叶结点执行发送报文并向上触发父结点的报文发送处理，待根结点接收到所有子结点的数据报文进行归约计算后，触发归约计算结果发送到本结点的报文接收队列。算法执行的具体过程如下：根结点准备好本结点参与归约计算的数据报文，等待接收所有子结点参与计算的归约MP报文，当接收到所有子结点的归约MP报文后触发归约操作，执行完毕后将触发归约计算结果发送到本结点的报文接收队列；中间结点准备本结点参与归约计算的MP数据报文，等待接收来自所有子结点的归约数据报文，接收完毕后触发归约计算执行，并将计算结果的数据报文向上发送给父结点；叶结点准备各自的归约数据MP报文发送给父结点，不需要触发立即执行。中间结点和叶结点提交完通信描述请求后即完成本结点任务，根结点提交完通信请求后，等待接收归约结果，待完成归约计算后，接收归约计算结果并解析报文数据。

4 性能测试与分析

4.1 实验测试环境

实验测试环境为搭载天河互连网络的超算系统，每个结点搭载1个FT-1500A/16核处理器，结点内存大小为32 GB，操作系统为Linux 4.19内核版本。

4.2 实验过程

将实现的Allreduce和Reduce通信卸载算法部署在天河互连网络中，参与归约的实验结点数量从8个增加到256个(2的幂次倍增)，每个结点上运行一个进程，每种问题规模下测试5 000次归约操作的迭代完成时间，然后计算平均时间。单个消息大小为48 B(归约计算同时支持6个浮点数);如果分叉度设置更大，虽通信步骤较少，但结点的通信负载较为不平衡，会影响算法性能，树形结构分叉度K设置为2,4,8。在同等结点规模下，对基于触发机制的Allreduce和Reduce通信卸载算法与MPICH-3.3.2版本中基于点对点实现的MPI_Allreduce和MPI_Reduce接口进行了对比测试，并对测试结果进行了详细分析。

4.3 实验结果与分析

4.3.1 Allreduce测试结果

Figure 5 Results comparison diagram of Allreduce offloading algorithm and MPICH implementation图5 Allreduce通信卸载算法与MPICH对比图

图5所示为采用不同树形结构的Allreduce通信卸载算法与MPICH系统中的MPI_Allreduce实现的对比测试结果，图中横轴为结点数量，纵轴为归约操作的延迟，其中mpich表示MPICH的MPI_Allreduce实现算法，K-nomial和K-ary表示基于不同分叉度的K-nomial树和K-ary树Allreduce通信卸载算法的性能数据。从测试结果可以看出，相比于MPICH的实现，基于触发操作实现的2种树形结构Allreduce通信卸载算法减少了归约操作的延迟，并且随着结点数增加，性能提升效果越明显。对于P(2的幂次)个结点的短消息通信，MPICH实现的通信步骤为log2P步，树形结构Allreduce通信卸载算法的通信步骤为2 logKP步。当分叉度K=4时，两者的通信步骤数相等。在结点数为64,128,256时，4-nomial树形结构的Allreduce通信卸载算法的延迟时间分别为24.94 μs,31.21 μs,38.42 μs，MPICH实现的延迟时间分别为34.22 μs, 45.23 μs, 58.73 μs。为进一步探究Allreduce通信卸载算法的性能优化参数，本文对比了2种树形结构和不同分叉度设置的测试结果。改变分叉度大小能改变通信步骤数，当K-nomial树的的分叉度改变为2和8，结点数为16,32,64时，2-nomial树的Allreduce通信卸载算法性能较另2种分叉度(K=4，8)更好。当结点数增加到128,256时，4-nomial树形结构的Allreduce通信卸载算法性能更优。当结点数量较小时，分叉度较大的树形结构 Allreduce通信卸载算法的实现性能优势不明显，这是因为结点数较少时通信时间较短，且通信卸载算法中父结点为多个子结点构造通信请求描述符序列时存在一定的开销。改变树形结构，将K-nomial树改为K-ary树，则K-ary树形结构的整体性能相对于于K-nomial树形结构有较好提升，原因在于触发机制下的通信卸载算法中各层结点间的通信负载不同。K-ary树形结构较对称，各层结点的通信负载差异较小，K-nomial树形结构各层结点间的通信负载差异较大。在文献[11]中提到的基于SHArP的Allreduce通信卸载算法测试结果，64 B在32,64,128结点下的延迟时间分别为2.89 μs, 2.92 μs, 3.04 μs，具有更好的延迟特性，但其测试用的主机CPU和互连平台有所不同，并且其通过专用的互连交换结点来实现数据的处理计算，硬件设计复杂度高，而天河互连仅对网络接口芯片进行简单的硬件扩展就能实现通信卸载的功能。

4.3.2 Reduce测试结果

图6中比较了不同结点规模下Reduce操作的性能，同样图中mpich表示MPICH系统中MPI_Reduce的实现算法，K-nomial和K-ary是基于不同分叉度的K-nomial树和K-ary树Reduce通信卸载算法的测试结果。对于短消息通信和P(2的幂次)个结点，MPICH的MPI_Reduce接口是基于2-nomial树形算法实现，通信步骤为log2P步，与同等通信步骤的2-nomial树形结构Reduce通信卸载算法相比较，可以看出基于触发操作的通信卸载算法明显减少了归约操作的延迟，主机处理器参与接收消息和执行归约计算操作的软件层开销被消除，使得整个归约过程中受到系统噪声干扰的影响很少。通过改变nomial树形结构的分叉度为4和8，来进一步探究树形结构Reduce通信卸载算法的性能优化参数，分叉度的大小对2种树形结构的Reduce通信卸载算法有着显著影响，且随着分叉度增大，通信卸载算法的优化效果更明显。这是因为在Reduce的通信卸载实现中，通过增加分叉度降低了树的层数，有效减少了数据的传输步骤。将K-nomial树形结构改变为K-ary树形结构，在各个结点规模下，2种树形结构对Reduce通信卸载实现的延迟差异不大，测试结果中当结点数为128时，8-nomial树的通信卸载实现延迟为5.61 μs，8-ary树的通信卸载实现延迟为4.79 μs，此时延迟差最大为0.82 μs，不超过1 μs。在Reduce通信卸载算法中各结点的单次归约执行过程是：叶结点仅将本结点参与归约计算的数据报文发送到网络接口即完成任务，中间结点等待接收完子结点的归约计算报文并将计算结果向上发送给父结点后完成任务，根节点需要接收所有子结点的归约数据并将计算结果发到本结点的报文接收队列里，发送完报文后一直等待接收归约计算结果并完成解析才完成任务。与Allreduce的通信卸载算法实现相比，Reduce的通信卸载算法实现不包含向下广播数据的隐式同步过程，通信任务更为简单，对树形结构不敏感，性能提升更明显。

Figure 6 Comparison diagram of Reduce communication offloaded algorithm and MPICH implementation图6 Reduce通信卸载算法与MPICH实现对比图

5 结束语

本文描述了面向聚合通信优化的基于触发操作的通信卸载机制，并基于这种通信卸载机制优化了MPI接口中的Allreduce和Reduce 2种归约操作，通过设计与实现在互连网络硬件中自动触发执行的树形结构归约算法，去优化归约操作的性能。实验测试评估了在天河互连网络上，针对不同结点规模和树形分叉度的归约操作性能。测试结果表明，利用通信卸载实现的归约操作，比基于点对点通信的软件层归约操作有更好的延迟性能和可扩展性，并且在树形结构通信卸载算法中选用合适的分叉度能实现最优的性能。下一步工作将利用触发操作，实现多种其它聚合通信操作卸载算法，并更好地集成到MPI实现系统中。