刘博阳，胡舒凯，施得君，卢宏生

（1.战略支援部队信息工程大学，郑州 450001；2.江南计算技术研究所，江苏 无锡 214100；3.国家并行计算机工程技术研究中心，北京 100190）

0 概述

在2022 年上半年top500 的榜单中，美国橡树岭国家实验室的超级计算机“Frontier”超过“富岳”，排在了top500 的第一位。“Frontier”基于HPE Cray EX235A 架构，使用Slingshot 互连技术，处理器选择AMD RPYC 64C 2 GHz，拥有8 730 112 个内核。根据Linpack 基准测试，“Frontier”峰值性能达到了1.102 Exaflop/s，即每秒110.2 亿亿次，超过了E 级计算机每秒百亿亿次的标准［1］。“Frontier”的发布标志着超算的发展正式进入E 级时代。

随着高性能计算系统进入E 级时代，超算整体规模越来越大，急剧膨胀的系统规模对高性能互连网络设计在拓扑结构、路由算法、拥塞控制等方面提出了更高的要求。在单个节点故障概率相同的条件下，高性能计算系统的规模越大，系统无故障工作的期望时间MTTF（Mean Time to Failure）就越短，系统性能随故障数量提高而呈现阶梯式下降趋势，故障数量每累积到一定程度，系统性能就发生一次严重下降［2］。分析近年来超算规模变化与故障的情况可以发现，随着系统规模的扩大，容错能力在超算中的重要性逐渐提升至与效率、算力相当的程度［3］。在E 级时代的超大规模高性能计算系统中，频繁的因故障停工，无论是在时间成本上还是在能耗上都是不可接受的，而故障的发生不可避免，因此，要有相应的容错手段来保证出现少量故障时整个系统仍能保持一定的工作能力，进而延长系统的单次工作时间。

高维胖树是一种近年来被提出的混合拓扑结构，其不仅拥有与胖树结构［4］相当的对分带宽性能，还有较经典胖树更好的可扩展性与更低的网络直径，在E 级甚至后E 级时代有望成为主流高性能互连网络拓扑结构。本文对高性能互连网络中容错路由相关工作进行介绍，分析高维胖树及其故障情况，提出一种针对高维胖树叶交换机故障的容错路由算法VTFTR，并对其优越性进行实验分析。

1 相关工作

1.1 容错路由算法

容错路由算法是互连网络容错设计的重要组成部分，可以使计算节点之间在发生故障时仍然保持一定的通信能力。容错路由的设计基础是存在物理链路或路由路径的冗余，冗余的设置一般是以成本增加或性能下降为代价来实现的。以网络中两个固定节点之间的连接为例，增加一条用于容错的物理链路会额外占用两个端口，从而导致网络可支持的最大规模下降，也可以使用不增加物理链路的方法，在路径上出现故障时从其他节点间的路径上绕行，这种方法会挤占其他路径上的网络资源，引起整体网络性能下降。容错算法设计的重点是平衡容错性能与成本之间的关系，设计目标是以尽可能低的性能代价或硬件成本来实现最好的容错效果。

对于路由算法设计而言，对死锁的预防或恢复很有必要。转向模型是一种应用广泛的路由算法设计思路，其核心是通过控制消息在Mesh/Torus 中的流动方向来预防可能产生的死锁。转向模型的成本主要在于限制消息的转向会降低部分链路的使用率，从而导致网络性能下降。目前最常见的死锁预防方法是在可能形成环路的部分进行虚通道切换［5］，在一条物理通道中划分出多条虚拟通道。容错虚通道在Mesh/Torus 拓扑结构与Dragonfly［6］拓扑结构中得到十分广泛的使用，其用于容错的成本是非容错路径可用的缓冲等网络资源下降。动态缓冲管理［7］的使用通过私有缓冲与共享缓冲组合的方法，从一定程度上减轻了使用多条虚通道带来的缓冲资源浪费与头阻塞问题。即便如此，过多地设置容错虚通道、频繁地进行容错虚通道切换，仍然会给路由芯片的设计带来极大困难。文献［8］提出一种转向模型与虚通道相结合的容错算法，该算法在不同的虚网络中分别使用不同的路由规则，保证每一套虚网络中无环路存在，最终达到使用少量虚通道实现片上Mesh 网络无死锁容错的效果。

1.2 高维胖树

如图1 所示，胖树结构是高性能互连网络中常用的一种拓扑结构，其凭借着高对分带宽、高可扩展性、优良的容错能力、拓扑易于搭建等优势在当前的高性能计算系统中占据了主流位置［9］。目前，关于胖树的研究主要分为3 个方向：

图1 4-port 3-tree 胖树结构Fig.1 4-port 3-tree fat-tree structure

1）拓展胖树结构的使用范围，如提升胖树结构在数据中心的表现［10］、探索在片上网络中使用类胖树结构的可能性［11］。

2）寻找性能优于胖树的新拓扑结构，如第一台使用Hyperx 结构［12］的超算，其某些方面的性能优于等规模的胖树结构［13］，LIANG等［14］提出一种在部分通信模式下性能高于三层胖树的均等拓扑，WANG等［15］结合胖树与k-ary n-cube 的结构特点提出k-Cube k-Ary n-Tree（CAT）与Mirrored k-Cube k-Ary n-Tree（MiCAT）两种拓扑结构，可以大幅降低网络对交换机与链路在数量上的需求。

3）对胖树结构进行拓展或者优化。近年来，一系列胖树的拓展结构先后被提出，ADDO等［16］提出一种胖树的拓展结构Zfattree 并给出其弹回重路由容错路由策略，WANG等［17］提出一种可以降低硬件成本的镜像叉树网络，并针对该网络给出邻居切换算法、下一级算法与X 转弯算法3 种容错路由算法。此外，还有一种结合胖树与多维环网结构而提出的高维胖树结构，高维胖树拥有优于经典胖树的可扩展性，同时还兼具多维环网结构的部分优势，是E 级时代高性能互连网络拓扑的重要组成。

如图2 所示（RSW 为行交换机，CSW 为列交换机，LSW 为叶交换机），高维胖树是一种新型混合拓扑，这种结构可以视为将高维环网每一维度的连接从环连接替换为高阶交换机或胖树连接。高维胖树结构的雏形可以认为是1996年日立公司的高性能计算系统SR2201所使用的Hybrid Crossbar Network［18］。Hybrid Crossbar Network 是一个三维的拓扑结构，每一维度连接使用交叉开关来实现。高阶路由芯片YARC［19］与对应高阶路由器的提出与使用［20］，将高性能互连网络带入了高阶时代。文献［21］与文献［22］分别提出使用高阶路由器构建的高维胖树结构。高维胖树在文献［21］中被称为K-ary N-direct M-indirect结构（在该作者的后续论文中修改为K-ary N-direct S-indirect（KNS）），在文献［22］中被称为k-ary n-bridge 结构。其中，KNS 结构的定义更为丰富，每一维度的连接可以使用高阶交换机、胖树或者RUFT（Reduced Unidirectional Fat-Tree）［23］结构来实现。国防科技大学的天河团队在其E 级原型机中使用了该拓扑，并称其为k-dimension tree［24］。本文将该结构统称为高维胖树（k-dimension fat-tree）。高维胖树拥有优秀的可扩展性，使用72 端口交换机构建的二维胖树规模可以达到十万个节点以上，基本满足E 级时代的设计需求。此外，在高维胖树中二维以上的算法性能均可由二维扩展推出。因此，本文所提算法与相关分析均是基于二维胖树，每个子维度上至多使用二层胖树。

图2 二维胖树（16×16）Fig.2 2-dimension fat-tree（16×16）

胖树拓扑结构节点间存在大量的路径冗余，且其上下网的模式较Mesh 而言更难产生死锁，当前已经有大量相关的容错算法［2，25-26］。高维胖树中一般采取维序路由，当使用误路由［27］进行容错设计时维序路由的无环特性可能被打破，因此，高维胖树中容错路由的设计需要预防死锁。

高维胖树中的交换机类型主要分为根交换机与叶交换机，其中，叶交换机直接与计算节点相连，根交换机负责每一维度上叶交换机之间的连接。高维胖树结构每一个子维度上的根交换机与叶交换机都可以视为一个独立的胖树结构，因此，当根交换机发生故障时可以使用胖树中的算法进行上下行路由容错。而叶交换机是高维胖树中较为独特的结构，需要为其故障设计独特的容错算法。根据高维胖树的结构特点，在使用维序路由时，叶交换机故障会影响其自身连接的所有计算节点，同时影响其所在行列间的所有通信。以规模为n×n的二维胖树为例，任意一个叶交换机故障都会导致网络中的n2条节点间的通路断开，极大影响网络的可用性。高维胖树中叶交换机故障的影响范围和处理模式与Mesh/Torus中的节点故障具有很高的相似度，因此，进行容错设计时可以参考部分Mesh/Torus 网络中的容错算法［28-29］。文献［30］提出一种针对叶交换机故障的误路由容错算法，采用一定的误路由策略，可以在故障发生时屏蔽故障节点以便维护人员进行故障排除。但是，该算法只描述了单个故障的对策，还需要考虑在故障节点得到维修前出现新故障的情况，且该算法不选择切换虚通道来预防死锁，没有对算法可能产生死锁的情况进行分析。文献［31］提出一种通过实时重构路由表、选择中介节点绕行解决高维胖树中链路故障的容错算法，该算法每选择一个中介节点就需要进行一次虚通道切换，在故障数量较多时会因为容错虚通道的设置而降低网络资源利用率，从而给硬件设计带来难度。

2 VTFTR 算法

结合转向模型与虚通道切换的思想，本文提出一种针对高维胖树中叶交换机故障的容错路由算法VTFTR，该算法通过控制容错路径的选择与转向，可以选择出最短跳步数的容错路径，同时显著降低对容错虚通道数量的需求。在高维胖树中，报文在根交换机的上下行路径会导致每个维度的正负方向间存在部分重叠，因此，传统的禁止单个转向的方法并不适用。在高维胖树中避免环路的形成，至少要在网络中禁止两个以上的转向，因此，只要使单套网络中仅存在x维度至y维度的转向或仅存在y维度至x维度的转向，就可以保证网络无环无死锁，最终达到仅靠一条容错虚通道实现无死锁容错路由的效果。为了更好地描述算法，本文使用部分词语对网络中的结构或路由操作进行替代，具体如表1 所示。

表1 文中部分词语释义Table 1 Definitions of some words in the text

2.1 算法说明

VTFTR 算法的基础是xy维序路由，每次发现故障时通过路由重构修改3 项信息：将xy路由中经过故障节点的路径修改为yx路由；将故障发生列从所有行交换机的容错备选条目中删除；将故障发生行从所有列交换机的容错备选条目中删除。在此基础上，本文算法根据故障数量与状态进行如下处理：

1）发现叶交换机故障。消息在行交换机查表时发现目标叶交换机故障无法下行，通过查询备选条目路由至同行的其他任意叶交换机，之后进行一次列路由至目标所在行，再通过一次行路由到达目标叶交换机。

2）后续发生故障。xy路由路径上发现的故障可以继续按照第1）步中的处理方式进行绕行；yx容错路径上的突发故障则需要在列交换机上进行一次误路由，到达非故障所在行后重新进行一次xy路由即可。

3）存在多点故障。在已存在故障且未发现新故障时，网络中节点间的通信分为3 种：（1）正常路径不经过故障节点，采取xy路由；（2）正常路径经过故障节点而容错路径不经过故障节点，采取yx容错路由；（3）xy与yx路由均经过故障节点，则采取第（1）步或第（2）步中的误路由方案进行绕行。

具体地，如图3 所示，当报文发现叶交换机故障时，报文在行路由阶段选择原中介节点的同行备选节点进行路由，绕开故障节点之后进行一次列路由，到达相应的列之后再行路由至目标节点。图中虚线箭头为无故障情况下的原始路径，实线部分是LSW(xd，ys)故障后的两条容错路径。

图3 VTFTR 容错路径Fig.3 Fault-tolerant path in VTFTR

图3 中路由策略对应的伪代码如算法1 所示：

算法1Routing in fig.3

当叶交换机发生故障时，发现故障的根交换机将故障叶交换机的信息通过消息包传递到子网管理模块，子网管理模块通过广播包的方式改写全部根交换机的路由表项，将存在叶交换机故障的维度从容错选项中删除或屏蔽，保证后续再出现故障时不会因为容错而路由至已经故障的叶交换机，以至于形成死锁或其他问题。具体表现为：当网络中无故障发生时，所有行/列交换机的备选条目均为n-1 个，当某个叶交换机发生故障时，所有行/列交换机中去往该列/行条目对应的备选条目不变，去往所有其他列/行的备选条目中屏蔽该列对应的条目，达到将此列/行从容错路径中删除的效果。

如图4 所示，行交换机0 在无故障时，每个端口的备选条目都包含同行的其他全部叶交换机；当叶交换机12 与叶交换机21 发生故障后，行交换机0 中的容错条目被修改，故障所在列（1和2）从容错条目中被删除。网络中的叶交换机因为故障而再进入容错路由时，不会选择列1 与列2 作为容错路径，避免了路径上出现多故障的可能性。列交换机0 的情况同理。

图4 VTFTR 容错条目修改Fig.4 Fault-tolerant table modification in VTFTR

最终，在多故障情况下本文算法中节点的路径选择如图5 所示。S1 至D1 之间叶交换机02 与20 同时故障，报文需要误路由至03 节点，再进行一次yx路由到达目标节点；S2 至D2 之间叶交换机02 故障，需要进行yx路由经过11 到达D2；S3 至D3 之间无故障存在，按照xy维序路由即可。该算法提供的绕路方案会破坏网络的无环特性从而导致死锁，因此，需要在容错路径从列路由到行路由时进行一次虚通道切换进入容错虚通道。图中实线部分为无故障虚通道，虚线部分为容错虚通道。

图5 多故障下的路径示例Fig.5 Examples of paths with multiple faults

2.2 VTFTR 优越性分析

VTFTR 算法的优越性主要体现在3 个方面：

1）优势1。通过控制容错路径，将多故障问题化解为单故障问题，避免了路径上重复出现故障节点的情况，能选出跳步数最少的容错路径。

2）优势2。通过将维序路由与虚通道切换相结合，控制容错路径的选择，仅使用一条容错虚通道即可实现对多个故障的无死锁容错。

3）优势3。容错能力强，只要故障节点没有覆盖所有行列，即可保证全网无故障节点间可达，且在每次路由重构完成前对新故障有即时处理的策略。

其中，优势1 通过本文算法的定义与描述即可推导，且通过图5 可以看出，该算法容错时根据故障情况分别需要2、3、4 次行/列路由，相较于目前现有的算法（文献［30］所提算法，下文称算法A），大部分路径会有2～4 个跳步的节约。由优势1 可知，本文算法中的稳定路径至多包含行-列-行三步，容错路径上突发故障的即时误路由策略至多包含列-行-列与行-列-行-列两种，只需在yx路由时（即列路由到行路由之间）进行一次虚通道切换，即可保证无故障路径与容错路径均无死锁。

对优势3 推论如下：该算法理论上可以在（n-1）行/列的交换机都存在单个或多个故障的情况下仍然保持其他非故障节点间的通信。在故障节点数超过n时，在k个叶交换机发生故障的情况下，仍然有的概率保持网络中正常节点间连接。更直观地，在16×16个叶交换机组成的二维胖树中，如果故障叶交换机的数量在15 个及以下，VTFTR 可以实现完全容错；如果故障节点超过16 个，以20 个为例，VTFTR 只有极小的概率（4.807e-22）无法维持非故障节点间的连接。VTFTR的强容错能力还表现在，当发现叶交换机故障后，路由重构完成前如果出现了新故障，该算法的绕行策略仍然可以完成容错路由，且根据优势2 可保证无死锁，不再需要额外的容错虚通道。

2.3 VTFTR 无死锁推论

本节对VTFTR 的无死锁特性进行推导与论证。VTFTR 中的虚通道分为无故障虚通道（默认虚通道）与容错虚通道，要证明VTFTR 无死锁，只需要证明报文在无故障虚通道与容错虚通道中均无环无死锁即可。

在高维胖树（仍然以二维胖树为例，更高维度同理）中，报文在网络中的路径根据维度与方向可以分为x上、x下、y上、y下4 种，其中，“上”指从 叶交换机到行列交换机，“下”则相反。VTFTR 的基本路由策略采取维序路由，报文根据源节点与目标节点的位置关系，按照x上＞x下＞y上＞y下的优先级进行路由。按照固定维序进行路由的报文在网络中不会形成环路，也就不会产生死锁。

在无故障发生时，所有报文均选择无故障虚通道并采取维序路由，该环节不会产生死锁。当故障存在时，报文在无故障虚通道进行一次维序路由后进行一次虚通道切换，在容错虚通道中重新按照x上、x下、y上、y下的顺序进行维序路由。根据2.2 节VTFTR 优越性分析，参考图5 中多故障模式下的路径示例，在VTFTR 中至多需要切换一次容错虚通道、进行一次序的优先级重置，即可完成对多故障节点与突发故障节点的绕行。在低序到高序的部分进行虚通道切换，即可确保本文算法整体不会产生死锁。

3 实验结果与性能分析

本文实验在NetSim 网络模拟器中进行，NetSim是基于正在某超算系统中使用的交换机结构而设计开发的网络模拟器。

3.1 实验方案

在NetSim 模拟器中构建不同规模的二维胖树进行如下两组测试：

1）单点故障。在小规模（8×8）的二维胖树中测试单叶交换机故障情况下的单点通信延迟与全网通信性能变化，将本文算法与算法A 进行对比。

2）多点故障。在4 096 个节点规模的二维胖树中，测试不同注入率下虚通道的设置与容错路径的使用对全网平均延迟与吞吐率的影响，逐渐增加网络中叶交换机的故障数量，观察算法在多点故障下的容错能力。根据VTFTR 的容错原理可知，当多点故障分布的行列增加时，需增加跳步容错的路径越多，整体网络冲突越严重，相应的网络性能会越差。因此，还需要对每种确定的故障数量情况进行不同分布的模拟，观察故障分布对容错性能的影响。需要说明的是，算法A 用于多点故障时没有死锁预防策略，存在死锁的可能，因此，多点故障时选择对本文算法在不同故障数量与不同故障分布情况下的性能进行模拟实验，以观察本文算法的容错成本。

3.2 结果分析

在单点故障（高维胖树拓扑在结构上具有对称性，单个叶交换机的故障位置对结果不会产生影响）中，首先对比单点通信延迟的增加。网络中任意行列均不同的两点间通信延迟为237 ns，本文算法误路由时增加2 个跳步，延迟为307 ns，yx路由时不增加跳步，延迟为237 ns；算法A 增加4 个跳步，延迟为377 ns。2 种算法单点通信延迟的差距符合预期。图6 中0 error 1vc 为VTFTR 无故障时的全网性能，较不配置容错虚通道（0 error 2 vc）时的性能有略微下降，该现象的原因是设置的容错虚通道资源没有使用，属于正常的容错成本，可以通过提高硬件成本或改变缓冲配置来降低该影响。对比图6 中吞吐率与网络延迟的数据可以看出，在单点故障发生时，使用VTFTR 进行容错只在高注入率时有少量的吞吐率下降与网络延迟上升。算法A 在注入率超过50%时延迟明显上升，这是因为该算法使用固定的容错路径，网络负载提升到一定程度时，容错路径上的网络拥塞严重。综合来看，VTFTR 的性能表现优于算法A，具体地，VTFTR 与算法A 在低注入率时性能表现差别不大，均对网络性能没有明显影响，但是在注入率升高至50%以上时，本文算法的吞吐率较算法A 有明显提升，网络延迟有明显下降，原因是本文算法在单点故障容错时较算法A 少用了2 个～4 个跳步，且随机分配容错路径较固定容错路径能避免单一容错路径上的拥塞。

图6 单点故障下2 种算法的性能对比Fig.6 Performance comparison of two algorithms under single point fault

当网络中存在多点故障时，故障的行列分布会在一定程度上影响容错算法的整体性能。图7 是故障叶交换机数量为5 时不同故障分布情况对应的网络性能（c 为故障同列，all 为故障不同行不同列，r 为故障同行，r1、r2为随机），可以看出，不同分布之间网络性能差距极小。在图8 中，故障数量增加至10 个，故障分布对网络性能的影响逐渐凸显，但是整体吞吐率的波动在2%以内。

图7 故障分布对网络性能的影响（5 节点）Fig.7 Effect of fault distribution on network performance（5 nodes）

图8 故障分布对网络性能的影响（10 节点）Fig.8 Effect of fault distribution on network performance（10 nodes）

在模拟不同故障数量对网络的影响时，将故障节点设置在不同行不同列，降低故障分布给结果带来的影响。如图9 所示，网络整体性能随着故障数量的增加而逐渐降低，主要表现在吞吐率的下降与延迟的增加。当故障数量较少时，全网的通信性能几乎不变，故障数量上升至5 时，VTFTR 能以1%的吞吐率下降与少许延迟提升为代价实现非故障节点间的正常通信。即使叶交换机故障数量上升至10，其他节点之间的网络仍然可以正常使用，代价仅为2%的吞吐率下降与延迟上升。

图9 不同故障数量对网络性能的影响Fig.9 Effect of different fault numbers on network performance

结合模拟结果可以看出：在网络负载较低时，容错路径的使用对整个网络间的通信影响极小，无论是吞吐率还是整个网络的延迟都没有因为容错路径与虚通道的设置而降低；在网络负载较高时，对于仍处于网络中的节点来说，整个网络的延迟仍然没有明显提升；在多点故障尤其是故障数量较多时，本文算法能够以较低的吞吐率下降为代价实现对全部无故障节点的无死锁容错路由，相较于算法A，VTFTR算法不仅在单点故障时表现更好，还补充了多点故障时的无死锁容错方案，整体容错能力有较大提升。

4 结束语

本文通过分析高维胖树中的容错设计特点，提出一种用于高维胖树叶交换机故障的容错路由算法VTFTR。该算法对容错虚通道的需求较小、容错跳步较少，且适用于多节点故障与实时突发故障的情况。本文的模拟推论都是基于二维胖树，在更高维度的胖树中可以推广使用，从而为高维胖树中容错路由的设计与选择提供新思路。下一步考虑从微结构入手，将胖树中的多轨结构［32］或泛树结构［33］应用于高维胖树，并针对这些结构设计容错算法，从而为高维胖树中的容错、故障修复等可靠性问题提供解决方案。