InfiniBand中面向有限多播表條目數的多播路由算法

陳淑平 何王全 李 祎 漆鋒濱

(國家并行計算機工程技術研究中心 北京 100190)

(chenshuping_hit@163.com)

多播是一種重要的集合操作，對高性能應用的性能具有重要的影響.它可以通過點對點消息實現，也可以通過專用的硬件實現.相比用點對點消息實現的多播，硬件支持的多播操作具有性能高、CPU占用率低等優點，正受到越來越多的關注.InfiniBand等高速互連網絡中，硬件支持的多播操作通過構建多播樹實現，樹的高度、路由的負載均衡程度等對多播消息的性能具有至關重要的影響.過去的研究中，主要關注于降低樹高、提升路由負載均衡程度.

隨著超級計算機系統規模的不斷擴大，多播組的個數急劇增加，可能會超過硬件支持的多播表(multicast forwarding table, MFT)條目數，而現有的多播路由算法沒有給出相應的解決方案.為此，本文提出一種面向有限多播表條目數的多播路由算法，在硬件僅支持很小的多播表時，能夠支持創建數千甚至數萬個多播組.本文主要貢獻有2個方面：

1) 提出了面向有限多播表條目數的多播路由算法MR4LMS(multicast routing for limited MFT size)，僅需較小的多播表就可支持數千甚至數萬個多播組，并盡量降低多播樹高度及鏈路EFI(edge forwarding index).

2) 在多種典型拓撲結構及典型通信模式下對MR4LMS的鏈路EFI、運行時間等進行了測試，獲得了令人滿意的性能開銷，表明MR4LMS可用于大規?；ミB網絡系統.

1 背景及相關工作

目前，超級計算機系統的規模越來越大，擁有的處理器數及核心數越來越多.例如2020年6月全球Top500排名第一的Fugaku系統[1-2]擁有7 299 072個核心.與之相應，高性能計算應用的性能越來越依賴于互連網絡系統的性能，尤其是集合通信的性能[3-4].集合通信包括廣播、同步、規約、scatter、gather等類型及其變體，可實現多個進程間的同步、數據分發與收集等功能，對高性能計算應用的性能至關重要.最新研究表明，集合通信在消息通信中所占的比例越來越大.Chunduri等人[5]對IBM BG/Q Mira中MPI調用次數及時間開銷進行了研究，發現集合通信時間開銷約占消息通信總時間開銷的2/3.因此，如何優化集合操作的性能成為高性能互連網絡研究的一個熱點.

集合通信可以通過點對點消息實現，也可以通過專用的硬件集合操作實現.很長一段時間以來，無論是在廣域網還是在數據中心網絡中，硬件支持的集合操作由于其復雜度、可擴展性、容錯等方面的原因，并未得到廣泛應用.例如，MPICH,MVAPICH, OpenMPI等[6-9]雖然也針對不同互連網絡提供了硬件版本的集合操作，但大部分用戶仍然選擇使用點到點版本的集合通信.

但是，基于點到點消息實現的集合操作，其性能與硬件支持的集合操作相比存在不小差距.一是同一數據包在很多鏈路上會傳輸多次，造成資源浪費.二是由于缺乏獲取底層網絡拓撲信息的能力，集合操作的邏輯結構不能適配底層網絡的物理結構，導致其無法充分利用底層網絡的傳輸能力.隨著系統規模的不斷擴大，以軟件方式實現的集合操作面臨越來越嚴重的性能問題；而硬件支持的集合操作具有性能高、CPU占用率低等優點，正受到越來越多的關注.近幾年出現了很多硬件集合通信技術，如Mellanox的SHARP技術[10].

Fig. 1 Illustration for multicast tree圖1 多播樹示意圖

硬件支持的集合操作中，多播技術是重要的支撐.集合通信中的廣播、同步、全局規約、AllGather等操作需要將相同的數據分發給參與集合通信的不同進程，它們均可通過硬件支持的多播進行加速.多播消息性能對這些集合操作的性能具有重要影響.

InfiniBand網絡中，OpenSM負責生成多播路由，基本原理是構建1棵多播樹覆蓋參與多播操作的所有節點.用戶根據需要創建很多個多播組，OpenSM為每個多播組構建1棵多播樹，并占用多播路由表的1個條目號.多播組的1個成員向其他成員進行多播操作時，數據包沿著多播樹進行傳輸.例如，在圖1所示的多播組中，陰影所示節點發送多播包時，每到達1個交換機，就查詢該多播組對應的多播表條目，以決定將數據包從哪些端口分發出去.

OpenSM目前支持MINIHOP,UP/DN,DN/UP,FTREE,LASH[11-12],DOR,TORUS-2QoS,NUE[13],DFSSSP[14-15]這9種路由引擎.它們使用的多播路由算法概括起來分為2類，分別是MINIHOP-MC及SSSP-MC.兩者都是從樹根開始自上而下構建多播樹，區別在于MINIHOP-MC是基于最小跳表(minihop table)構建多播樹，而SSSP-MC是基于單源最短路徑(single source shortest path)構建多播樹.兩者各有優缺點：MINIHOP-MC運行速度快，但路由均衡性較差；SSSP-MC具有良好的路由均衡性，但運行時間長.

InfiniBand規范[16]規定每個子網最多支持16 384個多播表條目.由此帶來的問題是：隨著系統規模的不斷擴大，系統中多播組的個數也急劇增加，可能會超過硬件支持的多播表條目數.很多情況下，多播表條目數不能滿足應用程序的需要，原因包括：

1) 不同廠商的交換機支持的多播表條目數是不同的，有些廠商僅支持少量的多播條目數，以降低硬件成本及功耗.

2) 隨著系統規模的不斷擴大，應用程序需要創建的多播組個數急劇增加，可能會超過16 384.例如，當應用程序規模達到262 144個進程時，若將這些進程組織成256×32×32的3維網格結構，為每個維度中每行都創建1個多播組，則共需17 408個多播組，已經超過了InfiniBand支持的最大多播組個數.

OpenSM中現有的多播路由算法均默認多播表條目數是夠用的，因此沒有給出當多播表條目數不足時構建多播表的方案.本文提出一種面向有限多播表條目數的多播路由算法，在硬件僅支持很小的多播表時，能夠支持創建數千甚至數萬個多播組.

2 定義及假設

2.1 基本概念

定義1.互連網絡.互連網絡是1個有向圖I=G(N,C)，其中N為網絡節點集合，C為通信鏈路集合.網絡節點又分為終端及交換機.終端一般是網卡設備，用于收發數據；而交換機用于轉發數據.

定義3.多播樹.多播樹(multicast tree, MCT)是互連網絡有向圖的連通子圖，對應互連網絡中的1棵樹.該樹內的1個節點發送數據時，會復制到該樹內的所有節點中.為了實現多播功能，多播組必須映射到1棵多播樹中.1個多播組對應1棵多播樹，但1棵多播樹可供多個多播組使用.

定義4.多播表條目號.InfiniBand進行路由時利用LID(local identification)進行尋址.LID是16 b長度的標識符，其構成的地址空間中，前49 152個用于單播路由，每個對應子網中的1個節點，例如交換機、網卡等；后16 384個用于多播路由，稱為MLID(multicast identification)，每個對應多播表中的1個條目.每個多播表條目都是1個位圖，每位對應1個交換機端口.

用戶在發送多播消息時，需同時指定目的MGID及目的MLID.多播數據包中包含MGID及MLID字段.當多播數據包在網絡中傳輸時，交換機以MLID為索引查找對應的多播表條目，并將多播包復制到不同端口；而終端在收到多播包后，由于記錄了每個MGID包含哪些QP (queue pair)等信息，可以根據MGID將多播數據包放入不同的QP.InfiniBand協議規定：必須為每個多播組指定1個MLID，但多個多播組可共用同一個MLID.

不同廠商支持的多播路由表條目數不同，例如Mellanox每個交換機中的多播表條目數為16 384，而有些廠商采用精簡InfiniBand協議，僅支持少量的多播條目數.在本文中，多播表條目號與MLID含義相同，后文將交替使用這2個術語.

需要指出的是，InfiniBand規范及現有文獻中，每個MLID僅能被1棵多播樹使用.而本文提出的多播路由算法中，只要不經過相同的交換機，多棵多播樹就可以共用同一個MLID，即占用同一個多播表條目號.

定義5.多播樹的染色.需要為每棵多播樹都分配1個多播表條目號.在不考慮多播表大小的情況下，可以為每棵多播樹分配1個全局唯一的多播表條目號.而在考慮到多播表有大小限制時，需要重用多播表條目號.為多播樹分配多播表條目號時，必須遵循2個原則：1)同一棵多播樹在其使用的所有交換機內使用相同的多播表條目號；2)若2棵多播樹經過同一個交換機，則這2棵多播樹不能使用相同的多播表條目號.可以用術語“染色”來描述多播表條目號分配問題.構建1個圖，將每棵多播樹作為圖的頂點；只要2棵多播樹經過同一交換機，則稱這2棵多播樹“相鄰”，對應的2個頂點間添加1條邊.我們將多播表條目號用顏色表示，顏色的數量等于交換機內的多播表條目數.為“相鄰”的多播樹指定不同的多播表條目號，也即用不同的顏色染色.后文將用術語“染色”表示為多播樹分配多播表條目號.

定義6.EFI(edge forwarding index).文獻[17-18]定義了單播路由中的EFI指數.我們對此進行擴展，將鏈路的EFI定義為經過該鏈路的多播組個數.所有鏈路的最大EFI值一定程度上反映了路由均衡程度，值越大表示擁塞程度越高.最大EFI由拓撲結構、路由算法、通信模式等決定，對多播操作性能具有重要影響，因此需要盡量降低最大EFI.

定義7.TFI(tree forwarding index).每棵多播樹的TFI定義為使用該多播樹的多播組個數.該指標反映了多播樹中多播數據包的冗余程度.多個多播組共用1棵多播樹時，1個多播組發送的多播數據包會復制到其他多播組內(但不會被QP接收)，造成資源浪費.

定義8.最小跳表.每個交換機都有1張最小跳表，邏輯上組織成2維表格形式，行號為i、列號為j的單元記錄了從該交換機的端口j出發到LID為i的目標節點的最短路徑長度.最小跳表是由OpenSM在拓撲探查階段構建的.

為闡述定義1～8，以圖2為例進行說明.

Fig. 2 Illustration for multicast groups圖2 多播組示意圖

1) 終端A,B組成1個多播組，MGID為ff00∷0001，其多播樹包含A,B,sw1及它們之間的鏈路，使用0號多播表條目；

2) 終端C,D組成另一個多播組，MGID為ff00∷0002，其多播樹包含C,D,sw2及它們之間的鏈路，由于該多播樹與1)中多播樹沒有共同的交換機，因此也使用0號多播表條目；

3) 終端E,G組成又一個多播組，MGID為ff00∷0003，其多播樹包含E,F,G,H,sw0,sw3,sw4及它們之間的鏈路，多播條目號仍為0；

4) 終端F,H組成另外一個多播組，MGID為ff00∷0004；它與MGID為ff00∷0003的多播組共用同一棵多播樹.當ff00∷0003多播組內的成員發送數據時， ff00∷0004多播組內的網卡也會收到數據，但由于MGID不同，最終會刪掉這些數據包.

2.2 影響多播性能的因素

多播操作的性能受多播樹高度及鏈路EFI等的影響.僅考慮1個多播組時，多播樹高度對集合操作性能至關重要.當網絡中有多個多播組同時收發消息時，鏈路EFI對集合操作的性能也有重要影響.

2.2.1 多播樹高度

多播樹高度會影響多播消息的延遲.我們構建了如圖3所示的實驗環境，并進行了2組測試，每組測試均使用4個進程構成的多播組進行多播操作，但2組測試中的進程距離不同.第1組測試中，4個進程位于拓撲結構中臨近的終端上，使用的多播樹高度為1.第2組測試中，4個進程分散在拓撲結構中的不同位置，多播樹高度為2.每組測試中各種消息長度均進行5 000次測試，分別計算平均延遲及99%消息尾延遲.其中99%消息尾延遲的計算方法為：對這5 000個消息的延遲進行排序，取末尾第4 950(5 000×99%)個消息的延遲.

Fig. 3 Experimental environment for testing the effect of multicast tree height on multicast performance圖3 用于測試多播樹高度對多播性能影響的實驗環境

測試結果如表1所示.對小消息來說，無論是平均值還是99%尾延遲都增長了約20%；對2 KB消息來說，增長幅度在15%左右.這是因為對長消息來說，增加的跳步數導致的時間開銷相比數據拷貝的時間開銷較小.可以預見，隨著廣播樹高度的增大，延遲增加會更加明顯.

Table1 Multicast Message Latency for Different Tree Height

2.2.2 鏈路EFI

如果有大量多播組經過同一條鏈路，則會對集合操作的性能造成影響.如圖4所示，每4個相鄰的終端節點組成1個多播組，但所有多播組都使用粗線所示的同一棵多播樹，因此鏈路EFI等于創建的多播組的個數.例如，EFI=1，表示僅使用4個終端節點，創建1個多播組；EFI=128，表示使用512個終端節點，創建128個多播組.在這種情況下，1個多播組發送的數據會復制到使用同一多播樹的其他多播組內.下面的實驗分別測試了不同EFI下多播操作的延遲.每種EFI下均進行5 000次測試，分別計算平均延遲及99%消息尾延遲.

Fig. 4 Experimental environment for testing the effect of EFI on multicast performance圖4 用于測試EFI對多播操作性能影響的實驗環境

結果如表2所示.對8B長度的小消息來說，隨著EFI的增加，延遲會略有增加，但是由于數據長度非常小，即使有多個廣播組經過同一條鏈路，也不會對延遲造成很大影響.而對2 KB消息來說，由于數據較大，EFI增大帶來的影響會比較明顯.例如EFI=16時，平均延遲會增大約38%；EFI=128時，平均延遲會增大約1066%.這對大量使用廣播操作的應用程序來說會帶來不可忽視的性能影響.需要指出的是，在實際運行的課題中，共用同一條鏈路的多播組可能不會同時發送數據，此時EFI對多播消息性能的影響沒有實驗所示的這么明顯.

Table2 Multicast Message Latency for Different EFI

2.3 多播路由算法的設計目標

結合上面實驗，我們列出多播路由算法的設計目標：1)滿足硬件多播表條目數的限制；2)最小化多播樹的高度，以降低多播消息延遲；3)最小化鏈路EFI，使不同多播組盡量分布到不同鏈路上，降低不同多播組間的相互干擾.給定一系列多播組，找出同時滿足上述3個目標的多播路由是非常困難的，有時候這3個目標甚至是相互矛盾的.在實際的使用場景中，新創建1個多播組后，沒有必要對已經存在的多播組重新計算路由，原因包括：1)重算路由的時間開銷很大；2)如果重算路由，則可能導致新計算的路由跟原來的路由不一致，從而引起多播路由的暫時失效，進而引起丟包等問題.

考慮到多播組的實際使用場景，我們對上述目標進行排序：首先必須滿足多播表條目數的限制，然后盡量降低多播樹高度及EFI指數.以此為目標，我們提出了面向有限多播表條目數的多播路由算法MR4LMS.

3 面向有限多播表條目數的多播路由

當多播表條目數少于多播組個數時，我們有2種策略：1)構建合適的多播樹，使它們使用不同的交換機，從而可以共用同一種顏色；2)使多個多播組共用1棵多播樹，從而減少多播樹數量.

我們提出了2種算法來構造多播樹，并設計了開銷模型從這2種算法中選擇一種使用.我們還提出了多播組合并算法，在顏色數不足時將多個多播組合并成1個虛擬多播組.下面具體介紹這些算法.表3列出了MR4LMS使用的符號.

Table3 Symbols Used in MR4LMS

3.1 先構造后染色算法

先構造后染色算法(first build then color, FBTC)的基本原理是先構造1棵高度最低、所經過鏈路負載較輕的多播樹，然后嘗試用不同的顏色為其染色.如果染色不成功，則嘗試用其他的交換機作為根構造1棵新的多播樹.如果所有備選交換機都嘗試了一遍仍不成功，則需要將該多播組合并到1個已存在的多播樹中.詳細過程見算法1.

算法1.FBTC算法.

輸入：互連網絡I=G(N,C)、多播組mcg；

輸出：多播樹mct.

① 遍歷所有交換機，找出到mcg各成員最大跳步數最小的交換機作為備選樹根，并按負載情況進行排序，存入rootList；

② for eachrootinrootList

③mct←build_mct_from_down_to_up(I,

root,mcg)；

④color←color_mcast_tree(mct)；

⑤ ifcolor是無效值 then

⑥ continue;

⑦ end if

⑧mcg.mct←mct;

⑨ 更新mct每條鏈路的權重;

⑩ 更新mct中每個交換機的多播路由表;

3.1.1 選擇樹根

算法1中行①代碼用于找出所有可能的樹根.樹根的位置決定了多播樹的高度，應該選擇到多播組內各成員最大跳步數最小的交換機作為樹根，以降低多播操作的延遲.根據各交換機的最小跳表，可以很容易地計算出每個交換機到多播組內各成員的最少跳步數，并找出其中的最大值，從而找到所有的備選樹根.如果某個備選樹根的多播組條目號已用完，則需要忽略該樹根.當有多個備選樹根時，可根據備選樹根的負載情況進行排序，優先使用負載低的樹根.在最壞情況下，其運行時間上限為O(|N|2).在超大規?；ミB網絡中，可以利用多線程同時計算多個交換機的最大跳步數.

3.1.2 自底向上構建多播樹

算法1中行③代碼用于構建多播樹.此時需要考慮負載均衡問題，也就是盡量使用負載低的鏈路.有2種方法可用于構建負載均衡的多播樹.

1) 采用SSSP-MC使用的方法，以經過各鏈路的多播組個數作為權重，利用Dijkstra算法計算樹根到所有節點的單源最短路徑，從而構造出1棵樹.其時間復雜度為Θ(|E|+|N|log|N|).該方法的缺點是不管多播組中有多少個成員，都需要遍歷整個拓撲結構以構建1棵包括所有節點的生成樹，因此其運行時間較長.

2) 基于最小跳表自底向上構建.選擇樹根后，每次從多播組的1個成員出發向樹根前進.每次經過1個交換機選擇下一跳時，都查詢該交換機的最小跳表，選出到樹根跳步最少的端口.如果有多個端口滿足條件，則根據負載情況從中選擇一條負載最輕的.該方法構建的多播樹一定是路徑最短的.其運行時間由多播組中成員數決定，在最壞情況下，運行時間上限為O(|E|+|N|).當多播組成員很少時，該方法比基于Dijkstra的方法快得多.

我們選擇基于最小跳表的自底向上構建方法，過程如算法2所示.

算法2.build_mct_from_down_to_up.

輸入：互連網絡I=G(N,C)、多播組mcg、樹根root；

輸出：多播樹mct.

① 對N中每個節點ω做初始化，ω.visited←

false,ω.parent←?；

② for eachμ∈mcg.membersdo

③curr←μ;

④ whilecurr≠root且curr.visited≠true

do

⑤curr.visited←true,Q←?;

⑥least_hop←curr.hops[root][0];

⑦ 依次檢查curr的每個端口p，若curr.hops[root][p]==least_hop，則將該端口連接的遠端節點ν加入隊列Q；

⑧ 從Q中找出具有最小權重的節點ν*;

⑨curr.parent←ν*;

⑩curr←ν*;

/*開始構建多播樹*/

3.1.3 為多播樹染色

算法1中行④代碼嘗試為構建的多播樹染色.依次嘗試每種顏色，檢查多播樹中各交換機是否已經使用了該顏色.若是，則不能使用該顏色進行染色，需嘗試下一種顏色.如果嘗試了所有顏色仍不成功，則嘗試其他交換機作為根.在最壞情況下，為1棵多播樹染色，其運行時間上限為O(Ncolor×(|E|+|N|))，其中Ncolor為顏色數.FBTC算法在最壞情況下的運行時間上限為O(Ncolor×|N|×(|E|+|N|)+|N|2).

當為多播樹找到一種可用的顏色后，算法1行⑨⑩用于更新各交換機的權重及多播表.如果嘗試了所有的樹根仍不能染色成功，則需要進行合并操作(見3.3節).

3.2 先染色后構造算法

FBTC算法在構造多播樹時沒有考慮目前的顏色使用情況.當可用的多播表條目很多時，可以快速構建出多播樹；但當可用的多播表條目數較少時，構造出的多播樹很可能染色失敗，此時就需要嘗試使用其他的樹根.而在大規?；ミB網絡中，能夠作為備選樹根的交換機有成千上萬臺，將所有交換機嘗試一遍是非常費時的.尤其是當系統中已經存在大量多播組時，很可能嘗試了所有樹根仍不能染色成功，最終只能將該多播組合并到已有的多播組中，那么前面的所有嘗試都是徒勞的.

如果在建立多播樹的過程中，能夠考慮到目前的顏色使用情況，則會提高染色成功的概率，避免盲目的嘗試.先染色后構造算法(first color then build, FCTB)根據每種顏色的使用情況，先確定一種顏色，然后在該顏色下構建多播樹.

首先引入Gcolor子圖.每個交換機需要記錄各顏色的使用情況，其中colorBusy[color]表示對應顏色是否已被使用，mcts[color]記錄了使用該顏色的多播樹.

對每種顏色color，我們都可以構造1個子圖Gcolor，構造方法如下.以網絡拓撲圖G為基礎，檢查每條鏈路(μ,ν)，如果符合下列條件之一，則將該鏈路從圖中刪除:

1)μ是交換機，ν是終端，μ.colorBusy[color]=1；

2)μ和ν均是交換機，μ.colorBusy[color]≠ν.colorBusy[color]；

3)μ和ν均是交換機,μ.colorBusy[color]及ν.colorBusy[color]都是1，但μ.mcts[color]≠ν.mcts[color].

實際上Gcolor由2部分組成：1)使用該顏色的所有多播樹包含的節點及鏈路；2)G中去掉使用該顏色的所有多播樹包含的節點及其所有鏈路后剩余的部分.在具體實現中，可以不用單獨存儲每個Gcolor，后面描述的所有對Gcolor的操作，均可通過G及colorBusy位圖實現.

先染色后構造算法具體過程見算法3.

算法3.FCTB算法.

輸入：互連網絡I=G(N,C)、多播組mcg；

輸出：多播樹mct.

① 利用算法1所述方法找出所有的備選樹根；

② for 0到Ncolor-1范圍內的每種color, do

③ 任選mcg的1個成員作為出發點，以廣度優先搜索(breadth first search, BFS)在圖Gcolor中進行遍歷；

④ 若mcg某個成員在Gcolor中不可達，則嘗試下一種顏色；

⑤ 對每個可達的樹根root,以它為出發點在Gcolor中進行廣度優先遍歷，計算root到mcg各成員的跳步數，若在Gcolor中的最大跳步數大于在G中的最大跳步數，則嘗試下一個樹根；

⑥ 若找到了可用的顏色color及樹根root，則跳到步驟⑨;

⑦ end for/*未找到可用的樹根及顏色，需要與其他多播組合并*/

⑧ return NULL;

⑨mct←build_mct_by_dijkstra(I,mcg,

root,color)；

⑩ 更新mct每條鏈路的權重;

3.2.1 選擇顏色

算法3中行①找出所有可能的樹根，方法與算法1行①完全一樣.行②～⑦依次檢查每種顏色下能否構建出高度最低的多播樹.行③④首先利用廣度優先搜索在Gcolor中進行遍歷，檢查多播組內各成員是否是連通的.如果不連通，則在該顏色下不可能構造出多播樹，從而可以忽略該顏色；如果連通，則需要找到可用的樹根.行⑤檢查備選樹根是否滿足下列條件：1)該樹根在Gcolor中是可達的，否則以它為根不能構造多播樹；2)該樹根在Gcolor中到多播組內各成員的最大距離不大于在G中到多播組內各成員的最大距離，否則構建出的多播樹不是高度最優的.計算樹根在Gcolor中到多播組各成員的最大距離時，只能使用廣度優先搜索進行遍歷，而不能直接使用最小跳表.若找不到合適的顏色及樹根，則需要將該多播組跟其他多播組進行合并.需要指出的是，找出的連通子圖，有可能是某棵已經創建好的多播樹，此時新創建的多播組是該多播樹的1個子集，可以直接使用該多播樹.

FCTB需要執行多次廣度優先遍歷，時間開銷較大.與FBTC一樣，FCTB最壞情況下運行時間上限為O(Ncolor×|N|×(|E|+|N|)).但隨著Gcolor中鏈路數逐漸減少，進行廣度優先遍歷的時間會大大減少.尤其是當系統中存在大量多播組時，對很多顏色來說，多播組成員在Gcolor中已不是連通的，從而可以節省后續檢查時間，直接嘗試其他顏色.

3.2.2 在Gcolor中構造多播樹

當選擇好顏色及樹根后，我們必定可以在Gcolor中構造出1棵高度最低的多播樹.此時只能使用Dijkstra算法(算法3行⑨)，而不能使用3.1.2節提到的自底向上構建方法.原因是自底向上構建方法需要利用最小跳表，但最小跳表是基于圖G構造的，不能用于Gcolor中構造多播樹.另外，為Gcolor構造新的最小跳表時間開銷很大，得不償失.具體算法見3.3.2節算法5.

3.3 多播組合并算法

當多播組個數太多而無法成功染色時，需要合并1個或多個已經存在的多播組，形成1個大的虛擬多播組.

3.3.1 選擇被合并的多播組

首先要確定需合并哪些多播組才能使新創建的多播組染色成功.被合并的多播組要盡量少，以降低鏈路EFI.分2個步驟確定被合并的多播組.

1) 從已存在的多播組中選出與新創建的多播組最相似者，并將兩者合并.由于已存在的多播組已經染色，合并后的多播組只能使用被選中多播組的顏色，即color.在Gcolor中檢查合并后的多播組是否是連通的，若是連通的，則無需再合并其他的多播組.

2) 若合并后的多播組是非連通的，則基于最小跳表為合并后的多播組自底向上構建1棵臨時的多播樹.然后在Gcolor中檢查該臨時多播樹的每個交換機，若該顏色對應的多播表條目已被使用，則將使用該條目的所有多播組也合并到虛擬多播組中，從而保證虛擬多播組在Gcolor中是連通的.

步驟1中，如何選擇最“相似”的多播組，對后續染色及多播性能具有重要影響.直觀上看，2個節點距離越近越“相似”.受此啟發，我們定義了多播組與多播樹間的距離：

(1)

2個組(多播組或多播樹)的距離定義為每個組中各成員到對方組中成員最短距離的均值.2個多播組的距離越近，則這2個多播組共用同一個交換機的可能性越高，兩者合并后用同一種顏色染色成功的概率也越大.

上述過程實際上采用了2種策略選擇被合并的多播組：首先使用樂觀策略，選擇1個最相似的多播組進行合并；如果合并后仍不能染色成功，則使用悲觀策略，將所需的多個多播組同時合并到一起.實際上，我們也可以全部采用樂觀策略：當第1次合并后仍不能染色成功時，則可以再選擇1個與合并后多播組最相似的多播組繼續合并，該過程一直重復，直到合并成功或將所有多播組合并到一起.我們未采用該方法的原因是：當系統中存在大量多播組時，可用的顏色數嚴重不足，可能需要進行多次合并才能染色成功，而每次合并都需利用式(1)計算“相似度”，時間開銷很大.

經過上述2個步驟，我們獲得1個包含多個多播組的虛擬多播組，稱為vMcg(virtual MCG).偽代碼描述的合并算法見算法4.

算法4.合并算法.

輸入：互連網絡I=G(N,C)、多播組mcg；

輸出：多播樹mct.

① 對I.existingMctList中的每棵多播樹，都利用式(1)計算它與mcg的距離，找出具有最小距離的那棵多播樹，記為mct1；

② 將mcg的成員與mct1合并，創建1個虛擬多播組vMcg；

③color←mct1.color;

④ 若vMcg的所有成員在Gcolor中是連通的，則跳到步驟；

/*需要合并其他多播組*/

⑤ 為vMcg選擇1個樹根roottmp；

⑥mct2←build_mct_from_down_to_up(I,

roottmp,vMcg);

⑦ for each switchswinmct2do

⑧ ifsw.colorBusy[color]==true

⑨ 將sw.mcts[color]與vMcg合并;

⑩ end if

/*在Gcolor中為vMcg構建多播樹*/

root,color)；

算法4行①計算所有多播樹與新創建的多播組間的距離，最壞情況下耗時O(|N|3).為加快計算速度，可以用多線程同時計算.另外，當多播樹個數很多時，根據式(1)計算距離的時間開銷很大.此時可以采用另一種更簡單高效的方式，即不再選擇最“相似”的多播樹進行合并，而是選擇多播組數最少的那個Gcolor，然后直接從行⑤代碼開始在Gcolor中合并所需的多播組.也就是不再嘗試樂觀策略，而是直接使用悲觀策略選擇所需合并的多播組.

3.3.2 利用Dijkstra構建多播樹

合并后vMcg的成員在Gcolor中是連通的，為vMcg構建多播樹的過程類似于FCTB算法.首先通過廣度優先遍歷計算各個交換機到vMcg各成員的最大距離，據此選擇1個作為樹根，然后利用Dijkstra算法在Gcolor中構造1棵樹.為vMcg構建多播樹時，需要考慮是否保留原有的多播樹.我們有2種策略.

1) 銷毀舊的多播樹，為vMcg重新創建1棵多播樹.由于需要為原有的多播組重新計算并更新路由，該方法可能會導致短暫的路由一致性問題，即在更新路由的過程中出現丟包等現象.此時需要由上層應用采用其他手段保證可靠傳輸.

2) 不銷毀舊的多播樹，而是在原多播樹上通過添加枝葉形成1棵新的、更大的多播樹，從而保證原來那些多播組不受影響.缺點是構建的多播樹可能不是最優的.

我們同時支持這2種策略，用戶可以通過環境變量選擇一種.下面介紹第2種方法，偽代碼見算法5.行②～④是標準的Dijkstra算法.行⑤～用于將舊的多播樹鏈入新多播樹.每處理完1個節點，就檢查該節點是否在原多播樹中.如果是，則從該節點出發，用廣度優先遍歷將原多播樹中的所有節點及鏈路加入新產生的多播樹中.

算法5.build_mct_by_dijkstra.

輸入：互連網絡I=G(N,C)、多播組mcg、樹根root、顏色color、舊的多播樹對應的圖I′=G(N′,C′)；

輸出：多播樹mct.

① 對N中每個節點ω做初始化，設置ω.parent←?,ω.distance←∞，并設置root.dist←0，Q←N;

② whileQ≠? do

③ 在Q中找到具有最小dist的節點μ，并從Q中刪除節點μ；

④ 在圖Gcolor中檢查μ的每條鏈路(μ,υ)，若υ仍在Q中，且μ.dist+weight(e)<υ.dist，則設置υ.dist←μ.dist+weight(e)，υ.parent←e；/*處理舊的多播樹中的節點*/

⑤ ifμ∈N′

⑥QBFS←{μ};

⑦ whileQBFS≠? do

⑧ 取QBFS的首元素μ′，檢查μ′的每條鏈路e=(μ′,υ′)，若υ′不在Q中，則繼續檢查下一條鏈路；

⑨ 若e是舊的多播樹中的鏈路，則設置υ′.dist←μ′.dist+weight(e)，υ′.parent←e，并將υ′加到QBFS的隊尾；

⑩ 若υ′不是舊多播樹中的節點，且μ′.dist+weight(e)<υ′.dist，則設置υ′.dist←μ′.dist+weight(e)，υ′.parent←e；

/*開始構建多播樹*/

3.3.3 刪除多播組

被刪除的多播組可能跟其他多播組共用同一棵多播樹，因此刪除該多播組不能影響其他多播組的正常使用.首先將待刪除多播組中的成員從多播樹中刪掉，然后遞歸檢查多播樹中剩余交換機.若該交換機僅有1個上行端口連接到多播樹的上一層，而所有下行端口都是空的，則從多播樹中刪除該交換機.偽代碼見算法6.

算法6.從多播樹中刪除1個多播組.

輸入：多播樹mct、多播組mcg.

① 初始化1個空隊列Q；

② 將mcg的每個成員從mct中刪掉；

③ 檢查mct中的每個交換機，若它的下行鏈路均不在mct中，則將該交換機加入Q；

④ whileQ≠? do

⑤ 取Q的首元素sw，并將sw從mct中刪除；

⑥ 依次檢查sw上行端口連接的交換機υ，若υ在mct中，且下行鏈路均不在mct中，則將該交換機加入Q；

⑦ end while

3.4 時間開銷模型及算法選擇

由于不能精確測量各部分開銷，上述開銷模型僅能用于定性分析.直觀上看，我們采用2種啟發式：

Fig. 5 Algorithm selection policy圖5 算法選擇策略

我們采用如圖5所示的策略在FBTC和FCTB中進行選擇：初始化時使用FBTC算法；一旦FBTC染色失敗，則下一次構建多播表時切換為FCTB算法；在使用FCTB算法時，不需要合并而能夠連續成功的次數超過某預設閾值(例如20次)，則切換回FBTC算法.偽代碼描述的算法見算法7.

算法7.MR4LMS算法.

輸入：互連網絡I=G(N,C)、多播組mcg、當前路由算法current_alg；

輸出：多播樹mct.

① ifcurrent_alg為FBTC then

②mct←FBTC(I,mcg);

③ 若失敗，則設置current_alg為FCTB;

④ else

⑤mct←FCTB(I,mcg);

⑥ 若成功，且連續成功的次數達到20，則設置current_alg為FBTC;

⑦ end if

⑧ 若mct創建失敗，則利用算法4創建mct;

⑨ returnmct.

4 實現及實驗評估

4.1 實 現

我們在OpenSM 3.3.22中實現了MR4LMS，共有約5 000行代碼.為了支持多棵多播樹共用1個多播表條目號，我們對OpenSM源碼進行了修改，包括為每棵多播樹(OpenSM中稱為mbox)添加color字段，用戶在發送多播消息時指定的不再是MLID，而是該color值.

另外，我們還對加入、離開多播組的機制進行了簡單的修改，以解決頻繁重算路由的問題.加入多播組時，不是每收到1個加入多播組的請求就重算路由，而是等收齊同一個多播組的所有請求之后再計算路由.1個成員離開多播組后，也不重算路由；僅當所有成員均離開后，再刪掉該多播組.

為了提升運行速度，我們在很多地方使用了多線程進行加速，包括：1)利用式(1)計算2個多播組間的距離時；2)計算各交換機到多播組內各成員最大距離時；3)在Gcolor內進行廣度優先搜索時.

4.2 實驗環境

我們使用ibsim-0.7[19]模擬各種網絡拓撲；使用測試程序模擬發起加入或離開多播組的請求.OpenSM運行在1臺48核Intel Xeon E5-2680 v3服務器上，頻率為2.50 GHz.需要指出的是，在ibsim下的測試結果跟在真實網絡環境下的測試結果是一樣的，因為后面測試的EFI及運行時間等性能數據跟是否使用ibsim模擬拓撲結構無關.

4.2.1 拓撲結構

我們將在不同拓撲結構下對MR4LMS的性能進行測試，包括2個超算中心使用的拓撲，以及幾種典型的人造拓撲結構(包括標準胖樹[20-21]、3D環網、蜻蜓網絡[22]等).

1) 超算中心的拓撲結構

我們利用ibnetdiscover獲得了2個超算中心的網絡拓撲結構，包括“神威藍光”計算機及“神威太湖之光”計算機.“神威藍光”計算機[23]安裝于濟南超算中心，包含8 704個運算處理器，采用裁剪胖樹結構[24]，每個葉子交換機與最頂層交換機間都有8條路徑.“神威太湖之光”計算機[25-26]安裝于無錫超算中心，包含40 960個運算處理器，是目前世界上規模最大的InfiniBand網絡，其結構與“神威藍光”類似，但規模更大，每個葉子交換機與最頂層交換機間都有2條路徑.

2) 典型的人造拓撲結構

包括4種拓撲：

① 3層胖樹.采用40端口交換機構建標準3層胖樹結構，終端個數N=16 000.

② 3D -Torus.構造了30×20×20的3D -Torus網絡，每個交換機連接2個終端，終端個數為N=24 000.

③ 蜻蜓網絡.配置參數為a=18,p=h=9，終端個數N=26 406.

④ 隨機網絡.共2 048臺40口交換機，每臺交換機20個端口連接網卡，另外20個端口隨機連接到其他交換機端口，終端個數為N=40 960.

4.2.2 通信模式

MPI集合通信中，主要有2種通信域劃分方法[27-28]：1)劃分成2維或3維網格，其每個維度中每行或每列都是1個通信域，對應1個多播組.2)劃分成層次結構，例如樹型結構，每層分成很多組，每個組構成1個通信域；每個組再選出1個leader，形成更高層次的組.劃分成網格時，通信域內的成員數較少，但通信域的個數很多，對多播表條目數的需求量更大.后面實驗中，我們采用2維及3維網格劃分進程，以測試存在大量多播組時多播路由算法的性能.對每種拓撲結構，我們都測試了多種典型的通信模式，包括2維及3維網格模式，以及隨機加入多播組的模式.

在多核及眾核編程模型中，每個處理器上可運行多個進程.一般采用混合編程模型，如MPI+OpenMP等.位于同一處理器上的進程可以建立1個獨立的通信域.每個處理器中選出1個leader用于在處理器間進行通信.我們的實驗中，既測試了每個終端運行1個進程的情況，也測試了每個終端運行多個進程的情況.

Fig. 6 Counts of MCGs and colors for different topologies and communication patters圖6 不同拓撲和通信模式下的多播組個數及所需顏色數

需要指出的是，FBTC及FCTB算法在選擇樹根時，僅考慮了那些到多播組內各成員最大距離最小的交換機作為備選樹根，因此構造出的多播樹高度是最低的；而合并算法也優先考慮到多播組內各成員最大距離小的交換機作為樹根.因此，影響多播性能的2個因素中，我們僅測試最大鏈路EFI，而不再關注多播樹高度.

4.3 無合并時所需的顏色數

MR4LMS中，只要2棵多播樹不使用同一個交換機，它們就可以共用同一個多播表條目號，從而使所需的多播表條目數少于多播組個數.對每種拓撲結構，我們都通過實驗測試MR4LMS算法在典型通信模式下所需的多播表條目數，并據此為每種拓撲結構選擇1個合理的Ncolor值.我們測試了6種典型的通信模式，包括2種2維網格結構，該模式下每個終端運行1個進程；2種3維網格結構，每個終端運行1個進程； 1種隨機多播組模式，每個終端運行1個進程；1種3維網格結構，每個終端運行4個進程.

測試最后2種通信模式的目的是觀察MR4LMS在創建大量多播組時的性能；實際應用課題一般不采用這2種通信模式.前面4種2維或3維網格模式中，有些是按拓撲結構進行劃分，模擬拓撲感知的通信模式[27-28]；有些劃分成正方形或立方體形狀，模擬拓撲無感的通信模式.以神威藍光為例，256×34通信模式下，第1維有34個多播組，每個組都位于同一個運算中板內，因此通信模式與拓撲結構匹配.而90×90通信模式下，存在很多跨運算中板的多播組，因此通信模式與拓撲結構不匹配.

測試結果如圖6所示，圖6(a)～(c)分別是神威藍光、神威太湖之光以及3層標準胖樹結構下的測試結果.存在下列現象：

1) 使用的顏色數遠低于多播組的個數.例如，神威太湖之光中，128×32×40通信模式下，創建了10 496個多播組，僅使用了269種顏色.這是因為胖樹及裁剪胖樹中有大量冗余路徑，多播組可以分布到不同的冗余路徑上，從而可以盡量使用相同的顏色.

2) 大部分通信模式下，所需的顏色數少于128.因此，在這3種拓撲結構中，Ncolor=128對大部分多播通信模式來說是夠用的.

3) 通信模式是否與底層拓撲結構匹配，對所需的顏色數影響不大.例如，圖6(a)中256×34模式需要29種顏色，而90×90需要50種顏色，沒有劇烈增加.

圖6(d)顯示了3D環網下的測試結果.3D環網中雖然也有很多冗余路徑，但這些冗余路徑有共用的交換機，因此很多MCG需要經過相同的鏈路，導致所需的顏色數較大.當通信模式與拓撲結構匹配時(例如240×100，60×20×20)，所需顏色數很少.當通信模式與拓撲結構不匹配時，所需顏色數較大，最大達到了2166.圖6(e)(f)分別顯示了蜻蜓網絡和隨機網絡下的測試結果.與3D環網一樣，由于互不干擾的冗余路徑較少，這2種拓撲結構下所需的顏色數也較大，最大分別為486，2852.

4.4 無合并時的最大EFI

本節將測試無合并時MR4LMS算法的最大EFI，與MINIHOP-MC及SSSP-MC多播路由算法進行比較，結果如圖7所示.可以發現，大部分情況下MR4LMS算法的EFI明顯低于MINIHOP-MC算法，而與SSSP-MC算法基本相當.MINIHOP-MC的EFI較大的原因是，它沒有考慮多個多播組間的負載均衡問題，因此多個多播組可能共用同一條鏈路.該測試結果表明，MR4LMS產生的多播表，其性能高于MINIHOP-MC，而與SSSP-MC基本相當.

Fig. 7 Maximum EFI for different algorithms圖7 不同算法的最大EFI

Fig. 8 Maximum EFI for different Ncolor圖8 不同Ncolor下的最大EFI

4.5 合并算法有效性測試

合并多播組會導致鏈路EFI升高，影響多播消息性能.圖8顯示了2種通信模式下不同Ncolor的最大EFI變化情況：1)神威太湖之光下的34×34×34通信模式；2)隨機網絡下的32×32×40通信模式.可以發現，如果將Ncolor設成較小的值，會導致最大EFI變的很大，對多播消息性能造成影響.

我們為上述6種拓撲結構采用如表4所示的Ncolor配置，并測試各種通信模式下的最大EFI及TFI，以檢驗這些Ncolor是否合理.對其他拓撲結構及網絡規模，也可以采用類似方法：先確定其典型的通信模式，并通過實驗確定1個合適的Ncolor，使得大部分通信模式下Ncolor是夠用的，或合并后EFI沒有顯著增加，從而在多播表大小與多播消息性能間進行適當的平衡.

Table4 Ncolor Used in MR4LMS

Fig. 9 Maximum EFI for the recommended Ncolor圖9 推薦Ncolor下的最大EFI

4.5.1 推薦Ncolor下的EFI

本節將測試推薦Ncolor下的最大EFI.對每種拓撲結構，我們都進行2組對比實驗：1)將Ncolor設為無窮大，從而保證不會發生合并；2)測試推薦的Ncolor.每組測試都分別記錄各通信模式下的最大EFI，結果如圖9所示.存在下列現象：

1) 大部分通信模式下，由于顏色數夠用，不需要合并多播組，最大EFI也較小，一般低于50，這表明2種構造多播樹的方法具有良好的負載均衡性，能夠將多播組分布到不同鏈路上.

2) 少量通信模式下，由于顏色數不夠用，需要合并多播組，其中一部分通信模式合并后EFI與無合并時相比并無顯著增加.例如，在神威藍光下，Ncolor=128時僅64×16×34模式下需要合并多播組，最大EFI由無合并時的24增加到58；隨機網絡拓撲中，Ncolor=256時256×160模式下需要合并多播組，最大EFI由無合并時的20增加到34.

3) 還有一部分通信模式，合并后EFI顯著增大.例如，在神威太湖之光中，128×32×40模式下最大EFI由無合并時的37增加到300；在隨機拓撲中，128×32×40模式下最大EFI由無合并時的139增加到4 687.最大EFI劇烈增加的情況基本都出現在每個處理器運行4個進程的通信模式下.這是因為每個處理器上有4個進程時，每個交換機上多播組的個數顯著增加.例如在胖樹結構中，原來每個處理器上僅有1個進程時，每個葉子交換機上僅有20個進程，在3維網格通信模式下，最多需要60個多播組(實際上不需要這么多多播組，因為有些進程可能位于同一個多播組內).而當每個處理器上有4個進程時，每個葉子交換機上有80個進程，在3維網格通信模式下，最多需要240個多播組，導致多播組的個數超過交換機支持的多播表條目數，因此需要進行很多多播組合并操作.

在實際應用場景中，很少會遇到這樣的通信模式，因為當1個處理器上運行多個進程時，用戶一般會為它們建立1個單獨的通信域用于處理器內的集合通信，并從中選擇一個作為leader用于處理器間的集合通信.

4) 3D環網中，28×28×28通信模式下，Ncolor=256時的最大EFI反而低于Ncolor無限制時.這是因為在顏色數足夠時，FBTC算法在嘗試第1個樹根時總會成功，而它采用貪心策略根據局部信息進行負載均衡，有可能產生非最優的解，也即產生最大EFI非最小的多播樹.

綜上所述，我們選擇的Ncolor對大部分通信模式來說，不需要合并多播組；部分通信模式需要合并多播組，但合并后EFI沒有顯著增加，因此不會對多播消息性能帶來嚴重影響；極少數需要創建超過1萬個多播組的情況，合并后EFI可能會顯著增加，但用戶使用該類通信模式的情況較少.

4.5.2 推薦Ncolor下的TFI

最大TFI反映了有多少個多播組共用1棵多播樹.TFI越小越好；當沒有合并發生時，TFI=1.本節將測試推薦Ncolor下的最大TFI，以進一步觀察多播組的合并情況，檢查是否存在大量多播組合并到同一棵多播樹的情況.我們統計了每種通信模式下的最大TFI，測試結果如圖10所示.可以發現，每個處理器上運行1個進程的通信模式中，TFI最大為10，表明最多有10個多播組共用1棵多播樹.而在每個處理器上運行4個進程的通信模式中，TFI最大為66.

Fig. 10 Maximum TFI for the recommended Ncolor圖10 推薦Ncolor下的最大TFI

除了測試TFI指標，我們還記錄了每種顏色下的多播樹及多播組個數信息.不同拓撲結構、不同通信模式下測試結果會有差異.圖11顯示了神威太湖之光中Ncolor=128時，128×32×40模式下各顏色下的多播樹及多播組個數.該模式下共創建10 496個多播組，最大TFI為66，平均TFI為1.36.可以發現下列現象：1)多播組在各顏色下分布比較均衡；2)陰影標記的顏色下，某些多播組發生了合并；3)有8種顏色下，各有66個多播組，但被合并成了1個虛擬多播組，共用1棵多播樹.可以預見，隨著多播組個數的增加，合并情況會進一步加劇，嚴重時可能每種顏色下都只有1棵超級多播樹存在.

上述實驗表明：MR4LMS在合并多播組時，能夠較均勻地選擇多播條目號，從而使每個多播條目號下多播組個數大體相等，而不是將所有多播組合并成1棵包含所有節點的多播樹.

4.6 算法運行時間

超大規?；ミB網絡中可能存在大量多播組，多播路由算法需要在較短的時間內完成多播路由的計算.本節將對MR4LMS計算多播路由的時間進行測試.

對每種拓撲結構，我們都進行2組對比實驗：1)將Ncolor設為無窮大，從而保證不會發生合并；2)測試推薦的Ncolor，分別記錄各通信模式下MR4LMS的運行時間.測試結果如圖12所示.該時間僅包括計算路由的時間(包括選擇樹根、構建多播樹、為多播樹染色)，不包括發送加入多播組請求、分發路由等其他步驟的開銷.存在3種現象：

1) 算法運行時間跟創建的多播組個數有關，胖樹結構、蜻蜓網絡平均約5 ms創建1個多播組，3D -Torus、隨機網絡平均約9 ms創建1個多播組.

2) 除去每個處理器上運行4個進程的通信模式，最長運行時間為40.6 s.每個處理器上運行4個進程的通信模式下，Ncolor無限制時，最長運行時間為48.0 s；推薦Ncolor下，最長運行時間為191.5 s，均在可接受的范圍內.

3) 每種通信模式下，推薦Ncolor下的運行時間與Ncolor無限制時相比，最多增加3倍.某些通信模式下，時間開銷增加較大，原因是顏色數不夠時，需要花費更多的時間在Gcolor中進行廣度優先搜索，以及進行合并操作.

Fig. 11 Count of MCT and MCG for each color圖11 每種顏色下的MCT及MCG數

Fig. 12 Runtime of MR4LMS圖12 MR4LMS的運行時間

4.7 討 論

本節將從運行時間、適用范圍等方面對MR4LMS算法進行進一步的討論.

1) 運行時間

大部分應用中，各通信域劃分好之后一般不會頻繁變動，因此僅在應用程序初始化階段才需要創建多播組.對那些運行時間超過數小時、甚至數天的應用而言，利用MR4LMS創建多播組的時間一般不超過數十秒，因此MR4LMS的運行時間并不會對應用性能帶來嚴重影響.

當然，當網絡拓撲或通信域劃分方式頻繁變動而需要重算多播路由時，MR4LMS算法的時間開銷會給應用程序的性能帶來不可忽略的影響.下一步我們將繼續對MR4LMS算法進行改進以降低其運行時間，一種可行的思路是針對特定的拓撲結構進行相應優化.

2) 適用范圍

MR4LMS并不針對特定的網絡拓撲結構.我們在胖樹、3D環網、蜻蜓網絡、隨機網絡等常見網絡中測試了該算法的性能，都能夠獲得不錯的EFI指標.但該算法并不適用于動態可配置的網絡，如光開關控制的網絡，因為這些網絡的拓撲結構會頻繁變動，導致需要頻繁計算多播路由；而MR4LMS的運行時間較長，頻繁計算多播路由會對應用性能帶來影響.

另外，MR4LMS算法適用范圍不僅僅局限于InfiniBand，也可用于其他高速互連網絡.這需要互連網絡提供下列支持：首先該互連網絡必須為集合操作提供相應的硬件支持；其次，該互連網絡要允許多播鏈號在同一時刻分配給多個多播組使用，從而允許用戶向不同多播組發送消息時可以使用同一個多播鏈號.

需要指出的是，InfiniBand中每個交換機所有端口共用1份路由表；如果采用每個端口都有1份路由表的設計，則可以進一步降低所需顏色數及鏈路EFI指數.

5 結 論

本文提出一種面向有限多播表條目數的多播路由算法，在硬件僅支持很小的多播表時，能夠支持創建數千甚至數萬個多播組.我們采用2種策略來達到此目的：1)構建合適的多播樹，使它們使用不同的交換機，從而可以共用同一種顏色；2)使多個多播組共用1棵多播樹，從而減少多播樹數量.

我們對MR4LMS進行了大量測試，結果表明，通過維護1個較小的多播表即可滿足大部分通信模式的需求，從而可以降低硬件設計復雜度，降低功耗及成本.對極少數需要創建大量多播組的情況，通過合并多播組，以犧牲少量性能的代價，滿足其需求.我們還對MR4LMS的運行時間進行了測試，結果表明其運行時間在可接受的范圍內，能夠滿足大規模并行應用的需求.

下一步我們將對MR4LMS算法做進一步的改進，優化其時間開銷及存儲開銷.同時，我們還需要對MR4LMS在真實應用課題中的性能進行更全面的評價.

作者貢獻聲明：陳淑平提出研究思路，設計并實現算法，進行試驗并對實驗數據進行分析，撰寫并修改論文；何王全參與實驗數據分析、論文審閱修訂；李祎參與算法實現、實驗驗證、數據分析、論文修訂；漆鋒濱負責課題監管與指導、論文審閱與修訂.