“天河一號”互連網絡中FC—Switch及其路由算法

摘要：提出了一種組合交換器——FC-Switch，定義了該組合交換器的交換級連接模式，初步分析了該組合交換器的性能.研究了FC-Switch的四種路由算法，并在“天河一號”（TH-1A）實際網絡測試平臺上，對這四種路由算法的性能進行了對比測試.研究結果表明，通過合理選擇交換級連接模式和路由算法，FC-Switch可獲得高帶寬低延遲的優良性能.

關鍵詞：高階互連網絡；組合交換器；交換級連接模式；路由算法

中圖分類號：TP393 文獻標識碼：A

Research on FC-Switch and Its Routing Algorithm

in TH-1A Interconnect Network

CAO Ji-jun， WANG Ke-fei， LIU Lu， ZHANG Lei

（College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China）

Abstract： This paper proposed FC-Switch， which is a nova combined switch， defined its switch-level connection pattern and primarily analyzed its performance. Moreover， four routing algorithms for the FC-Switch were discussed， and the experiments on TH-1A network testing platform was carried out. Experiments result shows that the FC-Switch can achieve a good performance by correctly choosing switch-level connection pattern and the routing algorithm.

Key words： high radix interconnect network； combined switch； switch-level connection pattern； routing algorithms

互連網絡是高性能計算機系統的重要部件，互連網絡的性能直接決定著高性能計算系統的整體性能.高帶寬和低延遲一直是互連網絡設計者追求的主要目標.高性能計算機系統的互連網絡可以采用標準互連和專用互連，Top500^[1]中最高端的計算系統偏向于采用專用互連網絡，即通過定制設計突破通信瓶頸以獲得更高的計算性能，這種技術選擇特點將在未來面向艾級計算（Exaflops，每秒1018次浮點運算）的高性能計算系統設計中得到延續.

Kim和Dally[2-3]的研究結果表明，在大規模高性能互連網絡中，使用高階交換（High Radix Switch）技術將減小網絡直徑和報文傳輸跳步數，從而可獲得更低的報文傳輸延遲；此外，由于高階交換網絡使用更少的交換芯片和互連鏈路，所以網絡成本和功耗將顯著降低.然而，設計高階交換芯片面臨著多方面的挑戰——首先，隨著交換芯片端口數的

增加，硬件邏輯設計變得越來越復雜，單芯片的功耗也越來越高.其次，對于多種可選的交換結構而言，芯片實現所需要的緩沖區大小和仲裁調度邏輯復雜度等都隨著芯片端口數的增長而呈現平方增長.再者，根據ITRS^[4]預測，未來10年單芯片封裝的引腳容量將增長緩慢，這將使得交換芯片的端口數增長受到ASCI工藝技術的限制.

因此，將現有的低階交換（Low Radix Switch）芯片組合成為高階交換模塊，是實現高階交換網絡的另外一種可選的解決方案.這種方案可超越當前ASCI工藝技術的限制并大大縮短高階交換網絡（使用高階交換芯片或高階交換模塊的互連網絡）的設計和制造時間.在學術界，瓦倫西亞理工大學的Duato教授對組合交換器及其交換級連接模式（Switch-level Connection Pattern，SCP）展開了具有開創性和代表性的研究[5-7].在實際構建的系統中，由國防科學技術大學研制的“天河一號”（TH-1A）高性能計算機中的高速互連網絡采用特定組合交換器及其交換級連接模式，從而突破了通信瓶頸，為系統實測試性能位居2010年下半年TOP500榜首做出了重要貢獻.

1 C-Switch簡介

定義1 C-Switch^[6]也稱為組合交換器（Combined Switch），它由多個小互連交換器（Internal Switch，內部交換器）構成.C-Switch向外提供的交換端口是各個內部交換器內部互連后剩余的端口.

上述定義僅僅指出了由內部小交換器構造C-Switch的基本原理，并沒有給出C-Switch內部交換器的數量及它們之間的交換級連接模式.實際上，合理選擇內部交換器的數量、交換級連接模式和路由算法需做多方面的權衡（tradeoff），如下所述.

1）交換延遲（Switch Delay）：為了獲得較低的內部延遲，需要實現所有內部交換器的全連接.然而，隨著內部交換器數目的增加，內部交換器之間的路由將占用大量端口.若內部交換器之間不采用全連接方式，則C-Switch的內部平均延遲將變大，而且可能會出現延遲不均勻的情況.

2）交換帶寬（Switch Bandwidth）：由多個內部交換器構成C-Switch時，需要合理選擇內部交換器之間的交換級連接模式，并合理分配外部端口和內部端口的比例，從而使得帶寬均衡，避免內部路徑出現帶寬瓶頸以影響C-Switch的總體通信性能.

3）組合代價（Combined Cost）：假設C-Switch的所有內部交換器端口總數為P，而且C-Switch的內部端口總數為W，則比值W/P一定程度上反映了從多個低階的單芯片交換器構成一個高階的多芯片交換器C-Switch的代價.為了降低代價，需要將內部交換器更高比例的端口設計為C-Switch的外部端口.

根據系統設計追求的目標不同，構建C-Switch可以采用不同的交換級連接模式.例如，為了追求較低的組合代價，相關研究者提出了一種特殊的C-Switch——T-Switch.

定義2 T-Switch^[6]也稱為雙子組合交換器（Twin Switch），它是由兩個同構的內部交換器構成的組合交換器.T-Switch向外提供的交換端口是這兩個內部交換器內部互連后剩余的端口.

T-Switch由兩個內部小交換器構成.如何合理設計兩個內部交換器的交換級連接模式并選擇連接兩個內部交換器的內部端口？對于該問題，Duato教授及其研究團隊已做了深入研究，見文獻[5-7].

T-Switch的組合代價比較低，但是其帶寬性能較差.實際上，許多高性能計算系統互連網絡設計都以高帶寬低延遲為追求目標.為此，本文提出一種新型的組合交換器——FC-Switch，并針對FC-Switch的交換級連接模式提出了4種路由算法.基于“天河一號（TH-1A）”互連網絡測試平臺，對本文提出的4種路由算法的性能進行了對比測試.

2 FC-Switch研究與分析

本節將從交換級連接模式、特性分析和路由算法等3個方面對FC-Switch進行深入的研究.

2.1 交換級連接模式

定義3 FC-Switch也稱為全互連交換器（Full Connected Switch），它是由偶數個同構的內部交換器構成的組合交換器，每個內部交換器使用一半數量的端口進行內部互連，另外一半的剩余端口向外提供交換端口.

上述定義簡單地給出了FC-Switch的基本構造方法，關于FC-Switch的交換級連接模式的更嚴格描述見定義4.

定義4 FC-Switch由n（n為偶數）個內部交換器組成，第i個內部交換器標記為NRi（0≤i≤n-1）.NRi所處位置分為第0級和第1級，其中NR⁰， NR¹，…， NRn/2-1為第0級內部交換器，而NRn/2， NRn/2+1， …， NRn-1為第1級內部交換器.每個內部交換器包含m（m為偶數）個雙向端口.內部交換器NRi的第k個端口標記為（NRi）k，其中k∈{0，1，…，m-1}.處于不同級的任意內部交換器NRi和NRj一定有端口相連，假定NRi和NRj分別為第0級和第1級內部交換器，則NRi提供第（m/2），（m/2）+1，…，m-1為內部互連端口，NRj提供第0，1，…，（m/2）-1為內部互連端口，而且連接的端口對數目為（m/2）/（n/2）.處于同一級的任意內部交換器NRi′和NRj′一定沒有端口相連.

注意，由于影響FC-Switch帶寬和延遲的因素為各個內部交換器之間端口連接數目，各個端口性能相同，而具體連接哪個端口并不重要，所以定義4明確了任意內部交換器NRi和NRj端口是否互連以及連接數目，但是并沒有明確定義具體由哪些端口對間實現互連，這是合理的.

定理1 由端口數目為m（m為偶數）的內部交換器構建FC-Switch的最小階數為2m，而且構建這種FC-Switch共需要4個內部交換器.

實際上，對于兩個端口數為m的內部交換器而言，每個將m/2個端口彼此相連，其余共m個端口成為外部端口，這種連接方式雖然符合FC-Switch的交換級連接模式（定義4），但是與單交換器相比，這種連接模式并沒有增加外部端口數，反而增加了交換延遲，實際中并不會出現這種FC-Switch.因此，構成FC-Switch的最小內部交換器數目為4，而每個NR的m/2個端口組合成為外部端口，該FC-Switch共有m/2×4=2m個外部端口.

定理2 由端口數目為m（m為偶數）的內部交換器構建FC-Switch的最大階數為m2/2，而且構建這種FC-Switch共需要m個內部交換器.

為了獲得最大階數的FC-Switch，任意NRi與和它處于不同級的每個NRj都有且僅有1對端口相連.所以該FC-Switch共有2×m/2=m個內部交換器，每個NR的m/2個端口組合成為外部端口，故該FC-Switch共有m2/2個外部端口.

例如，圖1，圖2和圖3分別是由4個、8個和16個16端口的內部交換器構成的FC-Switch，它們分別向外提供32×32，64×64和128×128的交換能力.其中，32外部端口和128端口的FC-Switch分別是由16端口內部交換器構成的最低階數和最高階數的FC-Switch組合交換器.

2.2 特性分析

結論1 假設FC-Switch由n（n為偶數）個內部交換器組成，每個內部交換器包含m（m為偶數）個端口，則FC-Switch的外部端口數（階數）和內部端口數均為（n×m）/2.

根據FC-Switch的定義，其每個內部交換器的一半端口用來內部互連，另一半端口成為外部端口，而FC-Switch的內部交換器共有n×m個端口，所以其外部端口數（階數）和內部端口數均為（n×m）/2.

結論2 FC-Switch的組合代價為50%，階數增加因子（Radix Increment Factor，RIF）為100%.

文獻[5]用階數增加因子（Radix Increment Factor，RIF）反映特定交換級連接模式的擴展性能，RIF定義為用作FC-Switch外部端口數占內部交換器總端口數的比值.由結論1可知，結論2成立.

2.3 路由算法

這樣一來，FC-Switch成為構建大規模高速互連網絡系統的基本單元.在構建大規?；ミB網絡系統時，我們考慮FC-Switch的如下應用場景，即將FC-Switch的處于同一級的所有外部端口連接計算節點，而將FC-Switch的處于另外一級的所有外部端口通過光纖或電纜連接交換機，以實現網絡的系統級擴展.因此，在研究FC-Switch的路由算法時，我們只能考慮FC-Switch連接計算節點間通信的路由算法.為了獲得較高的性能，路由算法設計的基本原則包括：1）最短路徑原則，即保證網絡路徑延遲最小；2）流量均衡原則，即保證網絡帶寬得到充分的利用.

顯然，要保證FC-Switch中計算節點間網絡路徑延遲最小，則連接在FC-Switch的同一內部交換器的節點間直接交換，其網絡跳步數為1，而連接在FC-Switch的不同內部交換器上的節點需要借助第二級內部交換器的中轉，其網絡跳步數為3.

網絡流量均衡是針對特定流量模式而言的.通常意義的網絡流量均衡是以均勻流量模式（Uniform Dataflow Pattern）為假定條件的，即所有計算節點間的通信概率是相等的.FC-Switch采用確定性路由（Deterministic Routing），可以依據目的節點或源節點的節點號分配流量，以達到均衡流量的目的.

設計FC-Switch路由算法時分配流量可以根據源節點或目的節點號，而分配流量的時機可以是第0級交換器出口或第1級交換器入口.因此，FC-Switch的路由算法可以分為4種，見表1.

為了方便起見，假定計算節點表示為cnx，其中x為計算節點的編號.假定cn[x-y]（x

2.3.1 Src-0Out-Routing路由算法

路由分兩種情況：1）如果NRi=NRj，從cnx直接路由（Hop=1）到cny.2）如果NRi≠NRj，從cnx需要3跳路由到cny——①根據cnx編號，從NRi的m/2個可選端口中選擇1個作為輸出端口，從而到達NRk；②根據cnx編號，從NRk的m/n個可選端口中選擇1個作為輸出端口，從而到達NRj；③直接路由到cny.

圖4給出了Src-0Out-Routing路由算法的示例.在圖示64×64的FC-Switch中，從cn[0-7]到cn28的流量以帶箭頭粗線條給出.cn[0-7]輸出的流量分別從NR⁰的端口0-7輸入到FC-Switch，然后根據源節點號不同分別從NR⁰的端口8-f均勻輸出到FC-Switch的第1級內部交換器.從每個第1級內部交換器中選擇到NR³的輸出端口時，仍然根據源節點號從兩條可選路徑中均勻選擇.從NR³到cn28時從確定的端口輸出即可.

2.3.2 Dest-0Out-Routing路由算法

路由分兩種情況：1）如果NRi=NRj，從cnx直接路由（Hop=1）到cny.2）如果NRi≠NRj，從cnx需要3跳路由到cny——①根據cny編號，從NRi的m/2個可選端口中選擇1個作為輸出端口，從而到達NRk；②根據cny編號，從NRk的m/n個可選端口中選擇1個作為輸出端口，從而到達NRj；③直接路由到cny.

圖5給出了Dest-0Out-Routing路由算法的示例.在圖示64×64的FC-Switch中，從cn3到cn[24-31]的流量以帶箭頭粗線條給出.cn3輸出的流量從NR⁰的端口3輸入到FC-Switch，然后根據目的節點號不同分別從NR⁰的端口8-f輸出到FC-Switch的第1級內部交換器.從每個第1級內部交換器中選擇到NR³的輸出端口時，仍然根據目的節點號從兩條可選路徑中均勻選擇.從NR³到cn[24-31]時從確定的端口輸出即可.

2.3.3 Src-1In-Routing路由算法

路由分兩種情況：1）如果NRi=NRj，從cnx直接路由（Hop=1）到cny.2）如果NRi≠NRj，從cnx需要3跳路由到cny——①根據cnx編號，從到達NRk的m/n個可選端口中選擇1個作為輸出端口，從而到達NRk；②根據cnx編號，從NRk的m/n個可選端口中選擇1個作為輸出端口，從而到達NRj；③直接路由到cny.

圖6給出了Src-1In-Routing路由算法的示例.在圖示64×64的FC-Switch中，從cn[0-7]到cn28的流量以帶箭頭粗線條給出.cn[0-7]輸出的流量分別從NR⁰的端口0-7輸入到FC-Switch，由于cn[0-7]對應的第1級內部交換器為NR⁴，所以根據源節點號不同分別從NR⁰的端口9和B輸出到FC-Switch的第1級內部交換器NR⁴.從NR⁴內部交換器中選擇到NR³的輸出端口時，仍然根據源節點號從兩條路徑中均勻選擇.從NR³到cn28時從確定的端口輸出即可.

2.3.4 Dest-1In-Routing路由算法

路由分兩種情況：1）如果NRi=NRj，從cnx直接路由（Hop=1）到cny.2）如果NRi≠NRj，從cnx需要3跳路由到cny——①根據cny編號，從到達NRk的m/n個可選端口中選擇1個作為輸出端口，從而到達NRk；②根據cny編號，從NRk的m/n個可選端口中選擇1個作為輸出端口，從而到達NRj；③直接路由到cny.

圖7給出了Dest-1In-Routing路由算法的示例.在圖示64×64的FC-Switch中，從cn3到cn[24-31]的流量以帶箭頭粗線條給出.cn3輸出的流量從NR⁰的端口3輸入到FC-Switch，由于cn[24-31]對應的第1級內部交換器為NR⁷，所以根據目的節點號不同從NR⁰的端口C和E輸出到FC-Switch的第1級內部交換器NR⁷.從NR⁷內部交換器中選擇到NR³的輸出端口時，仍然根據目的節點不同從兩條路徑中均勻選擇.從NR³到cn[24-31]時從確定的端口輸出即可.

可見，各種算法在處理同一內部交換器所連接的計算節點間流量時，都采用相同的直接路由策略（Hop=1）.各種算法的差異主要體現在連接于不同內部交換器上計算節點間的路由策略——*-0Out-Routing和*-1In-Routing路由算法分別從第0級內部交換器的輸出端口和第1級內部交換器輸入端口進行路徑選擇；Src-*-Routing和Dest-*-Routing路由算法分別根據源節點編號和目的節點編號選擇路徑（此處*表示通配符）.

3 性能測試與分析

實際上，圖1和圖2所示FC-Switch的兩種交換級連接模式在“天河一號”（TH-1A）互連網絡^[8]中都得到了實際應用.“天河一號”高性能計算系統互連網絡的交換芯片采用90 nm工藝制造，其端口數目為16，每個端口綁定了8條高速SERDES通道（High Speed SERDES，HSS），所以端口雙向數據傳輸帶寬達到160 Gbps，單芯片總吞吐率達到2.56 Tbps.

為了比較FC-Switch組合交換器中上述4種路由算法的性能，我們選擇64×64的FC-Switch作為實驗平臺.在實驗中，我們將W-Switch的32個端口連接32個終端節點，每個終端節點包含兩個12核的Intel處理器（Intel（R）Xeon（R）CPU E5-2692 V2@2.20 GHz）.節點網卡使用PCIE 2.0接口8通道（Lane）并行數據傳輸.網絡性能測試使用IMB-MPI測試測序（Intel（R） MPI Benchmark Suit V3.2.4）.

3.1 單向鏈路覆蓋率分析

首先，我們分析4種路由算法的單向鏈路覆蓋情況，因為路由的單向鏈路覆蓋情況反映了負載的均衡性.

定義5 單向鏈路覆蓋率：任意計算節點間通信所經過的內部單向鏈路總和占全部單向鏈路的比率.

定理3 假設FC-Switch由n（n為偶數）個內部交換器組成，每個內部交換器包含m（m為偶數）個端口，則Src-0Out-Routing和Dest-0Out-Routing路由算法的鏈路覆蓋率為1，Src-1In-Routing和Dest-1In-Routing路由算法的鏈路覆蓋率為3/4+1/（2n）.

FC-Switch第0級內部交換器所連接的節點間的路由路徑不經過第1級內部交換器的外部端口，所以在統計FC-Switch中路由算法單向鏈路覆蓋率時，將其排除在外.各種路由算法對各種鏈路的覆蓋情況通過過程見表2.

可見，以64×64的FC-Switch為例，*-0Out-Routing路由算法的單向鏈路覆蓋率為1，而*-1In-Routing路由算法的單向鏈路覆蓋率為81.25%.

3.2 帶寬及延遲性能測試

利用IMB-MPI測試程序對上述4種路由算法的性能進行測試.測試過程中，IMB-MPI程序對長度小于65 536字節數據的測試次數為1 000次，長度為65 536， 524 288， 4 194 304字節數據的測試次數分別為640， 80和10次.為了盡量降低測試環境微觀變化對測試結果的影響，每次更換節點的路由表時都在線進行（無需重啟計算節點或網卡）.測試結果如圖8所示.

可見，*-0Out-Routing的兩種路由算法的性能相當，*-1In-Routing兩種路由算法的性能也相當.與采用*-1In-Routing路由算法相比，采用*-0Out-Routing路由算法時FC-Switch可以獲得更優的帶寬和延遲性能.同時可見，各種路由算法性能的實際對比測試結果與3.1節對各種路由算法單向鏈路覆蓋率的理論分析結果一致，即：若算法的鏈路覆蓋率較高，則其實測性能較優.

4 結 論

本文提出了一種新型的組合交換器FC-Switch，詳細描述了FC-Switch的交換級連接模式，初步分析了FC-Switch的性能.基于FC-Switch交換級連接模式，進一步深入研究了FC-Switch的4種路由算法（Src-0Out-Routing， Src-1In-Routing， Dest-0Out-Routing， Dest-1In-Routing），并在“天河一號”（TH-1A）實際網絡測試平臺上，對這4種路由算法的性能進行了對比測試.研究結果表明，通過合理選擇交換級互連模式及路由算法（*-0Out-Routing），FC-Switch可獲得高帶寬低延遲的優良性能.

參考文獻

[1] MEUER H， SIMON H， STROHMAIER E， et al. TOP500 supercomputer sites[EB/OL]. [2012-05-15]. http：//www.top500.org.

[2] KIM J， DALLY W J， TOWLES B， et al. Microarchitecture of a high-radix router [J]. SIGARCH Comput Archit News， 2005， 33（2）： 420-431.

[3] SCOTT S， ABTS D， KIM J， et al. The blackwidow high-radix clos network [J]. SIGARCH Comput Archit News， 2006， 34（2）：16-28.

[4] WILSON L. International technology roadmap for semiconductors： 2010 update [EB/OL]. [2010-12-12]. http：//www.itrs.net/Links/ 2010ITRS/Home2010.htm.

[5] VILLAR J A， ANDUJAR F J， SANCHEZ J L， et al. Evaluation of an alternative for increasing switch radix[C]//Proceeding of the 2011 IEEE International Symposium on Network Computing and Applications （NCA）. Washington， DC： IEEE Computer Society， 2011：320-323.

[6] VILLAR J A， ANDUJAR F J， SANCHEZ J L， et al. C-Switches： increasing switch radix with current integration scale[C]//Proceeding of the 2011 IEEE International Conference on High Performance Computing and Communications （HPCC）. Washington， DC： IEEE Computer Society， 2011： 40-49.

[7] VILLAR J A， ANDUJAR F J， SANCHEZ J L， et al. Optimal configuration of high-radix combined switches[C]//Proceeding of 20th Euromicro Int Conference on Parallel Distributed and Network-based Processing （PDP）. Washington， DC： IEEE Computer Society， 2012： 102-111.

[8] XIE Min， LU Yu-tong， WANG Ke-fei， et al. Thianhe-1A interconnect and message-passing services [J]. IEEE Micro Hotinterconects， 2012， 32（1）：8-20.