聚合通信操作的实现和优化现状综述∗

张 鑫 董德尊 庞征斌

（国防科技大学计算机学院 长沙 410073）

1 引言

在共享和分布式存储的并行系统中，聚合通信通常是分布式应用程序的一组进程间互相协作，通过相互之间的消息传递来达到数据交换、任务控制和全局计算的目的。聚合操作可以被认为是一种同步操作，因为它要求在通信中涉及的所有过程协同工作。因此，聚合通信操作的快慢会直接影响并行应用的效率。并且聚合操作在高性能计算机的科学计算时间消耗上有时候可占据高达70%。文献［1］总结了在不同大规模应用程序中不同聚合通信操作所占据的比例。而许多并行程序的执行都是计算和通信交替进行，在计算阶段，各个进程在处理节点上独立的运行，通信阶段进程则在互连网络中执行同步和数据交换。在通信阶段，处理节点实际上是处于等待状态，不进行任何计算操作，极大地降低了高性能计算机的效率，并行程序难以获得理想的运算速度和并行效率。聚合通信性能尤其对统计、数据挖掘和人工智能领域发展产生关键影响，因此如何更进一步地提高聚合通信性能仍是研究的热点。

随着高性能计算机越来越复杂，在通信系统中引入了越来越多的异构性［2］。这导致了系统内不同层级的通信性能差异，给聚合通信的优化提出了更多的挑战。目前有很多研究［3］为具体应用程序中的同步、广播或者规约操作提供了更有效的算法和优化。由于聚合通信操作的性能取决于特定通信操作的内在因素和基础环境的等外在因素，不存在所有场景中都高效的聚合通信操作算法，所以多数用户都会通过多种形式的优化策略来满足其具体应用场景的性能需求，诸如研究拓扑感知的聚合通信算法以及根据网络中实时消息的大小进行相应的算法选择和处理。在大规模的聚合通信场景下，合理和有针对性的算法选择显得十分关键。但在目前高性能计算机系统内不同层级通信性能变化的条件下，找到一个合适的优化策略也是一项挑战。

目前聚合通信实现有三种方式：软件实现、硬件实现和软硬件结合的方式。硬件实现有许多优点但是因为其复杂度高和经济投入高的特点，本文中不再具体讨论。高性能计算领域新技术的发展给软硬件开发提供了更多的支持，给提出高性能的聚合通信方案提供了基础，使得新技术在各种系统上的有效集成成为了可能。智能网卡和交换机对聚合通信操作的支持使得聚合通信的计算可以卸载到互连网络中，使得计算和通信同时进行，有效地提高了CPU的使用效率。同时，也给部署新型的拓扑感知的聚合通信算法提供了有利的条件。

本文的主要目的是探讨聚合通信优化技术的广度和现状，并深入了解它们在各种应用领域的适用性和局限性。文章将详细介绍聚合通信算法的各种实现方式，总结近年来优化实现的典型案例。从而总结出未来聚合通信优化的趋势。

2 聚合通信的概念和聚合通信操作算法的简介

2.1 聚合通信的概念

聚合通信涉及参与一个通信操作的多个进程，并且影响所有或一些节点之间的数据传输。聚合通信操作包括：广播（Broadcast）、栅栏同步（Barrier）、规约（Reduce）、分散（Scatter）和收集（Gather）等。与使用一系列单播消息实现相同的操作相比，聚合通信操作可以减少延迟和网络流量。支持聚合通信的网络提供了有效和可扩展的聚合操作架构，有效地降低了处理器的开销。

根据聚合通信的数据流的流向，可以将聚合通信操作分为有根的通信操作（Rooted Communication）和无根的通信操作（Non-Rooted Communication）。有 根 的 聚 合 操 作 包 括Broadcast、Gather、Scatter 和Reduce。无根操作则不是源于或者是将消息注入一个特定的节点。这类的操作主要有Allgather，AllScatter，AllReduce和Barrier等。

2.2 常见的聚合通信操作算法

2.2.1 广播（Broadcast）

广播是许多应用中常见的聚合操作，它由根进程向其他所有进程发送消息。广播操作常见的算法有：扁平树、二叉树、二项树、流水线树、拆分二叉树、链式算法、Van de Geijn 算法［5］。

2.2.2 规约/分散/收集（Reduce/Scatter/Gather）

这些操作的实现都紧密跟随着广播算法。例如，收集操作可以通过特征或链式算法来实现，它们通过树或链拓扑将分布式数据向上游传递到根进程。

2.2.3 栅栏同步（Barrier）

同步是指应用程序需要保证所有的进程都到达某个检查点后才能继续执行。有各种各样的算法可以用于实现同步操作，该操作可以是有根的操作也可以是无根的。这一类算法有线性同步算法、基于树的同步算法、蝴蝶算法（迭代算法）。

2.2.4 Allgather/Allreduce/All-to-All

Allgather 是一个收集的操作，其中每个进程贡献的数据将收集在所有参与的进程上。这个操作的本质是非根类的聚合操作。该聚合通信操作使用许多不同类型的算法，一些比较常用的算法有：环算法、递归加倍算法、布鲁克（Bruck）算法等。

Allreduce 是一种非根型聚合操作。其交换消息的时候额外有一个规约操作，对每个进程贡献的数据进行相应的规约，最后所有的进程都得到该规约结果。其算法有环算法、递归加倍算法、向量减半与距离加倍算法［4］、Rabenseifner［5］算法等。

All-to-All 也是一种非根型聚合通信操作，其中每一个进程都有各自唯一的数据要发送到每个其他进程。该操作的算法有布鲁克索引算法、RDMA算法等。

2.3 聚合通信算法的分析和选择

在不同的应用场景和网络结构中，以及消息大小的不同时，选择不同的算法开销可能存在很大的差异。虽然目前研究领域提出了众多算法，但是在实际的应用中，往往并非只使用单一的算法。在聚合通信操作中，不存在一个算法在任何应用场景都高效的情况，需要根据消息的大小，节点的规模等来决定。表1 是对常用的聚合通信算法应用的一些归类总结。

表1 聚合通信操作算法归类总结

2.4 聚合通信算法的发展

2.1 ～2.3 节介绍的是传统算法和基于传统算法改进的一些算法。目前，随着系统规模的扩大，通信渠道的异构性特点更加显著，如RDMA，NVMe协议，GPU+CPU 等，这导致了系统内不同层级通信性能的变化。近年来，通信设备提供商Mellanox公司生产的新一代BlueFieldTM智能网卡，Connect-X 系列交换机功能不断强大，可以帮助网络中的设备去实时地了解网络拓扑经有诸多研究成果致力于拓扑感知［13］的聚合通信算法，它们将从全局上了解整个网络的拓扑信息，根据这些全局信息，来有效地分配通信和计算资源，以避免消息在较慢的信道上传输。

3 聚合通信实现方式的发展历程和现状

聚合通信的实现方式可以根据硬件的支持程度划分为三类：基于软件方式、基于硬件方式和软硬件结合的方式。在本章中，将对聚合通信的软件实现方式和软硬件结合实现方式的方法进行介绍。

3.1 软件实现

3.1.1 软件实现的发展历程

软件聚合通信是当前实现聚合通信操作种类最全，使用最广的方式。一直被广泛使用并且功能强大、算法丰富的聚合通信操作接口是MPI［6～7］。

聚合通信操作的软件实现是在单播实现的基础上结合前面介绍的算法来实现的，并且软件算法具有很好的适应性，可以在不需要改变原语的情况下，根据实际的需要采用不同的聚合通信算法。

3.1.2 软件实现的优势分析和潜在局限性

聚合通信操作的软件实现是在单播实现的基础上结合前面介绍的算法来实现的，并且软件算法具有很好的适应性，平台通用性很好使用范围广泛，几乎所有的高性能计算机系统都使用MPI编程模型进行应用的开发和优化。它可以在不需要改变原语的情况下，根据实际的需要采用不同的聚合通信算法，在实际使用的时候只需要将软件库配置好就可以使用。

这种方法虽然使用简单，但是仍然有以下缺点：

1）可扩展性差；

2）容易受到系统噪声的影响；

3）降低了计算和通信的重叠率。

3.2 软硬件结合方式实现

研究表明，虽然软件实现的方式有诸多优点，但是网络的利用效率低下，为了增加资源的利用率，提出了软硬件结合的方法。硬件的实现可以获得高速度，软件灵活性强、代价低。该方法就是希望结合两种方式的优点来优化聚合通信操作。目前主要有两大类实现方式，一种是基于网卡（NIC）的实现方式，一种是基于交换机（Switch）的方式。

3.2.1 基于NIC的方式实现

1）实现动机和基础

计算节点通过网卡连接到网络中，网卡最接近终端处理器。因此，可以用于执行各种网络卸载机制。带有处理器的智能网卡可用于对传入的网络数据执行复杂的操作。它们还可以用于卸载一系列聚合通信操作然后网卡继续执行，从而释放主处理器以返回计算。

2）典型实现

Connect-X［15］系列从Connect-2 NIC 就开始支持简单的聚合通信操作卸载。最新的Connect-6产品嵌入了eSwitch，不但支持L2交换，数据包分类和虚拟网络隧道协议处理，如VXLAN封装和解封装，而且支持诸如包重写之类的L3 层操作，比如标签推送/弹出之类的MPLS操作。基于eSwitch网卡硬件的ASAP2 技术允许整个虚拟交换机的等功能卸载到网卡上，以实现聚合通信数据包处理速度的极大提高，并且显著降低CPU开销。

3）优缺点总结

总结基于NIC实现的方式有如下优点：

（1）数据发送由网卡上的辅助硬件完成，减少发送延迟，减轻CPU负担，促使计算和通信重叠。

（2）系统噪声小。

（3）可扩展性较好。

但是，这种方法不能从根本上改变整个系统聚合通信效率低下的问题。

3.2.2 基于Switch的方式实现

1）实现动机和基础

交换机构成了互连网络的主干。高性能网络具有点对点链接以最大化性能。交换机负责将数据包从源节点路由到目标节点。由于交换机处于中心位置，因此聚合通信操作卸载到交换机中是非常具有吸引力的。一些公司也设计了产品来加速聚合通信操作，这些产品的目的是将处理机端的通信和简单计算工作卸载到交换机端，以此来解决软件聚合通信的可扩展性问题，同时提高计算与通信的重叠率和屏蔽系统噪声。

2）典型的实现和分析

（1）FCA［8］

Voltaire（现已与Mellanox 合并）的Fabric Channel Accelerator技术，简称FCA。FCA是一个软件插包，已经集成到MPI 库上。并且，已经实现了映射底层网络拓扑到聚合算法的能力，使得聚合通信操作在算法层能够获取物理拓扑结构的信息，并根据这些信息构建拓扑感知的聚合通信树。在聚合通信树中，一旦聚合通信树的父节点知道了最终结果，则FCA 仅发送一条消息，就可以利用交换机硬件将结果广播到其他过程。FCA 还提供了通信隔离专用虚拟网络（VLane）将聚合通信流量和交换中的其余流量隔离，从而消除与其他类型流量的争用［11］。

图1 FCA整体架构示意图

（2）SHArP（Scalable Hierarchical Aggregation Protocol）

SHArP［9］是Mellanox 公司在2016 年发布的卸载聚合通信到网络中的协议。2019年3月，Mellanox 宣布其采用“可扩展分层聚合和归约协议”SHArP 技术的HDR 200G InfiniBand 创造了新的性能记录，使深度学习操作性能提高了一倍。

SHArP 提供了描述数据规约的抽象。实现了消息在遍历网络时操纵数据，最小化数据移动距离。

3）优缺点总结

（1）可以在交换机端口复制数据包，从而减少网络流量［10］。

（2）提供了基于硬件的可靠机制来确保广播分组到达其目的地。

（3）计算和通信的重叠率提高。

（4）可以创建拓扑感知的聚合通信树来获得更低的聚合通信操作延迟。

目前，基于Switch 的卸载聚合通信操作的这种实现方式还在进一步研究和部署中。

4 结语

影响聚合通信性能的因素有很多，主要有以下几个方面：集群热点和拥塞，算法对物理拓扑不敏感，操作系统的噪声。根据前面三章的介绍，需要不断地采用创新的架构来优化聚合通信操作。在算法上，继续开发拓扑敏感的聚合通信算法，使得能够充分利用网络的全局信息来调度聚合通信；在实现上，不断提升计算和通信的重叠率，使得数据在移动的过程中被处理，减轻CPU 负担，降低系统噪声。

未来一段时间内，该领域的研究主要集中在通过利用先进的多核架构和网络功能来增强软件设计降低聚合操作的延迟；利用先进的智能网卡［14］和交换机，设计和改进允许应用程序实现计算与通信重叠的非阻塞类型的聚合通信操作算法；探索检测系统拓扑的替代方案，开发新型拓扑感知聚合通信算法，最终使得并行应用程序获得更快的运算速度。