HAN: a Hierarchical AutotuNed Collective Communication Framework

作者：Xi Luo
会议：2020 IEEE International Conference on Cluster Computing (CLUSTER)
doi：10.1109/CLUSTER49012.2020.00013
IEEE Xplore URL：https://ieeexplore.ieee.org/abstract/document/9229573
会议最佳论文之一

一个分层自调优的集合通信框架，实现在Open MPI的集合通信框架中（/ompi/mca/coll/han）。HAN为每个硬件级别选择合适的同种集合通信模块作为子模块，将子模块的集合操作视为任务，并组织这些任务来高效执行分层的集合操作。

分层的集合通信

HPC系统日益复杂，具有不同的硬件层级（同一NUMA节点、同一物理节点、同一交换机等），分层的集合通信能够充分利用每一个分层上的硬件资源，提高复杂系统上的通信性能。一个性能良好的分层集合通信框架考虑三个因素：

1. 每个分层上运行的集合通信算法要能充分利用该分层的硬件资源

2. 提高不同分层上的通信重叠

3. 面对快速变化的硬件环境，框架需要足够灵活，方便适配新的硬件分层或在某一层内选择新的集合通信模块

HAN的做法是：

• 按照硬件层次进行分层，目前的实现为按照是否处于同一节点分为两层，即Intra-Node和Inter-Node，Intra-Node中为处于同一个物理主机上的所有进程，Inter-Node由每个物理主机选出一个leader进程构成。Han的分层是方便扩展的。

• 为每个硬件分层选择已有集合通信组件，如在Inter-Node层中选择LibNBC或ADAPT，在Intra-Node层中选择SM或SOLO。选择的原因是LibNBC与ADAPT提供了非阻塞式的集合通信操作，有利于通信的重叠；而SM和SOLO在通信中使用了节点内的共享内存进行通信，具有较好的节点内通信效率。

• 基于任务的设计，也就是将一次集合通信划分为多个细粒度的“任务”，并将通信的消息分段。通信中通过流水线技术来重叠不同层次上的的通信。

以上三点使HAN框架能够较为高效地进行分层集合通信。

基于任务的设计与流水线

在HAN中，消息分段通过任务进行传输。为了执行分层的集合操作，每个任务包含一个或多个来自不同子模块的细粒度的集合操作。通过基于任务的设计，用于集合操作的底层子模块是可以改变的，这使得我们的框架可以很容易地为新的硬件架构选择子模块。任务的划分在不同的集合通信操作中是不同的，论文中以MPI_Bcast和MPI_Allreduce为例子做了详细讲解。

MPI_Bcast

一个分层的广播操作可以通过两步来实现，首先由根进程在Inter-Node上广播，每个节点上的leader得到消息后在各自的Intra-Node中广播。

HAN框架基于任务的设计将广播划分为3个任务：

• ib(i)：在节点间对消息i进行广播，i代表inter；

• sb(i)：在节点内对消息i进行广播，s代表shared memory；

• sbib(i)：在节点内对i-1进行广播，节点间对i进行广播。

经过这样的划分，一个共有u个消息分段的分层广播操作能够以下图所示的方式进行：

MPI_Allreduce

一个分层的全归约操作可以首先在Intra-Node中将数据归约到每个节点的leader进程，再在Inter-Node中将数据归约到根进程，然后由根进程在Inter-Node中广播，最后由每个结点的leader在Intra-Node中广播。

相应的HAN框架划分出了如下的任务：

• 任务sr(i)与sb(i)分别代表对分段i的sr和sb；

• 任务irsr(i)包括了对分段i-1的ir与对分段i的sr；

• 任务ibirsr(i)包括了对分段i-2的ib、分段i-1的ir与分段i的sr；

• 任务sbibirsr(i)包括了对分段i-3的sb、分段i-2的ib、分段i-1的ir与分段i的sr；

• 任务sbibir(i)包括了对分段i-2的sb、分段i-1的ib与分段i的ir；

• 任务sbib(i)包括了对分段i-1的sb与对分段i的ib；

• 任务sbsr(i)仅在节点非领导进程上进行、它通过sb从它节点上的领导进程接收已经归约好的分段i-3，然后通过sr将分段i归约到它节点上的领导进程；

HAN中Allreduce的示意图如下所示：

效果

HAN框架的方法带来提升主要在于三个地方：不同硬件层级选择不同的集合通信组件、消息分段实现的流水线、通信重叠。其中后两点是框架较有特色的地方。论文中的一些实验结果可以证明这两点对通信效率的提高是有意义的。

下图为同一节点上对广播操作的任务sbib进行测试的结果，这本是用于构建自调优模型的测试结果，图中最开始的sbib时间较长，之后缩短并趋于稳定，造成这一现象的主要原因是最初的一次sbib执行时流水线还未完全完成构建，这张图可以一定程度上从侧面证明采用流水线技术是有意义的。

在通信的重叠上，下图为单独进行ib、sb与同时进行ibsb的通信时间。可以直观地看到，并发的ibsb的时间比ib、sb中的最大值略长，但远小于它们的和，可以说明两个硬件层次上的通信是可以并行进行的，但二者之间仍会存在一些共享资源如DMA引擎、总线、CPU时间等的争用导致不可能达到完全的通信重叠。

作者在论文中指出同一硬件层级下两个不同方向的通信也是可以进行重叠的，例如使用相同一棵二项树的Bcast和Reduce，Bcast自根节点向叶节点同行，Reduce相反，若二者并行在同一时间它们通信涉及的链路与节点是不同的，因此也可以做到通信重叠。下图为单独进行ib、ir和同时进行ibir的用时，能够证明二者在同一层次中存在一定的通信重叠。

自调优（自适应）

自调优的方法可以总体上分为参数扫描和使用性能模型两种，前者测试所有参数组合下集合通信的性能，来在不同情况下选择一组最优的参数，缺点是耗时；后者构建出通信的性能模型，计算得出最佳的参数选择，缺点是不够准确。

HAN框架基于任务的设计使其可以结合二者的优点，首先对每个集合通信操作中划分出的每种任务进行测试，同时基于任务构建了集合通信的性能模型，根据二者选择出较好的参数，兼顾了效率与准确性。下图分别是不同自调优方法的耗时与性能对比。