一种面向大规模并发的Gatherv优化方法*

孙浩男,王 飞,魏 迪,尹万旺,史俊达

(1.国家并行计算机工程技术研究中心，北京 100080；2.清华大学计算机科学与技术系，北京 100084)

1 引言

科学与工程计算领域中并行应用对计算能力的需求使得高性能计算系统的规模日益增大。通常情况下，并行应用将数据存储于本地内存进行计算，并通过消息传递接口按照一定的规则进行交互。通用消息传递接口MPI(Message Passing Interface)成为交互的标准。MPI定义了多种集合通信标准，如Gather、Scatter和Alltoall。这些标准接口支持指定进程范围内的规则数据通信，即参与集合通信的进程发送或接收的数据量相同，且数据存储的位置连续。为了不失灵活性，对于Gather、Scatter和Alltoall，MPI标准还支持了上述操作的不规则版本，即参与集合通信的进程发送或接收的数据量不相同，且最终数据存储的位置可以不连续。

MPI不规则集合通信是在大规模并行应用中常用的通信手段。Laguna等[1]对高性能计算领域数百个开源应用的调研表明，不规则集合通信的使用十分广泛，其中超过30%的应用使用了Gatherv功能。在编码解码、深度学习和矩阵运算等[2 - 5]方向的研究工作中，Allgatherv或Gatherv不规则集合通信具有广泛的应用需求。

2 背景

Gatherv作为Gather的不规则版本，扩展之处在于：根进程可从不同的进程接收不同长度的消息，同时将收到的消息数据存放到缓冲区的任意位置。然而，不规则集合通信在为并行应用设计带来了极大的灵活性，提升了MPI标准描述能力的同时，也为MPI集合通信在大规模环境下的实现带来了较大的挑战。

2.1 Linear结构

Linear结构是Gatherv最为直观、简单的实现方式，如图1所示，根节点以串行方式逐次与其他节点进行交互。MPICH[6]和OpenMPI[7]作为主流MPI实现方式，均采用传统Linear结构实现Gatherv。但是，当节点数为n时，其时间复杂度为O(n),由此带来了严重的可扩展性问题。随着进程规模的增大，根进程root需要和其他进程建立大量连接通路，需要同时处理来自其他n-1个节点的通信请求，这使得连接通路产生的内存开销随之陡增，且通信热点问题显著，难以支撑大规模并发应用的不规则通信需求。

Figure 1 Structure of Linear图1 Linear结构

2.2 Binomial-Tree结构

Binomial-Tree结构如图2所示，是一种二项式模型。当进程数为m时，根节点的通信连接数控制在lb (m)，其余进程逐级承担通信任务，通信过程在各层级间有序异步并发，可以有效缓解Linear结构中根进程连接通路内存开销大、通信热点显著的问题。目前，Binomial-Tree结构广泛应用于诸如Bcast、Gather、Scatter和Reduce等规则集合通信实现。

Figure 2 Structure of Binomial-Tree图2 Binomial-Tree结构

2.3 相关研究

在不规则集合通信的相关研究方面，Kang等[8]重点讨论了通信拓扑结构上的优化;Mallón等[9]通过在预处理阶段使用Gather替代Gatherv的方式优化图像合成应用的性能；Ascension等[10]基于Gatherv数据分块进行改进，以提高大型阵列计算应用的性能;Jocksch等[11]着重于不规则集合通信算法的选择与组合，此类研究有一定的参考意义，但对物理环境和应用类型有一定的局限性。在Gatherv算法模型的相关研究上，Pješivac- Grbovic[12]和Nuriyev等[13]均详细对比分析了Binomial-Tree结构相对于Linear结构在Gather上的应用优势；Traff[14,15]讨论了MPI不规则集合通信建模方法， 对基于Binomial-Tree结构建模的Scatterv和Gatherv进行了深入的理论研究，为Gatherv基于Binomial-Tree结构的高性能实现提供了理论支撑。

Binomial-Tree结构在降低通信通路内存开销和提升通信并发度方面，相对于Linear结构具有无可比拟的优势。但是，将其应用于不规则集合通信实现，将面临如下挑战：(1)接收数据量和偏移仅对根进程有效，其他进程无法掌握全局信息，导致根节点外的其他中间节点无法掌握本子树内的通信细节，因此无法实现通信缓冲区的精细化管理；(2)该模型结构涉及多个层次的消息通信，大规模并发条件下建立通信关系存在一定的计算开销；(3)由于消息目的地址可能不连续，根进程在处理消息偏移过程中可能存在频繁的拷贝操作。

针对上述挑战，本文对MPI不规则集合通信Gatherv进行了深入分析，从优化等级、临时缓冲区管理等方面，解决了不规则特性带来的优化难题，将Binomial-Tree结构应用于Gatherv实现；并进一步提出消息链调度机制，提升Gatherv在大规模环境下的性能。

3 基于Binomial-Tree的Gatherv实现

3.1 基于等级划分的优化策略

在MPI文本定义[16]中，Gatherv部分参数,如消息长度recvcounts、偏移displs属性,仅对根进程有效，使得其它进程在无法获取全局信息的情况下难以建立Binomial-Tree结构中的节点映射关系。为此，本文提出2种优化等级：符合文本定义的保守优化等级和充分挖掘性能潜力的激进优化等级。

(1)保守优化等级：由根进程通过广播操作将recvcounts、displs及算法决策发送给其他进程，使所有进程都可以掌握全局信息。该方式符合文本定义，作为保守优化等级。

(2)激进优化等级：保守优化等级严格遵守文本定义，但带来了一定的广播开销。在使用Gatherv的实际并行应用中，各进程常共享全局信息，因此本文在不规则属性对所有进程都有效、可见的条件下省略广播操作，作为Gatherv激进优化等级。

2种优化等级都能够令所有进程掌握全局信息，为构建Binomial-Tree结构提供先决条件。

3.2 模型结构

建立Gatherv的模型结构：首先根据式(1)，由各进程的进程号rank相对于根进程的进程号root计算相对进程号relative_rank:

relative_rank=(rank-root+nt)%n

(1)

其中,nt为通信域进程数。根据relative_rank建立进程到节点的映射关系，将各进程映射为叶节点、中间节点和根节点，构成Binomial-Tree。主要模型结构如图3所示，由各叶节点发送消息至其中间节点，根节点和各中间节点接收子树节点消息并存入各自临时缓冲区tmp_buf，经过多轮的消息收集和转发，最终将所有节点消息汇集至根节点。

该模型结构不仅能消除根进程通信热点问题，充分利用网络带宽，还能够节省大量因建立连接通路而占用的内存空间，对于进程数为nt的通信域，根节点所需建立的连接通路个数为lb(nt)，对比Linear结构的n-1个连接通路，内存开销大大降低。

Figure 3 Structure of Gatherv model图3 Gatherv模型结构

3.3 消息规则3.3.1 消息源计算

Gatherv支持进程消息长度各异的特性，为模型中临时缓冲区管理带来了难度：(1)为控制内存开销、按需分配缓冲区空间，需要设计算法令根节点和中间节点计算出其子树中所有节点进程号src(作为消息源)，从而根据进程号src计算得出所需空间大小；(2)多层次的通信过程也需要计算消息源以建立通信关系，冗杂的计算过程带了一定的成本。

为此，本文设计了消息源列表计算算法。如算法1所示，根节点和中间节点计算出当前迭代mask下的直接消息源src，再分别计算出以直接消息源src作为中间节点的子树中节点个数recvblks；根节点和中间节点分别根据式(2)和式(3)计算每轮通信中消息源节点个数recvblks;经消息轮数mask和每轮通信中消息源节点个数recvblks的迭代逐个计算出所有消息源并写入src_list列表，完成根节点和中间节点消息源列表src_list的建立。可以看到，src_list一方面用于计算临时缓冲区大小，为进程按需分配空间,以控制内存开销；另一方面用于计算消息收发过程中的消息长度，以“一次计算，多次使用”的方式控制计算成本。

(2)

(3)

算法1Calculatesrc_list

Input:relative_rank,nt。

Output:src_list。

1mask←1;

2num←0;

3whilemask

4ifmask&relative_rank=0then

5src←relative_rank|mask;

6ifrank=rootthen

7 Calculaterecvblksaccording to formula (2);

8else

9 Calculaterecvblksaccording to formula (3);

10end

11forx←0 torecvblksdo

12src_list[num]←(src+x+nt)%nt;

13num++;

14end

15else

16break;

17end

18mask≪1;

19end

Figure 4 Instant copy图4 即时拷贝

此外，该模型结构需要为根节点和中间节点分配临时缓冲区tmp_buf以暂存消息，为节省内存采取按需分配空间的方式。分配规则如下所示：(1)中间节点分配的临时缓冲区大小为所需接收的所有子节点的消息长度总和；(2)根节点分配的临时缓冲区大小为除根节点及其直接叶节点外的所有节点的消息长度总和。

3.3.2 消息收发规则

如图4所示，模型中消息收发规则如下所示：(1)叶节点：在第1轮通信中(step 1)直接将消息发给中间节点。(2)中间节点：将自身消息从本地拷贝至临时缓冲区tmp_buf，逐轮接收子节点消息至临时缓冲区tmp_buf，最终将tmp_buf发给中间节点。中间节点根据模型结构分布，有若干次接收操作和一次发送操作。(3)根节点：预先(step 0)将自身消息由sendbuf本地拷贝至recvbuf对应位置disp[root]；再将直接叶节点在第1轮通信中(step 1)直接接收至recvbuf对应的位置(参考disp属性)；来自中间节点的消息逐轮接收至临时缓冲区tmp_buf。

由图中可知，根节点临时缓冲区在每轮接收消息后，结合消息源列表src_list和不规则属性即时将临时缓冲区消息拷贝至recvbuf，以通信和拷贝轮转进行的方式，避免了根节点前期通信密集、后期拷贝密集而造成的网络拥塞和读写繁忙。此处拷贝方式和次数对性能影响较大，将在第3节详细介绍关于消息链调度的优化机制。

4 基于消息链调度的性能优化机制

根节点逐个将每条消息按不规则属性从临时缓冲区拷贝至recvbuf的过程带来了巨大开销。如图3和图4所示，根节点除了其叶节点消息直接发送至recvbuf外，其余所有消息都需从本地拷贝，且拷贝的次数随消息轮数的增加呈指数级增长，当消息长度较大时，拷贝带宽受限，可以预见优化效果并不理想。因此结合应用特点，尽量将消息直接写入用户地址空间，以减少拷贝次数，这是提高Gatherv性能的有效途径。

4.1 消息链初始化

假设在每轮由中间节点发送至根节点的消息集中，将中间节点临时缓冲区内相邻的消息相对划分为前置消息pre_msg和当前消息cur_msg，其对应消息源称为pre_src和cur_src，则2条消息连续的条件如式(4)所示：

recvcounts[pre_src]*recvtype_size=

displs[cur_src]*datatype_size

(4)

当式(4)成立时，中间节点临时缓冲区中相邻消息在根节点recvbuf中的接收位置也相邻，则定义2个相邻消息为连续消息，否则为非连续消息。

对于使用Gatherv的大规模并行应用，尽量将符合连续条件的通信过程合并成消息链，由根节点直接接收消息链至recvbuf，以减少本地拷贝操作，进一步提升性能。需要说明的是，根节点在每轮通信中从不同子树接收消息，因此每轮通信之间的消息是否连续并不影响根节点行为。构建消息链的工作主要集中在中间节点向根节点发送消息集的内部。

首先基于消息源列表src_list获取消息集内每个消息的长度和偏移属性，并以第1个消息为起点构建消息链。如图5所示，依据式(4)以第1个消息(msg4)为消息链起点，当第2个消息(msg5)与第1个消息的目的空间连续时，则初始化消息链为连续消息链，否则为非连续消息链。

Figure 5 Construction of message chain图5 消息链构建

4.2 连续消息调度

此后，每个当前消息cur_msg都与前置消息pre_msg以式(4)为依据进行连续性匹配，从而进行消息链扩展或重构。如图6所示，当前消息与前置消息连续，则需查看前置消息pre_msg所在消息链是否为连续消息链：

(1)对于连续消息链，则将当前消息cur_msg连接在前置消息pre_msg后，扩展该消息链。

(2)对于非连续消息链，则将前置消息pre_msg之前的消息链(不包括pre_msg)执行接收/发送操作，根节点通过临时缓冲区接收非连续消息链，进行“一次接收，逐个拷贝”操作，将各消息拷贝至recvbuf相应位置。随后中间节点以前置消息pre_msg作为起点，将当前消息cur_msg连接在pre_msg后，构成连续消息链。

Figure 6 Scheduling of continuous message图6 连续消息调度

4.3 非连续消息调度

如图7所示，当前消息与前置消息不连续时，也需根据前置消息pre_msg所在的消息链类型进行处理：

(1)对于非连续消息链，则将当前消息cur_msg连接在前置消息pre_msg后，扩展该非连续消息链。非连续链的构建和扩展目的在于最大程度地将非连续消息链合并发送至根节点，虽无法避免根节点在接收到非连续消息链后的拷贝开销，但能够有效减少通信次数，减轻网络压力。

(2)对于连续消息链，则根据“连续消息最大化直接接收”的原则，将前置消息pre_msg扩展至连续消息链，再令连续消息链执行接收/发送操作，根节点直接将连续消息链接收至recvbuf。随后以当前消息cur_msg为起点重构消息链。

Figure 7 Scheduling of discontinuous message图7 非连续消息调度

在每轮通信处理完最后一个消息后，将连续/非连续消息链发出，根节点依据消息链类型进行接收。由此，通过消息链调度机制，根节点能够最大程度地由recvbuf直接接收连续消息，避免对连续消息进行拷贝，减少了开销；对非连续消息也能实现“一次接收，逐个拷贝”，减轻了网络压力。

5 测试与分析

本文在神威高性能计算系统上实现了Gatherv优化方法，并以神威高性能计算系统为目标平台，使用自编micro-benchmark及标准测试程序IMB(Intel MPI Benchmark)，分别对本文优化方法的内存开销及Gatherv通信性能进行了测试，并和Gather规则通信的性能进行了对比。

5.1 内存开销测试

通信过程中，通信双方需要通过上下文来支持连接通路，连接通路的数量将决定通信支撑环境的内存开销。本文采用自编micro-benchmark，通过通信过程结束前后的可用内存差值来计算通信过程中构建通信连接通路所产生的内存开销。本节对比了Linear结构实现和本文优化实现的Gatherv在构建连接通路方面的内存开销情况。如图8所示，32 768个进程规模下Linear结构产生了约1 312.12 MB内存开销，而本文基于Binomial-Tree结构将内存开销控制在较低水平(仅约0.60 MB)；其他进程规模下，本文优化实现方法(保守优化与激进优化内存开销一致)的内存开销为Linear结构的lbn/(n-1)，优化效果符合预期。通过上述测试数据不难发现，本文优化方法可以以极低的内存开销高效支持用户在大规模并发条件下的Gatherv不规则集合通信。

Figure 8 Comparision of Gatherv memory overhead图8 Gatherv内存开销对比

5.2 通信性能对比测试

本节使用标准测试程序IMB对MPICH基于Linear结构实现的Gatherv与本文保守优化实现的Gatherv通信性能进行了对比测试。如表1、表2、图9和图10所示，相对于Linear结构实现，Gatherv保守优化实现有大幅的性能提升，且优化效果随进程规模增大而增强，在消息长度为8 B、进程规模为32 768时加速比达到41 068；在消息长度为8 KB、进程规模为32 768时，加速比达到32 709。另外，数据显示Linear结构下的短消息(8 B)开销比长消息(8 KB)开销更大，原因为短消息采用的Eager协议需要接收端进行用户数据的拷贝操作，而长消息采用Rendezvous协议，数据由发送端通过远程直接内存访问RDMA(Remote Direct Memory Access)写操作写入接收端目的地址。因此，短消息协议下Linear结构根节点的拷贝压力更大，热点效应更明显。

Table 1 Effect of Gatherv conservative optimization when message length is 8 B

Table 2 Effect of Gatherv conservative optimization when message length is 8 KB表2 消息长度为8 KB时的Gatherv保守优化效果

Figure 9 Gatherv overhead when message length is 8 B图9 消息长度为8 B时的Gatherv开销

Figure 10 Gatherv overhead when message length is 8 KB图10 消息长度为8 KB时的Gatherv开销

对比测试表明，本文提出的优化方法在模型结构上具备一定的优越性，同时消息链调度机制能够有效控制拷贝开销，相较于传统Linear方法具有明显优势。

5.3 性能扩展性测试

本节对2种Gatherv优化实现和基于Binomial-Tree结构实现的Gather进行性能对比测试，以验证本文优化方法可以有效扩展至大规模并发情况。测试使用标准测试程序IMB，分别测试8 B短消息和8 KB长消息的Gatherv及Gather开销。图11和图12的测试结果表明：(1)Gatherv保守优化和激进优化实现的开销在进程规模2倍递增时均实现了小于2倍的增长，具有良好的性能可扩展性。(2)Gatherv保守优化与激进优化实现之间存在略微的性能差距，主要来自于预处理阶段对recvcounts、displs及算法决策信息的广播开销。(3)激进优化实现的Gatherv性能，和基于Binomial-Tree结构实现的Gather性能相比，基本处于同一数量级，只存在局部差异。消息长度较短(8 B)时，激进优化实现的Gatherv开销略高于Gather的。原因为：通信开销相对较小，此时构建src_list和消息链的额外开销在整体开销中占比相对较大，因此导致整体开销略大。消息长度较长(8 KB)时，激进优化实现的Gatherv开销略低于Gather的原因为：通信开销在整体开销中的占比较大，一定程度上弱化了激进优化实现的额外开销的影响，且由于激进优化实现在通信过程中直接使用预先构建的src_list和消息链，而基于Binomial- Tree结构实现的Gather采用“边通信边计算对象”的模式，因此，激进优化的Gatherv实现带宽利用率略好。需要说明的是，构建src_list和消息链的额外开销会随着进程数的增加而增大，当进程数增加到一定程度且消息长度不变时，会使激进优化实现中的上述额外开销的影响逐渐显现。图12中当进程规模增大至32 768时，就出现了激进优化实现的Gatherv开销略高于Gather开销的现象。但是，如果消息长度增加，可以预见额外开销对于激进优化实现的性能影响将进一步被弱化，激进优化实现的Gatherv开销仍将低于基于Binomial-Tree结构实现的Gather的。

Figure 11 Gatherv/Gather overhead when message length is 8 B图11 消息长度为8 B时的Gatherv/Gather开销

Figure 12 Gatherv/Gather overhead when message length is 8 KB图12 消息长度为8 KB时的Gatherv/Gather开销

6 结束语

本文针对当前MPI不规则化集合通信Gatherv实现方法存在的通信热点突出、内存开销大和访存效率低等问题，提出了一种面向大规模并发的Gatherv优化方法。从优化等级、临时缓冲区管理等方面出发，研究高效均衡、内存开销可控的优化措施，将Binomial-Tree结构成功应用于Gatherv的实现，并基于此设计了消息链调度机制，有效限制根进程拷贝开销，进一步提升了Gatherv性能，对MPI不规则集合通信的优化工作有一定的参考意义。测试结果表明，本文方法可以有效解决现有方法存在的缺陷，相对于Linear结构，在内存开销和通信性能方面均有显著改进，可以有效保证Gatherv不规则集合通信在大规模并发条件下的高效可扩展性。