陳淑平 何王全 李 祎 漆鋒濱

(國(guó)家并行計(jì)算機(jī)工程技術(shù)研究中心 北京 100190)

(chenshuping_hit@163.com)

多播是一種重要的集合操作，對(duì)高性能應(yīng)用的性能具有重要的影響.它可以通過(guò)點(diǎn)對(duì)點(diǎn)消息實(shí)現(xiàn)，也可以通過(guò)專用的硬件實(shí)現(xiàn).相比用點(diǎn)對(duì)點(diǎn)消息實(shí)現(xiàn)的多播，硬件支持的多播操作具有性能高、CPU占用率低等優(yōu)點(diǎn)，正受到越來(lái)越多的關(guān)注.InfiniBand等高速互連網(wǎng)絡(luò)中，硬件支持的多播操作通過(guò)構(gòu)建多播樹(shù)實(shí)現(xiàn)，樹(shù)的高度、路由的負(fù)載均衡程度等對(duì)多播消息的性能具有至關(guān)重要的影響.過(guò)去的研究中，主要關(guān)注于降低樹(shù)高、提升路由負(fù)載均衡程度.

隨著超級(jí)計(jì)算機(jī)系統(tǒng)規(guī)模的不斷擴(kuò)大，多播組的個(gè)數(shù)急劇增加，可能會(huì)超過(guò)硬件支持的多播表(multicast forwarding table, MFT)條目數(shù)，而現(xiàn)有的多播路由算法沒(méi)有給出相應(yīng)的解決方案.為此，本文提出一種面向有限多播表?xiàng)l目數(shù)的多播路由算法，在硬件僅支持很小的多播表時(shí)，能夠支持創(chuàng)建數(shù)千甚至數(shù)萬(wàn)個(gè)多播組.本文主要貢獻(xiàn)有2個(gè)方面：

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

2) 在多種典型拓?fù)浣Y(jié)構(gòu)及典型通信模式下對(duì)MR4LMS的鏈路EFI、運(yùn)行時(shí)間等進(jìn)行了測(cè)試，獲得了令人滿意的性能開(kāi)銷，表明MR4LMS可用于大規(guī)?；ミB網(wǎng)絡(luò)系統(tǒng).

1 背景及相關(guān)工作

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

集合通信可以通過(guò)點(diǎn)對(duì)點(diǎn)消息實(shí)現(xiàn)，也可以通過(guò)專用的硬件集合操作實(shí)現(xiàn).很長(zhǎng)一段時(shí)間以來(lái)，無(wú)論是在廣域網(wǎng)還是在數(shù)據(jù)中心網(wǎng)絡(luò)中，硬件支持的集合操作由于其復(fù)雜度、可擴(kuò)展性、容錯(cuò)等方面的原因，并未得到廣泛應(yīng)用.例如，MPICH,MVAPICH, OpenMPI等[6-9]雖然也針對(duì)不同互連網(wǎng)絡(luò)提供了硬件版本的集合操作，但大部分用戶仍然選擇使用點(diǎn)到點(diǎn)版本的集合通信.

但是，基于點(diǎn)到點(diǎn)消息實(shí)現(xiàn)的集合操作，其性能與硬件支持的集合操作相比存在不小差距.一是同一數(shù)據(jù)包在很多鏈路上會(huì)傳輸多次，造成資源浪費(fèi).二是由于缺乏獲取底層網(wǎng)絡(luò)拓?fù)湫畔⒌哪芰?，集合操作的邏輯結(jié)構(gòu)不能適配底層網(wǎng)絡(luò)的物理結(jié)構(gòu)，導(dǎo)致其無(wú)法充分利用底層網(wǎng)絡(luò)的傳輸能力.隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，以軟件方式實(shí)現(xiàn)的集合操作面臨越來(lái)越嚴(yán)重的性能問(wèn)題；而硬件支持的集合操作具有性能高、CPU占用率低等優(yōu)點(diǎn)，正受到越來(lái)越多的關(guān)注.近幾年出現(xiàn)了很多硬件集合通信技術(shù)，如Mellanox的SHARP技術(shù)[10].

Fig. 1 Illustration for multicast tree圖1 多播樹(shù)示意圖

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

InfiniBand網(wǎng)絡(luò)中，OpenSM負(fù)責(zé)生成多播路由，基本原理是構(gòu)建1棵多播樹(shù)覆蓋參與多播操作的所有節(jié)點(diǎn).用戶根據(jù)需要?jiǎng)?chuàng)建很多個(gè)多播組，OpenSM為每個(gè)多播組構(gòu)建1棵多播樹(shù)，并占用多播路由表的1個(gè)條目號(hào).多播組的1個(gè)成員向其他成員進(jìn)行多播操作時(shí)，數(shù)據(jù)包沿著多播樹(shù)進(jìn)行傳輸.例如，在圖1所示的多播組中，陰影所示節(jié)點(diǎn)發(fā)送多播包時(shí)，每到達(dá)1個(gè)交換機(jī)，就查詢?cè)摱嗖ソM對(duì)應(yīng)的多播表?xiàng)l目，以決定將數(shù)據(jù)包從哪些端口分發(fā)出去.

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

InfiniBand規(guī)范[16]規(guī)定每個(gè)子網(wǎng)最多支持16 384個(gè)多播表?xiàng)l目.由此帶來(lái)的問(wèn)題是：隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，系統(tǒng)中多播組的個(gè)數(shù)也急劇增加，可能會(huì)超過(guò)硬件支持的多播表?xiàng)l目數(shù).很多情況下，多播表?xiàng)l目數(shù)不能滿足應(yīng)用程序的需要，原因包括：

1) 不同廠商的交換機(jī)支持的多播表?xiàng)l目數(shù)是不同的，有些廠商僅支持少量的多播條目數(shù)，以降低硬件成本及功耗.

2) 隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，應(yīng)用程序需要?jiǎng)?chuàng)建的多播組個(gè)數(shù)急劇增加，可能會(huì)超過(guò)16 384.例如，當(dāng)應(yīng)用程序規(guī)模達(dá)到262 144個(gè)進(jìn)程時(shí)，若將這些進(jìn)程組織成256×32×32的3維網(wǎng)格結(jié)構(gòu)，為每個(gè)維度中每行都創(chuàng)建1個(gè)多播組，則共需17 408個(gè)多播組，已經(jīng)超過(guò)了InfiniBand支持的最大多播組個(gè)數(shù).

OpenSM中現(xiàn)有的多播路由算法均默認(rèn)多播表?xiàng)l目數(shù)是夠用的，因此沒(méi)有給出當(dāng)多播表?xiàng)l目數(shù)不足時(shí)構(gòu)建多播表的方案.本文提出一種面向有限多播表?xiàng)l目數(shù)的多播路由算法，在硬件僅支持很小的多播表時(shí)，能夠支持創(chuàng)建數(shù)千甚至數(shù)萬(wàn)個(gè)多播組.

2 定義及假設(shè)

2.1 基本概念

定義1.互連網(wǎng)絡(luò).互連網(wǎng)絡(luò)是1個(gè)有向圖I=G(N,C)，其中N為網(wǎng)絡(luò)節(jié)點(diǎn)集合，C為通信鏈路集合.網(wǎng)絡(luò)節(jié)點(diǎn)又分為終端及交換機(jī).終端一般是網(wǎng)卡設(shè)備，用于收發(fā)數(shù)據(jù)；而交換機(jī)用于轉(zhuǎn)發(fā)數(shù)據(jù).

定義3.多播樹(shù).多播樹(shù)(multicast tree, MCT)是互連網(wǎng)絡(luò)有向圖的連通子圖，對(duì)應(yīng)互連網(wǎng)絡(luò)中的1棵樹(shù).該樹(shù)內(nèi)的1個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，會(huì)復(fù)制到該樹(shù)內(nèi)的所有節(jié)點(diǎn)中.為了實(shí)現(xiàn)多播功能，多播組必須映射到1棵多播樹(shù)中.1個(gè)多播組對(duì)應(yīng)1棵多播樹(shù)，但1棵多播樹(shù)可供多個(gè)多播組使用.

定義4.多播表?xiàng)l目號(hào).InfiniBand進(jìn)行路由時(shí)利用LID(local identification)進(jìn)行尋址.LID是16 b長(zhǎng)度的標(biāo)識(shí)符，其構(gòu)成的地址空間中，前49 152個(gè)用于單播路由，每個(gè)對(duì)應(yīng)子網(wǎng)中的1個(gè)節(jié)點(diǎn)，例如交換機(jī)、網(wǎng)卡等；后16 384個(gè)用于多播路由，稱為MLID(multicast identification)，每個(gè)對(duì)應(yīng)多播表中的1個(gè)條目.每個(gè)多播表?xiàng)l目都是1個(gè)位圖，每位對(duì)應(yīng)1個(gè)交換機(jī)端口.

用戶在發(fā)送多播消息時(shí)，需同時(shí)指定目的MGID及目的MLID.多播數(shù)據(jù)包中包含MGID及MLID字段.當(dāng)多播數(shù)據(jù)包在網(wǎng)絡(luò)中傳輸時(shí)，交換機(jī)以MLID為索引查找對(duì)應(yīng)的多播表?xiàng)l目，并將多播包復(fù)制到不同端口；而終端在收到多播包后，由于記錄了每個(gè)MGID包含哪些QP (queue pair)等信息，可以根據(jù)MGID將多播數(shù)據(jù)包放入不同的QP.InfiniBand協(xié)議規(guī)定：必須為每個(gè)多播組指定1個(gè)MLID，但多個(gè)多播組可共用同一個(gè)MLID.

不同廠商支持的多播路由表?xiàng)l目數(shù)不同，例如Mellanox每個(gè)交換機(jī)中的多播表?xiàng)l目數(shù)為16 384，而有些廠商采用精簡(jiǎn)InfiniBand協(xié)議，僅支持少量的多播條目數(shù).在本文中，多播表?xiàng)l目號(hào)與MLID含義相同，后文將交替使用這2個(gè)術(shù)語(yǔ).

需要指出的是，InfiniBand規(guī)范及現(xiàn)有文獻(xiàn)中，每個(gè)MLID僅能被1棵多播樹(shù)使用.而本文提出的多播路由算法中，只要不經(jīng)過(guò)相同的交換機(jī)，多棵多播樹(shù)就可以共用同一個(gè)MLID，即占用同一個(gè)多播表?xiàng)l目號(hào).

定義5.多播樹(shù)的染色.需要為每棵多播樹(shù)都分配1個(gè)多播表?xiàng)l目號(hào).在不考慮多播表大小的情況下，可以為每棵多播樹(shù)分配1個(gè)全局唯一的多播表?xiàng)l目號(hào).而在考慮到多播表有大小限制時(shí)，需要重用多播表?xiàng)l目號(hào).為多播樹(shù)分配多播表?xiàng)l目號(hào)時(shí)，必須遵循2個(gè)原則：1)同一棵多播樹(shù)在其使用的所有交換機(jī)內(nèi)使用相同的多播表?xiàng)l目號(hào)；2)若2棵多播樹(shù)經(jīng)過(guò)同一個(gè)交換機(jī)，則這2棵多播樹(shù)不能使用相同的多播表?xiàng)l目號(hào).可以用術(shù)語(yǔ)“染色”來(lái)描述多播表?xiàng)l目號(hào)分配問(wèn)題.構(gòu)建1個(gè)圖，將每棵多播樹(shù)作為圖的頂點(diǎn)；只要2棵多播樹(shù)經(jīng)過(guò)同一交換機(jī)，則稱這2棵多播樹(shù)“相鄰”，對(duì)應(yīng)的2個(gè)頂點(diǎn)間添加1條邊.我們將多播表?xiàng)l目號(hào)用顏色表示，顏色的數(shù)量等于交換機(jī)內(nèi)的多播表?xiàng)l目數(shù).為“相鄰”的多播樹(shù)指定不同的多播表?xiàng)l目號(hào)，也即用不同的顏色染色.后文將用術(shù)語(yǔ)“染色”表示為多播樹(shù)分配多播表?xiàng)l目號(hào).

定義6.EFI(edge forwarding index).文獻(xiàn)[17-18]定義了單播路由中的EFI指數(shù).我們對(duì)此進(jìn)行擴(kuò)展，將鏈路的EFI定義為經(jīng)過(guò)該鏈路的多播組個(gè)數(shù).所有鏈路的最大EFI值一定程度上反映了路由均衡程度，值越大表示擁塞程度越高.最大EFI由拓?fù)浣Y(jié)構(gòu)、路由算法、通信模式等決定，對(duì)多播操作性能具有重要影響，因此需要盡量降低最大EFI.

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

定義8.最小跳表.每個(gè)交換機(jī)都有1張最小跳表，邏輯上組織成2維表格形式，行號(hào)為i、列號(hào)為j的單元記錄了從該交換機(jī)的端口j出發(fā)到LID為i的目標(biāo)節(jié)點(diǎn)的最短路徑長(zhǎng)度.最小跳表是由OpenSM在拓?fù)涮讲殡A段構(gòu)建的.

為闡述定義1～8，以圖2為例進(jìn)行說(shuō)明.

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

1) 終端A,B組成1個(gè)多播組，MGID為ff00∷0001，其多播樹(shù)包含A,B,sw1及它們之間的鏈路，使用0號(hào)多播表?xiàng)l目；

2) 終端C,D組成另一個(gè)多播組，MGID為ff00∷0002，其多播樹(shù)包含C,D,sw2及它們之間的鏈路，由于該多播樹(shù)與1)中多播樹(shù)沒(méi)有共同的交換機(jī)，因此也使用0號(hào)多播表?xiàng)l目；

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

4) 終端F,H組成另外一個(gè)多播組，MGID為ff00∷0004；它與MGID為ff00∷0003的多播組共用同一棵多播樹(shù).當(dāng)ff00∷0003多播組內(nèi)的成員發(fā)送數(shù)據(jù)時(shí)， ff00∷0004多播組內(nèi)的網(wǎng)卡也會(huì)收到數(shù)據(jù)，但由于MGID不同，最終會(huì)刪掉這些數(shù)據(jù)包.

2.2 影響多播性能的因素

多播操作的性能受多播樹(shù)高度及鏈路EFI等的影響.僅考慮1個(gè)多播組時(shí)，多播樹(shù)高度對(duì)集合操作性能至關(guān)重要.當(dāng)網(wǎng)絡(luò)中有多個(gè)多播組同時(shí)收發(fā)消息時(shí)，鏈路EFI對(duì)集合操作的性能也有重要影響.

2.2.1 多播樹(shù)高度

多播樹(shù)高度會(huì)影響多播消息的延遲.我們構(gòu)建了如圖3所示的實(shí)驗(yàn)環(huán)境，并進(jìn)行了2組測(cè)試，每組測(cè)試均使用4個(gè)進(jìn)程構(gòu)成的多播組進(jìn)行多播操作，但2組測(cè)試中的進(jìn)程距離不同.第1組測(cè)試中，4個(gè)進(jìn)程位于拓?fù)浣Y(jié)構(gòu)中臨近的終端上，使用的多播樹(shù)高度為1.第2組測(cè)試中，4個(gè)進(jìn)程分散在拓?fù)浣Y(jié)構(gòu)中的不同位置，多播樹(shù)高度為2.每組測(cè)試中各種消息長(zhǎng)度均進(jìn)行5 000次測(cè)試，分別計(jì)算平均延遲及99%消息尾延遲.其中99%消息尾延遲的計(jì)算方法為：對(duì)這5 000個(gè)消息的延遲進(jìn)行排序，取末尾第4 950(5 000×99%)個(gè)消息的延遲.

Fig. 3 Experimental environment for testing the effect of multicast tree height on multicast performance圖3 用于測(cè)試多播樹(shù)高度對(duì)多播性能影響的實(shí)驗(yàn)環(huán)境

測(cè)試結(jié)果如表1所示.對(duì)小消息來(lái)說(shuō)，無(wú)論是平均值還是99%尾延遲都增長(zhǎng)了約20%；對(duì)2 KB消息來(lái)說(shuō)，增長(zhǎng)幅度在15%左右.這是因?yàn)閷?duì)長(zhǎng)消息來(lái)說(shuō)，增加的跳步數(shù)導(dǎo)致的時(shí)間開(kāi)銷相比數(shù)據(jù)拷貝的時(shí)間開(kāi)銷較小.可以預(yù)見(jiàn)，隨著廣播樹(shù)高度的增大，延遲增加會(huì)更加明顯.

Table1 Multicast Message Latency for Different Tree Height

2.2.2 鏈路EFI

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

Fig. 4 Experimental environment for testing the effect of EFI on multicast performance圖4 用于測(cè)試EFI對(duì)多播操作性能影響的實(shí)驗(yàn)環(huán)境

結(jié)果如表2所示.對(duì)8B長(zhǎng)度的小消息來(lái)說(shuō)，隨著EFI的增加，延遲會(huì)略有增加，但是由于數(shù)據(jù)長(zhǎng)度非常小，即使有多個(gè)廣播組經(jīng)過(guò)同一條鏈路，也不會(huì)對(duì)延遲造成很大影響.而對(duì)2 KB消息來(lái)說(shuō)，由于數(shù)據(jù)較大，EFI增大帶來(lái)的影響會(huì)比較明顯.例如EFI=16時(shí)，平均延遲會(huì)增大約38%；EFI=128時(shí)，平均延遲會(huì)增大約1066%.這對(duì)大量使用廣播操作的應(yīng)用程序來(lái)說(shuō)會(huì)帶來(lái)不可忽視的性能影響.需要指出的是，在實(shí)際運(yùn)行的課題中，共用同一條鏈路的多播組可能不會(huì)同時(shí)發(fā)送數(shù)據(jù)，此時(shí)EFI對(duì)多播消息性能的影響沒(méi)有實(shí)驗(yàn)所示的這么明顯.

Table2 Multicast Message Latency for Different EFI

2.3 多播路由算法的設(shè)計(jì)目標(biāo)

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

考慮到多播組的實(shí)際使用場(chǎng)景，我們對(duì)上述目標(biāo)進(jìn)行排序：首先必須滿足多播表?xiàng)l目數(shù)的限制，然后盡量降低多播樹(shù)高度及EFI指數(shù).以此為目標(biāo)，我們提出了面向有限多播表?xiàng)l目數(shù)的多播路由算法MR4LMS.

3 面向有限多播表?xiàng)l目數(shù)的多播路由

當(dāng)多播表?xiàng)l目數(shù)少于多播組個(gè)數(shù)時(shí)，我們有2種策略：1)構(gòu)建合適的多播樹(shù)，使它們使用不同的交換機(jī)，從而可以共用同一種顏色；2)使多個(gè)多播組共用1棵多播樹(shù)，從而減少多播樹(shù)數(shù)量.

我們提出了2種算法來(lái)構(gòu)造多播樹(shù)，并設(shè)計(jì)了開(kāi)銷模型從這2種算法中選擇一種使用.我們還提出了多播組合并算法，在顏色數(shù)不足時(shí)將多個(gè)多播組合并成1個(gè)虛擬多播組.下面具體介紹這些算法.表3列出了MR4LMS使用的符號(hào).

Table3 Symbols Used in MR4LMS

3.1 先構(gòu)造后染色算法

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

算法1.FBTC算法.

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

輸出：多播樹(shù)mct.

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

② for eachrootinrootList

③mct←build_mct_from_down_to_up(I,

root,mcg)；

④color←color_mcast_tree(mct)；

⑤ ifcolor是無(wú)效值 then

⑥ continue;

⑦ end if

⑧mcg.mct←mct;

⑨ 更新mct每條鏈路的權(quán)重;

⑩ 更新mct中每個(gè)交換機(jī)的多播路由表;

3.1.1 選擇樹(shù)根

算法1中行①代碼用于找出所有可能的樹(shù)根.樹(shù)根的位置決定了多播樹(shù)的高度，應(yīng)該選擇到多播組內(nèi)各成員最大跳步數(shù)最小的交換機(jī)作為樹(shù)根，以降低多播操作的延遲.根據(jù)各交換機(jī)的最小跳表，可以很容易地計(jì)算出每個(gè)交換機(jī)到多播組內(nèi)各成員的最少跳步數(shù)，并找出其中的最大值，從而找到所有的備選樹(shù)根.如果某個(gè)備選樹(shù)根的多播組條目號(hào)已用完，則需要忽略該樹(shù)根.當(dāng)有多個(gè)備選樹(shù)根時(shí)，可根據(jù)備選樹(shù)根的負(fù)載情況進(jìn)行排序，優(yōu)先使用負(fù)載低的樹(shù)根.在最壞情況下，其運(yùn)行時(shí)間上限為O(|N|2).在超大規(guī)模互連網(wǎng)絡(luò)中，可以利用多線程同時(shí)計(jì)算多個(gè)交換機(jī)的最大跳步數(shù).

3.1.2 自底向上構(gòu)建多播樹(shù)

算法1中行③代碼用于構(gòu)建多播樹(shù).此時(shí)需要考慮負(fù)載均衡問(wèn)題，也就是盡量使用負(fù)載低的鏈路.有2種方法可用于構(gòu)建負(fù)載均衡的多播樹(shù).

1) 采用SSSP-MC使用的方法，以經(jīng)過(guò)各鏈路的多播組個(gè)數(shù)作為權(quán)重，利用Dijkstra算法計(jì)算樹(shù)根到所有節(jié)點(diǎn)的單源最短路徑，從而構(gòu)造出1棵樹(shù).其時(shí)間復(fù)雜度為Θ(|E|+|N|log|N|).該方法的缺點(diǎn)是不管多播組中有多少個(gè)成員，都需要遍歷整個(gè)拓?fù)浣Y(jié)構(gòu)以構(gòu)建1棵包括所有節(jié)點(diǎn)的生成樹(shù)，因此其運(yùn)行時(shí)間較長(zhǎng).

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

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

算法2.build_mct_from_down_to_up.

輸入：互連網(wǎng)絡(luò)I=G(N,C)、多播組mcg、樹(shù)根root；

輸出：多播樹(shù)mct.

① 對(duì)N中每個(gè)節(jié)點(diǎ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的每個(gè)端口p，若curr.hops[root][p]==least_hop，則將該端口連接的遠(yuǎn)端節(jié)點(diǎn)ν加入隊(duì)列Q；

⑧ 從Q中找出具有最小權(quán)重的節(jié)點(diǎn)ν*;

⑨curr.parent←ν*;

⑩curr←ν*;

/*開(kāi)始構(gòu)建多播樹(shù)*/

3.1.3 為多播樹(shù)染色

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

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

3.2 先染色后構(gòu)造算法

FBTC算法在構(gòu)造多播樹(shù)時(shí)沒(méi)有考慮目前的顏色使用情況.當(dāng)可用的多播表?xiàng)l目很多時(shí)，可以快速構(gòu)建出多播樹(shù)；但當(dāng)可用的多播表?xiàng)l目數(shù)較少時(shí)，構(gòu)造出的多播樹(shù)很可能染色失敗，此時(shí)就需要嘗試使用其他的樹(shù)根.而在大規(guī)?；ミB網(wǎng)絡(luò)中，能夠作為備選樹(shù)根的交換機(jī)有成千上萬(wàn)臺(tái)，將所有交換機(jī)嘗試一遍是非常費(fèi)時(shí)的.尤其是當(dāng)系統(tǒng)中已經(jīng)存在大量多播組時(shí)，很可能?chē)L試了所有樹(shù)根仍不能染色成功，最終只能將該多播組合并到已有的多播組中，那么前面的所有嘗試都是徒勞的.

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

首先引入Gcolor子圖.每個(gè)交換機(jī)需要記錄各顏色的使用情況，其中colorBusy[color]表示對(duì)應(yīng)顏色是否已被使用，mcts[color]記錄了使用該顏色的多播樹(shù).

對(duì)每種顏色color，我們都可以構(gòu)造1個(gè)子圖Gcolor，構(gòu)造方法如下.以網(wǎng)絡(luò)拓?fù)鋱DG為基礎(chǔ)，檢查每條鏈路(μ,ν)，如果符合下列條件之一，則將該鏈路從圖中刪除:

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

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

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

實(shí)際上Gcolor由2部分組成：1)使用該顏色的所有多播樹(shù)包含的節(jié)點(diǎn)及鏈路；2)G中去掉使用該顏色的所有多播樹(shù)包含的節(jié)點(diǎn)及其所有鏈路后剩余的部分.在具體實(shí)現(xiàn)中，可以不用單獨(dú)存儲(chǔ)每個(gè)Gcolor，后面描述的所有對(duì)Gcolor的操作，均可通過(guò)G及colorBusy位圖實(shí)現(xiàn).

先染色后構(gòu)造算法具體過(guò)程見(jiàn)算法3.

算法3.FCTB算法.

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

輸出：多播樹(shù)mct.

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

② for 0到Ncolor-1范圍內(nèi)的每種color, do

③ 任選mcg的1個(gè)成員作為出發(fā)點(diǎn)，以廣度優(yōu)先搜索(breadth first search, BFS)在圖Gcolor中進(jìn)行遍歷；

④ 若mcg某個(gè)成員在Gcolor中不可達(dá)，則嘗試下一種顏色；

⑤ 對(duì)每個(gè)可達(dá)的樹(shù)根root,以它為出發(fā)點(diǎn)在Gcolor中進(jìn)行廣度優(yōu)先遍歷，計(jì)算root到mcg各成員的跳步數(shù)，若在Gcolor中的最大跳步數(shù)大于在G中的最大跳步數(shù)，則嘗試下一個(gè)樹(shù)根；

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

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

⑧ return NULL;

⑨mct←build_mct_by_dijkstra(I,mcg,

root,color)；

⑩ 更新mct每條鏈路的權(quán)重;

3.2.1 選擇顏色

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

FCTB需要執(zhí)行多次廣度優(yōu)先遍歷，時(shí)間開(kāi)銷較大.與FBTC一樣，F(xiàn)CTB最壞情況下運(yùn)行時(shí)間上限為O(Ncolor×|N|×(|E|+|N|)).但隨著Gcolor中鏈路數(shù)逐漸減少，進(jìn)行廣度優(yōu)先遍歷的時(shí)間會(huì)大大減少.尤其是當(dāng)系統(tǒng)中存在大量多播組時(shí)，對(duì)很多顏色來(lái)說(shuō)，多播組成員在Gcolor中已不是連通的，從而可以節(jié)省后續(xù)檢查時(shí)間，直接嘗試其他顏色.

3.2.2 在Gcolor中構(gòu)造多播樹(shù)

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

3.3 多播組合并算法

當(dāng)多播組個(gè)數(shù)太多而無(wú)法成功染色時(shí)，需要合并1個(gè)或多個(gè)已經(jīng)存在的多播組，形成1個(gè)大的虛擬多播組.

3.3.1 選擇被合并的多播組

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

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

2) 若合并后的多播組是非連通的，則基于最小跳表為合并后的多播組自底向上構(gòu)建1棵臨時(shí)的多播樹(shù).然后在Gcolor中檢查該臨時(shí)多播樹(shù)的每個(gè)交換機(jī)，若該顏色對(duì)應(yīng)的多播表?xiàng)l目已被使用，則將使用該條目的所有多播組也合并到虛擬多播組中，從而保證虛擬多播組在Gcolor中是連通的.

步驟1中，如何選擇最“相似”的多播組，對(duì)后續(xù)染色及多播性能具有重要影響.直觀上看，2個(gè)節(jié)點(diǎn)距離越近越“相似”.受此啟發(fā)，我們定義了多播組與多播樹(shù)間的距離：

(1)

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

上述過(guò)程實(shí)際上采用了2種策略選擇被合并的多播組：首先使用樂(lè)觀策略，選擇1個(gè)最相似的多播組進(jìn)行合并；如果合并后仍不能染色成功，則使用悲觀策略，將所需的多個(gè)多播組同時(shí)合并到一起.實(shí)際上，我們也可以全部采用樂(lè)觀策略：當(dāng)?shù)?次合并后仍不能染色成功時(shí)，則可以再選擇1個(gè)與合并后多播組最相似的多播組繼續(xù)合并，該過(guò)程一直重復(fù)，直到合并成功或?qū)⑺卸嗖ソM合并到一起.我們未采用該方法的原因是：當(dāng)系統(tǒng)中存在大量多播組時(shí)，可用的顏色數(shù)嚴(yán)重不足，可能需要進(jìn)行多次合并才能染色成功，而每次合并都需利用式(1)計(jì)算“相似度”，時(shí)間開(kāi)銷很大.

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

算法4.合并算法.

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

輸出：多播樹(shù)mct.

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

② 將mcg的成員與mct1合并，創(chuàng)建1個(gè)虛擬多播組vMcg；

③color←mct1.color;

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

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

⑤ 為vMcg選擇1個(gè)樹(shù)根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構(gòu)建多播樹(shù)*/

root,color)；

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

3.3.2 利用Dijkstra構(gòu)建多播樹(shù)

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

1) 銷毀舊的多播樹(shù)，為vMcg重新創(chuàng)建1棵多播樹(shù).由于需要為原有的多播組重新計(jì)算并更新路由，該方法可能會(huì)導(dǎo)致短暫的路由一致性問(wèn)題，即在更新路由的過(guò)程中出現(xiàn)丟包等現(xiàn)象.此時(shí)需要由上層應(yīng)用采用其他手段保證可靠傳輸.

2) 不銷毀舊的多播樹(shù)，而是在原多播樹(shù)上通過(guò)添加枝葉形成1棵新的、更大的多播樹(shù)，從而保證原來(lái)那些多播組不受影響.缺點(diǎn)是構(gòu)建的多播樹(shù)可能不是最優(yōu)的.

我們同時(shí)支持這2種策略，用戶可以通過(guò)環(huán)境變量選擇一種.下面介紹第2種方法，偽代碼見(jiàn)算法5.行②～④是標(biāo)準(zhǔn)的Dijkstra算法.行⑤～用于將舊的多播樹(shù)鏈入新多播樹(shù).每處理完1個(gè)節(jié)點(diǎn)，就檢查該節(jié)點(diǎn)是否在原多播樹(shù)中.如果是，則從該節(jié)點(diǎn)出發(fā)，用廣度優(yōu)先遍歷將原多播樹(shù)中的所有節(jié)點(diǎn)及鏈路加入新產(chǎn)生的多播樹(shù)中.

算法5.build_mct_by_dijkstra.

輸入：互連網(wǎng)絡(luò)I=G(N,C)、多播組mcg、樹(shù)根root、顏色color、舊的多播樹(shù)對(duì)應(yīng)的圖I′=G(N′,C′)；

輸出：多播樹(shù)mct.

① 對(duì)N中每個(gè)節(jié)點(diǎn)ω做初始化，設(shè)置ω.parent←?,ω.distance←∞，并設(shè)置root.dist←0，Q←N;

② whileQ≠? do

③ 在Q中找到具有最小dist的節(jié)點(diǎn)μ，并從Q中刪除節(jié)點(diǎn)μ；

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

⑤ ifμ∈N′

⑥QBFS←{μ};

⑦ whileQBFS≠? do

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

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

⑩ 若υ′不是舊多播樹(shù)中的節(jié)點(diǎn)，且μ′.dist+weight(e)<υ′.dist，則設(shè)置υ′.dist←μ′.dist+weight(e)，υ′.parent←e；

/*開(kāi)始構(gòu)建多播樹(shù)*/

3.3.3 刪除多播組

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

算法6.從多播樹(shù)中刪除1個(gè)多播組.

輸入：多播樹(shù)mct、多播組mcg.

① 初始化1個(gè)空隊(duì)列Q；

② 將mcg的每個(gè)成員從mct中刪掉；

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

④ whileQ≠? do

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

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

⑦ end while

3.4 時(shí)間開(kāi)銷模型及算法選擇

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

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

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

算法7.MR4LMS算法.

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

輸出：多播樹(shù)mct.

① ifcurrent_alg為FBTC then

②mct←FBTC(I,mcg);

③ 若失敗，則設(shè)置current_alg為FCTB;

④ else

⑤mct←FCTB(I,mcg);

⑥ 若成功，且連續(xù)成功的次數(shù)達(dá)到20，則設(shè)置current_alg為FBTC;

⑦ end if

⑧ 若mct創(chuàng)建失敗，則利用算法4創(chuàng)建mct;

⑨ returnmct.

4 實(shí)現(xiàn)及實(shí)驗(yàn)評(píng)估

4.1 實(shí) 現(xiàn)

我們?cè)贠penSM 3.3.22中實(shí)現(xiàn)了MR4LMS，共有約5 000行代碼.為了支持多棵多播樹(shù)共用1個(gè)多播表?xiàng)l目號(hào)，我們對(duì)OpenSM源碼進(jìn)行了修改，包括為每棵多播樹(shù)(OpenSM中稱為mbox)添加color字段，用戶在發(fā)送多播消息時(shí)指定的不再是MLID，而是該color值.

另外，我們還對(duì)加入、離開(kāi)多播組的機(jī)制進(jìn)行了簡(jiǎn)單的修改，以解決頻繁重算路由的問(wèn)題.加入多播組時(shí)，不是每收到1個(gè)加入多播組的請(qǐng)求就重算路由，而是等收齊同一個(gè)多播組的所有請(qǐng)求之后再計(jì)算路由.1個(gè)成員離開(kāi)多播組后，也不重算路由；僅當(dāng)所有成員均離開(kāi)后，再刪掉該多播組.

為了提升運(yùn)行速度，我們?cè)诤芏嗟胤绞褂昧硕嗑€程進(jìn)行加速，包括：1)利用式(1)計(jì)算2個(gè)多播組間的距離時(shí)；2)計(jì)算各交換機(jī)到多播組內(nèi)各成員最大距離時(shí)；3)在Gcolor內(nèi)進(jìn)行廣度優(yōu)先搜索時(shí).

4.2 實(shí)驗(yàn)環(huán)境

我們使用ibsim-0.7[19]模擬各種網(wǎng)絡(luò)拓?fù)?；使用測(cè)試程序模擬發(fā)起加入或離開(kāi)多播組的請(qǐng)求.OpenSM運(yùn)行在1臺(tái)48核Intel Xeon E5-2680 v3服務(wù)器上，頻率為2.50 GHz.需要指出的是，在ibsim下的測(cè)試結(jié)果跟在真實(shí)網(wǎng)絡(luò)環(huán)境下的測(cè)試結(jié)果是一樣的，因?yàn)楹竺鏈y(cè)試的EFI及運(yùn)行時(shí)間等性能數(shù)據(jù)跟是否使用ibsim模擬拓?fù)浣Y(jié)構(gòu)無(wú)關(guān).

4.2.1 拓?fù)浣Y(jié)構(gòu)

我們將在不同拓?fù)浣Y(jié)構(gòu)下對(duì)MR4LMS的性能進(jìn)行測(cè)試，包括2個(gè)超算中心使用的拓?fù)?，以及幾種典型的人造拓?fù)浣Y(jié)構(gòu)(包括標(biāo)準(zhǔn)胖樹(shù)[20-21]、3D環(huán)網(wǎng)、蜻蜓網(wǎng)絡(luò)[22]等).

1) 超算中心的拓?fù)浣Y(jié)構(gòu)

我們利用ibnetdiscover獲得了2個(gè)超算中心的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，包括“神威藍(lán)光”計(jì)算機(jī)及“神威太湖之光”計(jì)算機(jī).“神威藍(lán)光”計(jì)算機(jī)[23]安裝于濟(jì)南超算中心，包含8 704個(gè)運(yùn)算處理器，采用裁剪胖樹(shù)結(jié)構(gòu)[24]，每個(gè)葉子交換機(jī)與最頂層交換機(jī)間都有8條路徑.“神威太湖之光”計(jì)算機(jī)[25-26]安裝于無(wú)錫超算中心，包含40 960個(gè)運(yùn)算處理器，是目前世界上規(guī)模最大的InfiniBand網(wǎng)絡(luò)，其結(jié)構(gòu)與“神威藍(lán)光”類似，但規(guī)模更大，每個(gè)葉子交換機(jī)與最頂層交換機(jī)間都有2條路徑.

2) 典型的人造拓?fù)浣Y(jié)構(gòu)

包括4種拓?fù)洌?/p>

① 3層胖樹(shù).采用40端口交換機(jī)構(gòu)建標(biāo)準(zhǔn)3層胖樹(shù)結(jié)構(gòu)，終端個(gè)數(shù)N=16 000.

② 3D -Torus.構(gòu)造了30×20×20的3D -Torus網(wǎng)絡(luò)，每個(gè)交換機(jī)連接2個(gè)終端，終端個(gè)數(shù)為N=24 000.

③ 蜻蜓網(wǎng)絡(luò).配置參數(shù)為a=18,p=h=9，終端個(gè)數(shù)N=26 406.

④ 隨機(jī)網(wǎng)絡(luò).共2 048臺(tái)40口交換機(jī)，每臺(tái)交換機(jī)20個(gè)端口連接網(wǎng)卡，另外20個(gè)端口隨機(jī)連接到其他交換機(jī)端口，終端個(gè)數(shù)為N=40 960.

4.2.2 通信模式

MPI集合通信中，主要有2種通信域劃分方法[27-28]：1)劃分成2維或3維網(wǎng)格，其每個(gè)維度中每行或每列都是1個(gè)通信域，對(duì)應(yīng)1個(gè)多播組.2)劃分成層次結(jié)構(gòu)，例如樹(shù)型結(jié)構(gòu)，每層分成很多組，每個(gè)組構(gòu)成1個(gè)通信域；每個(gè)組再選出1個(gè)leader，形成更高層次的組.劃分成網(wǎng)格時(shí)，通信域內(nèi)的成員數(shù)較少，但通信域的個(gè)數(shù)很多，對(duì)多播表?xiàng)l目數(shù)的需求量更大.后面實(shí)驗(yàn)中，我們采用2維及3維網(wǎng)格劃分進(jìn)程，以測(cè)試存在大量多播組時(shí)多播路由算法的性能.對(duì)每種拓?fù)浣Y(jié)構(gòu)，我們都測(cè)試了多種典型的通信模式，包括2維及3維網(wǎng)格模式，以及隨機(jī)加入多播組的模式.

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

Fig. 6 Counts of MCGs and colors for different topologies and communication patters圖6 不同拓?fù)浜屯ㄐ拍Ｊ较碌亩嗖ソM個(gè)數(shù)及所需顏色數(shù)

需要指出的是，F(xiàn)BTC及FCTB算法在選擇樹(shù)根時(shí)，僅考慮了那些到多播組內(nèi)各成員最大距離最小的交換機(jī)作為備選樹(shù)根，因此構(gòu)造出的多播樹(shù)高度是最低的；而合并算法也優(yōu)先考慮到多播組內(nèi)各成員最大距離小的交換機(jī)作為樹(shù)根.因此，影響多播性能的2個(gè)因素中，我們僅測(cè)試最大鏈路EFI，而不再關(guān)注多播樹(shù)高度.

4.3 無(wú)合并時(shí)所需的顏色數(shù)

MR4LMS中，只要2棵多播樹(shù)不使用同一個(gè)交換機(jī)，它們就可以共用同一個(gè)多播表?xiàng)l目號(hào)，從而使所需的多播表?xiàng)l目數(shù)少于多播組個(gè)數(shù).對(duì)每種拓?fù)浣Y(jié)構(gòu)，我們都通過(guò)實(shí)驗(yàn)測(cè)試MR4LMS算法在典型通信模式下所需的多播表?xiàng)l目數(shù)，并據(jù)此為每種拓?fù)浣Y(jié)構(gòu)選擇1個(gè)合理的Ncolor值.我們測(cè)試了6種典型的通信模式，包括2種2維網(wǎng)格結(jié)構(gòu)，該模式下每個(gè)終端運(yùn)行1個(gè)進(jìn)程；2種3維網(wǎng)格結(jié)構(gòu)，每個(gè)終端運(yùn)行1個(gè)進(jìn)程； 1種隨機(jī)多播組模式，每個(gè)終端運(yùn)行1個(gè)進(jìn)程；1種3維網(wǎng)格結(jié)構(gòu)，每個(gè)終端運(yùn)行4個(gè)進(jìn)程.

測(cè)試最后2種通信模式的目的是觀察MR4LMS在創(chuàng)建大量多播組時(shí)的性能；實(shí)際應(yīng)用課題一般不采用這2種通信模式.前面4種2維或3維網(wǎng)格模式中，有些是按拓?fù)浣Y(jié)構(gòu)進(jìn)行劃分，模擬拓?fù)涓兄耐ㄐ拍Ｊ絒27-28]；有些劃分成正方形或立方體形狀，模擬拓?fù)錈o(wú)感的通信模式.以神威藍(lán)光為例，256×34通信模式下，第1維有34個(gè)多播組，每個(gè)組都位于同一個(gè)運(yùn)算中板內(nèi)，因此通信模式與拓?fù)浣Y(jié)構(gòu)匹配.而90×90通信模式下，存在很多跨運(yùn)算中板的多播組，因此通信模式與拓?fù)浣Y(jié)構(gòu)不匹配.

測(cè)試結(jié)果如圖6所示，圖6(a)～(c)分別是神威藍(lán)光、神威太湖之光以及3層標(biāo)準(zhǔn)胖樹(shù)結(jié)構(gòu)下的測(cè)試結(jié)果.存在下列現(xiàn)象：

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

2) 大部分通信模式下，所需的顏色數(shù)少于128.因此，在這3種拓?fù)浣Y(jié)構(gòu)中，Ncolor=128對(duì)大部分多播通信模式來(lái)說(shuō)是夠用的.

3) 通信模式是否與底層拓?fù)浣Y(jié)構(gòu)匹配，對(duì)所需的顏色數(shù)影響不大.例如，圖6(a)中256×34模式需要29種顏色，而90×90需要50種顏色，沒(méi)有劇烈增加.

圖6(d)顯示了3D環(huán)網(wǎng)下的測(cè)試結(jié)果.3D環(huán)網(wǎng)中雖然也有很多冗余路徑，但這些冗余路徑有共用的交換機(jī)，因此很多MCG需要經(jīng)過(guò)相同的鏈路，導(dǎo)致所需的顏色數(shù)較大.當(dāng)通信模式與拓?fù)浣Y(jié)構(gòu)匹配時(shí)(例如240×100，60×20×20)，所需顏色數(shù)很少.當(dāng)通信模式與拓?fù)浣Y(jié)構(gòu)不匹配時(shí)，所需顏色數(shù)較大，最大達(dá)到了2166.圖6(e)(f)分別顯示了蜻蜓網(wǎng)絡(luò)和隨機(jī)網(wǎng)絡(luò)下的測(cè)試結(jié)果.與3D環(huán)網(wǎng)一樣，由于互不干擾的冗余路徑較少，這2種拓?fù)浣Y(jié)構(gòu)下所需的顏色數(shù)也較大，最大分別為486，2852.

4.4 無(wú)合并時(shí)的最大EFI

本節(jié)將測(cè)試無(wú)合并時(shí)MR4LMS算法的最大EFI，與MINIHOP-MC及SSSP-MC多播路由算法進(jìn)行比較，結(jié)果如圖7所示.可以發(fā)現(xiàn)，大部分情況下MR4LMS算法的EFI明顯低于MINIHOP-MC算法，而與SSSP-MC算法基本相當(dāng).MINIHOP-MC的EFI較大的原因是，它沒(méi)有考慮多個(gè)多播組間的負(fù)載均衡問(wèn)題，因此多個(gè)多播組可能共用同一條鏈路.該測(cè)試結(jié)果表明，MR4LMS產(chǎn)生的多播表，其性能高于MINIHOP-MC，而與SSSP-MC基本相當(dāng).

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

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

4.5 合并算法有效性測(cè)試

合并多播組會(huì)導(dǎo)致鏈路EFI升高，影響多播消息性能.圖8顯示了2種通信模式下不同Ncolor的最大EFI變化情況：1)神威太湖之光下的34×34×34通信模式；2)隨機(jī)網(wǎng)絡(luò)下的32×32×40通信模式.可以發(fā)現(xiàn)，如果將Ncolor設(shè)成較小的值，會(huì)導(dǎo)致最大EFI變的很大，對(duì)多播消息性能造成影響.

我們?yōu)樯鲜?種拓?fù)浣Y(jié)構(gòu)采用如表4所示的Ncolor配置，并測(cè)試各種通信模式下的最大EFI及TFI，以檢驗(yàn)這些Ncolor是否合理.對(duì)其他拓?fù)浣Y(jié)構(gòu)及網(wǎng)絡(luò)規(guī)模，也可以采用類似方法：先確定其典型的通信模式，并通過(guò)實(shí)驗(yàn)確定1個(gè)合適的Ncolor，使得大部分通信模式下Ncolor是夠用的，或合并后EFI沒(méi)有顯著增加，從而在多播表大小與多播消息性能間進(jìn)行適當(dāng)?shù)钠胶?

Table4 Ncolor Used in MR4LMS

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

4.5.1 推薦Ncolor下的EFI

本節(jié)將測(cè)試推薦Ncolor下的最大EFI.對(duì)每種拓?fù)浣Y(jié)構(gòu)，我們都進(jìn)行2組對(duì)比實(shí)驗(yàn)：1)將Ncolor設(shè)為無(wú)窮大，從而保證不會(huì)發(fā)生合并；2)測(cè)試推薦的Ncolor.每組測(cè)試都分別記錄各通信模式下的最大EFI，結(jié)果如圖9所示.存在下列現(xiàn)象：

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

2) 少量通信模式下，由于顏色數(shù)不夠用，需要合并多播組，其中一部分通信模式合并后EFI與無(wú)合并時(shí)相比并無(wú)顯著增加.例如，在神威藍(lán)光下，Ncolor=128時(shí)僅64×16×34模式下需要合并多播組，最大EFI由無(wú)合并時(shí)的24增加到58；隨機(jī)網(wǎng)絡(luò)拓?fù)渲?，Ncolor=256時(shí)256×160模式下需要合并多播組，最大EFI由無(wú)合并時(shí)的20增加到34.

3) 還有一部分通信模式，合并后EFI顯著增大.例如，在神威太湖之光中，128×32×40模式下最大EFI由無(wú)合并時(shí)的37增加到300；在隨機(jī)拓?fù)渲校?28×32×40模式下最大EFI由無(wú)合并時(shí)的139增加到4 687.最大EFI劇烈增加的情況基本都出現(xiàn)在每個(gè)處理器運(yùn)行4個(gè)進(jìn)程的通信模式下.這是因?yàn)槊總€(gè)處理器上有4個(gè)進(jìn)程時(shí)，每個(gè)交換機(jī)上多播組的個(gè)數(shù)顯著增加.例如在胖樹(shù)結(jié)構(gòu)中，原來(lái)每個(gè)處理器上僅有1個(gè)進(jìn)程時(shí)，每個(gè)葉子交換機(jī)上僅有20個(gè)進(jìn)程，在3維網(wǎng)格通信模式下，最多需要60個(gè)多播組(實(shí)際上不需要這么多多播組，因?yàn)橛行┻M(jìn)程可能位于同一個(gè)多播組內(nèi)).而當(dāng)每個(gè)處理器上有4個(gè)進(jìn)程時(shí)，每個(gè)葉子交換機(jī)上有80個(gè)進(jìn)程，在3維網(wǎng)格通信模式下，最多需要240個(gè)多播組，導(dǎo)致多播組的個(gè)數(shù)超過(guò)交換機(jī)支持的多播表?xiàng)l目數(shù)，因此需要進(jìn)行很多多播組合并操作.

在實(shí)際應(yīng)用場(chǎng)景中，很少會(huì)遇到這樣的通信模式，因?yàn)楫?dāng)1個(gè)處理器上運(yùn)行多個(gè)進(jìn)程時(shí)，用戶一般會(huì)為它們建立1個(gè)單獨(dú)的通信域用于處理器內(nèi)的集合通信，并從中選擇一個(gè)作為leader用于處理器間的集合通信.

4) 3D環(huán)網(wǎng)中，28×28×28通信模式下，Ncolor=256時(shí)的最大EFI反而低于Ncolor無(wú)限制時(shí).這是因?yàn)樵陬伾珨?shù)足夠時(shí)，F(xiàn)BTC算法在嘗試第1個(gè)樹(shù)根時(shí)總會(huì)成功，而它采用貪心策略根據(jù)局部信息進(jìn)行負(fù)載均衡，有可能產(chǎn)生非最優(yōu)的解，也即產(chǎn)生最大EFI非最小的多播樹(shù).

綜上所述，我們選擇的Ncolor對(duì)大部分通信模式來(lái)說(shuō)，不需要合并多播組；部分通信模式需要合并多播組，但合并后EFI沒(méi)有顯著增加，因此不會(huì)對(duì)多播消息性能帶來(lái)嚴(yán)重影響；極少數(shù)需要?jiǎng)?chuàng)建超過(guò)1萬(wàn)個(gè)多播組的情況，合并后EFI可能會(huì)顯著增加，但用戶使用該類通信模式的情況較少.

4.5.2 推薦Ncolor下的TFI

最大TFI反映了有多少個(gè)多播組共用1棵多播樹(shù).TFI越小越好；當(dāng)沒(méi)有合并發(fā)生時(shí)，TFI=1.本節(jié)將測(cè)試推薦Ncolor下的最大TFI，以進(jìn)一步觀察多播組的合并情況，檢查是否存在大量多播組合并到同一棵多播樹(shù)的情況.我們統(tǒng)計(jì)了每種通信模式下的最大TFI，測(cè)試結(jié)果如圖10所示.可以發(fā)現(xiàn)，每個(gè)處理器上運(yùn)行1個(gè)進(jìn)程的通信模式中，TFI最大為10，表明最多有10個(gè)多播組共用1棵多播樹(shù).而在每個(gè)處理器上運(yùn)行4個(gè)進(jìn)程的通信模式中，TFI最大為66.

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

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

上述實(shí)驗(yàn)表明：MR4LMS在合并多播組時(shí)，能夠較均勻地選擇多播條目號(hào)，從而使每個(gè)多播條目號(hào)下多播組個(gè)數(shù)大體相等，而不是將所有多播組合并成1棵包含所有節(jié)點(diǎn)的多播樹(shù).

4.6 算法運(yùn)行時(shí)間

超大規(guī)?；ミB網(wǎng)絡(luò)中可能存在大量多播組，多播路由算法需要在較短的時(shí)間內(nèi)完成多播路由的計(jì)算.本節(jié)將對(duì)MR4LMS計(jì)算多播路由的時(shí)間進(jìn)行測(cè)試.

對(duì)每種拓?fù)浣Y(jié)構(gòu)，我們都進(jìn)行2組對(duì)比實(shí)驗(yàn)：1)將Ncolor設(shè)為無(wú)窮大，從而保證不會(huì)發(fā)生合并；2)測(cè)試推薦的Ncolor，分別記錄各通信模式下MR4LMS的運(yùn)行時(shí)間.測(cè)試結(jié)果如圖12所示.該時(shí)間僅包括計(jì)算路由的時(shí)間(包括選擇樹(shù)根、構(gòu)建多播樹(shù)、為多播樹(shù)染色)，不包括發(fā)送加入多播組請(qǐng)求、分發(fā)路由等其他步驟的開(kāi)銷.存在3種現(xiàn)象：

1) 算法運(yùn)行時(shí)間跟創(chuàng)建的多播組個(gè)數(shù)有關(guān)，胖樹(shù)結(jié)構(gòu)、蜻蜓網(wǎng)絡(luò)平均約5 ms創(chuàng)建1個(gè)多播組，3D -Torus、隨機(jī)網(wǎng)絡(luò)平均約9 ms創(chuàng)建1個(gè)多播組.

2) 除去每個(gè)處理器上運(yùn)行4個(gè)進(jìn)程的通信模式，最長(zhǎng)運(yùn)行時(shí)間為40.6 s.每個(gè)處理器上運(yùn)行4個(gè)進(jìn)程的通信模式下，Ncolor無(wú)限制時(shí)，最長(zhǎng)運(yùn)行時(shí)間為48.0 s；推薦Ncolor下，最長(zhǎng)運(yùn)行時(shí)間為191.5 s，均在可接受的范圍內(nèi).

3) 每種通信模式下，推薦Ncolor下的運(yùn)行時(shí)間與Ncolor無(wú)限制時(shí)相比，最多增加3倍.某些通信模式下，時(shí)間開(kāi)銷增加較大，原因是顏色數(shù)不夠時(shí)，需要花費(fèi)更多的時(shí)間在Gcolor中進(jìn)行廣度優(yōu)先搜索，以及進(jìn)行合并操作.

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

Fig. 12 Runtime of MR4LMS圖12 MR4LMS的運(yùn)行時(shí)間

4.7 討 論

本節(jié)將從運(yùn)行時(shí)間、適用范圍等方面對(duì)MR4LMS算法進(jìn)行進(jìn)一步的討論.

1) 運(yùn)行時(shí)間

大部分應(yīng)用中，各通信域劃分好之后一般不會(huì)頻繁變動(dòng)，因此僅在應(yīng)用程序初始化階段才需要?jiǎng)?chuàng)建多播組.對(duì)那些運(yùn)行時(shí)間超過(guò)數(shù)小時(shí)、甚至數(shù)天的應(yīng)用而言，利用MR4LMS創(chuàng)建多播組的時(shí)間一般不超過(guò)數(shù)十秒，因此MR4LMS的運(yùn)行時(shí)間并不會(huì)對(duì)應(yīng)用性能帶來(lái)嚴(yán)重影響.

當(dāng)然，當(dāng)網(wǎng)絡(luò)拓?fù)浠蛲ㄐ庞騽澐址绞筋l繁變動(dòng)而需要重算多播路由時(shí)，MR4LMS算法的時(shí)間開(kāi)銷會(huì)給應(yīng)用程序的性能帶來(lái)不可忽略的影響.下一步我們將繼續(xù)對(duì)MR4LMS算法進(jìn)行改進(jìn)以降低其運(yùn)行時(shí)間，一種可行的思路是針對(duì)特定的拓?fù)浣Y(jié)構(gòu)進(jìn)行相應(yīng)優(yōu)化.

2) 適用范圍

MR4LMS并不針對(duì)特定的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).我們?cè)谂謽?shù)、3D環(huán)網(wǎng)、蜻蜓網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)等常見(jiàn)網(wǎng)絡(luò)中測(cè)試了該算法的性能，都能夠獲得不錯(cuò)的EFI指標(biāo).但該算法并不適用于動(dòng)態(tài)可配置的網(wǎng)絡(luò)，如光開(kāi)關(guān)控制的網(wǎng)絡(luò)，因?yàn)檫@些網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)會(huì)頻繁變動(dòng)，導(dǎo)致需要頻繁計(jì)算多播路由；而MR4LMS的運(yùn)行時(shí)間較長(zhǎng)，頻繁計(jì)算多播路由會(huì)對(duì)應(yīng)用性能帶來(lái)影響.

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

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

5 結(jié) 論

本文提出一種面向有限多播表?xiàng)l目數(shù)的多播路由算法，在硬件僅支持很小的多播表時(shí)，能夠支持創(chuàng)建數(shù)千甚至數(shù)萬(wàn)個(gè)多播組.我們采用2種策略來(lái)達(dá)到此目的：1)構(gòu)建合適的多播樹(shù)，使它們使用不同的交換機(jī)，從而可以共用同一種顏色；2)使多個(gè)多播組共用1棵多播樹(shù)，從而減少多播樹(shù)數(shù)量.

我們對(duì)MR4LMS進(jìn)行了大量測(cè)試，結(jié)果表明，通過(guò)維護(hù)1個(gè)較小的多播表即可滿足大部分通信模式的需求，從而可以降低硬件設(shè)計(jì)復(fù)雜度，降低功耗及成本.對(duì)極少數(shù)需要?jiǎng)?chuàng)建大量多播組的情況，通過(guò)合并多播組，以犧牲少量性能的代價(jià)，滿足其需求.我們還對(duì)MR4LMS的運(yùn)行時(shí)間進(jìn)行了測(cè)試，結(jié)果表明其運(yùn)行時(shí)間在可接受的范圍內(nèi)，能夠滿足大規(guī)模并行應(yīng)用的需求.

下一步我們將對(duì)MR4LMS算法做進(jìn)一步的改進(jìn)，優(yōu)化其時(shí)間開(kāi)銷及存儲(chǔ)開(kāi)銷.同時(shí)，我們還需要對(duì)MR4LMS在真實(shí)應(yīng)用課題中的性能進(jìn)行更全面的評(píng)價(jià).

作者貢獻(xiàn)聲明：陳淑平提出研究思路，設(shè)計(jì)并實(shí)現(xiàn)算法，進(jìn)行試驗(yàn)并對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分析，撰寫(xiě)并修改論文；何王全參與實(shí)驗(yàn)數(shù)據(jù)分析、論文審閱修訂；李祎參與算法實(shí)現(xiàn)、實(shí)驗(yàn)驗(yàn)證、數(shù)據(jù)分析、論文修訂；漆鋒濱負(fù)責(zé)課題監(jiān)管與指導(dǎo)、論文審閱與修訂.