目前超级计算机已经迈入E级计算时代，但随着摩尔定律接近失效、颠覆性使能技术迟迟不能实现，超级计算机在访存、通信、能耗等方面仍面临严重的发展瓶颈^[1]. 而MPI（message passing interface）集合通信^[2]是高性能计算中最重要的通信类型，对整机系统的性能具有重要的影响，提升MPI集合通信性能是突破通信墙的重要手段. 传统的MPI集合通信是基于点到点消息实现的^[3-4]，随着系统规模的不断扩大，这种实现方式面临越来越严重的性能及可扩展性问题，而硬件集合通信具有性能高、可扩展性好等优点，正受到越来越多的关注^[5].

硬件集合通信中，数据沿聚合树进行规约或广播操作，聚合树的高度、负载均衡性等对集合操作的性能具有至关重要的影响. 本文研究了影响硬件集合通信性能的因素，提出了硬件集合通信开销模型，并以此为基础提出了构建硬件集合通信聚合树的方法. 本文主要贡献包括4个方面：

1） 提出了硬件集合通信开销模型，能够较精确地计算硬件集合通信的时间开销；

2） 研究了如何根据消息大小确定聚合树的宽度，从而在网络传输开销与数据计算开销之间取得平衡，以降低集合操作的延迟；

3） 针对Ⅰ型聚合树，提出了最小高度分层k项聚合树构建方法，相比传统的Ⅰ型聚合树，降低了跨组聚合包的个数，减少了网络拥塞；

4） 针对Ⅱ型聚合树，提出了最小代价Ⅱ型聚合树构建方法，减少了聚合树使用的交换机数量.

1.   研究背景

1.1   硬件集合通信简介

近年来，网络计算技术发展迅速^[6-7]. 网络计算可将数据规约计算、协议处理、数据加解密等原本由处理器承担的计算任务卸载到网络设备中进行，解放了CPU，使CPU可以专注于其他任务的处理. 在高性能计算领域，可利用网络计算提升MPI集合通信性能. 本文将基于网络计算实现的MPI集合通信称为硬件集合通信. MPI集合通信中，Barrier，Bcast，Reduce，Allreduce是应用最广泛的操作，它们均是1对多或多对1的通信模式，适于以硬件集合通信方式实现. 图1显示了Allreduce的实现过程，它利用聚合树完成数据聚合及结果分发操作，该树中叶节点对应通信进程，根节点及中间节点对应交换机. 进行集合通信时，数据先从叶节点向根节点聚合，并在聚合的过程中计算规约结果；到达根节点后再沿反方向将规约结果广播给所有叶节点. 其他集合操作的实现方式与此类似.

图  1  基于网络计算的Allreduce操作实现过程

Figure  1.  Implementation phases of Allreduce operation based on in-network-computing

下载: 全尺寸图片 幻灯片

目前，很多公司推出了面向高性能计算的硬件集合通信技术，如IBM BlueG/Q中的硬件集合通信原语^[8-11]、Mellanox的SHARP技术^{[5, 12-14]}、神威互连网络中的硬件集合通信^[15]等. 相较于点到点消息实现的集合通信，硬件集合通信的性能有了显著提升. Zimmer等人^[16]在Summit系统中利用基准程序对SHARP性能进行了测试，4096个节点规模下集合消息性能至少提升了1倍.

1.2   硬件集合通信使用中存在的问题

硬件集合通信除了需要特殊的硬件支持外，还需要网络管理软件的密切配合，以完成聚合树分配、多播路由配置等操作. 其中，聚合树分配是其中最为关键的操作. 现有的硬件集合通信技术在分配聚合树时还存在3个问题：

1） 缺乏精确的集合通信开销模型，无法更好地指导聚合树构建. 基于$\mathrm{\alpha }$-$\mathrm{\beta }$模型的软件集合通信开销模型^[3]过于简化，而针对特定网络的专用模型又不具备通用性^[17]，它们均不适用于硬件集合通信.

2） 构造聚合树时未考虑相互干扰问题. 当系统中存在大量通信域时，需要为每个通信域分配1棵独立的聚合树，以降低各通信域间的相互干扰，而现有的聚合树分配方法未充分考虑到该问题. 例如，SHARP技术中每个作业的所有通信域共享同一棵聚合树^[18]，这会产生严重的相互干扰. 现有的聚合树构建方法也没有考虑到同一聚合树内不同消息间的相互干扰问题. 例如，传统方法构建出的聚合树会产生较多的跨组通信，使得同一集合操作的不同消息因竞争通信链路而相互干扰.

3） 未考虑硬件通信资源不够用问题. 网络中用于支持硬件集合通信的资源是有限的，而现有的聚合树构建方法未考虑该问题，导致出现通信资源不够用的情况. 例如，BlueG/Q中每个网络节点最多支持12棵聚合树，在很多情况下，由于聚合树数量不足，无法使用硬件集合通信^[11].

针对上述3个问题，本文研究如何建立硬件集合通信开销模型，以及如何基于该模型高效地构建聚合树.

2.   硬件集合通信开销模型

2.1   定义及假设

定义1. 互连网络. 互连网络定义为有向图I=（N, L），其中N为网络节点集合，L为通信链路集合. 网络节点包括网卡及交换机. 本文假设网卡在I中均是叶节点.

定义2. 聚合树. 在互连网络I=（N, L）上目标集合M（M$\subset$N）对应的聚合树是一棵树A=（N_A, L_A），M$\subseteq$N_A$\subseteq$N，其中M是通信域中各进程所在的网卡集合. A中边（$\mu$,$\upsilon$）的长度定义为I中$\mu$到$\upsilon$的距离，也即I中从$\mu$到$\upsilon$经过的网络链路数. A不必是I的子树，也即不要求L_A$\subseteq$L. 另外，M中允许有重复元素，从而使得每个节点上可同时运行多个通信进程. 聚合树还需满足度约束条件，也即每个节点的最大子节点数不能超过硬件阈值.

定义3. 聚合树高度. 设A=（N_A, L_A）是互连网络I=（N, L）上目标集合M对应的一棵聚合树，A中从叶节点出发到达根节点所经过的边的最大条数，称为聚合树的高度. 只有1个节点的聚合树高度为0.

定义4. 聚合树半径. 设A=（N_A, L_A）是互连网络I=（N, L）上目标集合M对应的一棵聚合树，A中从叶节点出发到根节点所经过边的长度之和的最大值称为聚合树半径. 聚合树半径实际上是从各叶节点出发沿该聚合树依次经过各祖先最终到达根节点时所经过的最大链路条数.

现有的硬件集合通信技术中，有的仅支持将集合操作卸载到网卡中进行，有的则还可将集合操作卸载到交换机中进行. 根据不同的卸载位置，本文将聚合树分为Ⅰ型聚合树及Ⅱ型聚合树2种类型.

定义5. Ⅰ型聚合树. 设A=（N_A, L_A）是互连网络I=（N, L）上目标集合M对应的一棵聚合树，若M = N_A，则称A为Ⅰ型聚合树. 该类聚合树中，集合操作均被卸载到网卡中执行，且仅使用进程所在的那些网卡.

定义6. Ⅱ型聚合树. 设A=（N_A, L_A）是互连网络I=（N, L）上目标集合M对应的一棵聚合树，T=（N_T, L_T）是I的一棵子树，M$\subseteq$N_A$\subseteq$N_T$\subseteq$N，且T中叶节点均在M中. 若$\forall u\in$N_A，$u$在A中的父亲p也是$u$在T中的某个祖先，则称A为Ⅱ型聚合树. Ⅱ型聚合树中的集合操作均被卸载到交换机中进行.

图2显示了Ⅰ型聚合树和Ⅱ型聚合树. 假设有8个进程参与集合通信，每个网卡上1个进程，互连网络的拓扑结构如图2（a）所示；图2（b）是一棵Ⅰ型聚合树，高度为3，半径为12；图2（c）是一棵Ⅱ型聚合树.

图  2  Ⅰ型聚合树和Ⅱ型聚合树

Figure  2.  Aggregate trees of type Ⅰ and type Ⅱ

下载: 全尺寸图片 幻灯片

2.2   开销模型

本文采用式（1）~（4）所示的开销模型，模型中各变量的含义如表1所示. 本文关注于如何降低聚合过程的开销，下面着重对聚合过程开销进行说明.

表  1  硬件集合通信开销模型中使用的符号

Table  1.  Symbols Used in the Cost Model of Hardware Supported Collectives

符号	含义
${T}_{\mathrm{c}\mathrm{o}\mathrm{l}\mathrm{l}}$	集合操作的总时间开销
${T}_{\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{t}\_\mathrm{w}\mathrm{r}}$	应用投递1个集合操作描述符的时间
${T}_{\mathrm{f}\mathrm{e}\mathrm{t}\mathrm{c}\mathrm{h}\_\mathrm{w}\mathrm{r}}$	网卡读取1个集合操作描述符的时间
${T}_{\mathrm{f}\mathrm{e}\mathrm{t}\mathrm{c}\mathrm{h}\_\mathrm{d}\mathrm{a}\mathrm{t}\mathrm{a}}$	网卡从内存读取操作数的时间
${T}_{\mathrm{a}\mathrm{g}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}}$	聚合过程的时间开销
${T}_{\mathrm{b}\mathrm{c}\mathrm{a}\mathrm{s}\mathrm{t}}$	广播过程的时间开销
${T}_{\mathrm{w}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{e}\_\mathrm{w}\mathrm{c}}$	网卡写完成条目及结果到内存的时间
${T}_{\mathrm{n}\mathrm{o}\mathrm{i}\mathrm{s}\mathrm{e}}$	噪声导致的开销
S	用户消息大小（不超过2 KB）
${S}^{'}$	聚合包大小
${S}^{*}$	规约数据长度
$\beta$	PCIE链路/网络链路带宽
$l$	消息经过1条网络链路的时间
${h}_{\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}$	聚合树高度
${r}_{\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}$	聚合树半径
P	进程总数
k	k叉树的宽度或k项树的基
$\theta$	每个聚合包的匹配处理时间
$\gamma$	单位长度数据的规约计算时间
$\delta$	任2个进程间单播路由的最大跳步数

下载: 导出CSV 

| 显示表格

${T}_{\mathrm{a}\mathrm{g}\mathrm{g}\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{e}}$是聚合过程的时间，其包括聚合包在网络链路上的传输时间，以及在网络节点内的处理时间. 假设聚合树是k叉完全树，聚合树的半径为${r}_{\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}$，则聚合包在网络链路中的传输总时间为${r}_{\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}\times l$. 设每个聚合包的匹配处理时间为$\theta$、存储转发时间为$\dfrac{{S'}}{\beta }$、规约计算时间为${S^{\text{*}}} \times \gamma$，则聚合包在网络节点内的处理总时间为${h}_{\text{atree}}\times k\times \left(\theta \text{+}\dfrac{S^{'}}{\beta }\text{+}{S}^{\text{*}}\times \gamma \right)$. 最终得到式（2）所示的聚合时间开销.

为进一步简化模型，除了假设聚合树是k叉完全树之外，还假设任意2个进程之间单播路由的路径长度相等，均需经过$\mathrm{\delta }$条链路，则对Ⅰ型聚合树，${h_{{\text{atree}}}} \approx {\log _k}P$，${r_{{\text{atree}}}} \approx \delta \times {\log _k}P$，从而得到式（3）所示的聚合过程开销. 而对Ⅱ型聚合树，${h_{{\text{atree}}}} \approx \left\lceil {{{\log }_k}P} \right\rceil$，${r_{{\text{atree}}}} \approx 0.5\delta$，从而得到式（4）所示的聚合过程开销.

2.3   模型验证

本文在新一代神威超级计算机上测试了各类集合消息的延迟，并与开销模型计算出的结果进行对比. 实验环境如图3所示.

图  3  测试环境使用的2层胖树

Figure  3.  2-level fat tree used in the test environment

下载: 全尺寸图片 幻灯片

使用1个超节点进行测试，超节点内共有256个节点，每个节点安装1块消息处理芯片，每块消息处理芯片有2个网络端口，故整个超节点内共有512个网络端口. 这512个网络端口通过一棵2层胖树进行互连. 该胖树共有48台交换机和其中32台叶交换机和16台骨干交换机. 每台交换机的端口数均为40，其中有些端口未被使用. 每台叶交换机有16个端口用于连接消息处理芯片的网络接口，16个端口用于连接骨干交换机.

分别在不同进程数下测试了各种类型、各种长度集合消息的延迟. 测试方法为：每种类型及长度均测试5000次，每次测试进程均记录集合操作的时间开销，取耗时最长的那个进程的时间开销作为该次集合通信的时间开销，再取这5000个时间开销的中位值作为当前类型、当前长度下集合消息的延迟.

限于篇幅，本文仅显示了Ⅰ型聚合树的部分测试结果. 不同进程数下，长度为8 B的广播操作的理论计算延迟与实际测试延迟如图4所示；进程数为512时不同长度Bcast消息的理论计算延迟与实际测试延迟如图5所示. 可以看出，Ⅰ型聚合树的理论计算延迟与实际测试延迟最多相差0.5 μs. 这表明本文提出的硬件集合通信开销模型能够较准确地拟合实测延迟.

图  4  不同进程数下集合操作的实测延迟及理论计算延迟

Figure  4.  Measured latency and estimated latency of collectives for different count of processes

下载: 全尺寸图片 幻灯片

图  5  进程数为512时不同消息大小下集合消息的实测延迟及理论计算延迟

Figure  5.  Measured latency and estimated latency of collectives for different message size when process count is 512

下载: 全尺寸图片 幻灯片

3.   Ⅰ型聚合树的构建

给定任意P个进程，为它们构造一棵开销最小的Ⅰ型聚合树是非常困难的，因为不但要考虑聚合树宽度、聚合树半径等因素，还要考虑通信与通信重叠、通信与计算重叠、消息间相互干扰等因素的影响，故目前Ⅰ型聚合树均是通过启发式算法进行构造. 本节首先研究如何根据消息类型、消息长度等确定Ⅰ型聚合树的宽度k，然后研究如何快速构造一棵聚合树，使得跨组聚合包的个数尽可能地少，尽量降低消息间的相互干扰.

3.1   根据聚合包大小确定聚合树的宽度

聚合过程的时间开销包括聚合包的传输时间以及处理时间. 聚合树的宽度k对聚合过程的时间开销具有重要影响. 直观上看，如果k很小，则聚合树很高，相应地聚合包的传输开销就很大；如果k很大，则每个网卡需要处理的聚合包很多，相应地聚合包的处理开销就很大. 需要研究k对聚合时间开销的影响.

先看如何选择k才能使式（3）计算出的聚合开销$F\left(k\right)$最小. 记$\delta\times l=\alpha$，$\theta+\dfrac{S^{\text{'}}}{\beta}+S^*\times\gamma=b$，定义如式（5）所示的$F\left(k\right)$，其导数函数如式（6）所示.

使$F\left(k\right)$取最小值的k记为${k}^{*}$，此时的$F\left(k\right)$记为${F}^{*}$. 根据式（5）（6），要使$F\left(k\right)$取最小值，需$F'\left(k\right)=0$，也即$k\left(\mathrm{l}\mathrm{n}k-1\right)=\dfrac{a}{b}$，而函数$f\left(k\right)=k(\mathrm{l}\mathrm{n}k-1)$是单调递增的. 对不同的集合操作类型及消息长度，$\dfrac{a}{b}$取值不同，使$F\left(k\right)$取最小值的$k$也不同. 在本文的实验环境中，对同步、广播操作来说，k = 41时$F\left(k\right)$取最小值.

很多情况下，选择其他k值时，F（k）与${F}^{*}$差别不大. 以同步、广播操作为例，在本文的实验环境中，设P = 512，a = 1.12 μs，b = 0.01 μs，$F\left(k\right)$的曲线如图6所示，可以看出，当$24\le k\le 64$时，$F\left(k\right)$相差不大，不超过0.1 μs. 对每种类型、每种长度的集合消息，都可以确定区间$[{k}_{\mathrm{m}\mathrm{i}\mathrm{n}},{k}_{\mathrm{m}\mathrm{a}\mathrm{x}}]$，使得$\forall k\in \left[{k}_{\mathrm{m}\mathrm{i}\mathrm{n}},{k}_{\mathrm{m}\mathrm{a}\mathrm{x}}\right]$时，$|F\left(k\right)-{F}^{*}|\le \varepsilon$成立（$\varepsilon$是常数）. 本文测试环境中使用的k如表2所示（仅显示了部分结果）. 可以发现，随着聚合包长度增大，${k}_{\mathrm{m}\mathrm{i}\mathrm{n}}$及${k}_{\mathrm{m}\mathrm{a}\mathrm{x}}$均逐渐下降. 对该现象的直观解释是：当聚合包长度较小时，聚合包在网络链路上的传输时间在总聚合时间中占比最大，此时应该采用较大的k，从而使得聚合包在网络链路上的传输尽量并行；而当聚合包长度较大时，聚合包在网卡内的处理时间在总聚合时间中占比最大，此时应采用较小的k，以使更多的网卡参与聚合包的处理.

图  6  同步、广播操作的$F\left(k\right)$曲线

Figure  6.  Curve of $F\left(k\right)$ for Barrier and Bcast operation

下载: 全尺寸图片 幻灯片

表  2  测试环境中使用的Ⅰ型聚合树宽度

Table  2.  Type Ⅰ Aggregate Tree Breadth Used in the Test Environment

消息类型	聚合包长度/B	${k}_{\mathrm{m}\mathrm{i}\mathrm{n}}$	${k}_{\mathrm{m}\mathrm{a}\mathrm{x}}$	推荐$k$
Barrier/Bcast	0	32	64	32
Reduce/AllReduce	32	16	63	32
Reduce/AllReduce	64	15	53	32
Reduce/AllReduce	128	13	40	16
Reduce/AllReduce	256	10	28	16
Reduce/AllReduce	512	8	19	16
Reduce/AllReduce	1024	6	12	8
Reduce/AllReduce	2048	5	8	8

下载: 导出CSV 

| 显示表格

3.2   传统的聚合树构建方法

确定k值后就可以构建聚合树了. 式（3）假设任意2个进程间的单播路由经过的链路数相等，但实际情况要复杂得多. 使用相同的k值构造的2棵聚合树值半径${r}_{\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{e}}$可能不同，导致聚合包的传输开销不同. 带度约束的最小半径聚合树问题是NP难的^[19-21]，尚未有高效的求解办法. 本文目标不是构造最优聚合树，而是快速构造出一棵满足度约束条件、半径尽可能小、冲突尽可能少的聚合树. 本节首先介绍2种传统的聚合树构建方法.

3.2.1   k叉树

定义7. k叉树. k叉树是一棵完全树，除最后一个中间节点外，根节点及其他中间节点都有k个子节点，故k叉树是平衡树，每个中间节点处理的聚合包个数相等.

在k叉树中，按广度优先遍历方式为进程编号，根进程编号为0. 若进程在通信域内的编号为my_rank，则其父节点编号为（my_rank−1）/k，第i个子节点编号为my_rank$\times$k+i$(i\ge 1)$.

由于未考虑网络拓扑结构，在胖树网络^[22-23]、蜻蜓网络^[24]等具有分组结构的网络中，k叉树会产生大量的组间通信，导致网络拥塞. 16个进程构建聚合树，其网络拓扑如图7 （a）所示，4叉树如图7（b）所示. 粗线表示该聚合包需要经过最顶层的交换机，图7（b）中共有8个聚合包经过最顶层的交换机. 如果最顶层的交换机传输能力不足，则很容易在顶层交换机处形成拥塞. 而图7（c）是另一棵聚合树，其高度、半径均与图7（b）所示聚合树一样，但仅有2个经过顶层交换机的聚合包，因而具有更优的性能.

图  7  k叉树易产生大量的组间通信

Figure  7.  k-ary aggregate tree is prone to generate lots of inter-group communication

下载: 全尺寸图片 幻灯片

3.2.2   k项树

定义8. k项树. k项树^[25]是一组递归定义的树${T}_{n}$，其中${T}_{0}$是1个单节点的树；而${T}_{n}$是由k棵${T}_{n-1}$连接起来构成的树，其中k−1棵${T}_{n-1}$的根节点直接连接到另外那棵${T}_{n-1}$的根节点上. k项树第i层的节点数是${{(k-1)}^{i}\times \mathrm{C}}_{n}^{i}$，节点总数是${k}^{n}$，高度为n.

图8分别显示了一棵2项树及一棵4项树. 2项树是特殊的k项树，在软件集合通信中已得到了广泛使用，例如在MPICH中短的Bcast、Reduce均是通过2项树实现的^[3]；而大于2的k项树目前使用得较少.

图  8  k项树（k=2, 4）

Figure  8.  k-nomial tree （k=2, 4）

下载: 全尺寸图片 幻灯片

与k叉树不同，k项树中不同深度的节点拥有不同数量的子节点，其中根节点的子节点数最多，为$(k-1)\times \lceil{\mathrm{log}}_{k}P \rceil$；而随着深度的增加，子节点数越来越少，故k项树是非平衡树.

由于k叉树是平衡树，k叉树中上层节点要等待下层节点处理完毕之后才开始处理聚合包，故上层节点会存在空等待现象. 而k项树是非平衡树，位于不同层的节点可以并发处理聚合包，不存在空等待现象.

在k项树中，按深度优先遍历方式为进程编号. 进程编号用k进制表示为${{k}_{n-1}\cdots {k}_{2},{k}_{1},k}_{0}$，其中最低位共有i个0（$0\le i\le n$），则第i个位置0即可得到其父节点编号，从最低的i位中任选一位置为$1,2,\cdots ,k-1$，则得到其子节点的编号最多有$i\times$ （$k-1)$个子节点.

每个进程调用算法1所示的build_k_nomial_tree函数计算parent_rank及children_cnt. 与k叉树一样，k项树也会产生很多跨组通信.

算法1. build_k_nomial_tree.

输入：本进程编号 my_rank，基数k，进程总数P；

输出：父节点parent_rank，子节点数children_cnt， 子节点列表children[].

① mask=1，children_cnt=0；

② while（mask<P）

③ 　if（my_rank%（k×mask）） then

④　　 $parent\_rank=my\_rank/(k\times mask)\times$ $(k\times mask)$；

⑤ 　　 break；

⑥ 　end if

⑦　 mask$=$mask×k；

⑧ end while

⑨ mask$=$mask/k；

⑩ while（mask>0） do

⑪　　for （r=1；r<k；r++）

⑫　　　 child$=$my_rank+mask×r；

⑬　　　 if （child < P） then

⑭ 　　　　children[children_cnt]$=$child；

⑮ 　　　　children_cnt$+=$1；

⑯ 　　　end if

⑰ 　　end for

⑱　　 mask$=$mask/k；

⑲ end while

⑳ 返回parent_rank，children_cnt，children.

3.3   分层k项树构建方法

传统的聚合树构建方法未考虑网络拓扑结构，容易产生较多的组间通信，从而造成网络拥塞. 为解决此问题，本文提出了分层k项树构建方法.

分层思想是优化集合通信的一种重要策略^[26-29]，该策略利用了不同的层具有不同数据传输性能的特点，将同一层内的进程组织成组，使尽可能多的通信在组内完成，以降低层间通信、提升集合消息性能.

在构建Ⅰ型聚合树时，利用分层思想也可以降低聚合过程的时间开销. Zhao等人^[25]提出了一种简单方法：先将进程分为不同的组，并为每个组单独构建一棵k项树；然后将各组的首进程组成一个新的组，并创建一棵k项树，从而将所有组连接起来形成一棵更大的k项树. 进行聚合操作时，同一个组内的进程会先聚合到本组的首进程，首进程再聚合到更高层的首进程，从而大大减少组间通信. 但该方法产生的k项树可能具有较大的高度. 图9举了一个例子：通信域内共有14个进程，依图案分属4个不同的组. 当k = 2时，构建的聚合树如图9（a）所示，其高度为4. 实际上，可以使某个组的首进程连接到另一个组的非首进程下，从而使得聚合树更加平衡，以降低聚合树的高度. 图9（b）即是一棵更优的聚合树，其高度为3. 本文的目标是在最小化组间通信的同时使聚合树高度最低.

图  9  具有分层结构的聚合树

Figure  9.  Aggregate tree with hierarchical structure

下载: 全尺寸图片 幻灯片

3.3.1   问题定义

本文将具有相同通信特性的一组进程称为一个进程组. 例如，位于同一节点内的多个进程，以及位于同一交换机内的多个进程等，均可构成一个进程组. 进程组可以嵌套，从而使得一个进程组可包含多个子进程组，最终构成1个层次结构.

进程组由如图10所示的数据结构定义. 每个进程组都对应一棵k项树，按深度优先方式为k项树内的节点编号. 进程被映射到k项树的某个节点上，树中有些节点可能无映射进程. 该数据结构中，cnt是k项树的节点数，它必须是k的幂；ranks_id是k项树内各节点对应的进程号，nodes_id是各进程对应的k项树节点号；sub_groups定义了属于该进程组的子进程组，共有sub_grp_cnt个子进程组.

图  10  进程组的数据结构

Figure  10.  The data structure of the process group

下载: 全尺寸图片 幻灯片

下面探讨最小高度分层k项Ⅰ型聚合树问题. 给定m个互不相交的进程组${g}_{0},{g}_{1},\cdots ,{g}_{m-1}$，$g$是满足2个条件的进程组：1）$g$包含${g}_{0},{g}_{1},\cdots ,{g}_{m-1}$的所有进程；2）$g$对应的k项树中，除首进程外其余进程的父节点均位于${g}_{i}$内；3）$g$对应的k项树中，每个节点的儿子数不超过硬件限制. 该问题为从中找出具有最小高度的进程组$g$，从而为进程组${g}_{0},g_1,\cdots ,{g}_{m-1}$构建一棵高度最小的分层k项Ⅰ型聚合树. 进程组${g}_{i}(0\le i < m)$内嵌套的子进程组也需满足条件2.

设${g}_{i}^{0}$是进程组${g}_{i}$首进程的进程号，根据k项树的性质，条件2等价于$g.nodes\left[{g}_{i}^{0}\right]\%\left({g}_{i}.cnt\right)=0$且对${g}_{i}$内每个进程${g}_{i}^{j}$有$g.nodes\left[{g}_{i}^{j}\right]/\left({g}_{i}.cnt\right)=g.nodes\left[{g}_{i}^{0}\right]/ \left({g}_{i}.cnt\right)$，也即进程${g}_{i}^{0}$被映射到某个编号为${g}_{i}.cnt$倍数的聚合树节点内，其余进程依次映射到后续节点内.

3.3.2   构建方法

给定m个进程组${g}_{0},{g}_{1},\cdots ,{g}_{m-1}$，且每个${g}_{i}$均已构建好各自的k项树之后，即完成了ranks的设置，采用算法2为这些进程组构建一棵更大的k项聚合树. 算法2采用贪心策略，每次找出2个最大的进程组${g}_{0}$和${g}_{1}$，然后在${g}_{0}$的空闲子树内寻找能够容纳${g}_{1}$的位置. 如果找不到这样的位置，则将${g}_{0}$的聚合树高度加1，即cnt变为原来的k倍，从而使${g}_{0}$内有足够的空余位置容纳${g}_{1}$. 该过程持续下去，直到最终只剩1个进程组为止. 算法2行⑤代码用于为$g\left[i\right]$寻找可用的位置，仅需检查分块的第1个位置是否可用即可判断整个分块是否可用. 行⑫~⑭代码用于将$g\left[{i}\right]$的ranks映射表拷贝到新的聚合树中.

算法2. merge_groups.

输入：子进程组列表$g\left[\right]$及列表长度m，基数k，父 进程组$parent$；

输出：无.

① 将$g\left[0\right],g\left[1\right],\cdots ,g[m-1]$按照cnt字段由大到 小的顺序排列；

② $parent.cnt=g\left[0\right].cnt$；

③ for（i=0；i<m；++i）

④ 　for（j=0；j<$parent.cnt$；j+=$g\left[i\right].cnt$）

⑤ 　　if（$parent.ranks\left[j\right]==-1)$then

⑥　　　 break；

⑦ 　　end if

⑧　 end for

⑨ 　if（$j\ge parent.cnt$） then

⑩　　 $parent.cnt=pareng\times k$；

⑪ 　end if

⑫ 　for（x=0；x<$g\left[i\right].cnt$；++x）

⑬　　 $parent.ranks\left[j+x\right]\leftarrow g\left[\mathrm{i}\right].ranks\left[x\right]$；

⑭　 end for

⑮ end for

采用数学归纳法可证明算法2所产生的k项树是高度最小的分层k项Ⅰ型聚合树，限于篇幅，不再赘述证明过程.

算法3以递归方式为每个层次建立进程到聚合树节点的映射关系. 算法4根据拓扑信息建立分层的k项树. build_hierarchical_tree建立的聚合树中，每个组的进程均位于同一子树内，从而保证除该组的首进程外其余进程均向本组内的进程发送聚合包，故跨组聚合包的个数相比传统聚合树构建方法减少了. 在使用算法4时，需要选择合适的k，以保证聚合树内每个节点的儿子数不超过硬件限制.

算法3. build_rank_mapping.

输入：进程组$g$；

输出：无.

① if（$g.sub\_grp\_cnt==0$）

② 　return；

③ end if

④ for（i=0；i<$g.sub\_grp\_cnt$；++i）

⑤　 build_rank_mappin（$g.sub\_groups\left[i\right]$）；

⑥ end for

⑦ merge_groups（g.sub_groups, g.sub_grp_cnt, k, g）.

算法4. build_hierarchical_tree.

输入：本进程编号my_rank，基数k，进程总数P；

输出：父节点parent_rank，子节点数children_cnt.

① 根据网络拓扑信息构建进程组信息，其中 底层的组其sub_grp_cnt = 0，ranks填充为该 组内各进程的rank号，其他层的组需填充 sub_groups，最高层的组记为$g$；

② build_rank_mapping（$g)$；

③ 遍历$g.ranks$找到my_rank在该数组内的下标 node_id；

④调用build_k_nomial_tree（node_id, k, g.cnt）获得 parent_node_id、子节点列表children及列 表长度cnt；

⑤ parent_rank=$g.ranks[parent\_node\_id]$；

⑥ children_cnt=0；

⑦ for （i=0；i<cnt；i++）

⑧ 　if （$g.ranks\left[children\left[i\right]\right]\ne -1$） then

⑨　　 children_cnt+=1；

⑩　 end if

⑪ end for

⑫ 返回parent_rank及children_cnt.

4.   Ⅱ型聚合树的构建

本节研究构造Ⅱ型聚合树的方法. 构造Ⅱ型聚合树时需要综合考虑网络拓扑、进程位置等因素. 另外，在每个交换机内，每棵Ⅱ型聚合树都占用1个聚合树条目，而硬件支持的聚合树条目是有限的，故创建Ⅱ型聚合树时，还需要考虑是否有可用的聚合树条目.

构造Ⅱ型聚合树时要考虑3个目标：1）最小化聚合树的半径，以降低集合操作延迟；2）尽量让不同的聚合树分布到不同链路上，以降低聚合树间的相互干扰；3）使用尽可能少的聚合树条目，以支持创建更多的Ⅱ型聚合树.

本文分2个步骤构造Ⅱ型聚合树. 1）选择1个交换机作为树根，并构造1棵生成树（称为物理树）；2）对物理树进行裁剪，去掉不需要的交换机.

定义9. 物理树. 设M是某通信域内进程所在的网卡集合，T=（N_T, L_T）是互连网络I=（N, L）的一棵子树，若T满足2个条件，则称T是关于M的物理树：

1）M$\subseteq$N_T；

2）T的叶节点除M中网卡之外，不包含任何其他网卡及交换机.

定义10. 由物理树推导出的Ⅱ型聚合树. 设K是交换机节点的度约束函数，给定互连网络I=（N, L）上一棵关于M的物理树T=（N_T, L_T），由物理树T导出的Ⅱ型聚合树是满足2个条件的树A=（N_A, L_A）：

1）M$\subseteq$N_A$\subseteq$N_T；

2）若$\forall u\in$N_A，$u$在A中的父亲p也是$u$在T中的某个祖先；

3）A中每个交换机sw的子节点数不大于度约束K（sw），其中K（sw）大于sw在T中的子节点数.

实际上，由物理树T导出的Ⅱ型聚合树A可看成是将T中某些节点提升位置而得到的（仅能提升为其祖先的儿子）.

定义11. Ⅱ型聚合树的代价. 设A=（N_A, L_A）是互连网络I=（N, L）上目标集合M对应的一棵Ⅱ型聚合树，A中交换机的个数称为该Ⅱ型聚合树的代价，记为cost（A）.

4.1   选择树根并构建物理树

树根的位置决定了聚合树的半径，应该选择到通信域内各进程最大跳步数最小的交换机作为树根.

本文采用集中式方法构建物理树. 在该方法中，由集中式的网络管理软件选择树根并构建物理树. 网络管理软件维护了网络的状态信息，包括交换机内空闲的聚合树条目数、网络链路的负载情况等. 网络管理软件可根据这些信息选择一个交换机作为树根.

该方法具体过程为：先计算出每个交换机到通信域组内各进程的最小跳步数，据此找到所有的备选树根. 然后根据备选树根的负载情况对备选树根进行排序，优先使用负载低的树根. 选择好一个树根后，就可以构造一棵物理树，使得每个进程到树根的跳步数最少. 然后检查该物理树的每个交换机是否有空闲的聚合树条目可用. 若每个交换机都有空闲的聚合树条目，则返回该物理树；若失败，则尝试下一个树根.

4.2   构建最小代价Ⅱ型聚合树

由物理树导出的最小代价Ⅱ型聚合树问题. 给定互连网络I=（N, L）上一棵关于M的物理树T=（N_T, L_T）及度约束函数K，在由物理树T导出的Ⅱ型聚合树中求代价最小的聚合树${A}^{*}$.

本文利用算法5所示的函数创建最小代价Ⅱ型聚合树. 可以证明算法5产生的聚合树${A}^{*}$是由物理树$T$导出的最小代价Ⅱ型聚合树. 限于篇幅，证明不再赘述.

算法5. build_minimum_type_Ⅱ_tree.

输入：物理树T=（N_T, L_T），度约束函数K；

输出：聚合树${A}^{*}$=（N_A, L_A）.

①记T的根节点为r，若r不是交换机，则返回仅 包含节点r的聚合树；

②否则，对r的每个子节点${s}_{i}$，记以${s}_{i}$为根的子 树为${T}_{i}$，调用build_minimum_type_Ⅱ_tree （${T}_{i},K$）产生由物理树${T}_{i}$导出的最小代价Ⅱ 型聚合树${A}_{i}^{*}$；

③若r仅有1个子节点${T}_{1}$，则返回该子节点对应 的最小代价Ⅱ型聚合树${A}_{1}^{*}$；

④否则，构造一棵树${A}^{*}$=（N_A, L_A），r为根节点，各 ${A}_{i}^{*}$为子树；

⑤若${A}^{*}$中r的子节点数小于r的度约束$K\left(r\right)$，则

⑥ 　从所有${A}_{i}^{*}$中找到一个最小的叶交换机L（叶 交换机是指所有子节点均是网卡的交换 机，最小是指子节点数最小）；

⑦ 　从L中任选一进程p，使p成为r的儿子；

⑧ 　若L删掉p后仅剩1个儿子q，则将q设为 q祖父的儿子并删掉L；

⑨ 　重复过程⑥~⑧，直到r的子节点数等于 $K\left(r\right)$为止；

⑩返回${A}^{*}$.

图11（a）显示了一棵物理树，该树中共有16个进程，使用了13个交换机，每个交换机的度约束均为5；其导出的最小代价Ⅱ型聚合树如图11（b）所示，仅使用了4个交换机.

图  11  一棵物理树及其导出的最小代价Ⅱ型聚合树

Figure  11.  A physical tree and its reduced minimum cost type Ⅱ aggregate tree

下载: 全尺寸图片 幻灯片

5.   在2种聚合树中进行选择

在性能方面，Ⅰ型聚合树与Ⅱ型聚合树各有优势. 对长度较小的集合操作，聚合包的传输时间占主导，而Ⅱ型聚合树中聚合包传输路径较短，故延迟比Ⅰ型聚合树低. 对长度较大的集合操作，规约计算时间占主导，Ⅰ型聚合树可以将规约计算分布到大量网卡中并发进行，故延迟较小. 创建通信域时，需要综合考虑各方面因素，选择使用Ⅰ型聚合树还是Ⅱ型聚合树.

为简化分析，假设Ⅱ型聚合树是标准的d叉树，记$\delta\times l=\alpha$，$\theta+\dfrac{S'}{\beta}+S^*\times\gamma=b$，则Ⅰ型、Ⅱ型聚合树的时间开销分别如式（7）（8）所示. 为简化讨论，仅考虑${S}'={S}^{*}={S}$的情况.

定义如式（9）所示的函数$F(d,k,P,S)$：

可以根据式（9）~（11）分析$F\left(d,k,P,S\right)$的变化趋势，并据此构造一张静态映射表. 给定集合操作类型及消息长度后，通过查表即可快速确定聚合树类型及宽度. 表3列出了本文实验环境中如何根据聚合包长度来选择使用Ⅰ型聚合树还是Ⅱ型聚合树. 当申请不到创建Ⅱ型聚合树所需的通信资源时，需要回退到Ⅰ型聚合树.

表  3  聚合树选择方法

Table  3.  Method to Select Aggregate Tree

d	聚合包长度/B	聚合树类型	$k$
16	（0, 2 048]	Ⅱ 型	16
64	[0, 323]	Ⅱ 型	64
	（323, 512]	Ⅰ 型	16
	（512, 2 048]	Ⅰ 型	8
不能创建Ⅱ 型聚合树时	[0, 64]	Ⅰ 型	32
	（64, 512]	Ⅰ 型	16
	（512, 2 048]	Ⅰ 型	8

下载: 导出CSV 

| 显示表格

6.   性能评估

本节将在新一代神威超级计算机中对聚合树性能进行测试.

6.1   Ⅰ型聚合树性能评估

首先测试不同的Ⅰ型聚合树集合消息的延迟. 对同步、广播、8B长度的规约操作而言，选择k = 32可以获得更好的性能，故分别构造了32叉树、32项树、分层32项树. 使用1个超节点进行测试，每个节点运行2个进程，每个进程使用1个网络端口，这2个端口间的通信不需要经过网络链路. 分别在2种场景下进行测试.

6.1.1   2层标准胖树中的性能

在2层标准胖树中进行测试. 分层32项树使用了3个层次，首先将位于同一节点的2个进程组成1个组，这2个进程间的通信不需要经过网络链路；然后将位于同一交换机内的16个进程组成1个组，该组内的进程通信时仅需经过2条链路；最后将位于同一超节点内的所有进程组成1个组，该组内的进程通信时需经过4条链路.

图12显示了Bcast-8B，Bcast-2KB这2种集合操作的测试结果. 可以看出：1）大部分情况下32叉树、32项树几乎具有相同的延迟；2）大部分情况下，分层32项树的延迟低32叉树、32项树约0.6 μs. 分层32项树延迟低的原因是：它先把位于同一节点内的2个进程组成1个组，而这2个进程间通信不需要经过网络链路，故延迟较低. 需要指出的是，进程数较少时分层32项树的延迟反而高于另外2种聚合树，原因是此时的分层32项树的高度大于32叉树、32项树；随着进程数的增多，这3种聚合树将具有相同的树高.

图  12  标准胖树拓扑中不同进程数下3种聚合树的消息延迟

Figure  12.  Messages latency of three types of aggregate trees for different count of processes in standard fat-tree topology

下载: 全尺寸图片 幻灯片

不同消息长度时3种构造方法下的聚合树的性能如图13所示. 测试时使用了512个进程，每个进程使用1个网络端口. 测试结果与图12的测试结果一致，即32叉树和32项树的性能相当，而分层32项树的延迟明显低于32叉树和32项树.

图  13  标准胖树拓扑中不同消息长度下3种聚合树的消息延迟

Figure  13.  Messages latency of three types of aggregate trees for different message sizes in standard fat-tree topology

下载: 全尺寸图片 幻灯片

6.1.2   2层裁剪胖树中有噪声干扰时的性能

使用如图14所示的裁剪胖树进行测试. 该拓扑中，同一交换机内的不同网络端口向其他交换机内的网络端口发消息时会共享一条通信链路. 测试时还在网络中加入了网络噪声，该噪声消耗约80%的网络带宽.

图  14  测试使用的2层裁剪胖树示意图

Figure  14.  Illustration of two-layer pruned fat-tree used in the test

下载: 全尺寸图片 幻灯片

分别测试不同进程数时3种方法构建的聚合树的性能，并将之与标准胖树下的测试结果进行了对比，结果如图15所示. 可以看出，加入网络噪声后，3种构建方法的集合消息延迟相比标准胖树下有显著增大. 其中32叉树增幅最大，分层32项树增幅最小.

图  15  裁剪胖树拓扑下有干扰时集合通信消息延迟

Figure  15.  Collective messages latency in pruned fat-tree topology with inference

下载: 全尺寸图片 幻灯片

图16显示了进程数为512时，3种方法构建的聚合树中跨组聚合包的数量，其中每条实线上的数字表示该实线所连接的2个交换机间的聚合包个数. 在32叉树中，大量聚合包发送到1号交换机的不同进程内，故每个集合操作中，0号交换机与1号交换机间链路上需传输496个聚合包，从而产生严重的链路竞争.

图  16  裁剪胖树下3种聚合树构建方法的跨组聚合包

Figure  16.  Inter-group aggregation packets of three types of aggregate trees constructed methods in pruned fat-tree

下载: 全尺寸图片 幻灯片

表4显示了不同进程数时3种聚合树下Bcast-8 B 的延迟对比，可以看出，在存在噪声干扰的情况下，分层32项树的延迟相比传统的聚合树构建方法下降了24%~89%. 这表明，相比另外2种聚合树构建方法，分层32项树具有更少的跨组聚合包，因而存在带宽竞争的情况下可以显著降低集合消息的延迟.

表  4  裁剪胖树拓扑下有干扰时不同进程数下Bcast-8B延迟

Table  4.  Bcast-8B Latency for Different Count of Processes in Pruned Fat-tree Topology with Inference

进程数	32叉树下 延迟/μs	32项树下 延迟/μs	分层32项树 下延迟/μs
64	19.92（↓39%）	17.79（↓32%）	12.11
128	25.11（↓49%）	18.58（↓31%）	12.75
192	35.75（↓64%）	18.54（↓31%）	12.73
256	42.87（↓70%）	18.62（↓32%）	12.75
320	71.81（↓82%）	18.86（↓32%）	12.83
384	97.33（↓86%）	18.94（↓30%）	13.33
448	115.82（↓87%）	18.80（↓26%）	13.94
512	136.60（↓89%）	19.48（↓24%）	14.89
注：括号内的百分比表示分层32项树相比32叉树、32项树的延迟下降比例；↓表示分层32项树相比32叉树、32项树的延迟下降比例.

下载: 导出CSV 

| 显示表格

需要注意的是，随着进程数的增大，32项树的延迟增加较缓慢，而分层32项树的延迟增加略快（分层32项树相比32项树的延迟下降比例由进程数为64时的32%下降为进程数为512时的24%）. 这是因为，在裁剪胖树中，随着进程数的增大，32项树中每条链路上传输的最大聚合包数保持为16，故32项树的延迟变化不大；而分层32项树中每条链路上传输的最大聚合包数由1逐渐增大到31，故分层32项树的延迟会缓慢增加. 但可以肯定的是，随着进程数的进一步增大，分层32项树的延迟仍低于32项树，这是因为32项树中每2个相邻交换机间都需要传输16个聚合包，从而更易受网络噪声的干扰.

除此之外，本文还在其他场景下测试了3种聚合树构建算法的消息延迟. 例如，利用更多超节点进行了测试，其网络拓扑采用3层裁剪胖树，故分层32项树可采用更多的层次. 此实验的测试结论与上述测试结论一致，即分层32项树延迟最低，32项树次之，32叉树延迟最高. 限于篇幅，不再赘述其详细测试数据.

6.2   Ⅱ型聚合树性能评估

6.2.1   Ⅱ型聚合树延迟测试

本节对Ⅰ型聚合树及Ⅱ型聚合树的性能进行对比. 测试环境如图17所示. 其中Ⅰ型聚合树采用64叉树进行构建，Ⅱ型聚合树的树根建在最高层的那个交换机上. 分别测试了不同进程数下2种类型聚合树的性能，Bcast-8 B及Bcast-2 KB的延迟如图18所示. 可以看出，Ⅱ型聚合树的延迟比Ⅰ型聚合树低1 μs左右.

图  17  使用网络拓扑对比Ⅰ型聚合树及Ⅱ型聚合树性能

Figure  17.  Network topology used to compare the performance of type Ⅰ and type Ⅱ aggregate trees

下载: 全尺寸图片 幻灯片

图  18  Ⅰ型聚合树及Ⅱ型聚合树的性能对比

Figure  18.  Performance comparison of type Ⅰ and type Ⅱ aggregate trees

下载: 全尺寸图片 幻灯片

6.2.2   Ⅱ型聚合树资源使用量测试

本节测试最小代价Ⅱ型聚合树构造算法的有效性以及不同通信模式下聚合树条目的使用情况.

MPI集合通信中，一般将进程划分为2维或3维网格通信域，其每个维度中的每行或每列都是一个通信域. 本文测试了5种典型的通信模式，包括2种2维网格结构、2种3维网格结构，以及1种随机模式. 选择的2维网格结构中，256$\times$160通信模式按拓扑结构划分通信域，模拟拓扑感知的通信模式，即第1维有160个通信域，故每个通信域都位于同一个超节点内；而202$\times$202通信模式存在很多跨超节点的通信域，模拟拓扑无感的通信模式. 2种3维网格结构也是按类似原则进行划分的. 随机模式是指进程随机加入一个通信域.

下面从2个方面证明最小代价Ⅱ型聚合树构造算法的有效性：一方面，最小代价Ⅱ型聚合树占用的聚合树条目数相比传统方法构建的Ⅱ型聚合树有显著下降；另一方面，最小代价Ⅱ型聚合树构建算法创建聚合树时的失败率相比传统的Ⅱ型聚合树也有显著下降.

1） 聚合树占用的总条目数

首先测试每种通信模式下聚合树占用的总条目数. 假设每个交换机内的聚合树条目数足够多. 对于每种通信模式，依次为每个通信域构建Ⅱ型聚合树，并统计占用的聚合树条目总数，结果如图19所示. 其中，传统方法构建的Ⅱ型聚合树是指利用集中式方法构建的物理树. 可以看出，所有通信模式下，最小代价Ⅱ型聚合树占用的条目总数明显低于传统方法构建的聚合树所占用的条目数，最少下降了90%. 这表明最小代价Ⅱ型聚合树算法在降低聚合条目使用量方面具有显著效果. 有些通信模式下，最小代价Ⅱ型聚合树的聚合树条目总数等于通信域个数，这是因为在这些通信模式下，每个通信域的最小代价Ⅱ型聚合树都仅使用1个交换机.

图  19  不同通信模式下Ⅱ型聚合树使用的总聚合树条目数

Figure  19.  Total count of aggregate tree entries used by type Ⅱ aggregate trees for different kinds of communication patterns

下载: 全尺寸图片 幻灯片

2）创建聚合树时的失败率

将每个交换机的聚合树条目数设为16，然后在每种通信模式下依次为每个通信域构建Ⅱ型聚合树，并记录创建失败的次数. 定义创建聚合树时的失败率为：$\mathrm{失}\mathrm{败}\mathrm{率}=\dfrac{\mathrm{失}\mathrm{败}\mathrm{次}\mathrm{数}}{\mathrm{通}\mathrm{信}\mathrm{域}\mathrm{总}\mathrm{数}}$，结果如图20所示. 可以看出，最小代价Ⅱ型聚合树算法均能为每个通信域成功构建聚合树；而传统的Ⅱ型聚合树构建方法失败率很高，最高可达74.51%.

图  20  不同通信模式下创建Ⅱ型聚合树的失败率

Figure  20.  Failure rate of creating type Ⅱ aggregate trees in different communication patterns

下载: 全尺寸图片 幻灯片

需要指出的是，将交换机的聚合树条目数设为更小的值后，某些通信模式下也存在不能创建最小代价Ⅱ型聚合树的情况，但其失败率仍低于传统的Ⅱ型聚合树构建方法，结果不再赘述.

综上所述，最小代价Ⅱ型聚合树算法可以显著减少对交换机内聚合树条目资源的占用，从而可以支持创建更多的Ⅱ型聚合树.

7.   结　　论

硬件集合通信中，聚合树对集合操作的性能具有重要影响. 构建聚合树时，需要综合考虑聚合树半径、宽度、负载均衡、网络噪声等的影响. 本文提出了硬件集合通信开销模型，并据此提出了3种构建聚合树的方法，包括：1）根据聚合包大小确定Ⅰ型聚合树的宽度；2）最小高度分层Ⅰ型聚合树构建方法；3）最小代价Ⅱ型聚合树构建方法. 然后在神威互连网络中对聚合树构建方法进行了全面测试，在存在网络噪声的情况下，分层Ⅰ型聚合树的消息延迟相比传统构建方法下降了24%~89%；最小代价Ⅱ型聚合树使用的交换机聚合条目数相比传统构建方法下降了约90%.

下一步，我们将利用真实的应用程序对聚合树构建方法的性能进行更全面的测试. 另外，我们还将研究如何利用硬件集合通信提升长度较大的规约、广播等集合操作的性能，扩大硬件集合通信的适用范围.

作者贡献声明：陈淑平提出研究思路，设计算法、实验，分析实验数据并撰写论文；尉红梅指导算法及完善实验方案；王飞、李祎负责算法实现、测试数据的整理与分析；何王全、漆锋滨提出研究课题，把握论文创新性，并对论文进行修改.