VTFTR：高維胖樹中的無死鎖容錯路由算法

劉博陽，胡舒凱，施得君，盧宏生

（1.戰略支援部隊信息工程大學，鄭州 450001；2.江南計算技術研究所，江蘇 無錫 214100；3.國家并行計算機工程技術研究中心，北京 100190）

0 概述

在2022 年上半年top500 的榜單中，美國橡樹嶺國家實驗室的超級計算機“Frontier”超過“富岳”，排在了top500 的第一位?！癋rontier”基于HPE Cray EX235A 架構，使用Slingshot 互連技術，處理器選擇AMD RPYC 64C 2 GHz，擁有8 730 112 個內核。根據Linpack 基準測試，“Frontier”峰值性能達到了1.102 Exaflop/s，即每秒110.2 億億次，超過了E 級計算機每秒百億億次的標準［1］?！癋rontier”的發布標志著超算的發展正式進入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］應用于高維胖樹，并針對這些結構設計容錯算法，從而為高維胖樹中的容錯、故障修復等可靠性問題提供解決方案。