“天河一號(hào)”互連網(wǎng)絡(luò)中FC—Switch及其路由算法

摘要：提出了一種組合交換器——FC-Switch，定義了該組合交換器的交換級(jí)連接模式，初步分析了該組合交換器的性能.研究了FC-Switch的四種路由算法，并在“天河一號(hào)”（TH-1A）實(shí)際網(wǎng)絡(luò)測(cè)試平臺(tái)上，對(duì)這四種路由算法的性能進(jìn)行了對(duì)比測(cè)試.研究結(jié)果表明，通過(guò)合理選擇交換級(jí)連接模式和路由算法，F(xiàn)C-Switch可獲得高帶寬低延遲的優(yōu)良性能.

關(guān)鍵詞：高階互連網(wǎng)絡(luò)；組合交換器；交換級(jí)連接模式；路由算法

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：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

互連網(wǎng)絡(luò)是高性能計(jì)算機(jī)系統(tǒng)的重要部件，互連網(wǎng)絡(luò)的性能直接決定著高性能計(jì)算系統(tǒng)的整體性能.高帶寬和低延遲一直是互連網(wǎng)絡(luò)設(shè)計(jì)者追求的主要目標(biāo).高性能計(jì)算機(jī)系統(tǒng)的互連網(wǎng)絡(luò)可以采用標(biāo)準(zhǔn)互連和專(zhuān)用互連，Top500^[1]中最高端的計(jì)算系統(tǒng)偏向于采用專(zhuān)用互連網(wǎng)絡(luò)，即通過(guò)定制設(shè)計(jì)突破通信瓶頸以獲得更高的計(jì)算性能，這種技術(shù)選擇特點(diǎn)將在未來(lái)面向艾級(jí)計(jì)算（Exaflops，每秒1018次浮點(diǎn)運(yùn)算）的高性能計(jì)算系統(tǒng)設(shè)計(jì)中得到延續(xù).

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

增加，硬件邏輯設(shè)計(jì)變得越來(lái)越復(fù)雜，單芯片的功耗也越來(lái)越高.其次，對(duì)于多種可選的交換結(jié)構(gòu)而言，芯片實(shí)現(xiàn)所需要的緩沖區(qū)大小和仲裁調(diào)度邏輯復(fù)雜度等都隨著芯片端口數(shù)的增長(zhǎng)而呈現(xiàn)平方增長(zhǎng).再者，根據(jù)ITRS^[4]預(yù)測(cè)，未來(lái)10年單芯片封裝的引腳容量將增長(zhǎng)緩慢，這將使得交換芯片的端口數(shù)增長(zhǎng)受到ASCI工藝技術(shù)的限制.

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

1 C-Switch簡(jiǎn)介

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

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

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

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

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

根據(jù)系統(tǒng)設(shè)計(jì)追求的目標(biāo)不同，構(gòu)建C-Switch可以采用不同的交換級(jí)連接模式.例如，為了追求較低的組合代價(jià)，相關(guān)研究者提出了一種特殊的C-Switch——T-Switch.

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

T-Switch由兩個(gè)內(nèi)部小交換器構(gòu)成.如何合理設(shè)計(jì)兩個(gè)內(nèi)部交換器的交換級(jí)連接模式并選擇連接兩個(gè)內(nèi)部交換器的內(nèi)部端口？對(duì)于該問(wèn)題，Duato教授及其研究團(tuán)隊(duì)已做了深入研究，見(jiàn)文獻(xiàn)[5-7].

T-Switch的組合代價(jià)比較低，但是其帶寬性能較差.實(shí)際上，許多高性能計(jì)算系統(tǒng)互連網(wǎng)絡(luò)設(shè)計(jì)都以高帶寬低延遲為追求目標(biāo).為此，本文提出一種新型的組合交換器——FC-Switch，并針對(duì)FC-Switch的交換級(jí)連接模式提出了4種路由算法.基于“天河一號(hào)（TH-1A）”互連網(wǎng)絡(luò)測(cè)試平臺(tái)，對(duì)本文提出的4種路由算法的性能進(jìn)行了對(duì)比測(cè)試.

2 FC-Switch研究與分析

本節(jié)將從交換級(jí)連接模式、特性分析和路由算法等3個(gè)方面對(duì)FC-Switch進(jìn)行深入的研究.

2.1 交換級(jí)連接模式

定義3 FC-Switch也稱(chēng)為全互連交換器（Full Connected Switch），它是由偶數(shù)個(gè)同構(gòu)的內(nèi)部交換器構(gòu)成的組合交換器，每個(gè)內(nèi)部交換器使用一半數(shù)量的端口進(jìn)行內(nèi)部互連，另外一半的剩余端口向外提供交換端口.

上述定義簡(jiǎn)單地給出了FC-Switch的基本構(gòu)造方法，關(guān)于FC-Switch的交換級(jí)連接模式的更嚴(yán)格描述見(jiàn)定義4.

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

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

定理1 由端口數(shù)目為m（m為偶數(shù)）的內(nèi)部交換器構(gòu)建FC-Switch的最小階數(shù)為2m，而且構(gòu)建這種FC-Switch共需要4個(gè)內(nèi)部交換器.

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

定理2 由端口數(shù)目為m（m為偶數(shù)）的內(nèi)部交換器構(gòu)建FC-Switch的最大階數(shù)為m2/2，而且構(gòu)建這種FC-Switch共需要m個(gè)內(nèi)部交換器.

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

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

2.2 特性分析

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

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

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

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

2.3 路由算法

這樣一來(lái)，F(xiàn)C-Switch成為構(gòu)建大規(guī)模高速互連網(wǎng)絡(luò)系統(tǒng)的基本單元.在構(gòu)建大規(guī)模互連網(wǎng)絡(luò)系統(tǒng)時(shí)，我們考慮FC-Switch的如下應(yīng)用場(chǎng)景，即將FC-Switch的處于同一級(jí)的所有外部端口連接計(jì)算節(jié)點(diǎn)，而將FC-Switch的處于另外一級(jí)的所有外部端口通過(guò)光纖或電纜連接交換機(jī)，以實(shí)現(xiàn)網(wǎng)絡(luò)的系統(tǒng)級(jí)擴(kuò)展.因此，在研究FC-Switch的路由算法時(shí)，我們只能考慮FC-Switch連接計(jì)算節(jié)點(diǎn)間通信的路由算法.為了獲得較高的性能，路由算法設(shè)計(jì)的基本原則包括：1）最短路徑原則，即保證網(wǎng)絡(luò)路徑延遲最?。?）流量均衡原則，即保證網(wǎng)絡(luò)帶寬得到充分的利用.

顯然，要保證FC-Switch中計(jì)算節(jié)點(diǎn)間網(wǎng)絡(luò)路徑延遲最小，則連接在FC-Switch的同一內(nèi)部交換器的節(jié)點(diǎn)間直接交換，其網(wǎng)絡(luò)跳步數(shù)為1，而連接在FC-Switch的不同內(nèi)部交換器上的節(jié)點(diǎn)需要借助第二級(jí)內(nèi)部交換器的中轉(zhuǎn)，其網(wǎng)絡(luò)跳步數(shù)為3.

網(wǎng)絡(luò)流量均衡是針對(duì)特定流量模式而言的.通常意義的網(wǎng)絡(luò)流量均衡是以均勻流量模式（Uniform Dataflow Pattern）為假定條件的，即所有計(jì)算節(jié)點(diǎn)間的通信概率是相等的.FC-Switch采用確定性路由（Deterministic Routing），可以依據(jù)目的節(jié)點(diǎn)或源節(jié)點(diǎn)的節(jié)點(diǎn)號(hào)分配流量，以達(dá)到均衡流量的目的.

設(shè)計(jì)FC-Switch路由算法時(shí)分配流量可以根據(jù)源節(jié)點(diǎn)或目的節(jié)點(diǎn)號(hào)，而分配流量的時(shí)機(jī)可以是第0級(jí)交換器出口或第1級(jí)交換器入口.因此，F(xiàn)C-Switch的路由算法可以分為4種，見(jiàn)表1.

為了方便起見(jiàn)，假定計(jì)算節(jié)點(diǎn)表示為cnx，其中x為計(jì)算節(jié)點(diǎn)的編號(hào).假定cn[x-y]（x

2.3.1 Src-0Out-Routing路由算法

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

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

2.3.2 Dest-0Out-Routing路由算法

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

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

2.3.3 Src-1In-Routing路由算法

路由分兩種情況：1）如果NRi=NRj，從cnx直接路由（Hop=1）到cny.2）如果NRi≠NRj，從cnx需要3跳路由到cny——①根據(jù)cnx編號(hào)，從到達(dá)NRk的m/n個(gè)可選端口中選擇1個(gè)作為輸出端口，從而到達(dá)NRk；②根據(jù)cnx編號(hào)，從NRk的m/n個(gè)可選端口中選擇1個(gè)作為輸出端口，從而到達(dá)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]對(duì)應(yīng)的第1級(jí)內(nèi)部交換器為NR⁴，所以根據(jù)源節(jié)點(diǎn)號(hào)不同分別從NR⁰的端口9和B輸出到FC-Switch的第1級(jí)內(nèi)部交換器NR⁴.從NR⁴內(nèi)部交換器中選擇到NR³的輸出端口時(shí)，仍然根據(jù)源節(jié)點(diǎn)號(hào)從兩條路徑中均勻選擇.從NR³到cn28時(shí)從確定的端口輸出即可.

2.3.4 Dest-1In-Routing路由算法

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

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

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

3 性能測(cè)試與分析

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

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

3.1 單向鏈路覆蓋率分析

首先，我們分析4種路由算法的單向鏈路覆蓋情況，因?yàn)槁酚傻膯蜗蜴溌犯采w情況反映了負(fù)載的均衡性.

定義5 單向鏈路覆蓋率：任意計(jì)算節(jié)點(diǎn)間通信所經(jīng)過(guò)的內(nèi)部單向鏈路總和占全部單向鏈路的比率.

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

FC-Switch第0級(jí)內(nèi)部交換器所連接的節(jié)點(diǎn)間的路由路徑不經(jīng)過(guò)第1級(jí)內(nèi)部交換器的外部端口，所以在統(tǒng)計(jì)FC-Switch中路由算法單向鏈路覆蓋率時(shí)，將其排除在外.各種路由算法對(duì)各種鏈路的覆蓋情況通過(guò)過(guò)程見(jiàn)表2.

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

3.2 帶寬及延遲性能測(cè)試

利用IMB-MPI測(cè)試程序?qū)ι鲜?種路由算法的性能進(jìn)行測(cè)試.測(cè)試過(guò)程中，IMB-MPI程序?qū)﹂L(zhǎng)度小于65 536字節(jié)數(shù)據(jù)的測(cè)試次數(shù)為1 000次，長(zhǎng)度為65 536， 524 288， 4 194 304字節(jié)數(shù)據(jù)的測(cè)試次數(shù)分別為640， 80和10次.為了盡量降低測(cè)試環(huán)境微觀變化對(duì)測(cè)試結(jié)果的影響，每次更換節(jié)點(diǎn)的路由表時(shí)都在線進(jìn)行（無(wú)需重啟計(jì)算節(jié)點(diǎn)或網(wǎng)卡）.測(cè)試結(jié)果如圖8所示.

可見(jiàn)，*-0Out-Routing的兩種路由算法的性能相當(dāng)，*-1In-Routing兩種路由算法的性能也相當(dāng).與采用*-1In-Routing路由算法相比，采用*-0Out-Routing路由算法時(shí)FC-Switch可以獲得更優(yōu)的帶寬和延遲性能.同時(shí)可見(jiàn)，各種路由算法性能的實(shí)際對(duì)比測(cè)試結(jié)果與3.1節(jié)對(duì)各種路由算法單向鏈路覆蓋率的理論分析結(jié)果一致，即：若算法的鏈路覆蓋率較高，則其實(shí)測(cè)性能較優(yōu).

4 結(jié) 論

本文提出了一種新型的組合交換器FC-Switch，詳細(xì)描述了FC-Switch的交換級(jí)連接模式，初步分析了FC-Switch的性能.基于FC-Switch交換級(jí)連接模式，進(jìn)一步深入研究了FC-Switch的4種路由算法（Src-0Out-Routing， Src-1In-Routing， Dest-0Out-Routing， Dest-1In-Routing），并在“天河一號(hào)”（TH-1A）實(shí)際網(wǎng)絡(luò)測(cè)試平臺(tái)上，對(duì)這4種路由算法的性能進(jìn)行了對(duì)比測(cè)試.研究結(jié)果表明，通過(guò)合理選擇交換級(jí)互連模式及路由算法（*-0Out-Routing），F(xiàn)C-Switch可獲得高帶寬低延遲的優(yōu)良性能.

參考文獻(xiàn)

[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.