陈淑平，周慧霖，何王全，漆锋滨

1.江南计算技术研究所，江苏 无锡 214083

2.国家并行计算机工程技术研究中心，北京 100080

近年来，随着高性能计算即将迈入E级时代，超级计算机的规模变得越来越大，拥有的处理器数及核心数越来越多。例如，2020年6月份全球Top500排名第一的富岳系统[1-2]拥有7 299 072个核心。与之相应，高性能计算应用的性能越来越依赖于互连网络的性能，尤其是集合通信的性能[3-5]。集合通信可以通过点对点消息实现，也可以通过专用的硬件集合操作实现。很长一段时间以来，无论是在广域网还是在数据中心网络中，硬件支持的集合操作由于其复杂度、可扩展性、容错等方面的原因，并未得到广泛应用。因此MPICH、MVAPICH、OpenMPI等[6-9]均基于点到点消息以软件方式实现集合通信。但是，基于点到点消息实现的集合操作，其性能与硬件支持的集合操作相比存在不小的差距。一是同样的数据包在某些链路上会传输多次，造成资源浪费。二是缺乏获取底层网络拓扑信息的能力，使得集合操作的逻辑结构不能适配底层网络的物理结构，导致其无法充分利用底层网络的传输能力。随着系统规模的不断扩大，以软件方式实现的集合操作面临越来越严重的性能问题。而硬件支持的集合操作具有性能高、CPU占用率低等优点，正受到越来越多的关注。因此，近几年出现了很多硬件集合通信技术，如Mellanox的SHARP技术[10]。

硬件支持的集合操作中，多播技术是重要的支撑。集合通信中的Bcast、Barrier、AllReduce、AllGather等操作需要将相同的数据分发给参与集合通信的不同进程，它们均可通过硬件支持的多播进行加速。多播路由算法对多播操作的性能具有至关重要的影响。Infiniband网络中，子网管理OpenSM[11-12]负责生成多播表，基本原理是构建一棵多播树覆盖参与多播操作的所有节点，利用多播树实现多播功能。多播树的高度及负载均衡性对多播消息的性能具有决定性的影响。多播路由算法的设计目标包括：尽量降低多播树高度，以降低多播操作延迟；在不同多播组间进行负载均衡，以降低单条链路的负载；缩短计算路由的的时间，以满足快速构建大量多播组的需求。

OpenSM目前支持9种路由算法，它们使用的多播路由方法概括起来分为2类，分别是MINIHOP-MC及SSSP-MC。它们在大规模互连网络环境下均存在问题。MINIHOP-MC算法在构建多播树时根据最小跳表从所有交换机中选出一个到多播组内各成员最大距离最小者作为多播树的根，因此构建出的多播树高度必定是最低的；但该算法未考虑多播路由均衡性问题，会出现大量多播组共用同一条链路甚至同一个树根的情况，严重影响多播消息的性能。而基于单源最短路径的SSSP-MC算法虽然考虑了多播路由均衡性，但该算法不管多播组有多少个成员都需要计算树根到网络中所有节点的最短路径，因此构建路由表的时间开销很大，不能满足存在大量多播组的应用场景的需求。综上所述，这两种多播路由算法均不适用于大规模互连网络环境。

为此，本文提出一种负载均衡的多播路由算法，试图在大规模互连网络环境中快速构建负载均衡的多播路由。该算法采用2种负载均衡策略，根据局部负载信息进行多播路由选择，在保证多播树高度最低的前提下，尽量将不同多播组分散到不同链路上，可应用于存在大量多播组的超大规模互连网络环境中。

1 概念及定义

1.1 基本概念

定义1（互连网络）互连网络定义为一个有向图I:=G(N,C)，其中N为网络节点集合，C为通信链路集合。网络节点又分为终端节点及交换机。终端节点一般是网卡设备，用于收发数据；而交换机用于转发数据。

定义2（多播组，MCG）多播组是网络节点集N的一个子集，其成员可以是终端节点，也可以是交换机。一个多播组中的成员发送的消息可以被同一多播组中的其他成员接收。每个多播组用multicast GID（MGID）标识。

定义3（多播树，MCT）多播树是互连网络有向图的一个子图，对应互连网络中的一棵树。该树内的一个节点发送数据时，会复制到该树内的所有节点中。

定义4（edge forwarding index，EFI）文献[13-14]将EFI定义为经过某链路的路由条数。在多播路由中，将其定义为经过该链路的多播组个数。最大链路EFI记为一定程度上反映了路由均衡程度。π(G,R)越大，表示拥塞程度越高。链路EFI对多播操作性能具有重要影响，多播路由算法需要尽量降低链路EFI。

定义5（最小跳表）每个交换机都有一张最小跳表，逻辑上组织成二维表格形式，行号为i、列号为j的单元记录了从该交换机的端口j出发到LID为i的目标节点的最小跳步数。j为0时记录的是所有端口中到LID为i的目标节点的最小跳步数。在完成拓扑探查后，OpenSM利用获取到的连接信息为每个交换机构建最小跳表。

1.2 影响多播消息性能的因素

多播操作的性能受多播树高度及链路EFI等的影响。仅考虑一个多播组时，多播树高度对集合操作性能至关重要。当网络中有多个多播组同时收发消息时，链路EFI对集合操作的性能也有重大影响。下面将通过实验说明，多播树高度及链路EFI都会对多播操作的性能产生重要影响。

1.2.1 多播树高度

多播树高度会影响集合操作的延迟。多播树越高，多播数据包的传输路径就越长，其延迟就越大。构建了如图1所示的实验环境，分别进行了2组测试。每组测试均使用4个进程构成的多播组进行多播操作，但每组测试中的进程距离不同。第一组测试中，4个进程位于物理临近的终端节点上，其对应的多播树高度为1。第二组测试中，4个进程分散在不同交换机上，对应的多播树高度为2。在每组测试中都对各种长度的消息进行5 000次测试，分别计算平均延迟及99%消息尾延迟。其中99%消息尾延迟的计算方法为：对这5 000个消息的延迟进行排序，取末尾第4 950（5 000×99%）个消息的延迟。

图1 用于测试多播树高度对多播性能影响的实验环境Fig.1 Experimental environment for testing effect of tree height on multicast performance

测试结果如表1所示。可以发现，无论是8 B长度的小消息，还是2 KB长度的大消息，第二组测试的延迟数据较第一组测试均有明显增加。这表明多播树高度对多播消息延迟具有不可忽视的影响。可以预见，随着广播树高度的增大，延迟增加会更加明显。另外，消息长度不同，延迟增大的幅度略有差异，长度较大的消息与长度较小的消息相比，其延迟增长幅度小。对8 B长度的小消息来说，无论是平均值还是99%尾延迟都增长了约20%；对2 KB长度的消息来说，平均值及99%尾延迟增长幅度均在15%左右。这是因为对长消息来说，增加的跳步数导致的时间开销相比数据拷贝的时间开销小。

表1 不同树高下的多播消息延迟Table 1 Multicast message latency for different tree height μs

1.2.2 链路EFI

当有大量多播组经过同一条链路，从而使该链路的EFI变得很大时，集合操作的性能会受到较大影响。构建了如图2所示的实验环境，以说明链路EFI对多播消息性能的影响程度。该实验中，每4个相邻的终端节点组成一个多播组，但所有多播组都使用粗线所示的同一棵多播树，因此链路EFI等于创建的多播组的个数。例如，EFI为1，表示仅使用4个终端节点，创建1个多播组；EFI为128，表示使用512个终端节点，创建128个多播组。当创建了多个多播组时，由于这些多播组共用同一棵多播树，一个多播组发送的数据会复制到使用同一多播树的其他多播组内，从而对其他多播组的性能带来影响。分别测试了不同EFI下多播操作的延迟，每种EFI下各多播组同时发送消息，均进行5 000次测试，分别计算平均延迟及99%消息尾延迟。结果如表2所示。

图2 用于测试EFI对多播性能影响的实验环境Fig.2 Experimental environment for testing effect of EFI on multicast performance

表2 不同EFI下的多播消息延迟Table 2 Multicast message latency for different EFI μs

可以发现，对8 B长度的小消息来说，随着EFI的增加，延迟会略有增加，但是由于数据长度很小，即使有多个广播组经过同一条链路，也不会对延迟造成很大影响。而对2 KB消息来说，由于数据较大，EFI增大带来的影响会比较明显。例如EFI为16时，平均延迟会增大约38%；EFI为128时，平均延迟会增大约1 066%。因此，链路EFI会对大量使用广播操作的应用程序性能带来重要影响。

结合上面2个实验的结果，给出多播路由算法的设计目标，包括：（1）最小化多播树的高度，以降低多播消息延迟；（2）尽量降低链路EFI，使不同多播组尽量分布到不同链路上，降低不同多播组间的相互干扰；（3）构建多播路由算法的时间开销要尽量低，以满足超大规模互连网络中快速创建大量多播组的需求。对多播路由算法的评价也是从上述3个方面进行的。

2 IB中现有的多播路由算法

OpenSM目前支持MINIHOP、UP/DN、DN/UP、FTREE、LASH[15-16]、DOR、TORUS-2QoS、NUE[17]、DFSSSP[18-19]等9种路由引擎。它们使用的多播路由算法概括起来分为2类，分别是MINIHOP-MC及SSSP-MC。两者都是从树根开始自顶向下构建多播树，区别在于MINIHOP-MC是基于最小跳表构建多播树，而SSSP-MC是基于单源最短路径算法构建多播树。

2.1 MINIHOP-MC

MINIHOP-MC基于最小跳表构建多播树。为某个多播组构建多播树时，分为两个步骤。

一是选择一个交换机作为树根，选择的依据是树根到多播组各成员的最大距离或平均距离在所有交换机中是最小的。

二是根据最小跳表，从树根出发自顶向下递归地构建一棵树。具体过程如下：（1）从树根开始，对多播组的每个成员mcm，都查询树根的最小跳表中对应mcm的行，找出跳数最小的端口，然后将mcm加入该端口对应的子树，从而将各成员分到不同子树中。（2）然后对每个子树，递归进行上述过程，将属于该子树的多播组成员划分为更小的子树，直到子树不能再拆分为止。

伪代码描述的构建过程见算法1。

算法1 MINIHOP-MC

MINIHOP-MC产生的多播树一定是高度最低的。另外，代码第8行在选择下行端口时，如果同时存在多个跳步数最少的端口，则只能选择固定的一个端口，而不能通过负载均衡机制将多播包分发到多条路径上，否则会形成环。MINIHOP-MC也没有考虑多个多播组间的负载均衡问题，即多个多播组可能共用同一个根或同一条链路，在存在大量多播组时，这会带来严重的性能问题。

2.2 SSSP-MC

SSSP-MC基于单源最短路径算法构建多播路由，一定程度上考虑了负载均衡问题。当选择树根后，SSSP-MC以网络中的所有交换机作为节点，以经过各链路的多播组个数作为权重，利用单源最短路径算法算法（如Dijkstra）计算树根到所有节点的单源最短路径，从而构造出一棵树。为保证从树根到各节点的路径都是最短路径，需要为每个链路设置一个足够大的初始权值，使得选择长路径永远比选择负载重的路径代价高。伪代码描述的SSSP-MC算法见算法2。

算法2 SSSP-MC

SSSP-MC可以将多播组分布到不同的链路上；缺点是运行时间较长，不适用于超大规模互连网络。原因是不管多播组有多少个成员，SSSP-MC都需要计算树根到网络中所有节点的最短路径。因此对互连网络G(N,C)来说，SSSP-MC算法的时间复杂度为Θ( ||C+ ||N lb ||N)，仅跟网络规模有关，而跟多播组大小无关。

2.3 实际课题中多播组使用模式

MPI集合通信中，主要有2种通信域划分方法，一是将所有进程划分成二维或三维网格，每个维度中每行都是一个通信域，对应一个多播组。二是划分成层次结构，例如树型结构，每层分成很多组，每个组构成一个通信域；每个组再选出一个leader，形成更高层次的组。在大规模互连网络环境下，按上述两种通信域划分方法划分进程时，都会产生大量多播组，而每个多播组内的成员个数却较少。当系统中存在大量规模较小的多播组时，MINIHOP-MC及SSSP-MC这两种多播路由算法均存在问题。对MINIHOP-MC来说，由于没有进行负载均衡，存在大量多播组共用同一条链路的情况，从而导致严重的性能问题。对SSSP-MC来说，虽然多播组很小，仍需计算树根到网络中所有节点的最短路径，导致创建多播组的时间很长，不能满足大规模互连网络的需求（后面实验将会看到，有时需要数几分钟才能完成所有多播组的创建）。因此，这两种路由算法均不适用于大规模互连网络环境。

需要一种适用于各种拓扑，能够自动进行负载均衡，且运行速度足够快的多播路由算法，以适应大规模互连网络中应用程序的使用模式。

3 FULB-MC多播路由算法

本章将描述一种负载均衡的通用快速多播路由算法FULB-MC。与现有多播算法的重要区别在于，FULBMC采用树根轮换及链路轮换策略进行负载均衡。另外，为了适应HPC环境，提出了新的多播组加入、离开机制及协议。FULB-MC还采用自底向上构建多播树的方法，目的是在避免形成环的同时提升算法运行速度。

3.1 自底向上的多播树构造方法

MINIHOP-MC及SSSP-MC均是从树根开始自顶向下构建多播树。而FULB-MC在选择树根之后，采用自底向上构建多播树的策略，目的是在避免形成环的同时提升算法运行速度。FULB-MC与MINIHOP-MC相似，均是基于最小跳表构建多播树。与MINIHOP-MC不同，FULB-MC通过2种简单的策略在多个多播组间进行负载均衡。

（1）树根轮换策略：在选择树根时，如果有多个交换机满足条件，则根据交换机的负载情况从中选择一个负载最轻的。

（2）链路轮换策略：选择树根后，每次从多播组的一个成员出发，根据最小跳表选择一条从该成员到树根的最短路径。每次经过一个交换机选择下一跳时，如果有多个端口都是跳步数最少的，则从中选择一个负载最轻的。为避免产生环，在从叶子到树根的前进过程中，如果遇到了以前访问过的节点，则重用以前构建的该中间节点到树根的路径。

伪代码描述的算法如下所示。hops是交换机的最小跳表，hops[root][0]记录的是所有端口中到树根的跳步数的最小值。代码第1到19行选择一个交换机作为树根。第20到33行为每个多播组成员构建一条到树根的最短路径。

算法3 FULB-MC

FULB-MC构建的多播树一定是高度最低的。另外，它使用贪心策略，无论是选择树根，还是选择多播链路时，总是根据局部负载信息进行负载均衡决策。而SSSP-MC算法则根据全局信息进行负载均衡决策。后面的实验中将会看到，FULB-MC算法虽然使用局部信息进行负载均衡决策，仍可以达到很好的负载均衡效果。

FULB-MC算法的运行时间与多播组的大小有关。当存在大量规模很小的多播组时，相比SSSP-MC，这将节省大量计算时间。不考虑选择树根的时间，在最坏情况下，其运行时间上限为O( ||E+ ||N)，即访问每个节点及每条链路各一次。

3.2 多播成员加入/离开机制

IB协议中原有的多播机制并不适用于HPC领域。原因是：多播组成员可以动态加入或离开多播组，导致每次多播组成员发生变化后都需要重新计算、更新路由，使多播路由处于暂时不可用状态的概率大大增加。

针对高性能计算应用的需求，设计了一套新的加入/离开多播组机制，以解决频繁重算路由的问题。加入多播组时，不是每收到一个加入多播组的请求就计算路由，而是等收齐同一个多播组的所有请求之后再计算路由。一个成员离开多播组后，也不重算路由；仅当所有成员均离开后，再删掉该多播组。

如图3所示，构建一个多播组需要4个步骤：

图3 加入多播组的过程Fig.3 Process used to join multicast group

（1）所有进程都向Open SM发送Subn AdmSet（MCMemberRecord），以请求加入多播组。请求中携带了参与该多播组的成员个数。需要修改IB协议的McMemberRecord属性，添加MemberCount字段，以记录该多播组中的成员数量。

（2）OpenSM收到第一个请求后，创建多播组，但不会立即计算多播路由。仅当收齐该多播组的所有请求后，才开始计算多播路由。

（3）0号进程发出加入多播组的请求后，周期性地向OpenSM发送SubnAdmGet（MCGStateRecord）以查询多播组状态。需要对现有的IB协议进行扩展，增加MCGStateRecord属性，用于报告多播组的状态。多播组可处于下列状态：①ReceivingJoinReq，表示正在接收加入多播组的请求；②ComputingRoutes，表示正在计算路由；③Ready，表示路由已计算完毕，可以使用该多播组发送数据；④ReceivingLeaveReq，表示正在接收离开多播组的请求；⑤Destroying，表示该多播组正在被销毁。

OpenSM计算完多播路由后，向0号进程返回SubnAdm-GetResp（MCGStateRecord）应答，其状态为Ready。

（4）0号进程收到多播组可用的通知后，通过多播操作将通知转发给其他进程，从而完成多播组的构建。每个进程在收到该通知后，即可使用该多播组进行通信。

OpenSM负责维护每个多播组的状态，其状态转换图见图4。由于某个进程崩溃或加入多播组的请求丢失而导致OpenSM不能在规定时间内收齐加入多播组的请求时，该多播组则由ReceivingJoinRequest状态转到Destroying状态，并开始销毁该多播组。同样，在ReceivingLeaveReq状态下未在规定时间内收齐离开多播组的请求，则转为Destroying状态，销毁该多播组。

图4 多播组状态转换示意图Fig.4 State transition diagram for multicast group

4 实验评价

在OpenSM中实现了FULB-MC。本章将在不同拓扑结构下对FULB-MC的性能进行测试，这些拓扑结构包括几种典型的标准拓扑结构（包括标准胖树[20-21]、3D环网、蜻蜓网络[22]等），以及2个超算中心实际使用的拓扑。使用ibsim-0.7模拟各种网络拓扑，使用测试程序模拟发起加入或离开多播组的请求。OpenSM的版本号为3.3.22，运行在一台x86服务器上，处理器为32核Intel Xeon E5-2630 v3，频率为2.40 GHz。

实验中，每个处理器上运行一个或多个进程。与实际课题通信模式一样，将这些进程划分成不同的通信组，为每个通信组建立一个多播组。一个进程可同时参与多个通信组，例如，当按三维网格结构划分通信组时，每个进程将参与3个多播组。对每种拓扑结构，都测试了多种典型的多播通信模式，包括二维网格、三维网格，以及随机产生的多播组。其中部分通信模式按拓扑结构划分进程，模拟拓扑感知的通信行为，而另外的通信模式则模拟拓扑无感的通信行为。

4.1 典型的标准拓扑结构

4.1.1 3层标准胖树

采用40端口交换机构建标准3层胖树结构，终端节点个数N=16 000。表3显示了每个处理器上运行1个进程时各种多播路由算法的最大EFI。

表3 3层胖树下各路由算法的最大EFITable 3 Maximum EFI of each algorithm under 3-layer FT

可以看出，在所有通信模式下，MINIHOP-MC及SSSP-MC的最大EFI都远远大于FULB-MC。出现该现象的原因是：MINIHOP-MC及SSSP-MC在选择树根时，总是使用第一个满足树高最低条件的交换机，导致大量多播组使用同一个树根。另外，MINIHOP-MC与SSSP-MC在所有通信模式下最大EFI均相同。这是由标准胖树的结构决定的：叶子交换机与顶层交换机间仅有一条最短路径，只要选择的树根相同，则它们构建的多播树完全相同。SSSP-MC虽然利用Dijkstra算法进行了大量运算，但最终效果跟MINIHOP-MC完全一样。

后面测试中，对原始MINIHOP-MC及SSSP-MC算法进行了修改：与FULB-MC一样，在有多个根可供选择时，从中选择负载最轻的一个。修改后的算法分别称为MINIHOP-MC-new及SSSP-MC-new。后面的测试中，原始MINIHOP-MC及SSSP-MC算法的最大EFI均很大，不再赘述其测试结果，而仅显示改进后的MINIHOPMC-new及SSSP-MC-new算法下的测试结果。标准胖树中MINIHOP-MC-new及SSSP-MC-new算法在每种通信模式下的最大EFI与FULB-MC完全相同，不再显示其结果。

表4显示了每个处理器上运行1个进程时各路由算法的运行时间。FULB-MC明显低于SSSP-MC，由最大2.4 s缩短为低于0.2 s。需要指出的是，该时间仅包括计算路由的时间，不包括发送加入多播组请求、选择树根、分发路由等其他步骤的时间。

表4 3层胖树下各路由算法的运行时间Table 4 Runtime of each algorithm under 3-layer FT s

4.1.2 3D-Torus

构造了30×20×20的3D-Torus网络，每个交换机连接2个终端节点，终端节点个数为N=24 000。表5及表6分别显示了每个处理器上运行1个进程时的最大EFI及运行时间。在运行时间方面，FULB-MC远低于SSSP-MC-new，由最大24 s缩短为低于2.3 s。

表5 3D-Torus下各路由算法的最大EFITable 5 Maximum EFI of each algorithm under 3D-Torus

表6 3D-Torus下各路由算法的运行时间Table 6 Runtime of each algorithm under 3D-Toruss

在3D-Torus中，多播组成员到树根的最短路径有多条，因此大部分通信模式下FULB-MC及SSSP-MC-new可以获得低于MINIHOP-MC-new的最大EFI。但在240×100通信模式下，MINIHOP-MC-new的EFI反而低于另外2种负载均衡算法。这是因为该通信模式与网络拓扑结构正好匹配，使得MINIHOP-MC分配的多播树正好是最优的；而SSSP-MC-new及FULB-MC在做路由均衡时，不是从全局的角度优化EFI，而仅仅是从当前新创建多播组的角度优化EFI，在某些时刻会选择非最优的路径。

以一个例子进行更直观的解释。如图5所示，浅灰色交换机是某个多播组的成员，深黑色交换机是其树根，（a）、（b）分别是两棵多播树。可以看出（a）经过的链路数较少，（b）经过的链路数较多。SSSP-MC-new及FULB-MC在做路由均衡时，可能构造出如（b）所示的多播树，进而导致EFI升高。而MINIHOP-MC-new使用固定的一条路径，有可能恰好避开这些代价高的路径。实际上，MINIHOP-MC-new也有可能固定使用图5（b）所示的多播树，从而恰好每次都选择代价高的路径。径则经过2条全局链路，选择后面那条路径可能会导致全局链路的拥塞，从而出现了SSSP-MC-new及FULBMC的EFI略高于MINIHOP-MC-new的情况。但是，如果修改MINIHOP-MC-new的实现，使其优先使用编号大的端口，则MINIHOP-MC会使用第二条路径，导致其最大EFI大于另外两种路由算法。出现该现象的根本原因在于SSSP-MC-new及FULB-MC在做路由均衡时，不是从全局的角度优化EFI。

图5 3D环网下为同一个多播组构建的两棵多播树Fig.5 Two multicast trees for same MCG in 3D-Torus

4.1.3 蜻蜓网络

配置参数为a=18,p=h=9，即每个组中有18个交换机，每个交换机连接9个处理器，有9条全局链路，终端节点个数N=26 406。最大EFI及运行时间分别见表7、表8。与前面测试结果一样，在运行时间方面，FULB-MC远低于SSSP-MC-new。

表7 蜻蜓网络下各路由算法的最大EFITable 7 Maximum EFI of each algorithm under DF network

表8 蜻蜓网络下各路由算法的运行时间Table 8 Runtime of each algorithm under DF networks

蜻蜓网络中，多播组成员到树根的最短路径可能有多条。但很多情况下，MINIHOP-MC-new的EFI反而比另外2种算法略低。例如，在81×27×12模式下，MINIHOP-MC-new的最大EFI为41，而FULB-MC达到了54。这是由蜻蜓网络特殊的拓扑结构导致的。如图6所示，Group 0内交换机B下连接的终端节点与Group 1内交换机X下连接的终端节点通信时，有2条最短路径，分别为B→D→E→X以及B→A→C→X。本文的实现中，MINIHOP-MC优先使用编号小的端口，而B→D的链路使用的端口号小于B→A的链路使用的端口号，因此MINIHOP-MC-new使用第一条路径。而SSSP-MC-new及FULB-MC轮流使用这两条路径；但实际上，在这两条路径间进行负载均衡有时不会带来好处，因为第一条路径仅经过一条全局链路，而第二条路

图6 蜻蜓网络下B到X的两条路径Fig.6 Two paths from B to X in Dragonfly network

4.2 超算中心的拓扑结构

上面测试中，已经验证了树根轮转策略可以显著降低最大EFI。但由于多播组成员到树根间的冗余路径不多，没有发挥链路轮转策略的作用。本节将在裁剪胖树结构下对上述3种路由算法进行测试，以验证链路轮转策略的有效性。获得了2个超算中心的网络拓扑结构，包括“神威蓝光”计算机及“神威太湖之光”计算机，它们均采用裁剪胖树结构。

4.2.1“神威蓝光”计算机下的实验结果

“神威蓝光”计算机[23]安装于济南超算中心，包含8 704个运算处理器，采用裁剪胖树结构，每个叶子交换机与最顶层交换机间都有8条最短路径。

表9、表10分别显示了每个处理器上运行4个进程时的最大EFI及运行时间。有下列现象：

表9 神威蓝光下各路由算法的最大EFITable 9 Maximum EFI of each algorithm under Sunway BlueLight

表10 神威蓝光下各路由算法的运行时间Table 10 Runtime of each algorithm under Sunway BlueLight s

（1）MINIHOP-MC-new的最大EFI明显高于另外两种多播路由算法。这表明除了根轮换策略外，SSSP-MC及FULB-MC采用的负载均衡策略可以进一步降低链路EFI。

（2）大部分情况下FULB-MC与SSSP-MC的最大EFI及平均EFI相比没有明显增加。这表明FULB-MC虽然使用局部信息进行负载均衡，仍然能够获得跟SSSP-MC类似的负载均衡结果。

（3）SSSP-MC的运行时间明显高于其他两种算法，特别是当存在大量小的多播组时，差异更加明显。FULB-MC的运行时间与MINIHOP-MC相当。

4.2.2“神威太湖之光”的实验结果

“神威太湖之光”计算机[24]安装于无锡超算中心，包含40 960个运算处理器，是目前世界上规模最大的IB网络，其互连网络与“神威蓝光”类似，但规模更大。每个叶子交换机与最顶层交换机都有2条路径。三种多播路由算法的性能测试结果如表11、表12所示。

表11 神威太湖之光下各路由算法的最大EFI Table 11 Maximum EFI of each algorithm under Sunway TaihuLight

表12 神威太湖之光下各路由算法的运行时间Table 12 Runtime under of each algorithmSunway TaihuLights

最大EFI方面，FULB-MC明显优于MINIHOP-MCnew，而与SSSP-MC-new接近。另外，FULB-MC的最大EFI最大下降为MINIHOP-MC的1/2左右；而神威蓝光中，FULB-MC的最大EFI最大下降为MINIHOP-MC的1/6左右。这是因为神威蓝光中，叶子交换机与顶层交换机间有更多的冗余路径。

在运行时间方面，FULB-MC明显优于SSSP-MCnew。值得注意的是，很多通信模式下，SSSP-MC-new的运行时间超过了10 s，最大达到了48 s；而FULB-MC的运行时间均低于3 s。加上发送加入多播组请求、选择树根等时间，SSSP-MC-new的运行时间很可能超过1 min。可以预见，随着网络规模的进一步扩大，以及多播组个数的进一步增多，SSSP-MC-new的运行时间会进一步增加。因此，在超大规模互连网络中，从运行时间角度看，FULB-MC是可接受的，而SSSP-MC-new的运行时间是不可接受的。

4.3 实验小结

EFI方面，有下列结论：

（1）各种拓扑结构下，FULB-MC的最大EFI相比MINIHOP-MC及SSSP-MC均大大下降，表明树根轮转策略可以有效降低链路EFI。

（2）将树根轮转策略应用于MINIHOP-MC及SSSPMC后，在裁剪胖树结构下，FULB-MC的最大EFI明显低于MINIHOP-MC-new，表明链路轮转策略可以进一步降低链路EFI。

（3）标准胖树结构下，MINIHOP-MC-new、SSSPMC-new、FULB-MC这3种多播路由算法的最大EFI完全相同。

（4）3D-Torus中，大部分情况下FULB-MC的最大EFI低于MINIHOP-MC-new，而与SSSP-MC-new基本相当。

（5）蜻蜓网络中，有些通信模式下SSSP-MC-new和FULB-MC的最大EFI大于MINIHOP-MC-new，原因是该拓扑结构下多播组成员与树根间可能有多条最短路径，但其中有些路径经过两条全局链路，而SSSP-MCnew和FULB-MC可能会选中该路径。通过添加额外的规则，FULB-MC可以避免选择这样的路径，从而保证最大EFI不大于MINIHOP-MC-new。

（6）FULB-MC虽然使用局部负载信息进行路由选择，但在各种拓扑结构、各种通信模式下，其最大EFI与SSSP-MC-new基本相当。

在运行时间方面，FULB-MC明显低于SSSP-MC，例如，有些通信模式下，SSSP-MC需要约48 s，而FULB-MC仅需不到3 s。

5 结束语

IB现有的多播路由算法中，要么没有采取任何负载均衡措施，要么采取负载均衡措施后运行时间很长，均不适用于大规模互连网络环境。本文提出一种用于大规模IB网络的负载均衡通用快速多播路由算法FULB。FULB利用最小跳表构建多播树，采用2种策略将多个多播组尽量均衡地分布到不同的链路上。另外，对加入/离开多播组的机制进行了改进，以适应高性能计算应用的需求。在典型的人造拓扑及超算中心实际使用的拓扑中对FULB的性能进行了测试，结果表明，在运行时间方面，FULB-MC显著低于SSSP-MC，由SSSPMC下最长的48 s缩短为FULB-MC下的3 s；在链路EFI指数方面，FULB-MC明显优于MINIHOP-MC，而与SSSP-MC基本相当。因此，FULB-MC可用于存在大量多播组的超大规模互连网络环境，为广泛使用硬件支持的多播操作提供支撑。

FULB-MC也有不足之处。一是它采用局部信息进行路径选择，有些通信模式下最大EFI比SSSP-MC有所增加。二是选择树根时仍需遍历所有交换机，当系统中存在大量交换机时，时间开销较大。下一步将针对这些不足做进一步的改进。