摘要：在大规模并行计算机中，聚合通信的性能一直是全系统的性能瓶颈.本文提出了一种在超大规模并行计算机系统中采用的基于NIC的硬件卸载MPI栅栏同步的方法.方法基于改进的Dissemination栅栏同步算法，由MPI驱动程序生成栅栏同步的算法框架，实际的通信操作由NIC硬件自动完成，针对算法设计了硬件易于实现的基于描述符的软硬件接口和硬件执行算法，大大提高了栅栏同步的效率.通过与软件实现的算法性能比较，本文方法的通信延迟比现有方法平均提高了40%.
关键词：栅栏同步；硬件卸载；描述符
中图分类号：TP302.1 文献标识码：A
NIC Based Hardware Offload of MPI Barrier
for Exascale Super Computer
WANG Shao-gang，XU Wei-xia，WU Dan，PANG Zheng-bin，XU Jin-bo
（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）
Abstract： Barrier synchronization is an important communication pattern for high performance super computers. This paper proposed a new NIC-based barrier communication offload method. The new method improved the traditional dissemination barrier algorithm to support parallel barrier message sending and receiving， which greatly reduced the communication delay. Based on the new barrier algorithm， this paper proposed new descriptor based hardware-software interface and the hardware implementation. The performance was greatly improved， compared with the traditional barrier implementation.
Key words： barrier communication；hardware offload； communication descriptor
聚合通信在MPI程序中占据相当大的比例，对系统性能的影响很大，据已有统计，在大量科学计算和工程应用程序中，聚合通信的通信时间占MPI通信时间的80%，其执行时间占总执行时间的60%[2].因而，对聚合通信进行硬件加速很有必要.事实上，目前的一些大系统上，节点控制器或NIC芯片有很大的一部分功能用来实现MPI卸载功能.因此，基于NIC芯片的聚合通信卸载是提高MPI聚合通信效率的重要途径[3-5].
基于Exascale级计算机系统的通信需求，本文提出了一种基于栅栏同步描述符的硬件卸载方案，将原来由软件实现的栅栏同步下放到硬件中自动执行，实现了计算与通信的并行，可有效地支持上10万个节点间的栅栏通信.
本文的主要贡献包括：1）提出了易于硬件实现的大规模栅栏同步算法，算法针对经典的Dissemination算法进行了改进[6-7]，提出了多路并行的改进算法，更适合在目前高带宽和延迟的网络中采用.
2）针对栅栏同步算法的特性，设计了基于描述符的软硬件接口.描述符描述了硬件执行算法时的执行过程，由软件负责生成，而具体的通信则交给NIC硬件自动执行，实现了聚合通信与主机计算的并行，可有效支持MPI3.0[8]的非阻塞通信特性.3） 详细测试了基于改进Dissemination算法的硬件卸载方案，测试表明，本文方案具有明显的性能优势，在128个节点规模下，比传统方案的延迟降低了近73%.
1 算 法
1.1 Dissemination算法
经典的Dissemination算法步骤如图1所示.
假设全系统参与栅栏同步的节点数目为p， 在Dissemination算法下，共需要进行s轮迭代.在第r轮中节点j获悉的已达到栅栏点的节点集合为Sj（r）， 则栅栏同步所需的轮数为「log2p轮.
在经典的Dissemination算法中，节点的一轮栅栏同步操作完成的条件是：向目的节点发送了栅栏到达的消息，且收到了其他节点发送来的栅栏消息， p个节点完成栅栏同步共需要「log2p轮.
根据大规模并行计算机节点通信的特点：节点带宽比较高而节点间传输的延迟比较大.在经典的Dissemination算法中，每一轮发出一个报文后，需要等待响应报文的到达，这期间节点是空闲的.如果增加每一轮发送的报文数，使节点等待响应报文的时间重叠，就可以有效利用节点网络的传输带宽，并减少栅栏算法的轮数. 针对以上问题，对Dissemination算法做出如下改进：在每一轮中，每个节点向多个目标节点发送栅栏到达报文，同时接收其他多个节点发送给该节点的报文消息.
在2路的Dissemination算法下，对任意节点i，在第s轮中，其发送的目标节点号j为： j=i+3smodp 和i-3s+pmodp；接收的两个节点号为：j=i+3smodp和 i-3s+pmodp.
改进的Dissemination算法的过程如图2所示.
假设全系统参与栅栏同步的节点数目为p， 在改进的Dissemination算法下，共需要进行s轮迭代.在第r轮中节点j获悉的已达到栅栏点的节点集合为Sj（r），则栅栏同步所需的轮数为「log3p轮.
证明 采用数学归纳法证明.
综上证明，对p个节点完成栅栏同步操作，需要满足3s≥p， 即共需要进行「log3p轮栅栏同步.
证毕.
改进的Dissemination算法的步骤数由原来的「og2p轮减少为「log3p轮，针对网络的具体情况，改进的Dissemination算法还允许继续增加轮中报文发送和接收的数量.如图3所示.
2 支持栅栏同步硬件卸载的NIC体系结构
针对改进的Dissemination算法，本文设计了支持硬件自动执行算法的体系结构.硬件执行改进Dissemination算法的主要思想是： 软件生成基于改进Dissemination的算法步骤计算出之后，生成栅栏同步描述符，通过主机与NIC间的描述符提交机制，交由NIC硬件自动执行.算法步骤在硬件执行完成后，硬件通知软件同步完成，在此期间，实现了通信与计算的并行.
2.1 NIC体系结构
本方案提出的硬件实现架构如图4所示，主要包含：描述符队列管理模块、各种描述符处理模块（MP，RDMA，BARRIER等）、访存仲裁模块、网络仲裁模块、主机接口以及网络接口模块.每个描述符处理模块支持一种类型的通信（点对点或聚合通信）.
2.1.1 描述符队列管理模块
其主要作用是管理虚端口上的各种软硬件接口队列和中断，包括描述符队列、完成队列、完成中断管理等.描述符队列管理模块读取一个描述符之后，根据描述符的类型，向描述符处理单元派发描述符信息，同时接收各个模块返回的完成信息，根据要求更新完成队列或触发中断等.
在NIC中，描述符管理模块及各种描述符处理模块会产生访存请求.例如，MP描述符处理模块需要向MP接收队列中写数据，RDMA描述符处理模块需要读写本地RDMA缓冲区，描述符中可能规定向本地节点的某个地址写完成值等.为了统一处理这些模块的访存请求，设置访存仲裁模块，用来仲裁这些模块的访存请求.为了支持虚拟地址传输模式，在访存仲裁模块中，还允许增加地址转换逻辑.
2.1.3 主机接口
主机接口实现与主机的通信，根据处理器类型，可选择支持PCIE或QPI等协议，主机接口的实现对内存处理逻辑透明.
2.1.4 网络接口
各种描述符处理模块都需要向网络中发送报文，为了实现各个描述符处理模块的独立性，简化设计，且方便网络报文的派发仲裁，每种类型的描述符处理模块定义自己的专用报文类型，并根据各自操作的要求，独立定义报文搭载数据的格式.网络仲裁模块根据报文类型，对来自于各个模块的网络报文发送请求进行仲裁，同时向各个模块派发从网络中接收到的报文.
NIC体系结构的优点是模块功能划分比较清晰，各模块间相互独立，易于硬件实现，并且能够灵活地根据实际情况对硬件功能进行增加或裁减.
2.2 基于改进Dissemination算法的描述符
在本文提出的方案中，描述符是软硬件之间的接口.描述符给出了基于改进Dissemination算法的执行步骤.在参与同步的各个节点上，软件通过节点本地的信息即可计算出算法步骤，包括以下信息：算法共需要多少轮操作，每轮操作的源节点是哪些，目的节点是哪些.节点上的软件只需要知道本结点的RANK号，及参与栅栏同步的通信域节点个数就能够计算出，而不需要进行实际的通信，最大化地实现数据处理与通信的独立及重叠.
栅栏同步描述符的格式如图5所示.
由于算法每轮的操作具有依赖的关系，及下一轮的操作需要等待上一轮的操作完成后才进行.硬件部件设计的关键是提供条件触发执行的机制. 基于本文给出的描述符结构，系统最多支持20轮的Dissemination栅栏同步算法，理论上，算法支持上百万个节点的栅栏同步，能够满足Exascale级计算机同步的需求.
软件生成的描述符提交的方式可以采用如下两种：
1） 描述符存放在系统主存中，由网络接口控制器NIC主动访问系统主存获取；
2） 主机通过主机与网络接口控制器NIC的接口PCIe发送NIO寄存器写命令将描述符写入网络接口控制器NIC的寄存器或片上存储器中.
2.3 栅栏同步报文
为了实现上述的改进Dissemination栅栏同步算法，需要基本的同步报文支持.经过分解算法，栅栏同步算法可以通过以下最基本的栅栏操作实现.
如图6所示，节点P0通过发送栅栏到达报文给目的节点P1，通知目的节点源节点已经到达栅栏点，由于目的节点可能会出现无法处理的情况，因而需要响应报文返回源节点.在目的方，设置有一定深度的报文缓冲DAMQ[9-10]，报文只要进入DAMQ，源节点就认为已经通知了目的节点，目的节点给出响应.目的节点的栅栏同步描述符提交后，检查DAMQ中是否有之前接收的栅栏到达报文，并进行处理.
若目的节点的DAMQ已满，且描述符还未提交，则给出NACK响应，通知源节点该通知报文未被处理，源节点收到NACK响应后，将延迟重发栅栏通知报文，直到目的节点的描述符提交，对报文进行了处理.
SDQ：内存中的描述符队列，软件通知NIC硬件主动到内存中取描述符.
HDQ：NIC使用片上存储器实现的描述符队列，软件通过PIO的方式提交.
OF：描述符派发逻辑，从SDQ和HDQ中取出描述符，并派发给相应的执行模块.
TE：从OF收到描述符后，根据描述符规定的栅栏到达报文发送顺序，向目标节点发出报文；在某一轮，有可能需要向多个节点发出通知报文，发送完毕后，检查响应报文DAMQ中，响应是否收齐，然后根据条件看是否处理下一轮栅栏操作的报文.某一轮栅栏通知报文可以发送的条件是：节点已经全部接收了该轮之前所应该收到的来自其他节点的栅栏通知报文，该信息由SE输出给TE模块.
SE：该模块接收来自其他节点的栅栏通知报文，根据描述符规定的顺序，当某一轮应当收到的栅栏通知报文收全后，才开始接收下一轮的报文.其他节点发送的栅栏通知报文，先保存在DAMQ中.该模块接收报文完成的轮数需要输出给TE模块，以便确定本节点栅栏报文的发送时机.
远程请求报文DAMQ：保存其他节点发送给本节点的栅栏到达通知，采用DAMQ方式管理，报文只要进入DAMQ，就认为已经通知了本节点，给出正常的响应，若DAMQ队列已满，则DAMQ模块给出NACK响应，通知发送节点目的方无法接收，发送节点需要在延迟一段时间后，重新发出报文.
远程响应报文DAMQ：本节点发出的栅栏通知报文的响应报文先保存在DAMQ中，DAMQ的容量应能够容纳下发出的所有报文的响应报文.
3 基于硬件卸载的栅栏同步性能评测
针对本文提出的支持改进Dissemination算法的NIC体系结构，采用SystemVerilog建模语言实现了本文提出的栅栏同步引擎（BE），并在VCS模拟器上针对多种系统规模和实现参数进行了仿真.
在模拟环境中，本文最多实例化了128个节点，节点间通过3D-Torus模式进行互连，为简化网络实现，路由采用维序路由，单跳延迟采取了固定值.
3.1 栅栏同步延迟
基于给定的网络延迟，本文测试了不同节点规模的栅栏同步性能.为了测试算法本身的性能，本次测试不考虑节点间到达栅栏点的时间不同步而带来的延迟.测试的结果如图8所示.
从本次测试能够看出，本文提出的基于改进Dissemination算法的栅栏同步硬件卸载方案具有很好的可扩展性，在节点数增多时，栅栏同步的延迟并没有像传统的聚合通信算法那样，呈现出指数级的延迟增加.本文提出的方案延迟基本呈现较缓慢的线性延迟增长，这种特性对于Exascale级的超计算机来说至关重要[11].
3.2 与软件算法的性能对比
为了测试基于硬件卸载的栅栏同步算法的性能改进，我们完全由软件实现了传统的Dissemination算法和改进的Dissemination算法，测试其性能，并与基于硬件实现改进算法的性能进行对比，测试结果如图9所示.
可以看出，与软件实现的方法相比，基于硬件卸载的实现途径具有明显的性能改进，特别是在大规模系统中，聚合通信的开销占全系统通信开销的80%以上，硬件卸载全局通信的性能优势更能有效地体现出来.软件算法实现建立在点对点算法基础上，而硬件卸载的改进Dissemination算法实现了多报文并行发送，算法性能更高.同时，硬件算法减少了与主机的交互，更有效地降低了栅栏同步的延迟.
3.3 栅栏到达时刻对延迟的影响
4 结 论
基于Exascale级计算机的栅栏同步的实现挑战，传统的方法在可扩展性和实现复杂度方面存在着明显的不足.本文提出了一种基于改进Dissemination算法的硬件卸载栅栏同步的方法.方法实现了由硬件完全自主完成的栅栏通信，具有非常明显的性能加速作用，并且硬件实现简单.
参考文献
[5] HOEFLER T， MEHLAN T， MIETKE F， et al. Fast barrier synchronization for InfiniBand[C]//Proceedings of 20th International Conference on Parallel and Distributed Processing Symposium. New York： IEEE， 2006.
[6] HENSGEN D， FINKEL R， MANBER U. Two algorithms for barrier synchronization[J]. International Journal of Parallel Programming， 1988， 17（1）： 1-17.
[7] MAMIDALA A R. Scalable and high performance collective communication for next generation multicore infiniband clusters[D].Columbus， Ohio： Ohio State University， 2008.
[8] TIPPARAJU V， GROPP W， RITZDORF H， et al. Investigating high performance RMA interfaces for the MPI-3 standard[C]//Proceedings of the 2009 International Conference on Parallel Processing （ICPP）. Washington， DC： IEEE Computer Society， 2009： 293-300.
