陳淑平 李 祎 何王全 漆鋒濱

(江南計(jì)算技術(shù)研究所 江蘇無(wú)錫 214083)(chenshuping_hit@163.com)

在高性能計(jì)算領(lǐng)域，多播路由算法對(duì)硬件支持的集合操作性能具有至關(guān)重要的影響.例如，集合通信中的Bcast,Barrier,AllReduce,AllGather等操作均可通過(guò)多播進(jìn)行加速.多播路由算法通過(guò)構(gòu)建多播樹(shù)實(shí)現(xiàn).過(guò)去主要研究如何降低樹(shù)高、如何提升路由負(fù)載均衡程度.目前高性能計(jì)算已經(jīng)邁入E級(jí)計(jì)算時(shí)代，系統(tǒng)中多播組的個(gè)數(shù)急劇增加，可能會(huì)超過(guò)硬件支持的多播表?xiàng)l目數(shù)，而現(xiàn)有的多播路由算法要么沒(méi)有給出解決方案，要么存在時(shí)間開(kāi)銷(xiāo)大、多播路由經(jīng)常變化等問(wèn)題.為此，本文提出一種用于胖樹(shù)的高效實(shí)用的定制多播路由算法(customized multicast routing for limited multicast forwarding table size, C-MR4LMS)，可用于包括Infiniband在內(nèi)的高速互連網(wǎng)絡(luò).本文主要貢獻(xiàn)包括：

1) 對(duì)胖樹(shù)結(jié)構(gòu)中可使用的無(wú)沖突多播生成樹(shù)個(gè)數(shù)進(jìn)行了量化研究，根據(jù)系統(tǒng)中的最大多播組個(gè)數(shù)確定多播表的大小，為設(shè)計(jì)互連網(wǎng)絡(luò)系統(tǒng)提供了理論依據(jù).

2) 提出了一種用于胖樹(shù)拓?fù)涞母咝?shí)用的定制多播路由算法C-MR4LMS，可根據(jù)MGID(multicast global identification)靜態(tài)地將多播組映射到1棵生成樹(shù)中，快速完成多播樹(shù)的構(gòu)建；當(dāng)需要合并多播組時(shí)，僅需合并那些使用同一生成樹(shù)的多播組，且僅需添加部分鏈路即可完成多播組的合并，不會(huì)改變被合并多播組的路由，因此不會(huì)影響這些多播組的正常使用.

3) 提出了分層的MGID分配策略，當(dāng)同一終端節(jié)點(diǎn)同時(shí)加入多個(gè)多播組時(shí)，每個(gè)多播組都使用不同層內(nèi)的MGID，避免出現(xiàn)同一終端節(jié)點(diǎn)使用同一顏色加入多個(gè)多播組的情況.

4) 提出了相互無(wú)干擾的作業(yè)節(jié)點(diǎn)分配策略，使得2個(gè)作業(yè)不共用任何通信鏈路，保證2個(gè)作業(yè)的多播組互不干擾.

5) 在多種典型拓?fù)浣Y(jié)構(gòu)及典型通信模式下對(duì)C-MR4LMS的鏈路EFI、TFI、運(yùn)行時(shí)間及應(yīng)用程序性能等進(jìn)行了測(cè)試，驗(yàn)證了其有效性.

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

集合通信[1-4]為實(shí)現(xiàn)一組進(jìn)程間的通信提供了非常方便的抽象，被廣泛應(yīng)用于高性能計(jì)算領(lǐng)域.它包括同步、廣播、規(guī)約、全規(guī)約、分散、收集、全收集等類(lèi)型及其變體，可實(shí)現(xiàn)多個(gè)進(jìn)程間的同步、數(shù)據(jù)分發(fā)與收集等功能.傳統(tǒng)的集合通信一般是由軟件利用點(diǎn)到點(diǎn)消息實(shí)現(xiàn)的.但隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，超級(jí)計(jì)算機(jī)對(duì)集合通信的性能及可擴(kuò)展性都提出了更高的要求，而軟件集合通信難以滿足E級(jí)系統(tǒng)的需求.硬件集合通信可將集合操作卸載到網(wǎng)絡(luò)設(shè)備中進(jìn)行，具有良好的性能及可擴(kuò)展性，已成為高速互連網(wǎng)絡(luò)領(lǐng)域的研究熱點(diǎn).近幾年出現(xiàn)了很多硬件集合通信技術(shù)，如Mellanox的SHARP技術(shù)[5]，神威互連網(wǎng)絡(luò)的硬件集合通信等[6].

硬件支持的集合操作中，多播技術(shù)是重要的支撐.集合通信中的Bcast,Barrier,AllReduce,AllGather等操作需要將相同的數(shù)據(jù)分發(fā)給參與集合通信的不同進(jìn)程，它們均可利用硬件多播進(jìn)行加速.因此多播路由的性能對(duì)這些集合操作具有重要影響.

目前的多播路由算法[7-12]均是為每個(gè)多播組構(gòu)建1棵多播樹(shù).用戶(hù)每創(chuàng)建1個(gè)多播組，就需要構(gòu)建1棵對(duì)應(yīng)的多播樹(shù)，并占用多播路由表的1個(gè)條目號(hào).而多播表大小是有限的，隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，多播組的個(gè)數(shù)會(huì)急劇增加，可能會(huì)超過(guò)硬件支持的多播表?xiàng)l目數(shù).而現(xiàn)有的多播路由算法要么默認(rèn)多播表?xiàng)l目數(shù)是夠用的，因此沒(méi)有給出多播表?xiàng)l目數(shù)不足時(shí)構(gòu)建多播表的方案；要么針對(duì)拓?fù)湮粗木W(wǎng)絡(luò)，存在時(shí)間開(kāi)銷(xiāo)大、多播路由經(jīng)常變化等問(wèn)題.本文在胖樹(shù)結(jié)構(gòu)下研究面向有限多播表?xiàng)l目數(shù)的多播路由算法.

1.1 基本概念

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

定義2.多播組.多播組(multicast group, MCG)是網(wǎng)絡(luò)節(jié)點(diǎn)集N的一個(gè)子集，其成員一般是終端節(jié)點(diǎn).

多播組對(duì)應(yīng)MPI中的1個(gè)通信域，用全局唯一的MGID標(biāo)識(shí).它不僅用于多播操作，還可用于包括同步、全局規(guī)約等在內(nèi)的其他集合操作.例如，神威互連網(wǎng)絡(luò)中，硬件全局規(guī)約可通過(guò)多播組將規(guī)約結(jié)果廣播給所有成員.

定義3.多播路由.從單個(gè)交換機(jī)的角度看，多播路由可定義為如下映射R:L×M→2L，其中M為MGID集合.該映射的輸入?yún)?shù)為輸入鏈路lij及多播組MGID，返回值為輸出鏈路列表{ljk}.

該定義允許交換機(jī)根據(jù)不同輸入鏈路選擇不同的輸出鏈路.這要求交換機(jī)每個(gè)端口都有獨(dú)立的多播路由表.而從全局角度看，多播路由R將多播組MGID映射為I的1棵子樹(shù)，該子樹(shù)包含該多播組的所有成員.我們稱(chēng)該子樹(shù)為多播樹(shù)(multicast tree, MCT).圖1所示的多播組中，陰影所示節(jié)點(diǎn)發(fā)送多播包時(shí)，每到達(dá)1個(gè)交換機(jī)的1個(gè)端口，就查詢(xún)?cè)摱嗖ソM對(duì)應(yīng)的多播表?xiàng)l目，從而確定將多播包復(fù)制到哪些端口進(jìn)行轉(zhuǎn)發(fā).1個(gè)多播組對(duì)應(yīng)1棵多播樹(shù)，但1棵多播樹(shù)可供多個(gè)多播組使用.

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

定義4.多播表?xiàng)l目號(hào).交換機(jī)多播表有多個(gè)條目，以支持不同的多播組，其編號(hào)稱(chēng)為多播表?xiàng)l目號(hào).每個(gè)條目都是1個(gè)位圖，指定了需要將數(shù)據(jù)包復(fù)制到哪些輸出端口.多播路由除了為每個(gè)多播組確定多播樹(shù)之外，還需要確定該多播樹(shù)使用的多播表?xiàng)l目號(hào).

在發(fā)送多播消息時(shí)，MGID及多播表?xiàng)l目號(hào)具有不同的作用.用戶(hù)需同時(shí)指定目的MGID及多播表?xiàng)l目號(hào).交換機(jī)收到多播包時(shí)，根據(jù)多播表?xiàng)l目號(hào)查找對(duì)應(yīng)的多播表?xiàng)l目，并將多播包通過(guò)該多播表?xiàng)l目指定的輸出端口轉(zhuǎn)發(fā)出去.而終端節(jié)點(diǎn)收到多播包后，則根據(jù)MGID決定將該包拷貝到哪些通信隊(duì)列中.

不同廠商支持的多播表?xiàng)l目數(shù)不同，例如Mellanox交換機(jī)最多可支持16 384個(gè)多播表?xiàng)l目，而神威互連網(wǎng)絡(luò)僅支持32個(gè)多播表?xiàng)l目.在不考慮多播表大小的情況下，可以為每個(gè)多播組都分配1個(gè)不同的多播表?xiàng)l目號(hào)；Infiniband即采用該策略，其多播表?xiàng)l目號(hào)稱(chēng)為MLID(multicast local identification).而在考慮到多播表有大小限制時(shí)，則沒(méi)有必要為每個(gè)多播組都分配1個(gè)單獨(dú)的多播表?xiàng)l目號(hào)，2個(gè)多播組只要不使用同一條鏈路，就可以共用同一個(gè)多播表?xiàng)l目號(hào)，從而大大降低對(duì)多播表?xiàng)l目數(shù)的需求；神威互連網(wǎng)絡(luò)即采用該策略，其多播表?xiàng)l目號(hào)稱(chēng)為多播鏈號(hào).

為多播樹(shù)分配多播表?xiàng)l目號(hào)時(shí)，必須遵循下列原則：1)同一棵多播樹(shù)在其使用的所有交換機(jī)內(nèi)使用相同的多播表?xiàng)l目號(hào)；2)若2棵多播樹(shù)經(jīng)過(guò)同一條鏈路，則這2棵多播樹(shù)不能使用同一個(gè)多播表?xiàng)l目號(hào).將每棵多播樹(shù)看做圖的頂點(diǎn)，只要2棵多播樹(shù)共用同一條鏈路，則稱(chēng)這2棵多播樹(shù)“相鄰”，對(duì)應(yīng)的2個(gè)頂點(diǎn)間添加1條邊.我們將多播表?xiàng)l目號(hào)用顏色表示，為“相鄰”的多播樹(shù)指定不同的多播表?xiàng)l目號(hào)，也即用不同的顏色染色.后文將用術(shù)語(yǔ)“染色”表示為多播樹(shù)分配多播表?xiàng)l目號(hào).

定義5.EFI(edge forwarding index).文獻(xiàn)[13-14]定義了單播路由中的EFI指數(shù).我們對(duì)此進(jìn)行擴(kuò)展，將每條鏈路的EFI定義為經(jīng)過(guò)該鏈路的多播組個(gè)數(shù).

鏈路的最大EFI值反映了擁塞程度，值越大表示擁塞程度越高.最大EFI對(duì)多播操作性能具有重要影響，故需要盡量將多播路由均衡分布到不同的鏈路上，以降低EFI指數(shù).

定義6.TFI(tree forwarding index).對(duì)多播樹(shù)而言，使用該多播樹(shù)的多播組個(gè)數(shù)稱(chēng)為該多播樹(shù)的TFI.

若多個(gè)多播組共享1棵多播樹(shù)，則1個(gè)多播組內(nèi)的多播數(shù)據(jù)包會(huì)復(fù)制到其它多播組內(nèi)，從而造成相互干擾，故TFI實(shí)際上反映了多播樹(shù)中多播數(shù)據(jù)包的冗余程度.

1.2 現(xiàn)有多播路由算法存在的問(wèn)題

Infiniband中現(xiàn)有的多播路由算法構(gòu)建多播樹(shù)的過(guò)程包括：1)選擇1個(gè)交換機(jī)作為多播樹(shù)的樹(shù)根，使其到多播組內(nèi)各成員的平均距離或最大距離最小；2)為多播組的每個(gè)成員分別找到1條到達(dá)樹(shù)根的路徑，從而完成多播樹(shù)的構(gòu)建.需要注意的是，在尋找到達(dá)樹(shù)根的路徑的過(guò)程中，不能形成環(huán).

現(xiàn)有的路由算法未考慮多播表?xiàng)l目數(shù)不夠用的問(wèn)題，它們?yōu)槊總€(gè)MGID都分配1個(gè)不同的多播表?xiàng)l目號(hào).隨著應(yīng)用規(guī)模的不斷擴(kuò)大，多播組的數(shù)量也隨之快速增大，系統(tǒng)中可能同時(shí)存在成百上千甚至數(shù)萬(wàn)個(gè)多播組，可能會(huì)超過(guò)硬件支持的多播表?xiàng)l目數(shù),導(dǎo)致多播表?xiàng)l目不夠用.

對(duì)于多播表?xiàng)l目不夠用的問(wèn)題，一種簡(jiǎn)單的解決方案是建立1棵超級(jí)多播樹(shù)(神威互連網(wǎng)絡(luò)中稱(chēng)為全局廣播鏈)，使其包含所有終端節(jié)點(diǎn)，使所有多播組都使用該多播樹(shù)進(jìn)行廣播.但該方案存在嚴(yán)重的性能問(wèn)題：1個(gè)多播組發(fā)送的數(shù)據(jù)會(huì)復(fù)制到整個(gè)網(wǎng)絡(luò)中，造成網(wǎng)絡(luò)中存在大量無(wú)用的多播包；當(dāng)很多個(gè)多播組同時(shí)使用該多播樹(shù)發(fā)送消息時(shí)，會(huì)造成集合操作性能的嚴(yán)重下降.

為此，我們?cè)谇捌诠ぷ髦衃15]提出了面向有限多播表?xiàng)l目數(shù)的多播路由算法(multicast routing for limited multicast forwarding table size, MR4LMS).MR4LMS工作原理為：只要多個(gè)多播組不經(jīng)過(guò)同一條鏈路，就盡量共用同一個(gè)多播表?xiàng)l目號(hào)；而當(dāng)n個(gè)相似的多播組無(wú)條目號(hào)可用時(shí)，就將它們合并到一起共用同一棵多播樹(shù).也即首先嘗試讓多個(gè)多播組共用同一個(gè)多播組條目號(hào)，如果失敗，則嘗試讓多個(gè)多播組共用同一棵多播樹(shù).

具體來(lái)說(shuō)，MR4LMS包括2個(gè)主要部分.一是采用2種方法來(lái)構(gòu)造多播樹(shù)，包括：1)在可用顏色數(shù)比較充足時(shí)，采用先構(gòu)造后染色算法，以每個(gè)備選交換機(jī)為樹(shù)根構(gòu)造1棵多播樹(shù)，然后嘗試用不同的顏色染色；2)在顏色數(shù)不足時(shí)，采用先染色后構(gòu)造算法，先找出可用的顏色，然后在該顏色下構(gòu)造1棵多播樹(shù).二是當(dāng)上述2種方法都不能構(gòu)造出多播樹(shù)時(shí)，采用合并算法，將多個(gè)多播組合并成1個(gè)多播組，從而降低對(duì)多播組顏色數(shù)的需求.

MR4LMS主要用于拓?fù)湮粗木W(wǎng)絡(luò)，可以顯著降低所需的多播表?xiàng)l目數(shù)，滿足大部分應(yīng)用創(chuàng)建多播組時(shí)的需求.但也存在一些實(shí)用性方面的問(wèn)題，包括：

1) MR4LMS需要進(jìn)行大量的圖遍歷操作，時(shí)間開(kāi)銷(xiāo)很大，特別是同時(shí)創(chuàng)建成百上千個(gè)多播組時(shí)，很可能出現(xiàn)顏色數(shù)不夠用的情況，則需要嘗試很多交換機(jī)做樹(shù)根，或嘗試很多種顏色，此時(shí)運(yùn)行時(shí)間可能會(huì)超過(guò)數(shù)分鐘.

2) MR4LMS根據(jù)系統(tǒng)中已存在的其他多播樹(shù)情況為新多播組構(gòu)建多播樹(shù)，因此對(duì)于同一個(gè)多播組，在不同時(shí)刻構(gòu)建的多播樹(shù)很可能是不同的，也即創(chuàng)建出的多播樹(shù)具有動(dòng)態(tài)可變性.這在實(shí)際應(yīng)用場(chǎng)景中會(huì)帶來(lái)很多問(wèn)題：①當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化而重新計(jì)算多播路由時(shí)，多播組使用的多播樹(shù)即使沒(méi)有使用故障鏈路，重新計(jì)算路由后也很可能會(huì)發(fā)生變化，從而造成多播路由的頻繁變化，影響用戶(hù)使用；②同一應(yīng)用在不同時(shí)刻運(yùn)行時(shí)，構(gòu)建的多播樹(shù)也可能不同，這會(huì)帶來(lái)應(yīng)用性能的差異，影響用戶(hù)體驗(yàn).

3) 當(dāng)顏色不足而需要合并多播組時(shí)，也可能會(huì)重構(gòu)已存在的多播樹(shù)，從而影響已存在的多播組的使用.另外，不同時(shí)刻進(jìn)行合并，產(chǎn)生的多播組也可能不同，帶來(lái)2)中所述的影響.

4) 未考慮容錯(cuò)問(wèn)題.當(dāng)多播樹(shù)的1條鏈路發(fā)生故障后，MR4LMS會(huì)重構(gòu)所有的多播路由，由此帶來(lái)下列問(wèn)題：一是需要為所有多播組都重算路由，導(dǎo)致整機(jī)范圍的路由重構(gòu)，影響范圍廣；二是經(jīng)過(guò)故障鏈路的多播包會(huì)丟失，即使有端到端的傳輸層控制協(xié)議可以重傳該包，但由于重構(gòu)多播路由需要相對(duì)較長(zhǎng)的時(shí)間，因此會(huì)對(duì)應(yīng)用性能帶來(lái)較大影響.

Fig. 2 Illustration of fat tree structure圖2 胖樹(shù)結(jié)構(gòu)示意圖

實(shí)際上，針對(duì)特定的拓?fù)浣Y(jié)構(gòu)，可以采用更高效的解決方案.胖樹(shù)是目前高性能計(jì)算中最流行的拓?fù)浣Y(jié)構(gòu)，Top500排名中很多計(jì)算機(jī)均采用胖樹(shù)或裁剪胖樹(shù).本文將針對(duì)胖樹(shù)結(jié)構(gòu)研究硬件僅支持少量多播組條目數(shù)時(shí)的多播路由算法.

1.3 本研究使用的胖樹(shù)結(jié)構(gòu)

目前Top500超級(jí)計(jì)算機(jī)中使用較多的是3層或4層胖樹(shù)[16-19].本文研究圖2所示的4層胖樹(shù).L0與L1層交換機(jī)被分成多個(gè)計(jì)算網(wǎng)絡(luò)中板(computing network midplane, CN)，每個(gè)CN包含q個(gè)L0層交換機(jī)以及m個(gè)L1層交換機(jī).L2層與L3層交換機(jī)也被分成多個(gè)頂層網(wǎng)絡(luò)中板(top network midplane, TN)，每個(gè)TN包含k個(gè)L2層交換機(jī)以及w個(gè)L3層交換機(jī).每個(gè)L1層交換機(jī)共有p個(gè)端口用于連接TN，故每個(gè)CN共有m×p個(gè)端口用于連接TN，TN的個(gè)數(shù)為m×p.每個(gè)TN有k×w個(gè)端口用于連接CN，因而CN的個(gè)數(shù)為k×w.

2 高效實(shí)用地定制多播路由算法

為了快速創(chuàng)建多播路由，可以預(yù)先構(gòu)建好一些多播樹(shù)，但這些多播樹(shù)并沒(méi)有真正寫(xiě)到多播表中.當(dāng)為多播組創(chuàng)建多播樹(shù)時(shí)，直接從這些預(yù)分配的多播樹(shù)中選擇1棵使用即可.每棵這樣的多播樹(shù)都應(yīng)該包含所有L0層交換機(jī)，以支持整機(jī)規(guī)模的多播組.為與1.1節(jié)所述的多播樹(shù)加以區(qū)別，稱(chēng)這些預(yù)先創(chuàng)建的多播樹(shù)為生成樹(shù)(spanning tree, SPT).一般情況下，多播組僅會(huì)使用該生成樹(shù)的部分枝葉.當(dāng)為多播組創(chuàng)建多播樹(shù)時(shí)，僅將所使用的那部分枝葉寫(xiě)進(jìn)多播表中即可.

在胖樹(shù)結(jié)構(gòu)中，多播組使用的多播樹(shù)的樹(shù)根應(yīng)該是多播組內(nèi)各成員的最近公共祖先.由于任一L0層交換機(jī)到給定樹(shù)根有且只有1條路徑，對(duì)每個(gè)多播組而言，只要確定了樹(shù)根及顏色就確定了多播樹(shù).因此，要預(yù)先建立生成樹(shù)，只需確定哪些交換機(jī)可以作為樹(shù)根即可.選擇交換機(jī)時(shí)，需要考慮以該交換機(jī)為樹(shù)根建立的生成樹(shù)，跟那些已建立的生成樹(shù)是否存在沖突.2棵生成樹(shù)若使用同一種顏色，則不能共用同一條鏈路；只有使用不同顏色時(shí)才可以共用同一條鏈路.

2.1 無(wú)沖突的生成樹(shù)個(gè)數(shù)

首先要回答的問(wèn)題是：給定顏色數(shù)C，可以建立多少棵不沖突的生成樹(shù)？首先分析僅有一種顏色時(shí)生成樹(shù)的個(gè)數(shù).暫不考慮L0層交換機(jī)與終端節(jié)點(diǎn)間的鏈路是否會(huì)存在沖突.

定理1.胖樹(shù)結(jié)構(gòu)中，一種顏色能且僅能創(chuàng)建m棵不沖突的生成樹(shù)，其中m是每個(gè)CN內(nèi)L1層交換機(jī)的個(gè)數(shù).

證明.首先，按下述方式構(gòu)造m棵生成樹(shù).先將TN按從左到右的順序編號(hào)并分組，每p個(gè)分為1組，共m組.按該分組方法，每個(gè)L1層交換機(jī)所連接的p個(gè)TN位于同一組內(nèi).然后從每組中任意選擇1個(gè)TN，共選出m個(gè).再在每個(gè)選出的TN中任選1個(gè)L3層交換機(jī)，共選出m個(gè)交換機(jī).以這m個(gè)交換機(jī)為根，以所有L0層交換機(jī)為葉節(jié)點(diǎn)，可產(chǎn)生m棵生成樹(shù).圖3單實(shí)線部分顯示了一棵以第1個(gè)TN為樹(shù)根的生成樹(shù).

Fig. 3 Illustration of spanning tree圖3 生成樹(shù)示意圖

其次，證明這m棵生成樹(shù)不共用任何一條鏈路.很明顯，這m棵生成樹(shù)沒(méi)有共用任何L2?L3以及L1?L2間鏈路，因?yàn)槊總€(gè)樹(shù)根都位于不同的TN內(nèi).而每個(gè)L1層交換機(jī)連接的p個(gè)TN位于同一組內(nèi)，這p個(gè)TN僅有1個(gè)被選為樹(shù)根.也就是說(shuō)，按上述方式構(gòu)建的2棵生成樹(shù)，不可能經(jīng)過(guò)同一個(gè)L1交換機(jī)，也就不可能共用L0?L1間鏈路.因此，上面構(gòu)造的m棵多播樹(shù)不共用任何1條鏈路，可使用同一種顏色.

最后，很容易就可看出，CN內(nèi)的每條鏈路都已被上述m棵生成樹(shù)中的1棵使用，因此不可能再創(chuàng)建出新的生成樹(shù)了.

綜上所述，僅有一種顏色時(shí)，能且僅能創(chuàng)建m棵不沖突的生成樹(shù).

證畢.

需要指出的是，僅使用一種顏色時(shí)，1個(gè)TN唯一確定了1棵生成樹(shù)，而不用關(guān)心該生成樹(shù)使用了該TN內(nèi)的哪個(gè)L3層交換機(jī)做根.因此，如果2個(gè)多播組選擇同一個(gè)TN內(nèi)的不同交換機(jī)做樹(shù)根，仍認(rèn)為這2個(gè)多播組使用了同一棵生成樹(shù).更進(jìn)一步，如果2個(gè)多播組選擇使用位于同一組內(nèi)的2個(gè)不同TN做樹(shù)根，由于它們可能共用L0?L1間鏈路，仍認(rèn)為這2個(gè)多播組使用了同一棵生成樹(shù).如果2個(gè)多播組選擇同一個(gè)TN內(nèi)的交換機(jī)做樹(shù)根，但使用了不同的顏色，則認(rèn)為這2個(gè)多播組使用了不同的生成樹(shù).概括而言，TN及顏色唯一確定了1棵生成樹(shù).

根據(jù)定理1，可以很容易得到下面的2個(gè)推論.

推論1.胖樹(shù)結(jié)構(gòu)中，C種顏色能且僅能創(chuàng)建C×m棵不沖突的生成樹(shù).其中每個(gè)L1交換機(jī)承擔(dān)C棵生成樹(shù)，可以把這C棵生成樹(shù)分布到跟該L1交換機(jī)連接的p個(gè)TN中.

在構(gòu)造網(wǎng)絡(luò)系統(tǒng)時(shí)，上述定理及推論為確定多播表大小提供了理論依據(jù).例如，若用40端口交換機(jī)構(gòu)造網(wǎng)絡(luò)系統(tǒng)，則m=20；在每個(gè)交換機(jī)端口僅支持256個(gè)多播表?xiàng)l目時(shí)，可支持不少于5 120個(gè)多播組.

需要說(shuō)明的是，系統(tǒng)中實(shí)際可創(chuàng)建的多播組個(gè)數(shù)一般大于C×m.這是因?yàn)楹芏嗲闆r下2個(gè)多播組可以共用同一棵生成樹(shù)而不沖突，只要它們不共用該生成樹(shù)的同一條鏈路即可.例如，如果使用該生成樹(shù)的多播組的所有成員都位于同一個(gè)CN內(nèi)，則該多播組僅使用了該生成樹(shù)位于該CN內(nèi)的那部分枝葉，剩余部分仍可供其他多播組使用.

即使多播組的成員分散在不同CN內(nèi)，從而需要將根建在L2或L3層交換機(jī)上，該多播組仍然可以跟其他多播組共用同一棵生成樹(shù).圖4顯示了一個(gè)這樣的例子.灰色陰影所示多播組和斜條紋填充所示多播組可以使用同一個(gè)L3層交換機(jī)做樹(shù)根.2個(gè)使用同一棵生成樹(shù)的多播組，只要它們沒(méi)有共用同一個(gè)L2交換機(jī)，就可以共同一個(gè)L3交換機(jī)做樹(shù)根，因?yàn)檫@樣產(chǎn)生的多播樹(shù)沒(méi)有共用任何相同的鏈路.

Fig. 4 Example for 2 MCGs using the same spanning tree圖4 2個(gè)多播組共用1棵生成樹(shù)的例子

系統(tǒng)中共有C×m棵不沖突的生成樹(shù)，對(duì)編號(hào)為spt_no的生成樹(shù)，根據(jù)式(1)確定其顏色color及樹(shù)根所在的頂層網(wǎng)絡(luò)中板tnid.另外，總是選擇該頂層網(wǎng)絡(luò)中板的第1個(gè)L3交換機(jī)做樹(shù)根，因此確定了tnid及color，就確定了樹(shù)根.由式(1)可以看出，我們將不同顏色的生成樹(shù)樹(shù)根分散到同一組內(nèi)的不同TN內(nèi)，來(lái)達(dá)到負(fù)載均衡的目的.

(1)

2.2 為多播組選擇生成樹(shù)

為多播組創(chuàng)建多播樹(shù)時(shí)，首先需要確定該多播組應(yīng)該使用哪棵生成樹(shù).對(duì)每一個(gè)多播組，根據(jù)其MGID將其映射到上述C×m棵生成樹(shù)中的1棵.具體來(lái)說(shuō)，假設(shè)多播組的MGID為mgid，根據(jù)式(2)確定該多播組使用的生成樹(shù).

spt_no=mgid%(C×m).

(2)

根據(jù)式(1)(2)我們可以得出根據(jù)MGID直接計(jì)算顏色編號(hào)及樹(shù)根所在TN編號(hào)：

(3)

采用該方式創(chuàng)建多播樹(shù)時(shí)，無(wú)需考慮系統(tǒng)中各鏈路的負(fù)載及顏色使用情況，僅由MGID即可確定使用哪棵生成樹(shù).如果多播組的個(gè)數(shù)多于C×m，則可能出現(xiàn)多個(gè)多播組共同一棵生成樹(shù)的情況，此時(shí)需要將幾個(gè)多播組合并成1個(gè)多播組.式(1)及式(3)保證使用同一棵生成樹(shù)的2個(gè)多播組在合并時(shí)，僅需在原來(lái)的多播樹(shù)上添加部分鏈路即可，被合并的那些多播組使用的多播樹(shù)并不受影響，從而不會(huì)影響這些多播組的正常使用.

1個(gè)終端加入多個(gè)多播組時(shí)，每個(gè)多播組需要使用不同的顏色，否則在終端節(jié)點(diǎn)與L0交換機(jī)間的鏈路上就會(huì)產(chǎn)生沖突.本文將在3.1節(jié)研究該問(wèn)題的解決方案.

2.3 為多播組構(gòu)造多播樹(shù)

確定樹(shù)根所在的頂層網(wǎng)絡(luò)中板及顏色后，就可以構(gòu)造多播樹(shù)了，步驟如算法1所示.該算法根據(jù)多播組成員的分布情況，從生成樹(shù)中選擇合適的交換機(jī)做為該多播組的樹(shù)根，它們可能位于L0,L1,L2,L3中的某一層.

算法1.多播樹(shù)構(gòu)造算法.

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

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

① 根據(jù)式(3)計(jì)算該多播組使用的顏色color以及樹(shù)根所在的頂層網(wǎng)絡(luò)中板tnid；

② 對(duì)多播組的每個(gè)成員，檢查其連接到L0交換機(jī)的那條鏈路上顏色color是否已被使用，若是則返回NULL；

③ 根據(jù)多播組各成員的物理位置，確定該多播組內(nèi)各成員的最近公共祖先所在的位置；

④ 若最近公共祖先位于L0或L1或L2層，則該公共祖先有且只有1個(gè)，記為root；

⑤ 若最近公共祖先位于L3層，則選擇頂層網(wǎng)絡(luò)中板tnid內(nèi)的第1個(gè)L3交換機(jī)做樹(shù)根root；

⑥ 以root為樹(shù)根，為mcg的每個(gè)成員都找出該成員到root的路徑，從而構(gòu)建出多播樹(shù)mct；

⑦ 檢查mct的每條鏈路中顏色color是否可用，若均為可用，則返回mct；

⑧ 否則，返回NULL./*需進(jìn)行合并操作*/

算法1步驟②用于檢查終端節(jié)點(diǎn)使用同一種顏色加入多個(gè)多播組的情況；若該顏色已被使用，則不能利用該顏色創(chuàng)建新的多播組，因此返回NULL，表示需要進(jìn)行合并操作.

算法1步驟③～⑤用于確定樹(shù)根，規(guī)則為：

1) 若多播組的成員都位于同一個(gè)L0交換機(jī)內(nèi)，則樹(shù)根即為該L0交換機(jī)；

2) 若多播組的成員均位于同一個(gè)CN內(nèi)，則樹(shù)根為生成樹(shù)在該CN內(nèi)的那個(gè)L1交換機(jī)；

3) 若多播組的成員位于不同CN內(nèi)(CN編號(hào)記為cnid)，且所有cnid/w相等，則樹(shù)根為生成樹(shù)中用于連接這些CN的那個(gè)L2交換機(jī)；

4) 其他情況下，選擇該生成樹(shù)中的第1個(gè)L3交換做樹(shù)根.

算法1步驟⑥⑦嘗試使用顏色color構(gòu)建多播樹(shù).在胖樹(shù)結(jié)構(gòu)中，確定了樹(shù)根后，多播組的每個(gè)成員到樹(shù)根僅有1條鏈路，因此也就確定了多播樹(shù).2個(gè)多播組使用同一棵生成樹(shù)時(shí)，有可能會(huì)共用同一條鏈路，從而會(huì)產(chǎn)生沖突，此時(shí)需要進(jìn)行合并操作，方法見(jiàn)2.4節(jié).

將多播組中成員個(gè)數(shù)記為S，則算法1的時(shí)間復(fù)雜度為O(S).

2.4 合并多播組

在算法1中，如果發(fā)現(xiàn)新構(gòu)造的多播樹(shù)與某個(gè)已經(jīng)創(chuàng)建的多播組使用了同一條鏈路，則需要進(jìn)行合并操作.方法如下：將算法1中構(gòu)建的多播樹(shù)記為tmpMct，檢查tmpMct的每條鏈路，若該鏈路中顏色color已被其他多播組使用，則根據(jù)式(3)這些多播組必定與新創(chuàng)建的多播組使用同一棵生成樹(shù)；將這些多播組的所有成員，連同新創(chuàng)建的多播組的成員一起，利用算法2構(gòu)建一個(gè)新的多播組，記為vmcg；然后利用算法1為vmcg創(chuàng)建多播樹(shù).

算法2.合并算法.

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

輸出：虛擬多播組vmcg.

① 根據(jù)式(3)計(jì)算該多播組使用的顏色color、樹(shù)根所在的頂層網(wǎng)絡(luò)中板tnid；

② 采用算法1找到樹(shù)根root，并以root為樹(shù)根構(gòu)造多播樹(shù)tmpMct;

③ 檢查tmpMct的每條鏈路，將使用該鏈路且顏色為color的所有多播組，連同mcg合并在一起，形成虛擬多播組vmcg；

④ 返回vmcg.

算法2在尋找需要合并哪些多播組時(shí)，僅檢查了tmpMct使用的鏈路，而tmpMct的樹(shù)根可能是非L3層的交換機(jī).也就是說(shuō)，算法2僅檢查了所用生成樹(shù)的一部分鏈路的使用情況.那么，算法2是否已經(jīng)合并了所有必須合并的多播組，從而保證一定能夠成功為vmcg構(gòu)建出多播樹(shù)呢？答案是肯定的，下面我們進(jìn)行證明.

引理1.利用算法1構(gòu)建多播樹(shù)時(shí)，如果某多播組需要進(jìn)行合并操作，則合并后產(chǎn)生的vmcg對(duì)應(yīng)的多播樹(shù)，其任意1條鏈路必定出現(xiàn)在某個(gè)被合并的多播組所對(duì)應(yīng)的多播樹(shù)內(nèi).

證畢.

定理2.利用算法1構(gòu)建多播樹(shù)時(shí)，如果某多播組需要進(jìn)行合并操作，則合并后產(chǎn)生的vmcg對(duì)應(yīng)的多播樹(shù)，與使用同一生成樹(shù)的其他多播組不共用任何鏈路.

證畢.

根據(jù)定理2，為vmcg構(gòu)建多播樹(shù)時(shí)，不會(huì)跟使用同一生成樹(shù)的其他多播組沖突，也就是說(shuō)算法2已經(jīng)合并了所有必須合并的多播組.

由上述論述可知，合并多播組時(shí)，僅會(huì)在原來(lái)多播樹(shù)的基礎(chǔ)上添加部分鏈路，因而不會(huì)對(duì)原多播樹(shù)帶來(lái)影響.完整的C-MR4LMS路由算法見(jiàn)算法3.

算法3.C-MR4LMS.

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

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

① 利用算法1為mcg構(gòu)建多播樹(shù)mct；

② 若mct為NULL，則

③ 利用算法2進(jìn)行合并操作，將幾個(gè)多播組合并成1個(gè)虛擬的多播組vmcg；

④ 再次利用算法1為vmcg創(chuàng)建多播樹(shù)mct；

⑤ 更新mct每條鏈路中相應(yīng)顏色的使用情況；

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

2.5 容錯(cuò)多播路由

本文采用圖5所示的容錯(cuò)策略：為每個(gè)多播組構(gòu)建多播路由時(shí)，選擇2個(gè)樹(shù)根并構(gòu)建2棵多播樹(shù)，兩者互為備份，數(shù)據(jù)包同時(shí)通過(guò)這2棵多播樹(shù)進(jìn)行傳輸.終端節(jié)點(diǎn)收到2份重復(fù)的數(shù)據(jù)包時(shí)，僅需丟棄其中1個(gè).當(dāng)其中1棵多播樹(shù)因鏈路故障而無(wú)法使用時(shí)，數(shù)據(jù)包可以通過(guò)另一棵多播樹(shù)進(jìn)行傳輸，從而做到對(duì)用戶(hù)透明的容錯(cuò).

Fig. 5 Illustration of multicast routing with fault tolerance圖5 容錯(cuò)多播路由示意圖

當(dāng)開(kāi)啟容錯(cuò)功能后，利用式(4)計(jì)算多播組使用的顏色及2棵多播樹(shù)樹(shù)根所在TN編號(hào).該方法實(shí)際上是將每種顏色下的m棵生成樹(shù)分為2組，從每組分別選擇1棵生成樹(shù)使用.因此，系統(tǒng)支持的無(wú)沖突生成樹(shù)的個(gè)數(shù)會(huì)減為原來(lái)的1/2.

(4)

2.6 另一種選擇樹(shù)根的方法

如果多播組內(nèi)各成員的最近公共祖先位于L3層，則頂層網(wǎng)絡(luò)中板tnid內(nèi)每個(gè)L3交換機(jī)都可以做樹(shù)根.從中選擇哪個(gè)做樹(shù)根實(shí)際上有2種策略：一是算法1所采用的固定選擇第1個(gè)交換機(jī)的策略，由此產(chǎn)生的算法稱(chēng)為C-MR4LMS-fixed；二是將所有L3交換機(jī)都作為備選樹(shù)根，從中選擇1個(gè)合適的做樹(shù)根(優(yōu)先選擇負(fù)載低的)，由此產(chǎn)生的算法稱(chēng)為C-MR4LMS-dynamic.

這2種變體各有優(yōu)缺點(diǎn).

1) 某些情況下，C-MR4LMS-dynamic可以通過(guò)選擇不同的L3交換機(jī)做樹(shù)根，使C-MR4LMS-fixed算法下原本有沖突的2個(gè)多播組不再?zèng)_突.如圖6所示，灰色陰影所示多播組與斜條紋所示多播組使用同一棵生成樹(shù).C-MR4LMS-fixed算法下這2個(gè)多播組共用同一個(gè)L3交換機(jī)做樹(shù)根，因此在L2?L3鏈路上會(huì)產(chǎn)生沖突.而C-MR4LMS-dynamic算法下這2個(gè)多播組可以使用不同的L3交換機(jī)做樹(shù)根，從而避免產(chǎn)生沖突.

Fig. 6 Example for 2 MCGs using different L3 switches as root圖6 2個(gè)多播組使用不同L3交換機(jī)做樹(shù)根的例子

2) 需要進(jìn)行合并操作時(shí)，C-MR4LMS-dynamic下同一棵生成樹(shù)的幾個(gè)多播組可能使用不同的L3交換機(jī)做樹(shù)根，它們被合并到一起后，樹(shù)根會(huì)發(fā)生變化，從而導(dǎo)致被合并的多播組其多播路由發(fā)生變化，而C-MR4LMS-fixed不存在該問(wèn)題.

Fig. 7 Illustration for merge algorithm fails to construct MCTs with C-MR4LMS-dynamic圖7 利用C-MR4LMS-dynamic算法構(gòu)建多播樹(shù)后合并算法失效的例子

3) C-MR4LMS-fixed算法下，利用算法2合并多播組時(shí)，已經(jīng)合并了所有必須合并的多播組，從而保證一定能夠成功為vmcg構(gòu)建出多播樹(shù).而C-MR4LMS-dynamic算法下，利用算法2合并多播組時(shí)，可能會(huì)漏掉某些必須合并的多播組，從而導(dǎo)致為vmcg構(gòu)建多播樹(shù)失敗.如圖7所示(圖中省略了L0,L1層交換機(jī))，假設(shè)新創(chuàng)建的多播組需要經(jīng)過(guò)R2,R4這2個(gè)交換機(jī)，且無(wú)論選擇R0還是R1做樹(shù)根均跟已存在的多播組存在沖突，因此需要利用算法2進(jìn)行合并操作.假設(shè)在合并時(shí)，選擇R0做樹(shù)根，且需要合并R1?R4,R1?R5間鏈路所示的多播組.在進(jìn)行合并時(shí)，僅會(huì)檢查R0?R4,R0?R2鏈路；而合并后的vmcg對(duì)應(yīng)的多播樹(shù)會(huì)用R0?R5間鏈路，但該鏈路在檢查需要合并哪些多播組時(shí)并未被考慮到，實(shí)際上該鏈路可能被另外的多播組使用，因而為vmcg構(gòu)建多播樹(shù)會(huì)因沖突而失敗.出現(xiàn)該問(wèn)題的原因是：R1?R4,R1?R5多播組使用了不同的L3交換機(jī)做樹(shù)根，導(dǎo)致原本未被vmcg內(nèi)任一多播組使用的鏈路R0?R5出現(xiàn)在了vmcg經(jīng)過(guò)的路徑上，從而使得C-MR4LMS-dynamic算法下引理1不再成立.也就是說(shuō)，C-MR4LMS-dynamic算法下，上述合并算法不能保證合并了所有必須合并的多播組.

基于上述原因，使用C-MR4LMS-dynamic時(shí)，為vmcg構(gòu)建多播樹(shù)可能失敗，此時(shí)需要再進(jìn)行1次合并方可成功.

4) 在多播組個(gè)數(shù)較多時(shí)，C-MR4LMS-dynamic需要嘗試很多個(gè)L3交換機(jī)做樹(shù)根，時(shí)間開(kāi)銷(xiāo)較大；而C-MR4LMS-fixed僅會(huì)嘗試1個(gè)L3交換機(jī)做樹(shù)根，時(shí)間開(kāi)銷(xiāo)較小.

具體使用哪種策略，可以根據(jù)實(shí)際情況進(jìn)行選擇.一般來(lái)說(shuō)，多播組個(gè)數(shù)不多時(shí)，可以采用C-MR4LMS-dynamic策略；而多播組個(gè)數(shù)很多而需要頻繁合并多播組時(shí)，比較適宜采用C-MR4LMS-fixed算法.

3 減少多播樹(shù)沖突的2種方法

MGID分配策略及節(jié)點(diǎn)分配策略都會(huì)影響C-MR4LMS算法的性能.例如，為某個(gè)多播組選擇不同的MGID，就會(huì)使用不同的生成樹(shù)；將多播組所在的作業(yè)映射到不同節(jié)點(diǎn)上，也會(huì)影響多播樹(shù)的分配.

本節(jié)將研究如何分配MGID及進(jìn)行節(jié)點(diǎn)映射，以達(dá)到減少多播樹(shù)沖突的目的.這些分配策略并不是C-MR4LMS的組成部分，目的是為了更好地發(fā)揮C-MR4LMS的性能.

3.1 分層的MGID分配策略

考慮每個(gè)終端節(jié)點(diǎn)可加入多個(gè)多播組的情況.1個(gè)終端加入多個(gè)多播組時(shí)，每個(gè)多播組需要使用不同的顏色，否則在終端節(jié)點(diǎn)與L0交換機(jī)間的鏈路上就會(huì)產(chǎn)生沖突.根據(jù)式(3)，如果不對(duì)用戶(hù)可用的MGID加以限制，就很容易出現(xiàn)1個(gè)終端加入的多個(gè)多播組時(shí)使用同一種顏色的情況.出現(xiàn)該情況后，需要將沖突的那些多播組合并.此時(shí)進(jìn)行的合并跟2.2節(jié)介紹的合并有很大不同.當(dāng)2個(gè)多播組因共用同一條交換機(jī)間鏈路而需要合并時(shí)，因?yàn)樗麄兪褂猛豢蒙蓸?shù)，只需在原多播樹(shù)的基礎(chǔ)上添加部分鏈路即可，不會(huì)影響原多播組的正常使用.而當(dāng)1個(gè)終端節(jié)點(diǎn)使用同一種顏色加入多個(gè)多播組時(shí)，這些多播組可能使用了不同的生成樹(shù)，其樹(shù)根位于不同TN內(nèi)，合并后多播組的樹(shù)根會(huì)發(fā)生變化，影響用戶(hù)使用.

基于上述原因，當(dāng)1個(gè)終端需要加入多個(gè)多播組時(shí)，我們需要對(duì)其使用的MGID加以限制.也就是說(shuō)，根據(jù)式(3)計(jì)算color及tnid時(shí)，要么每個(gè)多播組都使用不同的顏色，要么2個(gè)多播組可以使用同一種顏色，但計(jì)算出的tnid必須相同，從而保證這2個(gè)多播組可以不用切換TN做樹(shù)根即可進(jìn)行合并.

用戶(hù)可以采用多種策略保證1個(gè)終端節(jié)點(diǎn)使用的多個(gè)MGID沒(méi)有顏色上的沖突.一種可行的策略是：根據(jù)每個(gè)終端可加入的多播組的個(gè)數(shù)將顏色劃分為不同的區(qū)間，每個(gè)區(qū)間稱(chēng)為1個(gè)層，從而也就將MGID空間劃分成了多個(gè)互不重疊的層，稱(chēng)為MGID層.在每個(gè)MGID層內(nèi)，1個(gè)終端節(jié)點(diǎn)最多可加入其中的1個(gè)多播組；加入多個(gè)多播組時(shí)，選擇不同的MGID層即可保證他們使用不同的顏色.

每個(gè)終端可加入的多播組的個(gè)數(shù)一般不會(huì)太多，例如，以2維網(wǎng)格方式劃分通信域時(shí)，假設(shè)每個(gè)終端上僅運(yùn)行1個(gè)通信進(jìn)程，則每個(gè)終端僅需加入3個(gè)多播組，包括1個(gè)全局通信域、1個(gè)用于行通信的子通信域以及1個(gè)用于列通信的子通信域.在此情況下，我們可以將MGID劃分為3個(gè)層，使得每個(gè)MGID層均使用不同的顏色，為哪個(gè)維度的多播組分配多播組，就從該維度對(duì)應(yīng)的MGID層中選擇1個(gè)MGID使用.

當(dāng)每個(gè)終端上可運(yùn)行多個(gè)通信進(jìn)程時(shí)，情況變得復(fù)雜，因?yàn)槊總€(gè)終端節(jié)點(diǎn)在每個(gè)維度方向上可能加入多個(gè)多播組.此時(shí)需要考慮通信域的劃分方式，并將每個(gè)通信域映射到合適的MGID層.MPI集合通信中，主要有2種通信域劃分方法[20-21]：一是劃分成2維或3維網(wǎng)格，其每個(gè)維度中每行或每列都是1個(gè)通信域，對(duì)應(yīng)1個(gè)多播組；二是劃分成層次結(jié)構(gòu)，例如樹(shù)型結(jié)構(gòu)，每層分成很多組，每個(gè)組構(gòu)成1個(gè)通信域，每個(gè)組再選出1個(gè)leader，形成更高層次的組.以層次結(jié)構(gòu)劃分通信域時(shí)，將通信域映射到MGID層的方法比較簡(jiǎn)單，只需為每個(gè)通信域?qū)又付?個(gè)MGID層.

下面考慮3維網(wǎng)格劃分方式下將通信域映射到MGID層的方法，2維網(wǎng)格方式與此類(lèi)似，不再贅述.如圖8所示，假設(shè)每個(gè)終端節(jié)點(diǎn)上有P個(gè)通信進(jìn)程，且它們?cè)?維環(huán)網(wǎng)中的位置是連續(xù)的.例如，設(shè)3維環(huán)網(wǎng)x,y,z維長(zhǎng)度分別為X,Y,Z，某終端節(jié)點(diǎn)上首進(jìn)程的坐標(biāo)為(a,b,c)，則該終端節(jié)點(diǎn)上第n個(gè)進(jìn)程的坐標(biāo)為((a+n)%X,(b+(a+n)/X)%Y,c+(bX+a+n)/(XY)).

Fig. 8 Illustration for different process’s position on the same terminal node in 3D-torus圖8 3維環(huán)網(wǎng)中同一終端節(jié)點(diǎn)上不同進(jìn)程位置示意圖

給定坐標(biāo)為(a,b,c)的進(jìn)程，我們根據(jù)式(5)分別計(jì)算該進(jìn)程加入3個(gè)軸方向上的多播組時(shí)使用的MGID層號(hào)，其中l(wèi)ayerx,layery,layerz分別對(duì)應(yīng)x,y,z軸方向上的多播組.

(5)

定理3.以3維環(huán)網(wǎng)方式劃分通信域時(shí)，若每個(gè)終端節(jié)點(diǎn)上有P個(gè)通信進(jìn)程(P小于3維環(huán)網(wǎng)任一維的長(zhǎng)度)，且這些進(jìn)程在3維環(huán)網(wǎng)中位置連續(xù)，則利用式(5)將每個(gè)進(jìn)程的3個(gè)多播組放入某個(gè)MGID層時(shí)，對(duì)任一終端節(jié)點(diǎn)而言，每個(gè)多播組均位于不同的MGID層內(nèi).

證明.首先，很容易看出，不同方向上的多播組位于不同的MGID層內(nèi).其次，我們證明，同一終端節(jié)點(diǎn)上同一方向上的多播組也位于不同的MGID層內(nèi).我們先列出同一終端節(jié)點(diǎn)上各個(gè)進(jìn)程的位置分布情況，包括：

1)P個(gè)進(jìn)程位于與x軸平行的同一條線上(如灰色陰影進(jìn)程所示)；

2)P個(gè)進(jìn)程不在同一條直線上，但位于與xoy平面平行的同一平面內(nèi)(如斜紋填充進(jìn)程所示)；

3)P個(gè)進(jìn)程不在同一平面內(nèi)(如橫紋填充進(jìn)程所示).

先看x軸方向上的多播組.情況1)中，P個(gè)進(jìn)程屬于同一個(gè)多播組.情況2)中，P個(gè)進(jìn)程屬于多個(gè)多播組，但它們具有相同的z坐標(biāo)，以及連續(xù)的y坐標(biāo)，因此根據(jù)式(5)得到的MGID層號(hào)必不相等.情況3)中，P個(gè)進(jìn)程屬于多個(gè)多播組；若2個(gè)多播組具有相同的z坐標(biāo)，則與情況2)一樣，根據(jù)式(5)得到的MGID層號(hào)必不相等；若2個(gè)多播組具有不同的z坐標(biāo)，則其中1個(gè)多播組的y坐標(biāo)必小于P-1，另一個(gè)多播組的y坐標(biāo)必大于等于P-1，根據(jù)式(5)得到的MGID層號(hào)也不相等.因此，上述3種情況下，根據(jù)式(5)得到的MGID層號(hào)都互不相等.

同理，y,z軸方向上的多播組根據(jù)式(5)得到的MGID層號(hào)也互不相等.

證畢.

利用式(5)，可以將3維環(huán)網(wǎng)中的多播組映射到不同的MGID層內(nèi)，保證每個(gè)終端節(jié)點(diǎn)在每個(gè)MGID層內(nèi)最多加入1個(gè)多播組，從而保證該終端節(jié)點(diǎn)加入多個(gè)多播組時(shí)，每個(gè)多播組都使用不同的顏色，也就避免在終端節(jié)點(diǎn)與L0交換機(jī)間的鏈路上產(chǎn)生沖突.每層內(nèi)的顏色數(shù)可以根據(jù)該層內(nèi)的多播組個(gè)數(shù)進(jìn)行分配.

3.2 相互無(wú)干擾的作業(yè)節(jié)點(diǎn)分配策略

根據(jù)定理1及2個(gè)推論，當(dāng)系統(tǒng)中多播組的個(gè)數(shù)少于C×m時(shí)，無(wú)需合并多播組即可完成多播樹(shù)的創(chuàng)建；而當(dāng)多播組的個(gè)數(shù)多于C×m時(shí)，很可能出現(xiàn)2個(gè)多播組使用同一棵生成樹(shù)的同一條鏈路的情況，從而導(dǎo)致沖突，此時(shí)需要將這2個(gè)多播組合并在一起.多播組合并會(huì)導(dǎo)致1個(gè)多播組發(fā)送的數(shù)據(jù)拷貝到另一個(gè)多播組內(nèi)，從而使得鏈路EFI指數(shù)變大，影響集合操作的性能.因此需要盡量避免這種情況的出現(xiàn).

通過(guò)優(yōu)化節(jié)點(diǎn)分配來(lái)減少作業(yè)間的相互干擾是提升應(yīng)用性能的重要手段[22-23].本文提出了一種作業(yè)分配策略，使不同作業(yè)使用的網(wǎng)絡(luò)資源彼此隔離，從而使得不同作業(yè)可以共用同一棵生成樹(shù)而沒(méi)有任何沖突.這樣每個(gè)作業(yè)都至少可以創(chuàng)建C×m個(gè)不沖突的多播組，從而使得系統(tǒng)中支持的多播組總數(shù)遠(yuǎn)遠(yuǎn)大于C×m.

首先根據(jù)作業(yè)使用的終端個(gè)數(shù)將作業(yè)分為下列類(lèi)型：

1) T0作業(yè)，其終端個(gè)數(shù)小于等于m；

2) T1作業(yè)，其終端個(gè)數(shù)小于等于m2；

3) T2作業(yè)，其終端個(gè)數(shù)小于等于w×m2；

4) T3作業(yè)，其終端個(gè)數(shù)大于w×m2.

為作業(yè)分配終端節(jié)點(diǎn)時(shí)，必須遵循下列規(guī)則：

1) 1個(gè)節(jié)點(diǎn)僅能分配給1個(gè)作業(yè)使用；

2) T0作業(yè)使用的節(jié)點(diǎn)均位于同一L0交換機(jī)內(nèi)；

3) T1作業(yè)使用的節(jié)點(diǎn)均位于同一CN內(nèi)；

4) T2作業(yè)使用的節(jié)點(diǎn)，其計(jì)算網(wǎng)絡(luò)中板號(hào)cnid/w應(yīng)等于同一個(gè)值；

5) L0交換機(jī)可被多個(gè)T0作業(yè)共享，但最多只能被1個(gè)T1及以上規(guī)模的作業(yè)使用；

6) 1個(gè)計(jì)算網(wǎng)絡(luò)中板可以被多個(gè)T1作業(yè)共享，但最多只能被1個(gè)T2及以上規(guī)模的作業(yè)使用；

7) 編號(hào)為i×w,i×w+1,…,(i+1)×w-1的w個(gè)中板可以被多個(gè)T2作業(yè)共享，但最多只能被1個(gè)T3作業(yè)使用.

定理4.按規(guī)則1)～7)為作業(yè)分配節(jié)點(diǎn)時(shí)，任何2個(gè)作業(yè)不共用同一條鏈路.

證明. 首先考慮L0層交換機(jī).根據(jù)規(guī)則1)，L0交換機(jī)的下行鏈路只能被1個(gè)作業(yè)使用.根據(jù)規(guī)則2)，T0作業(yè)不會(huì)使用L0交換機(jī)的上行鏈路；而根據(jù)規(guī)則5)，L0交換機(jī)最多被1個(gè)T1及以上規(guī)模的作業(yè)使用，因此L0交換機(jī)的上行鏈路最多被1個(gè)作業(yè)使用.

再考慮L1層交換機(jī).同樣根據(jù)規(guī)則5)，其每條下行鏈路最多被1個(gè)作業(yè)使用；根據(jù)規(guī)則3)，T1作業(yè)不會(huì)使用L1交換機(jī)的上行鏈路；而根據(jù)規(guī)則6)，L1交換機(jī)最多被1個(gè)T2及以上規(guī)模的作業(yè)使用，因此L1交換機(jī)的上行鏈路最多被1個(gè)作業(yè)使用.

再考慮L2層交換機(jī).同樣根據(jù)規(guī)則6)，其每條下行鏈路最多被1個(gè)作業(yè)使用；根據(jù)規(guī)則4)，T2作業(yè)不會(huì)使用L2交換機(jī)的上行鏈路；而根據(jù)規(guī)則7)，L2交換機(jī)最多被1個(gè)T3作業(yè)使用，因此L2交換機(jī)的上行鏈路最多被1個(gè)作業(yè)使用.

最后考慮L3層交換機(jī).同樣根據(jù)規(guī)則7)，其每條下行鏈路最多被1個(gè)作業(yè)使用.

證畢.

由此可知，按規(guī)則1)～7)為作業(yè)分配節(jié)點(diǎn)時(shí)，來(lái)自不同作業(yè)的2個(gè)多播組使用同一棵生成樹(shù)創(chuàng)建多播樹(shù)時(shí)，不會(huì)產(chǎn)生沖突.因此，只要每個(gè)作業(yè)使用的多播組個(gè)數(shù)不超過(guò)C×m，就可以保證系統(tǒng)中所有的多播組不用合并就可成功創(chuàng)建多播樹(shù).

4 ibsim下的性能評(píng)估

我們?cè)贠penSM 3.3.22[24]中實(shí)現(xiàn)了C-MR4LMS，共有約2 000行代碼.對(duì)OpenSM源碼進(jìn)行了修改，使得每個(gè)交換機(jī)端口都有一份單獨(dú)的路由表.另外，還對(duì)加入、離開(kāi)多播組的機(jī)制進(jìn)行了簡(jiǎn)單的修改，以解決頻繁重算路由的問(wèn)題.

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

本文使用ibsim-0.7[24]模擬了圖2所示的一棵4層胖樹(shù)，參數(shù)如下：交換機(jī)端口數(shù)為40，m=w=16，q=k=32，p=6.理論上，該網(wǎng)絡(luò)最大支持512個(gè)CN，96個(gè)TN，262 144個(gè)終端節(jié)點(diǎn).但由于OpenSM及ibsim最多支持49 152個(gè)節(jié)點(diǎn)(包括交換機(jī)及終端)，因此僅使用了64個(gè)CN、96個(gè)TN；網(wǎng)絡(luò)中節(jié)點(diǎn)總數(shù)為40 448，其中交換機(jī)個(gè)數(shù)為7 680，終端節(jié)點(diǎn)數(shù)為32 768.

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

MPI中將進(jìn)程劃分為子通信域時(shí)，可以采用層次結(jié)構(gòu)進(jìn)行劃分，也可以采用2維或3維網(wǎng)格方式進(jìn)行劃分.采用2維或3維網(wǎng)格方式劃分通信域時(shí)，會(huì)產(chǎn)生大量多播組，對(duì)多播表?xiàng)l目數(shù)的需求量更大.后面實(shí)驗(yàn)中，采用2維及3維網(wǎng)格劃分進(jìn)程，以測(cè)試存在大量多播組時(shí)多播路由算法的性能.除此之外，還測(cè)試了進(jìn)程隨機(jī)加入某個(gè)多播組的通信模式.另外，既測(cè)試了每個(gè)終端運(yùn)行1個(gè)通信進(jìn)程的情況，也測(cè)試了每個(gè)終端運(yùn)行多個(gè)通信進(jìn)程的情況.

后面將要測(cè)試的2維或3維網(wǎng)格模式中，有些是按拓?fù)浣Y(jié)構(gòu)進(jìn)行劃分的，模擬拓?fù)涓兄耐ㄐ拍Ｊ?；有些劃分成正方形或立方體形狀，模擬拓?fù)錈o(wú)感的通信模式.以每個(gè)終端節(jié)點(diǎn)上運(yùn)行1個(gè)通信進(jìn)程為例， 512×64通信模式下，第1維有64個(gè)多播組，每個(gè)組都位于同一個(gè)CN內(nèi)，因此通信模式與拓?fù)浣Y(jié)構(gòu)匹配；而181×181通信模式下，存在很多跨計(jì)算中板的多播組，因此通信模式與拓?fù)浣Y(jié)構(gòu)不匹配.

神威互連網(wǎng)絡(luò)中每個(gè)交換機(jī)端口最多支持32個(gè)多播表?xiàng)l目，因此后面測(cè)試中，將最大顏色數(shù)設(shè)為32，不沖突的生成樹(shù)的個(gè)數(shù)為512.設(shè)為其他值時(shí)，測(cè)試結(jié)果會(huì)有差異，但測(cè)試結(jié)論與顏色數(shù)為32時(shí)基本一致，因此不再贅述其測(cè)試數(shù)據(jù).另外，為了與MR4LMS對(duì)比，關(guān)閉了C-MR4LMS的容錯(cuò)功能.

本文測(cè)試了原始MR4LMS算法及本文提出的2種多播路由算法(C-MR4LMS-fixed，C-MR4LMS-dynamic)在各種通信模式下的性能，其中每個(gè)終端節(jié)點(diǎn)上運(yùn)行1個(gè)通信進(jìn)程時(shí)的測(cè)試結(jié)果如圖9所示，每個(gè)終端節(jié)點(diǎn)上運(yùn)行4個(gè)通信進(jìn)程時(shí)的測(cè)試結(jié)果如圖10所示.

Fig. 9 The performance of three algorithms with only one communication process on each terminal node圖9 每個(gè)終端節(jié)點(diǎn)上僅有1個(gè)通信進(jìn)程時(shí)3種算法的性能

Fig. 10 The performance of three algorithms with 4 communication process on each terminal node圖10 每個(gè)終端節(jié)點(diǎn)上4個(gè)通信進(jìn)程時(shí)3種算法的性能

4.2 不同通信模式下的鏈路EFI

最大EFI及平均EFI反映了各鏈路上多播樹(shù)的數(shù)量，一定程度上代表了多播路由算法的均衡程度.

4.2.1 每個(gè)終端上僅1個(gè)通信進(jìn)程

先分析每個(gè)終端節(jié)點(diǎn)上運(yùn)行1個(gè)通信進(jìn)程時(shí)的情況，結(jié)果如圖9(a)(b)所示.

1) 2維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的最大EFI及平均EFI均低于MR4LMS算法.出現(xiàn)該現(xiàn)象的原因是：MR4LMS算法在選擇樹(shù)根時(shí)根據(jù)負(fù)載情況從很多備選樹(shù)根中選擇1個(gè)；而在胖樹(shù)結(jié)構(gòu)中，所有的L3交換機(jī)均可作為備選樹(shù)根，因此會(huì)被輪流作為樹(shù)根使用.而2維環(huán)網(wǎng)下多播組的個(gè)數(shù)較少，因此MR4LMS僅用到了那些位置靠前的L3交換機(jī)，而那些位置靠后的L3交換機(jī)未被使用.這就導(dǎo)致MR4LMS算法僅使用了部分頂層網(wǎng)絡(luò)中板，進(jìn)而導(dǎo)致連接L1交換機(jī)與L2交換機(jī)的那些鏈路上EFI指數(shù)偏大.而C-MR4LMS算法會(huì)輪流使用不同頂層網(wǎng)絡(luò)中板做樹(shù)根，因此可以將多播組分散到不同頂層網(wǎng)絡(luò)中板內(nèi).隨著多播組個(gè)數(shù)的增多，C-MR4LMS算法會(huì)重用頂層網(wǎng)絡(luò)中板，此時(shí)C-MR4LMS的優(yōu)勢(shì)將會(huì)消失.另外，由于創(chuàng)建的多播組不多，2種C-MR4LMS算法的EFI差別不大，C-MR4LMS-dynamic略?xún)?yōu)于C-MR4LMS-fixed.

2) 3維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的表現(xiàn)有時(shí)比MR4LMS好，有時(shí)比MR4LMS差，這是因?yàn)殡S著多播組個(gè)數(shù)的增大，MR4LMS算法會(huì)使用全部的頂層網(wǎng)絡(luò)中板，故3種算法均會(huì)將多播組分散到不同頂層網(wǎng)絡(luò)中板內(nèi)；而MR4LMS算法會(huì)根據(jù)負(fù)載情況選擇不同的交換機(jī)做樹(shù)根，因此大部分情況下MR4LMS算法具有更好的負(fù)載均衡性.2種C-MR4LMS算法比較，C-MR4LMS-dynamic略?xún)?yōu)于C-MR4LMS-fixed.

3) 進(jìn)程隨機(jī)加入某個(gè)多播組的模式下，MR4LMS算法明顯優(yōu)于2種C-MR4LMS算法.原因如下：C-MR4LMS算法下，多播組的個(gè)數(shù)已經(jīng)超過(guò)了不沖突的生成樹(shù)的個(gè)數(shù)，因而需要合并多播組，導(dǎo)致EFI偏大，而MR4LMS算法由于可以嘗試不同的交換機(jī)做樹(shù)根，不需要合并多播組，因而EFI指數(shù)小.后面將會(huì)看到，隨著多播組個(gè)數(shù)的進(jìn)一步增大，MR4LMS算法也會(huì)產(chǎn)生合并，此時(shí)其EFI指數(shù)也會(huì)明顯增加.需要指出的是，雖然2種C-MR4LMS算法的EFI明顯高于MR4LMS，但最大EFI為69，尚在可接受的范圍內(nèi).

4.2.2 每個(gè)終端上4個(gè)通信進(jìn)程

再分析每個(gè)終端節(jié)點(diǎn)上運(yùn)行4個(gè)通信進(jìn)程時(shí)的情況，結(jié)果如圖10(a)(b)所示.

1) 2維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的最大EFI及平均EFI略高于MR4LMS算法.這與每個(gè)終端上僅1個(gè)通信進(jìn)程時(shí)3維環(huán)網(wǎng)通信模式下的情況類(lèi)似，原因是進(jìn)程數(shù)增多后，多播組的個(gè)數(shù)也隨之增大，因而MR4LMS算法會(huì)使用全部的頂層網(wǎng)絡(luò)中板，故其表現(xiàn)優(yōu)于2種C-MR4LMS算法.

2) 3維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的表現(xiàn)有時(shí)比MR4LMS好，有時(shí)比MR4LMS差.MR4LMS比2種C-MR4LMS算法差的原因是：隨著多播組個(gè)數(shù)的增大，3種算法需要進(jìn)行合并，但2種C-MR4LMS算法僅會(huì)合并使用同一生成樹(shù)的多播組，合并的多播組較少；而MR4LMS算法在選擇樹(shù)根時(shí)是根據(jù)負(fù)載情況動(dòng)態(tài)選擇的，因此大量多播樹(shù)交錯(cuò)在一起，合并時(shí)極端情況下可能需要合并很多個(gè)多播組.

3) 進(jìn)程隨機(jī)加入某個(gè)多播組的模式下，2種C-MR4LMS算法的表現(xiàn)優(yōu)于MR4LMS，原因與2)一樣.

4.2.3 結(jié)論

綜合上面分析，在EFI方面，有4點(diǎn)結(jié)論：

1) 當(dāng)多播組個(gè)數(shù)少于不沖突的生成樹(shù)個(gè)數(shù)時(shí)，2種C-MR4LMS算法一般情況下略?xún)?yōu)于MR4LMS.

2) 當(dāng)多播組個(gè)數(shù)增大時(shí)，2種C-MR4LMS算法需要合并多播組，而MR4LMS算法不需要進(jìn)行合并操作，此時(shí)MR4LMS算法一般優(yōu)于2種C-MR4LMS算法.

3) 隨著多播組個(gè)數(shù)的繼續(xù)增大，從而使得3種算法都需要合并多播組時(shí)，2種C-MR4LMS算法一般情況下又會(huì)優(yōu)于MR4LMS算法.

4) 2種C-MR4LMS算法比較，C-MR4LMS-dynamic略?xún)?yōu)于C-MR4LMS-fixed；但大部分情況下，C-MR4LMS-fixed接近于C-MR4LMS-dynamic.

概括而言，依據(jù)圖9(a)、圖10(a)，當(dāng)多播組個(gè)數(shù)較少時(shí)，C-MR4LMS算法的最大EFI略高于MR4LMS算法，最多增大88；而當(dāng)多播組個(gè)數(shù)較多時(shí)，C-MR4LMS算法的最大EFI明顯低于MR4LMS算法，最多減少594.

4.3 不同通信模式下的TFI

多播樹(shù)的TFI表示有多少個(gè)多播組使用該多播樹(shù).最大TFI及平均TFI反映了多播組的合并程度.

4.3.1 每個(gè)終端上僅1個(gè)通信進(jìn)程

先分析每個(gè)終端節(jié)點(diǎn)上運(yùn)行1個(gè)通信進(jìn)程時(shí)的情況，結(jié)果如圖9(c)～(e)所示.

1) MR4LMS算法下，所有通信模式下均未發(fā)生合并，因此TFI均為1.

2) 2種C-MR4LMS算法下，當(dāng)多播組個(gè)數(shù)小于生成樹(shù)個(gè)數(shù)時(shí)(如181×181,100×327)，因不需要合并，TFI均為1.隨著多播組個(gè)數(shù)的增多，需要合并多播組，TFI大于1.有幾個(gè)有趣的現(xiàn)象需要注意：

① 64×32×16以及32×32×32這2種通信模式下，C-MR4LMS-fixed的最大TFI分別為7和6；而C-MR4LMS-dynamic的最大TFI均為1，這表明通過(guò)選擇同一TN內(nèi)的不同L3交換機(jī)做樹(shù)根可以避免一些不必要的合并操作.

② 25×50×26以及3種隨機(jī)加入多播組的通信模式下，2種C-MR4LMS算法的最大TFI均大于1且相等，但從平均TFI方面看C-MR4LMS-dynamic略?xún)?yōu)于C-MR4LMS-fixed.

③ 2種C-MR4LMS算法下，多播組發(fā)生合并后，剩余多播組的個(gè)數(shù)均不少于512(即系統(tǒng)中互不沖突的生成樹(shù)個(gè)數(shù)).

④ 隨機(jī)加入多播組的3種模式下，平均TFI接近于最大TFI，表明多播樹(shù)合并比較均勻.而3種3維環(huán)網(wǎng)通信模式下，平均TFI明顯低于最大TFI，原因是：采用分層的MGID分配策略后，有些層的多播組與拓?fù)浣Y(jié)構(gòu)匹配，因而不需要合并多播組，其TFI為1；而有些層的多播組與拓?fù)浣Y(jié)構(gòu)不匹配，需要合并多播組，其TFI較大，因此就出現(xiàn)了平均TFI與最大TFI差異較大的現(xiàn)象.

4.3.2 每個(gè)終端上4個(gè)通信進(jìn)程

分析每個(gè)終端節(jié)點(diǎn)上運(yùn)行4個(gè)通信進(jìn)程時(shí)的情況，結(jié)果如圖10(c)～(e)所示.有下列現(xiàn)象：

1) 3種2維環(huán)網(wǎng)模式，以及3維環(huán)網(wǎng)模式(256×32×16，128×32×32)，MR4LMS算法的最大TFI均為1，而2種C-MR4LMS算法的最大TFI均大于1.這是因?yàn)槊總€(gè)終端節(jié)點(diǎn)上運(yùn)行4個(gè)通信進(jìn)程時(shí)，這幾種2維環(huán)網(wǎng)通信模式中的多播組個(gè)數(shù)均超過(guò)了512，因而需要共用同一棵生成樹(shù)，導(dǎo)致2種C-MR4LMS均需合并多播組.

2) 100×50×26以及3種隨機(jī)加入多播組的模式下，3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)的最大TFI均大于1，但MR4LMS算法的最大TFI明顯高于2種C-MR4LMS算法，即MR4LMS算法在選擇樹(shù)根時(shí)是根據(jù)負(fù)載動(dòng)態(tài)選擇的，因此大量多播樹(shù)交錯(cuò)在一起，合并時(shí)極端情況下可能需要合并很多個(gè)多播組.以100×50×26通信模式為例，MR4LMS算法的最大TFI為168，而平均TFI僅為1.1，這表明大部分的多播組未被合并，而有168個(gè)多播組被合并到了一起.這也說(shuō)明MR4LMS算法在需要合并多播組時(shí)，TFI波動(dòng)較大.反觀2種C-MR4LMS算法，其最大TFI與平均TFI相比差別沒(méi)有這么明顯，特別是3種隨機(jī)加入多播組的模式下，平均TFI幾乎等于最大TFI，這是因?yàn)?種C-MR4LMS算法輪流使用不同的生成樹(shù).

3) 從合并后剩余的多播組個(gè)數(shù)上看，某些通信模式下MR4LMS算法僅剩下少量多播組，例如1 000個(gè)隨機(jī)多播組模式下僅剩下32個(gè)多播組，這進(jìn)一步表明MR4LMS算法極端情況下會(huì)合并大量多播組.而2種C-MR4LMS算法下，剩余多播組的個(gè)數(shù)均不少于512，這是因?yàn)?種C-MR4LMS算法在合并時(shí)僅合并那些使用同一生成樹(shù)的多播組.

4.3.3 結(jié)論

綜合上面分析，在TFI方面，有下列結(jié)論：

1) 當(dāng)多播組個(gè)數(shù)較少時(shí)，MR4LMS 算法不需要合并多播組，其TFI為1，而2種C-MR4LMS算法的TFI可能大于1.

2) 隨著多播組個(gè)數(shù)的繼續(xù)增大，3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)都需要合并多播組時(shí)，2種C-MR4LMS算法一般情況下會(huì)優(yōu)于MR4LMS算法，且剩余多播組的個(gè)數(shù)均不少于512;而MR4LMS算法在極端情況下會(huì)剩余很少的多播組.

3) 2種C-MR4LMS算法比較，C-MR4LMS-dynamic略?xún)?yōu)于C-MR4LMS-fixed.

概括而言，依據(jù)圖9(c)、圖10(c)，當(dāng)多播組個(gè)數(shù)較少時(shí)，C-MR4LMS算法的最大TFI略高于MR4LMS算法，最多增大25；而當(dāng)多播組個(gè)數(shù)較多時(shí)，C-MR4LMS算法的最大TFI明顯低于MR4LMS算法，最多減少148.

4.4 不同通信模式下的算法運(yùn)行時(shí)間

圖9(f)、圖10(f)分別顯示了每個(gè)終端節(jié)點(diǎn)上運(yùn)行不同數(shù)量的通信進(jìn)程時(shí)3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)的運(yùn)行時(shí)間.該時(shí)間僅包括計(jì)算路由的時(shí)間(選擇樹(shù)根、構(gòu)建多播樹(shù)、為多播樹(shù)染色等步驟的時(shí)間)，不包括發(fā)送加入多播組請(qǐng)求、分發(fā)路由等其他步驟的時(shí)間.

可以發(fā)現(xiàn)，2種C-MR4LMS算法的運(yùn)行時(shí)間明顯低于MR4LMS算法，最多下降94%.當(dāng)創(chuàng)建大量多播組而需要進(jìn)行合并的時(shí)候，兩者間的差異更加明顯.例如，圖10(f)所示100×50×26通信模式下，MR4LMS算法運(yùn)行時(shí)間超過(guò)575 s，而2種C-MR4LMS算法運(yùn)行時(shí)間均低于35 s，顯示出2種C-MR4LMS算法在減少運(yùn)行時(shí)間方面的巨大優(yōu)勢(shì).MR4LMS算法需要嘗試大量的樹(shù)根及顏色，故其運(yùn)行時(shí)間較長(zhǎng)，且受多播組大小、網(wǎng)絡(luò)中顏色使用情況等因素的影響；而2種C-MR4LMS算法直接根據(jù)MGID確定樹(shù)根及顏色，故其運(yùn)行時(shí)間固定，且時(shí)間較少.

另外，C-MR4LMS-dynamic運(yùn)行時(shí)間一般略高于C-MR4LMS-fixed，這是因?yàn)镃-MR4LMS-dynamic需要嘗試同一TN內(nèi)的不同T3交換機(jī)做樹(shù)根.

5 基準(zhǔn)測(cè)試程序性能

本文在神威E級(jí)原型機(jī)上對(duì)C-MR4LMS算法的集合消息性能進(jìn)行了測(cè)試.神威E級(jí)原型機(jī)采用神威互連網(wǎng)絡(luò)，以硬件方式支持同步、規(guī)約、廣播等集合消息類(lèi)型，相比點(diǎn)對(duì)點(diǎn)消息實(shí)現(xiàn)的集合操作具有更低的延時(shí)，其拓?fù)浣Y(jié)構(gòu)為4層胖樹(shù).使用了600個(gè)終端節(jié)點(diǎn)進(jìn)行測(cè)試，這些終端節(jié)點(diǎn)分布在4個(gè)CN內(nèi)，每個(gè)節(jié)點(diǎn)上運(yùn)行6個(gè)通信進(jìn)程.共測(cè)試了4種集合通信類(lèi)型，包括MPI_Barrier、8 B粒度的MPI_Allreduce、8 B及2 KB粒度的MPI_Bcast.通信模式如下：將所有進(jìn)程劃分為2維網(wǎng)格，為每行及每列均創(chuàng)建1個(gè)通信域；每個(gè)進(jìn)程先與同一行的所有進(jìn)程進(jìn)行1次集合通信，再與同一列的所有進(jìn)程進(jìn)行1次集合通信；所有進(jìn)程同時(shí)進(jìn)行通信，因此同一時(shí)刻有大量多播組在通信；共進(jìn)行5 000遍測(cè)試，由0號(hào)進(jìn)程記錄每遍測(cè)試中2次集合通信的總時(shí)間，2遍測(cè)試間不加同步；對(duì)每種進(jìn)程劃分方式、每種集合通信類(lèi)型，本文均測(cè)試了4種路由算法的性能，包括全局廣播鏈、MR4LMS、C-MR4LMS-fixed及MR4LMS-dynamic.

5.1 關(guān)閉容錯(cuò)時(shí)的集合消息性能

首先，測(cè)試關(guān)閉容錯(cuò)時(shí)的性能.表1顯示了不同路由算法下的集合消息延遲中位值.另外，圖11以小提琴圖的形式顯示了60×60通信模式下的集合消息延遲分布和概率密度.小提琴圖的兩側(cè)反映了密度信息，越寬表示出現(xiàn)在該區(qū)間的測(cè)試數(shù)據(jù)越多.小提琴圖的中間部分以箱線圖方式顯示了延遲的中位數(shù)及上下四分位數(shù)，其中上四分位數(shù)記為Q3，下四分位數(shù)記為Q1，Q3與Q1之間的差值稱(chēng)為四分位數(shù)差(interquartile range, IQR)，記為IQR.大于Q3+1.5×IQR或者小于Q1-1.5×IQR的值為異常值.IQR越小，表示數(shù)據(jù)越密集，波動(dòng)性越小.為便于顯示，圖11去掉了部分異常值.限于篇幅，未顯示其他通信模式下的小提琴圖.可以發(fā)現(xiàn)下列現(xiàn)象：

Table 1 Median Values of Collective Message Latencies Under Different Routing Algorithms

Fig. 11 Collective message latencies under different routing algorithms for 60×60 communication pattern圖11 60×60通信模式下不同路由算法的集合消息延遲

1) MR4LMS及2種C-MR4LMS-算法下的延遲明顯低于全局廣播鏈.以60×60通信模式下平均延遲為例，C-MR4LMS-fixed與全局廣播鏈相比，MPI_Barrier延遲降低10%，MPI_Allreduce延遲下降24%，8 B粒度MPI_Bcast延遲降低13%，2 KB粒度MPI_Bcast延遲降低40%.另外，全局廣播鏈下，對(duì)同一種集合操作來(lái)說(shuō)，不同通信模式下其延遲差異較大，這是因?yàn)椴煌ㄐ拍Ｊ较碌亩嗖ソM個(gè)數(shù)不同，而每個(gè)多播組都使用同一棵多播樹(shù)，導(dǎo)致不同通信模式下的鏈路EFI差異較大，測(cè)出的延遲差異也較大.相比而言，MR4LMS及2種C-MR4LMS-算法在不同通信模式下的延遲差異沒(méi)有這么明顯，這是因?yàn)檫@幾種算法可以將多播組分布到不同鏈路上.

2) 2種C-MR4LMS-算法的消息延遲與MR4LMS算法基本相當(dāng)，2 KB粒度的MPI_Bcast延遲甚至明顯低于MR4LMS.這與ibsim中的測(cè)試結(jié)果一致，即當(dāng)多播組個(gè)數(shù)較少時(shí)，C-MR4LMS算法的鏈路EFI低于MR4LMS算法，而2 KB粒度的集合消息對(duì)EFI較敏感.

3) C-MR4LMS-fixed與MR4LMS-dynamic算法的消息延遲差異不大，可以認(rèn)為是測(cè)試誤差及網(wǎng)絡(luò)噪音導(dǎo)致了這些差異.

4) 從圖11可以看出，4種路由算法在延遲數(shù)據(jù)的穩(wěn)定性方面差異不大.

本文也測(cè)試了3維環(huán)網(wǎng)及隨機(jī)加入多播組的情況，測(cè)試結(jié)果與表1及圖11類(lèi)似，不再贅述.

綜上所述，當(dāng)大量多播組同時(shí)通信時(shí)，2種C-MR4LMS算法下集合消息的延遲明顯低于全局廣播鏈，而與MR4LMS算法相當(dāng).

5.2 開(kāi)啟容錯(cuò)時(shí)的集合消息性能

首先測(cè)試容錯(cuò)功能的有效性.通過(guò)手工斷開(kāi)某條鏈路制造故障，然后運(yùn)行上述基準(zhǔn)測(cè)試程序，發(fā)現(xiàn)全局廣播鏈、MR4LMS均存在收不到消息的情況，而2種C-MR4LMS算法下測(cè)試課題均能正常運(yùn)行.這表明開(kāi)啟容錯(cuò)功能后可以對(duì)網(wǎng)絡(luò)故障進(jìn)行透明容錯(cuò).

由于開(kāi)啟容錯(cuò)功能后，原來(lái)的1個(gè)多播數(shù)據(jù)包會(huì)被復(fù)制2份，可能會(huì)影響消息延遲.下面以C-MR4LMS-fixed為例分別測(cè)試關(guān)閉及打開(kāi)容錯(cuò)功能時(shí)的消息延遲，觀察容錯(cuò)功能對(duì)消息性能的影響.圖12顯示了60×60通信模式下的測(cè)試結(jié)果.其中C-MR4LMS-fixed表示關(guān)閉容錯(cuò)，C-MR4LMS-fixed-ft表示開(kāi)啟容錯(cuò).可以發(fā)現(xiàn)：1)從延遲中位值的角度看，開(kāi)啟容錯(cuò)功能后MPI_Barrier,MPI_Allreduce的延遲略有下降，而MPI_Bcast的延遲略有上升.2)從分布范圍看，開(kāi)啟容錯(cuò)后延遲波動(dòng)范圍略有降低，可以認(rèn)為有更低的尾延遲.

Fig. 12 Collective message latencies under C-MR4LMS-fixed with and without fault tolerance圖12 開(kāi)啟及關(guān)閉容錯(cuò)功能C-MR4LMS-fixed算法下的集合消息延遲

上述測(cè)試結(jié)果表明，多復(fù)制一份數(shù)據(jù)包并不會(huì)對(duì)消息延遲帶來(lái)顯著影響，反而會(huì)緩解因多個(gè)多播組相互干擾而帶來(lái)的性能波動(dòng).出現(xiàn)該現(xiàn)象的原因是：終端節(jié)點(diǎn)收到第1個(gè)數(shù)據(jù)包后就可做后續(xù)處理，因而可以忽略延后到達(dá)的多播包，一定程度上抵消網(wǎng)絡(luò)噪音對(duì)多播消息帶來(lái)的影響.

6 結(jié) 論

本文針對(duì)胖樹(shù)拓?fù)涮岢鲆环N高效實(shí)用的定制多播路由算法C-MR4LMS，在硬件僅支持很小的多播表時(shí)，能夠快速地為數(shù)千甚至數(shù)萬(wàn)個(gè)多播組構(gòu)建多播路由.C-MR4LMS在構(gòu)建多播樹(shù)時(shí)，根據(jù)多播組的MGID靜態(tài)地將多播組映射到1棵生成樹(shù)中，這帶來(lái)了下列好處：1)可以快速選擇出樹(shù)根及顏色，從而快速完成多播樹(shù)的構(gòu)建；2)構(gòu)建出的多播樹(shù)是恒定不變的，重算多播路由不會(huì)改變多播樹(shù)；3)合并多播樹(shù)時(shí)，僅需合并使用同一生成樹(shù)的多播組，且僅需添加某些鏈路即可完成多播樹(shù)的合并，不會(huì)改變被合并的多播組的路由.而MR4LMS算法根據(jù)各多播鏈號(hào)的使用情況，動(dòng)態(tài)創(chuàng)建多播樹(shù)，因而多播路由具有動(dòng)態(tài)可變性，即在不同時(shí)刻、不同網(wǎng)絡(luò)狀態(tài)下為同一多播組構(gòu)建的多播樹(shù)可能不同.

實(shí)驗(yàn)結(jié)果表明，當(dāng)多播組個(gè)數(shù)少于不沖突的生成樹(shù)個(gè)數(shù)時(shí)，C-MR4LMS算法在EFI,TFI方面與MR4LMS算法相當(dāng)，某些情況下甚至略?xún)?yōu)于MR4LMS算法.隨著多播組個(gè)數(shù)的增多，C-MR4LMS算法需要進(jìn)行合并操作，而MR4LMS算法由于可以嘗試不同的樹(shù)根及顏色，不需要進(jìn)行大量合并操作，在EFI,TFI方面優(yōu)于C-MR4LMS算法.隨著多播組個(gè)數(shù)的進(jìn)一步增多，MR4LMS算法也需要進(jìn)行很多合并操作，此時(shí)C-MR4LMS算法大部分情況下又會(huì)優(yōu)于MR4LMS算法.可以認(rèn)為，很多情況下，C-MR4LMS算法在EFI,TFI方面優(yōu)于MR4LMS算法；而部分情況下，C-MR4LMS算法在EFI,TFI方面比MR4LMS算法差，但仍在可接受的范圍內(nèi).基準(zhǔn)測(cè)試程序也表明，在各種通信模式下，C-MR4LMS算法下的集合消息性能不比MR4LMS算法差，很多情況下還優(yōu)于MR4LMS算法；而在運(yùn)行時(shí)間方面，C-MR4LMS算法具有明顯的優(yōu)勢(shì).

綜上所述，在胖樹(shù)中C-MR4LMS算法的性能可以匹敵MR4LMS算法，而其運(yùn)行時(shí)間相比MR4LMS算法有了顯著下降，能夠更好地滿足大規(guī)模并行應(yīng)用的需求.

另外，C-MR4LMS算法還有需要完善的地方：1)C-MR4LMS采用由用戶(hù)指定MGID的策略，因此需要用戶(hù)巧妙地選取MGID，這對(duì)用戶(hù)提出了很高的要求.未來(lái)，我們將提供工具幫助用戶(hù)完成該工作.2)目前C-MR4LMS面向拓?fù)湟阎呐謽?shù)，影響了其適用性.未來(lái)我們將做下列改進(jìn)：①自動(dòng)感知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，動(dòng)態(tài)調(diào)整相關(guān)的網(wǎng)絡(luò)參數(shù)；②識(shí)別故障鏈路，并將使用該鏈路的生成樹(shù)標(biāo)記為不可用，從而在構(gòu)建多播路由時(shí)避開(kāi)這些故障鏈路.但這會(huì)導(dǎo)致C-MR4LMS遇到與MR4LMS一樣的難題：多播路由受網(wǎng)絡(luò)狀態(tài)的影響，具有動(dòng)態(tài)多變性，需要在多播路由的穩(wěn)定性與適用性這兩者間進(jìn)行適當(dāng)?shù)钠胶?

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