胖樹拓?fù)渲懈咝嵱玫亩ㄖ贫嗖ヂ酚伤惴?/h1>
2022-12-15 13:18陳淑平何王全漆鋒濱
計算機(jī)研究與發(fā)展 2022年12期
陳淑平 李 祎 何王全 漆鋒濱
(江南計算技術(shù)研究所 江蘇無錫 214083)(chenshuping_hit@163.com)
在高性能計算領(lǐng)域，多播路由算法對硬件支持的集合操作性能具有至關(guān)重要的影響.例如，集合通信中的Bcast,Barrier,AllReduce,AllGather等操作均可通過多播進(jìn)行加速.多播路由算法通過構(gòu)建多播樹實現(xiàn).過去主要研究如何降低樹高、如何提升路由負(fù)載均衡程度.目前高性能計算已經(jīng)邁入E級計算時代，系統(tǒng)中多播組的個數(shù)急劇增加，可能會超過硬件支持的多播表條目數(shù)，而現(xiàn)有的多播路由算法要么沒有給出解決方案，要么存在時間開銷大、多播路由經(jīng)常變化等問題.為此，本文提出一種用于胖樹的高效實用的定制多播路由算法(customized multicast routing for limited multicast forwarding table size, C-MR4LMS)，可用于包括Infiniband在內(nèi)的高速互連網(wǎng)絡(luò).本文主要貢獻(xiàn)包括：
1) 對胖樹結(jié)構(gòu)中可使用的無沖突多播生成樹個數(shù)進(jìn)行了量化研究，根據(jù)系統(tǒng)中的最大多播組個數(shù)確定多播表的大小，為設(shè)計互連網(wǎng)絡(luò)系統(tǒng)提供了理論依據(jù).
2) 提出了一種用于胖樹拓?fù)涞母咝嵱玫亩ㄖ贫嗖ヂ酚伤惴–-MR4LMS，可根據(jù)MGID(multicast global identification)靜態(tài)地將多播組映射到1棵生成樹中，快速完成多播樹的構(gòu)建；當(dāng)需要合并多播組時，僅需合并那些使用同一生成樹的多播組，且僅需添加部分鏈路即可完成多播組的合并，不會改變被合并多播組的路由，因此不會影響這些多播組的正常使用.
3) 提出了分層的MGID分配策略，當(dāng)同一終端節(jié)點同時加入多個多播組時，每個多播組都使用不同層內(nèi)的MGID，避免出現(xiàn)同一終端節(jié)點使用同一顏色加入多個多播組的情況.
4) 提出了相互無干擾的作業(yè)節(jié)點分配策略，使得2個作業(yè)不共用任何通信鏈路，保證2個作業(yè)的多播組互不干擾.
5) 在多種典型拓?fù)浣Y(jié)構(gòu)及典型通信模式下對C-MR4LMS的鏈路EFI、TFI、運(yùn)行時間及應(yīng)用程序性能等進(jìn)行了測試，驗證了其有效性.
1 研究背景及相關(guān)工作
集合通信[1-4]為實現(xiàn)一組進(jìn)程間的通信提供了非常方便的抽象，被廣泛應(yīng)用于高性能計算領(lǐng)域.它包括同步、廣播、規(guī)約、全規(guī)約、分散、收集、全收集等類型及其變體，可實現(xiàn)多個進(jìn)程間的同步、數(shù)據(jù)分發(fā)與收集等功能.傳統(tǒng)的集合通信一般是由軟件利用點到點消息實現(xiàn)的.但隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，超級計算機(jī)對集合通信的性能及可擴(kuò)展性都提出了更高的要求，而軟件集合通信難以滿足E級系統(tǒng)的需求.硬件集合通信可將集合操作卸載到網(wǎng)絡(luò)設(shè)備中進(jìn)行，具有良好的性能及可擴(kuò)展性，已成為高速互連網(wǎng)絡(luò)領(lǐng)域的研究熱點.近幾年出現(xiàn)了很多硬件集合通信技術(shù)，如Mellanox的SHARP技術(shù)[5]，神威互連網(wǎng)絡(luò)的硬件集合通信等[6].
硬件支持的集合操作中，多播技術(shù)是重要的支撐.集合通信中的Bcast,Barrier,AllReduce,AllGather等操作需要將相同的數(shù)據(jù)分發(fā)給參與集合通信的不同進(jìn)程，它們均可利用硬件多播進(jìn)行加速.因此多播路由的性能對這些集合操作具有重要影響.
目前的多播路由算法[7-12]均是為每個多播組構(gòu)建1棵多播樹.用戶每創(chuàng)建1個多播組，就需要構(gòu)建1棵對應(yīng)的多播樹，并占用多播路由表的1個條目號.而多播表大小是有限的，隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，多播組的個數(shù)會急劇增加，可能會超過硬件支持的多播表條目數(shù).而現(xiàn)有的多播路由算法要么默認(rèn)多播表條目數(shù)是夠用的，因此沒有給出多播表條目數(shù)不足時構(gòu)建多播表的方案；要么針對拓?fù)湮粗木W(wǎng)絡(luò)，存在時間開銷大、多播路由經(jīng)常變化等問題.本文在胖樹結(jié)構(gòu)下研究面向有限多播表條目數(shù)的多播路由算法.
1.1 基本概念
定義1.互連網(wǎng)絡(luò).互連網(wǎng)絡(luò)定義為一個有向圖I=G(N,L)，其中N為網(wǎng)絡(luò)節(jié)點集合，L為通信鏈路集合，網(wǎng)絡(luò)節(jié)點又分為終端(一般是網(wǎng)卡設(shè)備，用于收發(fā)數(shù)據(jù))及交換機(jī)(用于轉(zhuǎn)發(fā)數(shù)據(jù)).
定義2.多播組.多播組(multicast group, MCG)是網(wǎng)絡(luò)節(jié)點集N的一個子集，其成員一般是終端節(jié)點.
多播組對應(yīng)MPI中的1個通信域，用全局唯一的MGID標(biāo)識.它不僅用于多播操作，還可用于包括同步、全局規(guī)約等在內(nèi)的其他集合操作.例如，神威互連網(wǎng)絡(luò)中，硬件全局規(guī)約可通過多播組將規(guī)約結(jié)果廣播給所有成員.
定義3.多播路由.從單個交換機(jī)的角度看，多播路由可定義為如下映射R:L×M→2L，其中M為MGID集合.該映射的輸入?yún)?shù)為輸入鏈路lij及多播組MGID，返回值為輸出鏈路列表{ljk}.
該定義允許交換機(jī)根據(jù)不同輸入鏈路選擇不同的輸出鏈路.這要求交換機(jī)每個端口都有獨立的多播路由表.而從全局角度看，多播路由R將多播組MGID映射為I的1棵子樹，該子樹包含該多播組的所有成員.我們稱該子樹為多播樹(multicast tree, MCT).圖1所示的多播組中，陰影所示節(jié)點發(fā)送多播包時，每到達(dá)1個交換機(jī)的1個端口，就查詢該多播組對應(yīng)的多播表條目，從而確定將多播包復(fù)制到哪些端口進(jìn)行轉(zhuǎn)發(fā).1個多播組對應(yīng)1棵多播樹，但1棵多播樹可供多個多播組使用.
Fig. 1 Illustration for multicast tree圖1 多播樹示意圖
定義4.多播表條目號.交換機(jī)多播表有多個條目，以支持不同的多播組，其編號稱為多播表條目號.每個條目都是1個位圖，指定了需要將數(shù)據(jù)包復(fù)制到哪些輸出端口.多播路由除了為每個多播組確定多播樹之外，還需要確定該多播樹使用的多播表條目號.
在發(fā)送多播消息時，MGID及多播表條目號具有不同的作用.用戶需同時指定目的MGID及多播表條目號.交換機(jī)收到多播包時，根據(jù)多播表條目號查找對應(yīng)的多播表條目，并將多播包通過該多播表條目指定的輸出端口轉(zhuǎn)發(fā)出去.而終端節(jié)點收到多播包后，則根據(jù)MGID決定將該包拷貝到哪些通信隊列中.
不同廠商支持的多播表條目數(shù)不同，例如Mellanox交換機(jī)最多可支持16 384個多播表條目，而神威互連網(wǎng)絡(luò)僅支持32個多播表條目.在不考慮多播表大小的情況下，可以為每個多播組都分配1個不同的多播表條目號；Infiniband即采用該策略，其多播表條目號稱為MLID(multicast local identification).而在考慮到多播表有大小限制時，則沒有必要為每個多播組都分配1個單獨的多播表條目號，2個多播組只要不使用同一條鏈路，就可以共用同一個多播表條目號，從而大大降低對多播表條目數(shù)的需求；神威互連網(wǎng)絡(luò)即采用該策略，其多播表條目號稱為多播鏈號.
為多播樹分配多播表條目號時，必須遵循下列原則：1)同一棵多播樹在其使用的所有交換機(jī)內(nèi)使用相同的多播表條目號；2)若2棵多播樹經(jīng)過同一條鏈路，則這2棵多播樹不能使用同一個多播表條目號.將每棵多播樹看做圖的頂點，只要2棵多播樹共用同一條鏈路，則稱這2棵多播樹“相鄰”，對應(yīng)的2個頂點間添加1條邊.我們將多播表條目號用顏色表示，為“相鄰”的多播樹指定不同的多播表條目號，也即用不同的顏色染色.后文將用術(shù)語“染色”表示為多播樹分配多播表條目號.
定義5.EFI(edge forwarding index).文獻(xiàn)[13-14]定義了單播路由中的EFI指數(shù).我們對此進(jìn)行擴(kuò)展，將每條鏈路的EFI定義為經(jīng)過該鏈路的多播組個數(shù).
鏈路的最大EFI值反映了擁塞程度，值越大表示擁塞程度越高.最大EFI對多播操作性能具有重要影響，故需要盡量將多播路由均衡分布到不同的鏈路上，以降低EFI指數(shù).
定義6.TFI(tree forwarding index).對多播樹而言，使用該多播樹的多播組個數(shù)稱為該多播樹的TFI.
若多個多播組共享1棵多播樹，則1個多播組內(nèi)的多播數(shù)據(jù)包會復(fù)制到其它多播組內(nèi)，從而造成相互干擾，故TFI實際上反映了多播樹中多播數(shù)據(jù)包的冗余程度.
1.2 現(xiàn)有多播路由算法存在的問題
Infiniband中現(xiàn)有的多播路由算法構(gòu)建多播樹的過程包括：1)選擇1個交換機(jī)作為多播樹的樹根，使其到多播組內(nèi)各成員的平均距離或最大距離最?。?)為多播組的每個成員分別找到1條到達(dá)樹根的路徑，從而完成多播樹的構(gòu)建.需要注意的是，在尋找到達(dá)樹根的路徑的過程中，不能形成環(huán).
現(xiàn)有的路由算法未考慮多播表條目數(shù)不夠用的問題，它們?yōu)槊總€MGID都分配1個不同的多播表條目號.隨著應(yīng)用規(guī)模的不斷擴(kuò)大，多播組的數(shù)量也隨之快速增大，系統(tǒng)中可能同時存在成百上千甚至數(shù)萬個多播組，可能會超過硬件支持的多播表條目數(shù),導(dǎo)致多播表條目不夠用.
對于多播表條目不夠用的問題，一種簡單的解決方案是建立1棵超級多播樹(神威互連網(wǎng)絡(luò)中稱為全局廣播鏈)，使其包含所有終端節(jié)點，使所有多播組都使用該多播樹進(jìn)行廣播.但該方案存在嚴(yán)重的性能問題：1個多播組發(fā)送的數(shù)據(jù)會復(fù)制到整個網(wǎng)絡(luò)中，造成網(wǎng)絡(luò)中存在大量無用的多播包；當(dāng)很多個多播組同時使用該多播樹發(fā)送消息時，會造成集合操作性能的嚴(yán)重下降.
為此，我們在前期工作中[15]提出了面向有限多播表條目數(shù)的多播路由算法(multicast routing for limited multicast forwarding table size, MR4LMS).MR4LMS工作原理為：只要多個多播組不經(jīng)過同一條鏈路，就盡量共用同一個多播表條目號；而當(dāng)n個相似的多播組無條目號可用時，就將它們合并到一起共用同一棵多播樹.也即首先嘗試讓多個多播組共用同一個多播組條目號，如果失敗，則嘗試讓多個多播組共用同一棵多播樹.
具體來說，MR4LMS包括2個主要部分.一是采用2種方法來構(gòu)造多播樹，包括：1)在可用顏色數(shù)比較充足時，采用先構(gòu)造后染色算法，以每個備選交換機(jī)為樹根構(gòu)造1棵多播樹，然后嘗試用不同的顏色染色；2)在顏色數(shù)不足時，采用先染色后構(gòu)造算法，先找出可用的顏色，然后在該顏色下構(gòu)造1棵多播樹.二是當(dāng)上述2種方法都不能構(gòu)造出多播樹時，采用合并算法，將多個多播組合并成1個多播組，從而降低對多播組顏色數(shù)的需求.
MR4LMS主要用于拓?fù)湮粗木W(wǎng)絡(luò)，可以顯著降低所需的多播表條目數(shù)，滿足大部分應(yīng)用創(chuàng)建多播組時的需求.但也存在一些實用性方面的問題，包括：
1) MR4LMS需要進(jìn)行大量的圖遍歷操作，時間開銷很大，特別是同時創(chuàng)建成百上千個多播組時，很可能出現(xiàn)顏色數(shù)不夠用的情況，則需要嘗試很多交換機(jī)做樹根，或嘗試很多種顏色，此時運(yùn)行時間可能會超過數(shù)分鐘.
2) MR4LMS根據(jù)系統(tǒng)中已存在的其他多播樹情況為新多播組構(gòu)建多播樹，因此對于同一個多播組，在不同時刻構(gòu)建的多播樹很可能是不同的，也即創(chuàng)建出的多播樹具有動態(tài)可變性.這在實際應(yīng)用場景中會帶來很多問題：①當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化而重新計算多播路由時，多播組使用的多播樹即使沒有使用故障鏈路，重新計算路由后也很可能會發(fā)生變化，從而造成多播路由的頻繁變化，影響用戶使用；②同一應(yīng)用在不同時刻運(yùn)行時，構(gòu)建的多播樹也可能不同，這會帶來應(yīng)用性能的差異，影響用戶體驗.
3) 當(dāng)顏色不足而需要合并多播組時，也可能會重構(gòu)已存在的多播樹，從而影響已存在的多播組的使用.另外，不同時刻進(jìn)行合并，產(chǎn)生的多播組也可能不同，帶來2)中所述的影響.
4) 未考慮容錯問題.當(dāng)多播樹的1條鏈路發(fā)生故障后，MR4LMS會重構(gòu)所有的多播路由，由此帶來下列問題：一是需要為所有多播組都重算路由，導(dǎo)致整機(jī)范圍的路由重構(gòu)，影響范圍廣；二是經(jīng)過故障鏈路的多播包會丟失，即使有端到端的傳輸層控制協(xié)議可以重傳該包，但由于重構(gòu)多播路由需要相對較長的時間，因此會對應(yīng)用性能帶來較大影響.
Fig. 2 Illustration of fat tree structure圖2 胖樹結(jié)構(gòu)示意圖
實際上，針對特定的拓?fù)浣Y(jié)構(gòu)，可以采用更高效的解決方案.胖樹是目前高性能計算中最流行的拓?fù)浣Y(jié)構(gòu)，Top500排名中很多計算機(jī)均采用胖樹或裁剪胖樹.本文將針對胖樹結(jié)構(gòu)研究硬件僅支持少量多播組條目數(shù)時的多播路由算法.
1.3 本研究使用的胖樹結(jié)構(gòu)
目前Top500超級計算機(jī)中使用較多的是3層或4層胖樹[16-19].本文研究圖2所示的4層胖樹.L0與L1層交換機(jī)被分成多個計算網(wǎng)絡(luò)中板(computing network midplane, CN)，每個CN包含q個L0層交換機(jī)以及m個L1層交換機(jī).L2層與L3層交換機(jī)也被分成多個頂層網(wǎng)絡(luò)中板(top network midplane, TN)，每個TN包含k個L2層交換機(jī)以及w個L3層交換機(jī).每個L1層交換機(jī)共有p個端口用于連接TN，故每個CN共有m×p個端口用于連接TN，TN的個數(shù)為m×p.每個TN有k×w個端口用于連接CN，因而CN的個數(shù)為k×w.
2 高效實用地定制多播路由算法
為了快速創(chuàng)建多播路由，可以預(yù)先構(gòu)建好一些多播樹，但這些多播樹并沒有真正寫到多播表中.當(dāng)為多播組創(chuàng)建多播樹時，直接從這些預(yù)分配的多播樹中選擇1棵使用即可.每棵這樣的多播樹都應(yīng)該包含所有L0層交換機(jī)，以支持整機(jī)規(guī)模的多播組.為與1.1節(jié)所述的多播樹加以區(qū)別，稱這些預(yù)先創(chuàng)建的多播樹為生成樹(spanning tree, SPT).一般情況下，多播組僅會使用該生成樹的部分枝葉.當(dāng)為多播組創(chuàng)建多播樹時，僅將所使用的那部分枝葉寫進(jìn)多播表中即可.
在胖樹結(jié)構(gòu)中，多播組使用的多播樹的樹根應(yīng)該是多播組內(nèi)各成員的最近公共祖先.由于任一L0層交換機(jī)到給定樹根有且只有1條路徑，對每個多播組而言，只要確定了樹根及顏色就確定了多播樹.因此，要預(yù)先建立生成樹，只需確定哪些交換機(jī)可以作為樹根即可.選擇交換機(jī)時，需要考慮以該交換機(jī)為樹根建立的生成樹，跟那些已建立的生成樹是否存在沖突.2棵生成樹若使用同一種顏色，則不能共用同一條鏈路；只有使用不同顏色時才可以共用同一條鏈路.
2.1 無沖突的生成樹個數(shù)
首先要回答的問題是：給定顏色數(shù)C，可以建立多少棵不沖突的生成樹？首先分析僅有一種顏色時生成樹的個數(shù).暫不考慮L0層交換機(jī)與終端節(jié)點間的鏈路是否會存在沖突.
定理1.胖樹結(jié)構(gòu)中，一種顏色能且僅能創(chuàng)建m棵不沖突的生成樹，其中m是每個CN內(nèi)L1層交換機(jī)的個數(shù).
證明.首先，按下述方式構(gòu)造m棵生成樹.先將TN按從左到右的順序編號并分組，每p個分為1組，共m組.按該分組方法，每個L1層交換機(jī)所連接的p個TN位于同一組內(nèi).然后從每組中任意選擇1個TN，共選出m個.再在每個選出的TN中任選1個L3層交換機(jī)，共選出m個交換機(jī).以這m個交換機(jī)為根，以所有L0層交換機(jī)為葉節(jié)點，可產(chǎn)生m棵生成樹.圖3單實線部分顯示了一棵以第1個TN為樹根的生成樹.
Fig. 3 Illustration of spanning tree圖3 生成樹示意圖
其次，證明這m棵生成樹不共用任何一條鏈路.很明顯，這m棵生成樹沒有共用任何L2?L3以及L1?L2間鏈路，因為每個樹根都位于不同的TN內(nèi).而每個L1層交換機(jī)連接的p個TN位于同一組內(nèi)，這p個TN僅有1個被選為樹根.也就是說，按上述方式構(gòu)建的2棵生成樹，不可能經(jīng)過同一個L1交換機(jī)，也就不可能共用L0?L1間鏈路.因此，上面構(gòu)造的m棵多播樹不共用任何1條鏈路，可使用同一種顏色.
最后，很容易就可看出，CN內(nèi)的每條鏈路都已被上述m棵生成樹中的1棵使用，因此不可能再創(chuàng)建出新的生成樹了.
綜上所述，僅有一種顏色時，能且僅能創(chuàng)建m棵不沖突的生成樹.
證畢.
需要指出的是，僅使用一種顏色時，1個TN唯一確定了1棵生成樹，而不用關(guān)心該生成樹使用了該TN內(nèi)的哪個L3層交換機(jī)做根.因此，如果2個多播組選擇同一個TN內(nèi)的不同交換機(jī)做樹根，仍認(rèn)為這2個多播組使用了同一棵生成樹.更進(jìn)一步，如果2個多播組選擇使用位于同一組內(nèi)的2個不同TN做樹根，由于它們可能共用L0?L1間鏈路，仍認(rèn)為這2個多播組使用了同一棵生成樹.如果2個多播組選擇同一個TN內(nèi)的交換機(jī)做樹根，但使用了不同的顏色，則認(rèn)為這2個多播組使用了不同的生成樹.概括而言，TN及顏色唯一確定了1棵生成樹.
根據(jù)定理1，可以很容易得到下面的2個推論.
推論1.胖樹結(jié)構(gòu)中，C種顏色能且僅能創(chuàng)建C×m棵不沖突的生成樹.其中每個L1交換機(jī)承擔(dān)C棵生成樹，可以把這C棵生成樹分布到跟該L1交換機(jī)連接的p個TN中.
在構(gòu)造網(wǎng)絡(luò)系統(tǒng)時，上述定理及推論為確定多播表大小提供了理論依據(jù).例如，若用40端口交換機(jī)構(gòu)造網(wǎng)絡(luò)系統(tǒng)，則m=20；在每個交換機(jī)端口僅支持256個多播表條目時，可支持不少于5 120個多播組.
需要說明的是，系統(tǒng)中實際可創(chuàng)建的多播組個數(shù)一般大于C×m.這是因為很多情況下2個多播組可以共用同一棵生成樹而不沖突，只要它們不共用該生成樹的同一條鏈路即可.例如，如果使用該生成樹的多播組的所有成員都位于同一個CN內(nèi)，則該多播組僅使用了該生成樹位于該CN內(nèi)的那部分枝葉，剩余部分仍可供其他多播組使用.
即使多播組的成員分散在不同CN內(nèi)，從而需要將根建在L2或L3層交換機(jī)上，該多播組仍然可以跟其他多播組共用同一棵生成樹.圖4顯示了一個這樣的例子.灰色陰影所示多播組和斜條紋填充所示多播組可以使用同一個L3層交換機(jī)做樹根.2個使用同一棵生成樹的多播組，只要它們沒有共用同一個L2交換機(jī)，就可以共同一個L3交換機(jī)做樹根，因為這樣產(chǎn)生的多播樹沒有共用任何相同的鏈路.
Fig. 4 Example for 2 MCGs using the same spanning tree圖4 2個多播組共用1棵生成樹的例子
系統(tǒng)中共有C×m棵不沖突的生成樹，對編號為spt_no的生成樹，根據(jù)式(1)確定其顏色color及樹根所在的頂層網(wǎng)絡(luò)中板tnid.另外，總是選擇該頂層網(wǎng)絡(luò)中板的第1個L3交換機(jī)做樹根，因此確定了tnid及color，就確定了樹根.由式(1)可以看出，我們將不同顏色的生成樹樹根分散到同一組內(nèi)的不同TN內(nèi)，來達(dá)到負(fù)載均衡的目的.
(1)
2.2 為多播組選擇生成樹
為多播組創(chuàng)建多播樹時，首先需要確定該多播組應(yīng)該使用哪棵生成樹.對每一個多播組，根據(jù)其MGID將其映射到上述C×m棵生成樹中的1棵.具體來說，假設(shè)多播組的MGID為mgid，根據(jù)式(2)確定該多播組使用的生成樹.
spt_no=mgid%(C×m).
(2)
根據(jù)式(1)(2)我們可以得出根據(jù)MGID直接計算顏色編號及樹根所在TN編號：
(3)
采用該方式創(chuàng)建多播樹時，無需考慮系統(tǒng)中各鏈路的負(fù)載及顏色使用情況，僅由MGID即可確定使用哪棵生成樹.如果多播組的個數(shù)多于C×m，則可能出現(xiàn)多個多播組共同一棵生成樹的情況，此時需要將幾個多播組合并成1個多播組.式(1)及式(3)保證使用同一棵生成樹的2個多播組在合并時，僅需在原來的多播樹上添加部分鏈路即可，被合并的那些多播組使用的多播樹并不受影響，從而不會影響這些多播組的正常使用.
1個終端加入多個多播組時，每個多播組需要使用不同的顏色，否則在終端節(jié)點與L0交換機(jī)間的鏈路上就會產(chǎn)生沖突.本文將在3.1節(jié)研究該問題的解決方案.
2.3 為多播組構(gòu)造多播樹
確定樹根所在的頂層網(wǎng)絡(luò)中板及顏色后，就可以構(gòu)造多播樹了，步驟如算法1所示.該算法根據(jù)多播組成員的分布情況，從生成樹中選擇合適的交換機(jī)做為該多播組的樹根，它們可能位于L0,L1,L2,L3中的某一層.
算法1.多播樹構(gòu)造算法.
輸入：互連網(wǎng)絡(luò)I=G(N,L)、多播組mcg；
輸出：多播樹mct.
① 根據(jù)式(3)計算該多播組使用的顏色color以及樹根所在的頂層網(wǎng)絡(luò)中板tnid；
② 對多播組的每個成員，檢查其連接到L0交換機(jī)的那條鏈路上顏色color是否已被使用，若是則返回NULL；
③ 根據(jù)多播組各成員的物理位置，確定該多播組內(nèi)各成員的最近公共祖先所在的位置；
④ 若最近公共祖先位于L0或L1或L2層，則該公共祖先有且只有1個，記為root；
⑤ 若最近公共祖先位于L3層，則選擇頂層網(wǎng)絡(luò)中板tnid內(nèi)的第1個L3交換機(jī)做樹根root；
⑥ 以root為樹根，為mcg的每個成員都找出該成員到root的路徑，從而構(gòu)建出多播樹mct；
⑦ 檢查mct的每條鏈路中顏色color是否可用，若均為可用，則返回mct；
⑧ 否則，返回NULL./*需進(jìn)行合并操作*/
算法1步驟②用于檢查終端節(jié)點使用同一種顏色加入多個多播組的情況；若該顏色已被使用，則不能利用該顏色創(chuàng)建新的多播組，因此返回NULL，表示需要進(jìn)行合并操作.
算法1步驟③～⑤用于確定樹根，規(guī)則為：
1) 若多播組的成員都位于同一個L0交換機(jī)內(nèi)，則樹根即為該L0交換機(jī)；
2) 若多播組的成員均位于同一個CN內(nèi)，則樹根為生成樹在該CN內(nèi)的那個L1交換機(jī)；
3) 若多播組的成員位于不同CN內(nèi)(CN編號記為cnid)，且所有cnid/w相等，則樹根為生成樹中用于連接這些CN的那個L2交換機(jī)；
4) 其他情況下，選擇該生成樹中的第1個L3交換做樹根.
算法1步驟⑥⑦嘗試使用顏色color構(gòu)建多播樹.在胖樹結(jié)構(gòu)中，確定了樹根后，多播組的每個成員到樹根僅有1條鏈路，因此也就確定了多播樹.2個多播組使用同一棵生成樹時，有可能會共用同一條鏈路，從而會產(chǎn)生沖突，此時需要進(jìn)行合并操作，方法見2.4節(jié).
將多播組中成員個數(shù)記為S，則算法1的時間復(fù)雜度為O(S).
2.4 合并多播組
在算法1中，如果發(fā)現(xiàn)新構(gòu)造的多播樹與某個已經(jīng)創(chuàng)建的多播組使用了同一條鏈路，則需要進(jìn)行合并操作.方法如下：將算法1中構(gòu)建的多播樹記為tmpMct，檢查tmpMct的每條鏈路，若該鏈路中顏色color已被其他多播組使用，則根據(jù)式(3)這些多播組必定與新創(chuàng)建的多播組使用同一棵生成樹；將這些多播組的所有成員，連同新創(chuàng)建的多播組的成員一起，利用算法2構(gòu)建一個新的多播組，記為vmcg；然后利用算法1為vmcg創(chuàng)建多播樹.
算法2.合并算法.
輸入：互連網(wǎng)絡(luò)I=G(N,L)、多播組mcg；
輸出：虛擬多播組vmcg.
① 根據(jù)式(3)計算該多播組使用的顏色color、樹根所在的頂層網(wǎng)絡(luò)中板tnid；
② 采用算法1找到樹根root，并以root為樹根構(gòu)造多播樹tmpMct;
③ 檢查tmpMct的每條鏈路，將使用該鏈路且顏色為color的所有多播組，連同mcg合并在一起，形成虛擬多播組vmcg；
④ 返回vmcg.
算法2在尋找需要合并哪些多播組時，僅檢查了tmpMct使用的鏈路，而tmpMct的樹根可能是非L3層的交換機(jī).也就是說，算法2僅檢查了所用生成樹的一部分鏈路的使用情況.那么，算法2是否已經(jīng)合并了所有必須合并的多播組，從而保證一定能夠成功為vmcg構(gòu)建出多播樹呢？答案是肯定的，下面我們進(jìn)行證明.
引理1.利用算法1構(gòu)建多播樹時，如果某多播組需要進(jìn)行合并操作，則合并后產(chǎn)生的vmcg對應(yīng)的多播樹，其任意1條鏈路必定出現(xiàn)在某個被合并的多播組所對應(yīng)的多播樹內(nèi).
證畢.
定理2.利用算法1構(gòu)建多播樹時，如果某多播組需要進(jìn)行合并操作，則合并后產(chǎn)生的vmcg對應(yīng)的多播樹，與使用同一生成樹的其他多播組不共用任何鏈路.
證畢.
根據(jù)定理2，為vmcg構(gòu)建多播樹時，不會跟使用同一生成樹的其他多播組沖突，也就是說算法2已經(jīng)合并了所有必須合并的多播組.
由上述論述可知，合并多播組時，僅會在原來多播樹的基礎(chǔ)上添加部分鏈路，因而不會對原多播樹帶來影響.完整的C-MR4LMS路由算法見算法3.
算法3.C-MR4LMS.
輸入：互連網(wǎng)絡(luò)I=G(N,L)、多播組mcg；
輸出：多播樹mct.
① 利用算法1為mcg構(gòu)建多播樹mct；
② 若mct為NULL，則
③ 利用算法2進(jìn)行合并操作，將幾個多播組合并成1個虛擬的多播組vmcg；
④ 再次利用算法1為vmcg創(chuàng)建多播樹mct；
⑤ 更新mct每條鏈路中相應(yīng)顏色的使用情況；
⑥ 更新mct中每個交換機(jī)的多播路由表.
2.5 容錯多播路由
本文采用圖5所示的容錯策略：為每個多播組構(gòu)建多播路由時，選擇2個樹根并構(gòu)建2棵多播樹，兩者互為備份，數(shù)據(jù)包同時通過這2棵多播樹進(jìn)行傳輸.終端節(jié)點收到2份重復(fù)的數(shù)據(jù)包時，僅需丟棄其中1個.當(dāng)其中1棵多播樹因鏈路故障而無法使用時，數(shù)據(jù)包可以通過另一棵多播樹進(jìn)行傳輸，從而做到對用戶透明的容錯.
Fig. 5 Illustration of multicast routing with fault tolerance圖5 容錯多播路由示意圖
當(dāng)開啟容錯功能后，利用式(4)計算多播組使用的顏色及2棵多播樹樹根所在TN編號.該方法實際上是將每種顏色下的m棵生成樹分為2組，從每組分別選擇1棵生成樹使用.因此，系統(tǒng)支持的無沖突生成樹的個數(shù)會減為原來的1/2.
(4)
2.6 另一種選擇樹根的方法
如果多播組內(nèi)各成員的最近公共祖先位于L3層，則頂層網(wǎng)絡(luò)中板tnid內(nèi)每個L3交換機(jī)都可以做樹根.從中選擇哪個做樹根實際上有2種策略：一是算法1所采用的固定選擇第1個交換機(jī)的策略，由此產(chǎn)生的算法稱為C-MR4LMS-fixed；二是將所有L3交換機(jī)都作為備選樹根，從中選擇1個合適的做樹根(優(yōu)先選擇負(fù)載低的)，由此產(chǎn)生的算法稱為C-MR4LMS-dynamic.
這2種變體各有優(yōu)缺點.
1) 某些情況下，C-MR4LMS-dynamic可以通過選擇不同的L3交換機(jī)做樹根，使C-MR4LMS-fixed算法下原本有沖突的2個多播組不再沖突.如圖6所示，灰色陰影所示多播組與斜條紋所示多播組使用同一棵生成樹.C-MR4LMS-fixed算法下這2個多播組共用同一個L3交換機(jī)做樹根，因此在L2?L3鏈路上會產(chǎn)生沖突.而C-MR4LMS-dynamic算法下這2個多播組可以使用不同的L3交換機(jī)做樹根，從而避免產(chǎn)生沖突.
Fig. 6 Example for 2 MCGs using different L3 switches as root圖6 2個多播組使用不同L3交換機(jī)做樹根的例子
2) 需要進(jìn)行合并操作時，C-MR4LMS-dynamic下同一棵生成樹的幾個多播組可能使用不同的L3交換機(jī)做樹根，它們被合并到一起后，樹根會發(fā)生變化，從而導(dǎo)致被合并的多播組其多播路由發(fā)生變化，而C-MR4LMS-fixed不存在該問題.
Fig. 7 Illustration for merge algorithm fails to construct MCTs with C-MR4LMS-dynamic圖7 利用C-MR4LMS-dynamic算法構(gòu)建多播樹后合并算法失效的例子
3) C-MR4LMS-fixed算法下，利用算法2合并多播組時，已經(jīng)合并了所有必須合并的多播組，從而保證一定能夠成功為vmcg構(gòu)建出多播樹.而C-MR4LMS-dynamic算法下，利用算法2合并多播組時，可能會漏掉某些必須合并的多播組，從而導(dǎo)致為vmcg構(gòu)建多播樹失敗.如圖7所示(圖中省略了L0,L1層交換機(jī))，假設(shè)新創(chuàng)建的多播組需要經(jīng)過R2,R4這2個交換機(jī)，且無論選擇R0還是R1做樹根均跟已存在的多播組存在沖突，因此需要利用算法2進(jìn)行合并操作.假設(shè)在合并時，選擇R0做樹根，且需要合并R1?R4,R1?R5間鏈路所示的多播組.在進(jìn)行合并時，僅會檢查R0?R4,R0?R2鏈路；而合并后的vmcg對應(yīng)的多播樹會用R0?R5間鏈路，但該鏈路在檢查需要合并哪些多播組時并未被考慮到，實際上該鏈路可能被另外的多播組使用，因而為vmcg構(gòu)建多播樹會因沖突而失敗.出現(xiàn)該問題的原因是：R1?R4,R1?R5多播組使用了不同的L3交換機(jī)做樹根，導(dǎo)致原本未被vmcg內(nèi)任一多播組使用的鏈路R0?R5出現(xiàn)在了vmcg經(jīng)過的路徑上，從而使得C-MR4LMS-dynamic算法下引理1不再成立.也就是說，C-MR4LMS-dynamic算法下，上述合并算法不能保證合并了所有必須合并的多播組.
基于上述原因，使用C-MR4LMS-dynamic時，為vmcg構(gòu)建多播樹可能失敗，此時需要再進(jìn)行1次合并方可成功.
4) 在多播組個數(shù)較多時，C-MR4LMS-dynamic需要嘗試很多個L3交換機(jī)做樹根，時間開銷較大；而C-MR4LMS-fixed僅會嘗試1個L3交換機(jī)做樹根，時間開銷較小.
具體使用哪種策略，可以根據(jù)實際情況進(jìn)行選擇.一般來說，多播組個數(shù)不多時，可以采用C-MR4LMS-dynamic策略；而多播組個數(shù)很多而需要頻繁合并多播組時，比較適宜采用C-MR4LMS-fixed算法.
3 減少多播樹沖突的2種方法
MGID分配策略及節(jié)點分配策略都會影響C-MR4LMS算法的性能.例如，為某個多播組選擇不同的MGID，就會使用不同的生成樹；將多播組所在的作業(yè)映射到不同節(jié)點上，也會影響多播樹的分配.
本節(jié)將研究如何分配MGID及進(jìn)行節(jié)點映射，以達(dá)到減少多播樹沖突的目的.這些分配策略并不是C-MR4LMS的組成部分，目的是為了更好地發(fā)揮C-MR4LMS的性能.
3.1 分層的MGID分配策略
考慮每個終端節(jié)點可加入多個多播組的情況.1個終端加入多個多播組時，每個多播組需要使用不同的顏色，否則在終端節(jié)點與L0交換機(jī)間的鏈路上就會產(chǎn)生沖突.根據(jù)式(3)，如果不對用戶可用的MGID加以限制，就很容易出現(xiàn)1個終端加入的多個多播組時使用同一種顏色的情況.出現(xiàn)該情況后，需要將沖突的那些多播組合并.此時進(jìn)行的合并跟2.2節(jié)介紹的合并有很大不同.當(dāng)2個多播組因共用同一條交換機(jī)間鏈路而需要合并時，因為他們使用同一棵生成樹，只需在原多播樹的基礎(chǔ)上添加部分鏈路即可，不會影響原多播組的正常使用.而當(dāng)1個終端節(jié)點使用同一種顏色加入多個多播組時，這些多播組可能使用了不同的生成樹，其樹根位于不同TN內(nèi)，合并后多播組的樹根會發(fā)生變化，影響用戶使用.
基于上述原因，當(dāng)1個終端需要加入多個多播組時，我們需要對其使用的MGID加以限制.也就是說，根據(jù)式(3)計算color及tnid時，要么每個多播組都使用不同的顏色，要么2個多播組可以使用同一種顏色，但計算出的tnid必須相同，從而保證這2個多播組可以不用切換TN做樹根即可進(jìn)行合并.
用戶可以采用多種策略保證1個終端節(jié)點使用的多個MGID沒有顏色上的沖突.一種可行的策略是：根據(jù)每個終端可加入的多播組的個數(shù)將顏色劃分為不同的區(qū)間，每個區(qū)間稱為1個層，從而也就將MGID空間劃分成了多個互不重疊的層，稱為MGID層.在每個MGID層內(nèi)，1個終端節(jié)點最多可加入其中的1個多播組；加入多個多播組時，選擇不同的MGID層即可保證他們使用不同的顏色.
每個終端可加入的多播組的個數(shù)一般不會太多，例如，以2維網(wǎng)格方式劃分通信域時，假設(shè)每個終端上僅運(yùn)行1個通信進(jìn)程，則每個終端僅需加入3個多播組，包括1個全局通信域、1個用于行通信的子通信域以及1個用于列通信的子通信域.在此情況下，我們可以將MGID劃分為3個層，使得每個MGID層均使用不同的顏色，為哪個維度的多播組分配多播組，就從該維度對應(yīng)的MGID層中選擇1個MGID使用.
當(dāng)每個終端上可運(yùn)行多個通信進(jìn)程時，情況變得復(fù)雜，因為每個終端節(jié)點在每個維度方向上可能加入多個多播組.此時需要考慮通信域的劃分方式，并將每個通信域映射到合適的MGID層.MPI集合通信中，主要有2種通信域劃分方法[20-21]：一是劃分成2維或3維網(wǎng)格，其每個維度中每行或每列都是1個通信域，對應(yīng)1個多播組；二是劃分成層次結(jié)構(gòu)，例如樹型結(jié)構(gòu)，每層分成很多組，每個組構(gòu)成1個通信域，每個組再選出1個leader，形成更高層次的組.以層次結(jié)構(gòu)劃分通信域時，將通信域映射到MGID層的方法比較簡單，只需為每個通信域?qū)又付?個MGID層.
下面考慮3維網(wǎng)格劃分方式下將通信域映射到MGID層的方法，2維網(wǎng)格方式與此類似，不再贅述.如圖8所示，假設(shè)每個終端節(jié)點上有P個通信進(jìn)程，且它們在3維環(huán)網(wǎng)中的位置是連續(xù)的.例如，設(shè)3維環(huán)網(wǎng)x,y,z維長度分別為X,Y,Z，某終端節(jié)點上首進(jìn)程的坐標(biāo)為(a,b,c)，則該終端節(jié)點上第n個進(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é)點上不同進(jìn)程位置示意圖
給定坐標(biāo)為(a,b,c)的進(jìn)程，我們根據(jù)式(5)分別計算該進(jìn)程加入3個軸方向上的多播組時使用的MGID層號，其中l(wèi)ayerx,layery,layerz分別對應(yīng)x,y,z軸方向上的多播組.
(5)
定理3.以3維環(huán)網(wǎng)方式劃分通信域時，若每個終端節(jié)點上有P個通信進(jìn)程(P小于3維環(huán)網(wǎng)任一維的長度)，且這些進(jìn)程在3維環(huán)網(wǎng)中位置連續(xù)，則利用式(5)將每個進(jìn)程的3個多播組放入某個MGID層時，對任一終端節(jié)點而言，每個多播組均位于不同的MGID層內(nèi).
證明.首先，很容易看出，不同方向上的多播組位于不同的MGID層內(nèi).其次，我們證明，同一終端節(jié)點上同一方向上的多播組也位于不同的MGID層內(nèi).我們先列出同一終端節(jié)點上各個進(jìn)程的位置分布情況，包括：
1)P個進(jìn)程位于與x軸平行的同一條線上(如灰色陰影進(jìn)程所示)；
2)P個進(jìn)程不在同一條直線上，但位于與xoy平面平行的同一平面內(nèi)(如斜紋填充進(jìn)程所示)；
3)P個進(jìn)程不在同一平面內(nèi)(如橫紋填充進(jìn)程所示).
先看x軸方向上的多播組.情況1)中，P個進(jìn)程屬于同一個多播組.情況2)中，P個進(jìn)程屬于多個多播組，但它們具有相同的z坐標(biāo)，以及連續(xù)的y坐標(biāo)，因此根據(jù)式(5)得到的MGID層號必不相等.情況3)中，P個進(jìn)程屬于多個多播組；若2個多播組具有相同的z坐標(biāo)，則與情況2)一樣，根據(jù)式(5)得到的MGID層號必不相等；若2個多播組具有不同的z坐標(biāo)，則其中1個多播組的y坐標(biāo)必小于P-1，另一個多播組的y坐標(biāo)必大于等于P-1，根據(jù)式(5)得到的MGID層號也不相等.因此，上述3種情況下，根據(jù)式(5)得到的MGID層號都互不相等.
同理，y,z軸方向上的多播組根據(jù)式(5)得到的MGID層號也互不相等.
證畢.
利用式(5)，可以將3維環(huán)網(wǎng)中的多播組映射到不同的MGID層內(nèi)，保證每個終端節(jié)點在每個MGID層內(nèi)最多加入1個多播組，從而保證該終端節(jié)點加入多個多播組時，每個多播組都使用不同的顏色，也就避免在終端節(jié)點與L0交換機(jī)間的鏈路上產(chǎn)生沖突.每層內(nèi)的顏色數(shù)可以根據(jù)該層內(nèi)的多播組個數(shù)進(jìn)行分配.
3.2 相互無干擾的作業(yè)節(jié)點分配策略
根據(jù)定理1及2個推論，當(dāng)系統(tǒng)中多播組的個數(shù)少于C×m時，無需合并多播組即可完成多播樹的創(chuàng)建；而當(dāng)多播組的個數(shù)多于C×m時，很可能出現(xiàn)2個多播組使用同一棵生成樹的同一條鏈路的情況，從而導(dǎo)致沖突，此時需要將這2個多播組合并在一起.多播組合并會導(dǎo)致1個多播組發(fā)送的數(shù)據(jù)拷貝到另一個多播組內(nèi)，從而使得鏈路EFI指數(shù)變大，影響集合操作的性能.因此需要盡量避免這種情況的出現(xiàn).
通過優(yōu)化節(jié)點分配來減少作業(yè)間的相互干擾是提升應(yīng)用性能的重要手段[22-23].本文提出了一種作業(yè)分配策略，使不同作業(yè)使用的網(wǎng)絡(luò)資源彼此隔離，從而使得不同作業(yè)可以共用同一棵生成樹而沒有任何沖突.這樣每個作業(yè)都至少可以創(chuàng)建C×m個不沖突的多播組，從而使得系統(tǒng)中支持的多播組總數(shù)遠(yuǎn)遠(yuǎn)大于C×m.
首先根據(jù)作業(yè)使用的終端個數(shù)將作業(yè)分為下列類型：
1) T0作業(yè)，其終端個數(shù)小于等于m；
2) T1作業(yè)，其終端個數(shù)小于等于m2；
3) T2作業(yè)，其終端個數(shù)小于等于w×m2；
4) T3作業(yè)，其終端個數(shù)大于w×m2.
為作業(yè)分配終端節(jié)點時，必須遵循下列規(guī)則：
1) 1個節(jié)點僅能分配給1個作業(yè)使用；
2) T0作業(yè)使用的節(jié)點均位于同一L0交換機(jī)內(nèi)；
3) T1作業(yè)使用的節(jié)點均位于同一CN內(nèi)；
4) T2作業(yè)使用的節(jié)點，其計算網(wǎng)絡(luò)中板號cnid/w應(yīng)等于同一個值；
5) L0交換機(jī)可被多個T0作業(yè)共享，但最多只能被1個T1及以上規(guī)模的作業(yè)使用；
6) 1個計算網(wǎng)絡(luò)中板可以被多個T1作業(yè)共享，但最多只能被1個T2及以上規(guī)模的作業(yè)使用；
7) 編號為i×w,i×w+1,…,(i+1)×w-1的w個中板可以被多個T2作業(yè)共享，但最多只能被1個T3作業(yè)使用.
定理4.按規(guī)則1)～7)為作業(yè)分配節(jié)點時，任何2個作業(yè)不共用同一條鏈路.
證明. 首先考慮L0層交換機(jī).根據(jù)規(guī)則1)，L0交換機(jī)的下行鏈路只能被1個作業(yè)使用.根據(jù)規(guī)則2)，T0作業(yè)不會使用L0交換機(jī)的上行鏈路；而根據(jù)規(guī)則5)，L0交換機(jī)最多被1個T1及以上規(guī)模的作業(yè)使用，因此L0交換機(jī)的上行鏈路最多被1個作業(yè)使用.
再考慮L1層交換機(jī).同樣根據(jù)規(guī)則5)，其每條下行鏈路最多被1個作業(yè)使用；根據(jù)規(guī)則3)，T1作業(yè)不會使用L1交換機(jī)的上行鏈路；而根據(jù)規(guī)則6)，L1交換機(jī)最多被1個T2及以上規(guī)模的作業(yè)使用，因此L1交換機(jī)的上行鏈路最多被1個作業(yè)使用.
再考慮L2層交換機(jī).同樣根據(jù)規(guī)則6)，其每條下行鏈路最多被1個作業(yè)使用；根據(jù)規(guī)則4)，T2作業(yè)不會使用L2交換機(jī)的上行鏈路；而根據(jù)規(guī)則7)，L2交換機(jī)最多被1個T3作業(yè)使用，因此L2交換機(jī)的上行鏈路最多被1個作業(yè)使用.
最后考慮L3層交換機(jī).同樣根據(jù)規(guī)則7)，其每條下行鏈路最多被1個作業(yè)使用.
證畢.
由此可知，按規(guī)則1)～7)為作業(yè)分配節(jié)點時，來自不同作業(yè)的2個多播組使用同一棵生成樹創(chuàng)建多播樹時，不會產(chǎn)生沖突.因此，只要每個作業(yè)使用的多播組個數(shù)不超過C×m，就可以保證系統(tǒng)中所有的多播組不用合并就可成功創(chuàng)建多播樹.
4 ibsim下的性能評估
我們在OpenSM 3.3.22[24]中實現(xiàn)了C-MR4LMS，共有約2 000行代碼.對OpenSM源碼進(jìn)行了修改，使得每個交換機(jī)端口都有一份單獨的路由表.另外，還對加入、離開多播組的機(jī)制進(jìn)行了簡單的修改，以解決頻繁重算路由的問題.
4.1 實驗環(huán)境
本文使用ibsim-0.7[24]模擬了圖2所示的一棵4層胖樹，參數(shù)如下：交換機(jī)端口數(shù)為40，m=w=16，q=k=32，p=6.理論上，該網(wǎng)絡(luò)最大支持512個CN，96個TN，262 144個終端節(jié)點.但由于OpenSM及ibsim最多支持49 152個節(jié)點(包括交換機(jī)及終端)，因此僅使用了64個CN、96個TN；網(wǎng)絡(luò)中節(jié)點總數(shù)為40 448，其中交換機(jī)個數(shù)為7 680，終端節(jié)點數(shù)為32 768.
本文使用測試程序模擬發(fā)起加入或離開多播組的請求.OpenSM運(yùn)行在一臺48核Intel Xeon Silver 4214服務(wù)器上，頻率為2.20 GHz.需要指出的是，在ibsim下的測試結(jié)果跟在真實網(wǎng)絡(luò)環(huán)境下的測試結(jié)果是一樣的，因為EFI及運(yùn)行時間等性能數(shù)據(jù)跟是否使用ibsim模擬拓?fù)浣Y(jié)構(gòu)無關(guān).
MPI中將進(jìn)程劃分為子通信域時，可以采用層次結(jié)構(gòu)進(jìn)行劃分，也可以采用2維或3維網(wǎng)格方式進(jìn)行劃分.采用2維或3維網(wǎng)格方式劃分通信域時，會產(chǎn)生大量多播組，對多播表條目數(shù)的需求量更大.后面實驗中，采用2維及3維網(wǎng)格劃分進(jìn)程，以測試存在大量多播組時多播路由算法的性能.除此之外，還測試了進(jìn)程隨機(jī)加入某個多播組的通信模式.另外，既測試了每個終端運(yùn)行1個通信進(jìn)程的情況，也測試了每個終端運(yùn)行多個通信進(jìn)程的情況.
后面將要測試的2維或3維網(wǎng)格模式中，有些是按拓?fù)浣Y(jié)構(gòu)進(jìn)行劃分的，模擬拓?fù)涓兄耐ㄐ拍Ｊ剑挥行﹦澐殖烧叫位蛄⒎襟w形狀，模擬拓?fù)錈o感的通信模式.以每個終端節(jié)點上運(yùn)行1個通信進(jìn)程為例， 512×64通信模式下，第1維有64個多播組，每個組都位于同一個CN內(nèi)，因此通信模式與拓?fù)浣Y(jié)構(gòu)匹配；而181×181通信模式下，存在很多跨計算中板的多播組，因此通信模式與拓?fù)浣Y(jié)構(gòu)不匹配.
神威互連網(wǎng)絡(luò)中每個交換機(jī)端口最多支持32個多播表條目，因此后面測試中，將最大顏色數(shù)設(shè)為32，不沖突的生成樹的個數(shù)為512.設(shè)為其他值時，測試結(jié)果會有差異，但測試結(jié)論與顏色數(shù)為32時基本一致，因此不再贅述其測試數(shù)據(jù).另外，為了與MR4LMS對比，關(guān)閉了C-MR4LMS的容錯功能.
本文測試了原始MR4LMS算法及本文提出的2種多播路由算法(C-MR4LMS-fixed，C-MR4LMS-dynamic)在各種通信模式下的性能，其中每個終端節(jié)點上運(yùn)行1個通信進(jìn)程時的測試結(jié)果如圖9所示，每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時的測試結(jié)果如圖10所示.
Fig. 9 The performance of three algorithms with only one communication process on each terminal node圖9 每個終端節(jié)點上僅有1個通信進(jìn)程時3種算法的性能
Fig. 10 The performance of three algorithms with 4 communication process on each terminal node圖10 每個終端節(jié)點上4個通信進(jìn)程時3種算法的性能
4.2 不同通信模式下的鏈路EFI
最大EFI及平均EFI反映了各鏈路上多播樹的數(shù)量，一定程度上代表了多播路由算法的均衡程度.
4.2.1 每個終端上僅1個通信進(jìn)程
先分析每個終端節(jié)點上運(yùn)行1個通信進(jìn)程時的情況，結(jié)果如圖9(a)(b)所示.
1) 2維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的最大EFI及平均EFI均低于MR4LMS算法.出現(xiàn)該現(xiàn)象的原因是：MR4LMS算法在選擇樹根時根據(jù)負(fù)載情況從很多備選樹根中選擇1個；而在胖樹結(jié)構(gòu)中，所有的L3交換機(jī)均可作為備選樹根，因此會被輪流作為樹根使用.而2維環(huán)網(wǎng)下多播組的個數(shù)較少，因此MR4LMS僅用到了那些位置靠前的L3交換機(jī)，而那些位置靠后的L3交換機(jī)未被使用.這就導(dǎo)致MR4LMS算法僅使用了部分頂層網(wǎng)絡(luò)中板，進(jìn)而導(dǎo)致連接L1交換機(jī)與L2交換機(jī)的那些鏈路上EFI指數(shù)偏大.而C-MR4LMS算法會輪流使用不同頂層網(wǎng)絡(luò)中板做樹根，因此可以將多播組分散到不同頂層網(wǎng)絡(luò)中板內(nèi).隨著多播組個數(shù)的增多，C-MR4LMS算法會重用頂層網(wǎng)絡(luò)中板，此時C-MR4LMS的優(yōu)勢將會消失.另外，由于創(chuàng)建的多播組不多，2種C-MR4LMS算法的EFI差別不大，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
2) 3維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的表現(xiàn)有時比MR4LMS好，有時比MR4LMS差，這是因為隨著多播組個數(shù)的增大，MR4LMS算法會使用全部的頂層網(wǎng)絡(luò)中板，故3種算法均會將多播組分散到不同頂層網(wǎng)絡(luò)中板內(nèi)；而MR4LMS算法會根據(jù)負(fù)載情況選擇不同的交換機(jī)做樹根，因此大部分情況下MR4LMS算法具有更好的負(fù)載均衡性.2種C-MR4LMS算法比較，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
3) 進(jìn)程隨機(jī)加入某個多播組的模式下，MR4LMS算法明顯優(yōu)于2種C-MR4LMS算法.原因如下：C-MR4LMS算法下，多播組的個數(shù)已經(jīng)超過了不沖突的生成樹的個數(shù)，因而需要合并多播組，導(dǎo)致EFI偏大，而MR4LMS算法由于可以嘗試不同的交換機(jī)做樹根，不需要合并多播組，因而EFI指數(shù)小.后面將會看到，隨著多播組個數(shù)的進(jìn)一步增大，MR4LMS算法也會產(chǎn)生合并，此時其EFI指數(shù)也會明顯增加.需要指出的是，雖然2種C-MR4LMS算法的EFI明顯高于MR4LMS，但最大EFI為69，尚在可接受的范圍內(nèi).
4.2.2 每個終端上4個通信進(jìn)程
再分析每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時的情況，結(jié)果如圖10(a)(b)所示.
1) 2維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的最大EFI及平均EFI略高于MR4LMS算法.這與每個終端上僅1個通信進(jìn)程時3維環(huán)網(wǎng)通信模式下的情況類似，原因是進(jìn)程數(shù)增多后，多播組的個數(shù)也隨之增大，因而MR4LMS算法會使用全部的頂層網(wǎng)絡(luò)中板，故其表現(xiàn)優(yōu)于2種C-MR4LMS算法.
2) 3維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的表現(xiàn)有時比MR4LMS好，有時比MR4LMS差.MR4LMS比2種C-MR4LMS算法差的原因是：隨著多播組個數(shù)的增大，3種算法需要進(jìn)行合并，但2種C-MR4LMS算法僅會合并使用同一生成樹的多播組，合并的多播組較少；而MR4LMS算法在選擇樹根時是根據(jù)負(fù)載情況動態(tài)選擇的，因此大量多播樹交錯在一起，合并時極端情況下可能需要合并很多個多播組.
3) 進(jìn)程隨機(jī)加入某個多播組的模式下，2種C-MR4LMS算法的表現(xiàn)優(yōu)于MR4LMS，原因與2)一樣.
4.2.3 結(jié)論
綜合上面分析，在EFI方面，有4點結(jié)論：
1) 當(dāng)多播組個數(shù)少于不沖突的生成樹個數(shù)時，2種C-MR4LMS算法一般情況下略優(yōu)于MR4LMS.
2) 當(dāng)多播組個數(shù)增大時，2種C-MR4LMS算法需要合并多播組，而MR4LMS算法不需要進(jìn)行合并操作，此時MR4LMS算法一般優(yōu)于2種C-MR4LMS算法.
3) 隨著多播組個數(shù)的繼續(xù)增大，從而使得3種算法都需要合并多播組時，2種C-MR4LMS算法一般情況下又會優(yōu)于MR4LMS算法.
4) 2種C-MR4LMS算法比較，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed；但大部分情況下，C-MR4LMS-fixed接近于C-MR4LMS-dynamic.
概括而言，依據(jù)圖9(a)、圖10(a)，當(dāng)多播組個數(shù)較少時，C-MR4LMS算法的最大EFI略高于MR4LMS算法，最多增大88；而當(dāng)多播組個數(shù)較多時，C-MR4LMS算法的最大EFI明顯低于MR4LMS算法，最多減少594.
4.3 不同通信模式下的TFI
多播樹的TFI表示有多少個多播組使用該多播樹.最大TFI及平均TFI反映了多播組的合并程度.
4.3.1 每個終端上僅1個通信進(jìn)程
先分析每個終端節(jié)點上運(yùn)行1個通信進(jìn)程時的情況，結(jié)果如圖9(c)～(e)所示.
1) MR4LMS算法下，所有通信模式下均未發(fā)生合并，因此TFI均為1.
2) 2種C-MR4LMS算法下，當(dāng)多播組個數(shù)小于生成樹個數(shù)時(如181×181,100×327)，因不需要合并，TFI均為1.隨著多播組個數(shù)的增多，需要合并多播組，TFI大于1.有幾個有趣的現(xiàn)象需要注意：
① 64×32×16以及32×32×32這2種通信模式下，C-MR4LMS-fixed的最大TFI分別為7和6；而C-MR4LMS-dynamic的最大TFI均為1，這表明通過選擇同一TN內(nèi)的不同L3交換機(jī)做樹根可以避免一些不必要的合并操作.
② 25×50×26以及3種隨機(jī)加入多播組的通信模式下，2種C-MR4LMS算法的最大TFI均大于1且相等，但從平均TFI方面看C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
③ 2種C-MR4LMS算法下，多播組發(fā)生合并后，剩余多播組的個數(shù)均不少于512(即系統(tǒng)中互不沖突的生成樹個數(shù)).
④ 隨機(jī)加入多播組的3種模式下，平均TFI接近于最大TFI，表明多播樹合并比較均勻.而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 每個終端上4個通信進(jìn)程
分析每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時的情況，結(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.這是因為每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時，這幾種2維環(huán)網(wǎng)通信模式中的多播組個數(shù)均超過了512，因而需要共用同一棵生成樹，導(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算法在選擇樹根時是根據(jù)負(fù)載動態(tài)選擇的，因此大量多播樹交錯在一起，合并時極端情況下可能需要合并很多個多播組.以100×50×26通信模式為例，MR4LMS算法的最大TFI為168，而平均TFI僅為1.1，這表明大部分的多播組未被合并，而有168個多播組被合并到了一起.這也說明MR4LMS算法在需要合并多播組時，TFI波動較大.反觀2種C-MR4LMS算法，其最大TFI與平均TFI相比差別沒有這么明顯，特別是3種隨機(jī)加入多播組的模式下，平均TFI幾乎等于最大TFI，這是因為2種C-MR4LMS算法輪流使用不同的生成樹.
3) 從合并后剩余的多播組個數(shù)上看，某些通信模式下MR4LMS算法僅剩下少量多播組，例如1 000個隨機(jī)多播組模式下僅剩下32個多播組，這進(jìn)一步表明MR4LMS算法極端情況下會合并大量多播組.而2種C-MR4LMS算法下，剩余多播組的個數(shù)均不少于512，這是因為2種C-MR4LMS算法在合并時僅合并那些使用同一生成樹的多播組.
4.3.3 結(jié)論
綜合上面分析，在TFI方面，有下列結(jié)論：
1) 當(dāng)多播組個數(shù)較少時，MR4LMS 算法不需要合并多播組，其TFI為1，而2種C-MR4LMS算法的TFI可能大于1.
2) 隨著多播組個數(shù)的繼續(xù)增大，3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)都需要合并多播組時，2種C-MR4LMS算法一般情況下會優(yōu)于MR4LMS算法，且剩余多播組的個數(shù)均不少于512;而MR4LMS算法在極端情況下會剩余很少的多播組.
3) 2種C-MR4LMS算法比較，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
概括而言，依據(jù)圖9(c)、圖10(c)，當(dāng)多播組個數(shù)較少時，C-MR4LMS算法的最大TFI略高于MR4LMS算法，最多增大25；而當(dāng)多播組個數(shù)較多時，C-MR4LMS算法的最大TFI明顯低于MR4LMS算法，最多減少148.
4.4 不同通信模式下的算法運(yùn)行時間
圖9(f)、圖10(f)分別顯示了每個終端節(jié)點上運(yùn)行不同數(shù)量的通信進(jìn)程時3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)的運(yùn)行時間.該時間僅包括計算路由的時間(選擇樹根、構(gòu)建多播樹、為多播樹染色等步驟的時間)，不包括發(fā)送加入多播組請求、分發(fā)路由等其他步驟的時間.
可以發(fā)現(xiàn)，2種C-MR4LMS算法的運(yùn)行時間明顯低于MR4LMS算法，最多下降94%.當(dāng)創(chuàng)建大量多播組而需要進(jìn)行合并的時候，兩者間的差異更加明顯.例如，圖10(f)所示100×50×26通信模式下，MR4LMS算法運(yùn)行時間超過575 s，而2種C-MR4LMS算法運(yùn)行時間均低于35 s，顯示出2種C-MR4LMS算法在減少運(yùn)行時間方面的巨大優(yōu)勢.MR4LMS算法需要嘗試大量的樹根及顏色，故其運(yùn)行時間較長，且受多播組大小、網(wǎng)絡(luò)中顏色使用情況等因素的影響；而2種C-MR4LMS算法直接根據(jù)MGID確定樹根及顏色，故其運(yùn)行時間固定，且時間較少.
另外，C-MR4LMS-dynamic運(yùn)行時間一般略高于C-MR4LMS-fixed，這是因為C-MR4LMS-dynamic需要嘗試同一TN內(nèi)的不同T3交換機(jī)做樹根.
5 基準(zhǔn)測試程序性能
本文在神威E級原型機(jī)上對C-MR4LMS算法的集合消息性能進(jìn)行了測試.神威E級原型機(jī)采用神威互連網(wǎng)絡(luò)，以硬件方式支持同步、規(guī)約、廣播等集合消息類型，相比點對點消息實現(xiàn)的集合操作具有更低的延時，其拓?fù)浣Y(jié)構(gòu)為4層胖樹.使用了600個終端節(jié)點進(jìn)行測試，這些終端節(jié)點分布在4個CN內(nèi)，每個節(jié)點上運(yùn)行6個通信進(jìn)程.共測試了4種集合通信類型，包括MPI_Barrier、8 B粒度的MPI_Allreduce、8 B及2 KB粒度的MPI_Bcast.通信模式如下：將所有進(jìn)程劃分為2維網(wǎng)格，為每行及每列均創(chuàng)建1個通信域；每個進(jìn)程先與同一行的所有進(jìn)程進(jìn)行1次集合通信，再與同一列的所有進(jìn)程進(jìn)行1次集合通信；所有進(jìn)程同時進(jìn)行通信，因此同一時刻有大量多播組在通信；共進(jìn)行5 000遍測試，由0號進(jìn)程記錄每遍測試中2次集合通信的總時間，2遍測試間不加同步；對每種進(jìn)程劃分方式、每種集合通信類型，本文均測試了4種路由算法的性能，包括全局廣播鏈、MR4LMS、C-MR4LMS-fixed及MR4LMS-dynamic.
5.1 關(guān)閉容錯時的集合消息性能
首先，測試關(guān)閉容錯時的性能.表1顯示了不同路由算法下的集合消息延遲中位值.另外，圖11以小提琴圖的形式顯示了60×60通信模式下的集合消息延遲分布和概率密度.小提琴圖的兩側(cè)反映了密度信息，越寬表示出現(xiàn)在該區(qū)間的測試數(shù)據(jù)越多.小提琴圖的中間部分以箱線圖方式顯示了延遲的中位數(shù)及上下四分位數(shù)，其中上四分位數(shù)記為Q3，下四分位數(shù)記為Q1，Q3與Q1之間的差值稱為四分位數(shù)差(interquartile range, IQR)，記為IQR.大于Q3+1.5×IQR或者小于Q1-1.5×IQR的值為異常值.IQR越小，表示數(shù)據(jù)越密集，波動性越小.為便于顯示，圖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%.另外，全局廣播鏈下，對同一種集合操作來說，不同通信模式下其延遲差異較大，這是因為不同通信模式下的多播組個數(shù)不同，而每個多播組都使用同一棵多播樹，導(dǎo)致不同通信模式下的鏈路EFI差異較大，測出的延遲差異也較大.相比而言，MR4LMS及2種C-MR4LMS-算法在不同通信模式下的延遲差異沒有這么明顯，這是因為這幾種算法可以將多播組分布到不同鏈路上.
2) 2種C-MR4LMS-算法的消息延遲與MR4LMS算法基本相當(dāng)，2 KB粒度的MPI_Bcast延遲甚至明顯低于MR4LMS.這與ibsim中的測試結(jié)果一致，即當(dāng)多播組個數(shù)較少時，C-MR4LMS算法的鏈路EFI低于MR4LMS算法，而2 KB粒度的集合消息對EFI較敏感.
3) C-MR4LMS-fixed與MR4LMS-dynamic算法的消息延遲差異不大，可以認(rèn)為是測試誤差及網(wǎng)絡(luò)噪音導(dǎo)致了這些差異.
4) 從圖11可以看出，4種路由算法在延遲數(shù)據(jù)的穩(wěn)定性方面差異不大.
本文也測試了3維環(huán)網(wǎng)及隨機(jī)加入多播組的情況，測試結(jié)果與表1及圖11類似，不再贅述.
綜上所述，當(dāng)大量多播組同時通信時，2種C-MR4LMS算法下集合消息的延遲明顯低于全局廣播鏈，而與MR4LMS算法相當(dāng).
5.2 開啟容錯時的集合消息性能
首先測試容錯功能的有效性.通過手工斷開某條鏈路制造故障，然后運(yùn)行上述基準(zhǔn)測試程序，發(fā)現(xiàn)全局廣播鏈、MR4LMS均存在收不到消息的情況，而2種C-MR4LMS算法下測試課題均能正常運(yùn)行.這表明開啟容錯功能后可以對網(wǎng)絡(luò)故障進(jìn)行透明容錯.
由于開啟容錯功能后，原來的1個多播數(shù)據(jù)包會被復(fù)制2份，可能會影響消息延遲.下面以C-MR4LMS-fixed為例分別測試關(guān)閉及打開容錯功能時的消息延遲，觀察容錯功能對消息性能的影響.圖12顯示了60×60通信模式下的測試結(jié)果.其中C-MR4LMS-fixed表示關(guān)閉容錯，C-MR4LMS-fixed-ft表示開啟容錯.可以發(fā)現(xiàn)：1)從延遲中位值的角度看，開啟容錯功能后MPI_Barrier,MPI_Allreduce的延遲略有下降，而MPI_Bcast的延遲略有上升.2)從分布范圍看，開啟容錯后延遲波動范圍略有降低，可以認(rèn)為有更低的尾延遲.
Fig. 12 Collective message latencies under C-MR4LMS-fixed with and without fault tolerance圖12 開啟及關(guān)閉容錯功能C-MR4LMS-fixed算法下的集合消息延遲
上述測試結(jié)果表明，多復(fù)制一份數(shù)據(jù)包并不會對消息延遲帶來顯著影響，反而會緩解因多個多播組相互干擾而帶來的性能波動.出現(xiàn)該現(xiàn)象的原因是：終端節(jié)點收到第1個數(shù)據(jù)包后就可做后續(xù)處理，因而可以忽略延后到達(dá)的多播包，一定程度上抵消網(wǎng)絡(luò)噪音對多播消息帶來的影響.
6 結(jié) 論
本文針對胖樹拓?fù)涮岢鲆环N高效實用的定制多播路由算法C-MR4LMS，在硬件僅支持很小的多播表時，能夠快速地為數(shù)千甚至數(shù)萬個多播組構(gòu)建多播路由.C-MR4LMS在構(gòu)建多播樹時，根據(jù)多播組的MGID靜態(tài)地將多播組映射到1棵生成樹中，這帶來了下列好處：1)可以快速選擇出樹根及顏色，從而快速完成多播樹的構(gòu)建；2)構(gòu)建出的多播樹是恒定不變的，重算多播路由不會改變多播樹；3)合并多播樹時，僅需合并使用同一生成樹的多播組，且僅需添加某些鏈路即可完成多播樹的合并，不會改變被合并的多播組的路由.而MR4LMS算法根據(jù)各多播鏈號的使用情況，動態(tài)創(chuàng)建多播樹，因而多播路由具有動態(tài)可變性，即在不同時刻、不同網(wǎng)絡(luò)狀態(tài)下為同一多播組構(gòu)建的多播樹可能不同.
實驗結(jié)果表明，當(dāng)多播組個數(shù)少于不沖突的生成樹個數(shù)時，C-MR4LMS算法在EFI,TFI方面與MR4LMS算法相當(dāng)，某些情況下甚至略優(yōu)于MR4LMS算法.隨著多播組個數(shù)的增多，C-MR4LMS算法需要進(jìn)行合并操作，而MR4LMS算法由于可以嘗試不同的樹根及顏色，不需要進(jìn)行大量合并操作，在EFI,TFI方面優(yōu)于C-MR4LMS算法.隨著多播組個數(shù)的進(jìn)一步增多，MR4LMS算法也需要進(jìn)行很多合并操作，此時C-MR4LMS算法大部分情況下又會優(yōu)于MR4LMS算法.可以認(rèn)為，很多情況下，C-MR4LMS算法在EFI,TFI方面優(yōu)于MR4LMS算法；而部分情況下，C-MR4LMS算法在EFI,TFI方面比MR4LMS算法差，但仍在可接受的范圍內(nèi).基準(zhǔn)測試程序也表明，在各種通信模式下，C-MR4LMS算法下的集合消息性能不比MR4LMS算法差，很多情況下還優(yōu)于MR4LMS算法；而在運(yùn)行時間方面，C-MR4LMS算法具有明顯的優(yōu)勢.
綜上所述，在胖樹中C-MR4LMS算法的性能可以匹敵MR4LMS算法，而其運(yùn)行時間相比MR4LMS算法有了顯著下降，能夠更好地滿足大規(guī)模并行應(yīng)用的需求.
另外，C-MR4LMS算法還有需要完善的地方：1)C-MR4LMS采用由用戶指定MGID的策略，因此需要用戶巧妙地選取MGID，這對用戶提出了很高的要求.未來，我們將提供工具幫助用戶完成該工作.2)目前C-MR4LMS面向拓?fù)湟阎呐謽洌绊懥似溥m用性.未來我們將做下列改進(jìn)：①自動感知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，動態(tài)調(diào)整相關(guān)的網(wǎng)絡(luò)參數(shù)；②識別故障鏈路，并將使用該鏈路的生成樹標(biāo)記為不可用，從而在構(gòu)建多播路由時避開這些故障鏈路.但這會導(dǎo)致C-MR4LMS遇到與MR4LMS一樣的難題：多播路由受網(wǎng)絡(luò)狀態(tài)的影響，具有動態(tài)多變性，需要在多播路由的穩(wěn)定性與適用性這兩者間進(jìn)行適當(dāng)?shù)钠胶?
作者貢獻(xiàn)聲明：陳淑平提出研究思路，設(shè)計并實現(xiàn)算法，進(jìn)行試驗并對實驗數(shù)據(jù)進(jìn)行分析，撰寫并修改論文；李祎參與算法實現(xiàn)、實驗驗證和數(shù)據(jù)分析；何王全參與實驗數(shù)據(jù)分析，論文審閱與修訂；漆鋒濱對課題進(jìn)行監(jiān)管與指導(dǎo)，并審閱與修訂論文.
猜你喜歡
世界上最深的樹根小學(xué)科學(xué)(學(xué)生版)(2021年10期)2021-12-28 怎樣數(shù)出小正方體的個數(shù)小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2021年9期)2021-10-14 巧奪天工少兒畫王（7-10）(2020年11期)2020-09-13 等腰三角形個數(shù)探索 怎樣數(shù)出小木塊的個數(shù)小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2019年9期)2019-09-25 更換匯聚交換機(jī)遇到的問題網(wǎng)絡(luò)安全和信息化(2019年7期)2019-07-10 基于地鐵交換機(jī)電源設(shè)計思考電子制作(2019年24期)2019-02-23 怎樣數(shù)出小正方體的個數(shù)小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2018年9期)2018-09-26 樹干和樹根小溪流（畫刊）(2018年3期)2018-06-29 締造工業(yè)級的強(qiáng)悍——評測三旺通信IPS7110-2GC-8PoE工業(yè)交換機(jī)中國公共安全(2017年11期)2017-02-06
陳淑平 李 祎 何王全 漆鋒濱
(江南計算技術(shù)研究所 江蘇無錫 214083)(chenshuping_hit@163.com)
在高性能計算領(lǐng)域，多播路由算法對硬件支持的集合操作性能具有至關(guān)重要的影響.例如，集合通信中的Bcast,Barrier,AllReduce,AllGather等操作均可通過多播進(jìn)行加速.多播路由算法通過構(gòu)建多播樹實現(xiàn).過去主要研究如何降低樹高、如何提升路由負(fù)載均衡程度.目前高性能計算已經(jīng)邁入E級計算時代，系統(tǒng)中多播組的個數(shù)急劇增加，可能會超過硬件支持的多播表條目數(shù)，而現(xiàn)有的多播路由算法要么沒有給出解決方案，要么存在時間開銷大、多播路由經(jīng)常變化等問題.為此，本文提出一種用于胖樹的高效實用的定制多播路由算法(customized multicast routing for limited multicast forwarding table size, C-MR4LMS)，可用于包括Infiniband在內(nèi)的高速互連網(wǎng)絡(luò).本文主要貢獻(xiàn)包括：
1) 對胖樹結(jié)構(gòu)中可使用的無沖突多播生成樹個數(shù)進(jìn)行了量化研究，根據(jù)系統(tǒng)中的最大多播組個數(shù)確定多播表的大小，為設(shè)計互連網(wǎng)絡(luò)系統(tǒng)提供了理論依據(jù).
2) 提出了一種用于胖樹拓?fù)涞母咝嵱玫亩ㄖ贫嗖ヂ酚伤惴–-MR4LMS，可根據(jù)MGID(multicast global identification)靜態(tài)地將多播組映射到1棵生成樹中，快速完成多播樹的構(gòu)建；當(dāng)需要合并多播組時，僅需合并那些使用同一生成樹的多播組，且僅需添加部分鏈路即可完成多播組的合并，不會改變被合并多播組的路由，因此不會影響這些多播組的正常使用.
3) 提出了分層的MGID分配策略，當(dāng)同一終端節(jié)點同時加入多個多播組時，每個多播組都使用不同層內(nèi)的MGID，避免出現(xiàn)同一終端節(jié)點使用同一顏色加入多個多播組的情況.
4) 提出了相互無干擾的作業(yè)節(jié)點分配策略，使得2個作業(yè)不共用任何通信鏈路，保證2個作業(yè)的多播組互不干擾.
5) 在多種典型拓?fù)浣Y(jié)構(gòu)及典型通信模式下對C-MR4LMS的鏈路EFI、TFI、運(yùn)行時間及應(yīng)用程序性能等進(jìn)行了測試，驗證了其有效性.
1 研究背景及相關(guān)工作
集合通信[1-4]為實現(xiàn)一組進(jìn)程間的通信提供了非常方便的抽象，被廣泛應(yīng)用于高性能計算領(lǐng)域.它包括同步、廣播、規(guī)約、全規(guī)約、分散、收集、全收集等類型及其變體，可實現(xiàn)多個進(jìn)程間的同步、數(shù)據(jù)分發(fā)與收集等功能.傳統(tǒng)的集合通信一般是由軟件利用點到點消息實現(xiàn)的.但隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，超級計算機(jī)對集合通信的性能及可擴(kuò)展性都提出了更高的要求，而軟件集合通信難以滿足E級系統(tǒng)的需求.硬件集合通信可將集合操作卸載到網(wǎng)絡(luò)設(shè)備中進(jìn)行，具有良好的性能及可擴(kuò)展性，已成為高速互連網(wǎng)絡(luò)領(lǐng)域的研究熱點.近幾年出現(xiàn)了很多硬件集合通信技術(shù)，如Mellanox的SHARP技術(shù)[5]，神威互連網(wǎng)絡(luò)的硬件集合通信等[6].
硬件支持的集合操作中，多播技術(shù)是重要的支撐.集合通信中的Bcast,Barrier,AllReduce,AllGather等操作需要將相同的數(shù)據(jù)分發(fā)給參與集合通信的不同進(jìn)程，它們均可利用硬件多播進(jìn)行加速.因此多播路由的性能對這些集合操作具有重要影響.
目前的多播路由算法[7-12]均是為每個多播組構(gòu)建1棵多播樹.用戶每創(chuàng)建1個多播組，就需要構(gòu)建1棵對應(yīng)的多播樹，并占用多播路由表的1個條目號.而多播表大小是有限的，隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，多播組的個數(shù)會急劇增加，可能會超過硬件支持的多播表條目數(shù).而現(xiàn)有的多播路由算法要么默認(rèn)多播表條目數(shù)是夠用的，因此沒有給出多播表條目數(shù)不足時構(gòu)建多播表的方案；要么針對拓?fù)湮粗木W(wǎng)絡(luò)，存在時間開銷大、多播路由經(jīng)常變化等問題.本文在胖樹結(jié)構(gòu)下研究面向有限多播表條目數(shù)的多播路由算法.
1.1 基本概念
定義1.互連網(wǎng)絡(luò).互連網(wǎng)絡(luò)定義為一個有向圖I=G(N,L)，其中N為網(wǎng)絡(luò)節(jié)點集合，L為通信鏈路集合，網(wǎng)絡(luò)節(jié)點又分為終端(一般是網(wǎng)卡設(shè)備，用于收發(fā)數(shù)據(jù))及交換機(jī)(用于轉(zhuǎn)發(fā)數(shù)據(jù)).
定義2.多播組.多播組(multicast group, MCG)是網(wǎng)絡(luò)節(jié)點集N的一個子集，其成員一般是終端節(jié)點.
多播組對應(yīng)MPI中的1個通信域，用全局唯一的MGID標(biāo)識.它不僅用于多播操作，還可用于包括同步、全局規(guī)約等在內(nèi)的其他集合操作.例如，神威互連網(wǎng)絡(luò)中，硬件全局規(guī)約可通過多播組將規(guī)約結(jié)果廣播給所有成員.
定義3.多播路由.從單個交換機(jī)的角度看，多播路由可定義為如下映射R:L×M→2L，其中M為MGID集合.該映射的輸入?yún)?shù)為輸入鏈路lij及多播組MGID，返回值為輸出鏈路列表{ljk}.
該定義允許交換機(jī)根據(jù)不同輸入鏈路選擇不同的輸出鏈路.這要求交換機(jī)每個端口都有獨立的多播路由表.而從全局角度看，多播路由R將多播組MGID映射為I的1棵子樹，該子樹包含該多播組的所有成員.我們稱該子樹為多播樹(multicast tree, MCT).圖1所示的多播組中，陰影所示節(jié)點發(fā)送多播包時，每到達(dá)1個交換機(jī)的1個端口，就查詢該多播組對應(yīng)的多播表條目，從而確定將多播包復(fù)制到哪些端口進(jìn)行轉(zhuǎn)發(fā).1個多播組對應(yīng)1棵多播樹，但1棵多播樹可供多個多播組使用.
Fig. 1 Illustration for multicast tree圖1 多播樹示意圖
定義4.多播表條目號.交換機(jī)多播表有多個條目，以支持不同的多播組，其編號稱為多播表條目號.每個條目都是1個位圖，指定了需要將數(shù)據(jù)包復(fù)制到哪些輸出端口.多播路由除了為每個多播組確定多播樹之外，還需要確定該多播樹使用的多播表條目號.
在發(fā)送多播消息時，MGID及多播表條目號具有不同的作用.用戶需同時指定目的MGID及多播表條目號.交換機(jī)收到多播包時，根據(jù)多播表條目號查找對應(yīng)的多播表條目，并將多播包通過該多播表條目指定的輸出端口轉(zhuǎn)發(fā)出去.而終端節(jié)點收到多播包后，則根據(jù)MGID決定將該包拷貝到哪些通信隊列中.
不同廠商支持的多播表條目數(shù)不同，例如Mellanox交換機(jī)最多可支持16 384個多播表條目，而神威互連網(wǎng)絡(luò)僅支持32個多播表條目.在不考慮多播表大小的情況下，可以為每個多播組都分配1個不同的多播表條目號；Infiniband即采用該策略，其多播表條目號稱為MLID(multicast local identification).而在考慮到多播表有大小限制時，則沒有必要為每個多播組都分配1個單獨的多播表條目號，2個多播組只要不使用同一條鏈路，就可以共用同一個多播表條目號，從而大大降低對多播表條目數(shù)的需求；神威互連網(wǎng)絡(luò)即采用該策略，其多播表條目號稱為多播鏈號.
為多播樹分配多播表條目號時，必須遵循下列原則：1)同一棵多播樹在其使用的所有交換機(jī)內(nèi)使用相同的多播表條目號；2)若2棵多播樹經(jīng)過同一條鏈路，則這2棵多播樹不能使用同一個多播表條目號.將每棵多播樹看做圖的頂點，只要2棵多播樹共用同一條鏈路，則稱這2棵多播樹“相鄰”，對應(yīng)的2個頂點間添加1條邊.我們將多播表條目號用顏色表示，為“相鄰”的多播樹指定不同的多播表條目號，也即用不同的顏色染色.后文將用術(shù)語“染色”表示為多播樹分配多播表條目號.
定義5.EFI(edge forwarding index).文獻(xiàn)[13-14]定義了單播路由中的EFI指數(shù).我們對此進(jìn)行擴(kuò)展，將每條鏈路的EFI定義為經(jīng)過該鏈路的多播組個數(shù).
鏈路的最大EFI值反映了擁塞程度，值越大表示擁塞程度越高.最大EFI對多播操作性能具有重要影響，故需要盡量將多播路由均衡分布到不同的鏈路上，以降低EFI指數(shù).
定義6.TFI(tree forwarding index).對多播樹而言，使用該多播樹的多播組個數(shù)稱為該多播樹的TFI.
若多個多播組共享1棵多播樹，則1個多播組內(nèi)的多播數(shù)據(jù)包會復(fù)制到其它多播組內(nèi)，從而造成相互干擾，故TFI實際上反映了多播樹中多播數(shù)據(jù)包的冗余程度.
1.2 現(xiàn)有多播路由算法存在的問題
Infiniband中現(xiàn)有的多播路由算法構(gòu)建多播樹的過程包括：1)選擇1個交換機(jī)作為多播樹的樹根，使其到多播組內(nèi)各成員的平均距離或最大距離最?。?)為多播組的每個成員分別找到1條到達(dá)樹根的路徑，從而完成多播樹的構(gòu)建.需要注意的是，在尋找到達(dá)樹根的路徑的過程中，不能形成環(huán).
現(xiàn)有的路由算法未考慮多播表條目數(shù)不夠用的問題，它們?yōu)槊總€MGID都分配1個不同的多播表條目號.隨著應(yīng)用規(guī)模的不斷擴(kuò)大，多播組的數(shù)量也隨之快速增大，系統(tǒng)中可能同時存在成百上千甚至數(shù)萬個多播組，可能會超過硬件支持的多播表條目數(shù),導(dǎo)致多播表條目不夠用.
對于多播表條目不夠用的問題，一種簡單的解決方案是建立1棵超級多播樹(神威互連網(wǎng)絡(luò)中稱為全局廣播鏈)，使其包含所有終端節(jié)點，使所有多播組都使用該多播樹進(jìn)行廣播.但該方案存在嚴(yán)重的性能問題：1個多播組發(fā)送的數(shù)據(jù)會復(fù)制到整個網(wǎng)絡(luò)中，造成網(wǎng)絡(luò)中存在大量無用的多播包；當(dāng)很多個多播組同時使用該多播樹發(fā)送消息時，會造成集合操作性能的嚴(yán)重下降.
為此，我們在前期工作中[15]提出了面向有限多播表條目數(shù)的多播路由算法(multicast routing for limited multicast forwarding table size, MR4LMS).MR4LMS工作原理為：只要多個多播組不經(jīng)過同一條鏈路，就盡量共用同一個多播表條目號；而當(dāng)n個相似的多播組無條目號可用時，就將它們合并到一起共用同一棵多播樹.也即首先嘗試讓多個多播組共用同一個多播組條目號，如果失敗，則嘗試讓多個多播組共用同一棵多播樹.
具體來說，MR4LMS包括2個主要部分.一是采用2種方法來構(gòu)造多播樹，包括：1)在可用顏色數(shù)比較充足時，采用先構(gòu)造后染色算法，以每個備選交換機(jī)為樹根構(gòu)造1棵多播樹，然后嘗試用不同的顏色染色；2)在顏色數(shù)不足時，采用先染色后構(gòu)造算法，先找出可用的顏色，然后在該顏色下構(gòu)造1棵多播樹.二是當(dāng)上述2種方法都不能構(gòu)造出多播樹時，采用合并算法，將多個多播組合并成1個多播組，從而降低對多播組顏色數(shù)的需求.
MR4LMS主要用于拓?fù)湮粗木W(wǎng)絡(luò)，可以顯著降低所需的多播表條目數(shù)，滿足大部分應(yīng)用創(chuàng)建多播組時的需求.但也存在一些實用性方面的問題，包括：
1) MR4LMS需要進(jìn)行大量的圖遍歷操作，時間開銷很大，特別是同時創(chuàng)建成百上千個多播組時，很可能出現(xiàn)顏色數(shù)不夠用的情況，則需要嘗試很多交換機(jī)做樹根，或嘗試很多種顏色，此時運(yùn)行時間可能會超過數(shù)分鐘.
2) MR4LMS根據(jù)系統(tǒng)中已存在的其他多播樹情況為新多播組構(gòu)建多播樹，因此對于同一個多播組，在不同時刻構(gòu)建的多播樹很可能是不同的，也即創(chuàng)建出的多播樹具有動態(tài)可變性.這在實際應(yīng)用場景中會帶來很多問題：①當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化而重新計算多播路由時，多播組使用的多播樹即使沒有使用故障鏈路，重新計算路由后也很可能會發(fā)生變化，從而造成多播路由的頻繁變化，影響用戶使用；②同一應(yīng)用在不同時刻運(yùn)行時，構(gòu)建的多播樹也可能不同，這會帶來應(yīng)用性能的差異，影響用戶體驗.
3) 當(dāng)顏色不足而需要合并多播組時，也可能會重構(gòu)已存在的多播樹，從而影響已存在的多播組的使用.另外，不同時刻進(jìn)行合并，產(chǎn)生的多播組也可能不同，帶來2)中所述的影響.
4) 未考慮容錯問題.當(dāng)多播樹的1條鏈路發(fā)生故障后，MR4LMS會重構(gòu)所有的多播路由，由此帶來下列問題：一是需要為所有多播組都重算路由，導(dǎo)致整機(jī)范圍的路由重構(gòu)，影響范圍廣；二是經(jīng)過故障鏈路的多播包會丟失，即使有端到端的傳輸層控制協(xié)議可以重傳該包，但由于重構(gòu)多播路由需要相對較長的時間，因此會對應(yīng)用性能帶來較大影響.
Fig. 2 Illustration of fat tree structure圖2 胖樹結(jié)構(gòu)示意圖
實際上，針對特定的拓?fù)浣Y(jié)構(gòu)，可以采用更高效的解決方案.胖樹是目前高性能計算中最流行的拓?fù)浣Y(jié)構(gòu)，Top500排名中很多計算機(jī)均采用胖樹或裁剪胖樹.本文將針對胖樹結(jié)構(gòu)研究硬件僅支持少量多播組條目數(shù)時的多播路由算法.
1.3 本研究使用的胖樹結(jié)構(gòu)
目前Top500超級計算機(jī)中使用較多的是3層或4層胖樹[16-19].本文研究圖2所示的4層胖樹.L0與L1層交換機(jī)被分成多個計算網(wǎng)絡(luò)中板(computing network midplane, CN)，每個CN包含q個L0層交換機(jī)以及m個L1層交換機(jī).L2層與L3層交換機(jī)也被分成多個頂層網(wǎng)絡(luò)中板(top network midplane, TN)，每個TN包含k個L2層交換機(jī)以及w個L3層交換機(jī).每個L1層交換機(jī)共有p個端口用于連接TN，故每個CN共有m×p個端口用于連接TN，TN的個數(shù)為m×p.每個TN有k×w個端口用于連接CN，因而CN的個數(shù)為k×w.
2 高效實用地定制多播路由算法
為了快速創(chuàng)建多播路由，可以預(yù)先構(gòu)建好一些多播樹，但這些多播樹并沒有真正寫到多播表中.當(dāng)為多播組創(chuàng)建多播樹時，直接從這些預(yù)分配的多播樹中選擇1棵使用即可.每棵這樣的多播樹都應(yīng)該包含所有L0層交換機(jī)，以支持整機(jī)規(guī)模的多播組.為與1.1節(jié)所述的多播樹加以區(qū)別，稱這些預(yù)先創(chuàng)建的多播樹為生成樹(spanning tree, SPT).一般情況下，多播組僅會使用該生成樹的部分枝葉.當(dāng)為多播組創(chuàng)建多播樹時，僅將所使用的那部分枝葉寫進(jìn)多播表中即可.
在胖樹結(jié)構(gòu)中，多播組使用的多播樹的樹根應(yīng)該是多播組內(nèi)各成員的最近公共祖先.由于任一L0層交換機(jī)到給定樹根有且只有1條路徑，對每個多播組而言，只要確定了樹根及顏色就確定了多播樹.因此，要預(yù)先建立生成樹，只需確定哪些交換機(jī)可以作為樹根即可.選擇交換機(jī)時，需要考慮以該交換機(jī)為樹根建立的生成樹，跟那些已建立的生成樹是否存在沖突.2棵生成樹若使用同一種顏色，則不能共用同一條鏈路；只有使用不同顏色時才可以共用同一條鏈路.
2.1 無沖突的生成樹個數(shù)
首先要回答的問題是：給定顏色數(shù)C，可以建立多少棵不沖突的生成樹？首先分析僅有一種顏色時生成樹的個數(shù).暫不考慮L0層交換機(jī)與終端節(jié)點間的鏈路是否會存在沖突.
定理1.胖樹結(jié)構(gòu)中，一種顏色能且僅能創(chuàng)建m棵不沖突的生成樹，其中m是每個CN內(nèi)L1層交換機(jī)的個數(shù).
證明.首先，按下述方式構(gòu)造m棵生成樹.先將TN按從左到右的順序編號并分組，每p個分為1組，共m組.按該分組方法，每個L1層交換機(jī)所連接的p個TN位于同一組內(nèi).然后從每組中任意選擇1個TN，共選出m個.再在每個選出的TN中任選1個L3層交換機(jī)，共選出m個交換機(jī).以這m個交換機(jī)為根，以所有L0層交換機(jī)為葉節(jié)點，可產(chǎn)生m棵生成樹.圖3單實線部分顯示了一棵以第1個TN為樹根的生成樹.
Fig. 3 Illustration of spanning tree圖3 生成樹示意圖
其次，證明這m棵生成樹不共用任何一條鏈路.很明顯，這m棵生成樹沒有共用任何L2?L3以及L1?L2間鏈路，因為每個樹根都位于不同的TN內(nèi).而每個L1層交換機(jī)連接的p個TN位于同一組內(nèi)，這p個TN僅有1個被選為樹根.也就是說，按上述方式構(gòu)建的2棵生成樹，不可能經(jīng)過同一個L1交換機(jī)，也就不可能共用L0?L1間鏈路.因此，上面構(gòu)造的m棵多播樹不共用任何1條鏈路，可使用同一種顏色.
最后，很容易就可看出，CN內(nèi)的每條鏈路都已被上述m棵生成樹中的1棵使用，因此不可能再創(chuàng)建出新的生成樹了.
綜上所述，僅有一種顏色時，能且僅能創(chuàng)建m棵不沖突的生成樹.
證畢.
需要指出的是，僅使用一種顏色時，1個TN唯一確定了1棵生成樹，而不用關(guān)心該生成樹使用了該TN內(nèi)的哪個L3層交換機(jī)做根.因此，如果2個多播組選擇同一個TN內(nèi)的不同交換機(jī)做樹根，仍認(rèn)為這2個多播組使用了同一棵生成樹.更進(jìn)一步，如果2個多播組選擇使用位于同一組內(nèi)的2個不同TN做樹根，由于它們可能共用L0?L1間鏈路，仍認(rèn)為這2個多播組使用了同一棵生成樹.如果2個多播組選擇同一個TN內(nèi)的交換機(jī)做樹根，但使用了不同的顏色，則認(rèn)為這2個多播組使用了不同的生成樹.概括而言，TN及顏色唯一確定了1棵生成樹.
根據(jù)定理1，可以很容易得到下面的2個推論.
推論1.胖樹結(jié)構(gòu)中，C種顏色能且僅能創(chuàng)建C×m棵不沖突的生成樹.其中每個L1交換機(jī)承擔(dān)C棵生成樹，可以把這C棵生成樹分布到跟該L1交換機(jī)連接的p個TN中.
在構(gòu)造網(wǎng)絡(luò)系統(tǒng)時，上述定理及推論為確定多播表大小提供了理論依據(jù).例如，若用40端口交換機(jī)構(gòu)造網(wǎng)絡(luò)系統(tǒng)，則m=20；在每個交換機(jī)端口僅支持256個多播表條目時，可支持不少于5 120個多播組.
需要說明的是，系統(tǒng)中實際可創(chuàng)建的多播組個數(shù)一般大于C×m.這是因為很多情況下2個多播組可以共用同一棵生成樹而不沖突，只要它們不共用該生成樹的同一條鏈路即可.例如，如果使用該生成樹的多播組的所有成員都位于同一個CN內(nèi)，則該多播組僅使用了該生成樹位于該CN內(nèi)的那部分枝葉，剩余部分仍可供其他多播組使用.
即使多播組的成員分散在不同CN內(nèi)，從而需要將根建在L2或L3層交換機(jī)上，該多播組仍然可以跟其他多播組共用同一棵生成樹.圖4顯示了一個這樣的例子.灰色陰影所示多播組和斜條紋填充所示多播組可以使用同一個L3層交換機(jī)做樹根.2個使用同一棵生成樹的多播組，只要它們沒有共用同一個L2交換機(jī)，就可以共同一個L3交換機(jī)做樹根，因為這樣產(chǎn)生的多播樹沒有共用任何相同的鏈路.
Fig. 4 Example for 2 MCGs using the same spanning tree圖4 2個多播組共用1棵生成樹的例子
系統(tǒng)中共有C×m棵不沖突的生成樹，對編號為spt_no的生成樹，根據(jù)式(1)確定其顏色color及樹根所在的頂層網(wǎng)絡(luò)中板tnid.另外，總是選擇該頂層網(wǎng)絡(luò)中板的第1個L3交換機(jī)做樹根，因此確定了tnid及color，就確定了樹根.由式(1)可以看出，我們將不同顏色的生成樹樹根分散到同一組內(nèi)的不同TN內(nèi)，來達(dá)到負(fù)載均衡的目的.
(1)
2.2 為多播組選擇生成樹
為多播組創(chuàng)建多播樹時，首先需要確定該多播組應(yīng)該使用哪棵生成樹.對每一個多播組，根據(jù)其MGID將其映射到上述C×m棵生成樹中的1棵.具體來說，假設(shè)多播組的MGID為mgid，根據(jù)式(2)確定該多播組使用的生成樹.
spt_no=mgid%(C×m).
(2)
根據(jù)式(1)(2)我們可以得出根據(jù)MGID直接計算顏色編號及樹根所在TN編號：
(3)
采用該方式創(chuàng)建多播樹時，無需考慮系統(tǒng)中各鏈路的負(fù)載及顏色使用情況，僅由MGID即可確定使用哪棵生成樹.如果多播組的個數(shù)多于C×m，則可能出現(xiàn)多個多播組共同一棵生成樹的情況，此時需要將幾個多播組合并成1個多播組.式(1)及式(3)保證使用同一棵生成樹的2個多播組在合并時，僅需在原來的多播樹上添加部分鏈路即可，被合并的那些多播組使用的多播樹并不受影響，從而不會影響這些多播組的正常使用.
1個終端加入多個多播組時，每個多播組需要使用不同的顏色，否則在終端節(jié)點與L0交換機(jī)間的鏈路上就會產(chǎn)生沖突.本文將在3.1節(jié)研究該問題的解決方案.
2.3 為多播組構(gòu)造多播樹
確定樹根所在的頂層網(wǎng)絡(luò)中板及顏色后，就可以構(gòu)造多播樹了，步驟如算法1所示.該算法根據(jù)多播組成員的分布情況，從生成樹中選擇合適的交換機(jī)做為該多播組的樹根，它們可能位于L0,L1,L2,L3中的某一層.
算法1.多播樹構(gòu)造算法.
輸入：互連網(wǎng)絡(luò)I=G(N,L)、多播組mcg；
輸出：多播樹mct.
① 根據(jù)式(3)計算該多播組使用的顏色color以及樹根所在的頂層網(wǎng)絡(luò)中板tnid；
② 對多播組的每個成員，檢查其連接到L0交換機(jī)的那條鏈路上顏色color是否已被使用，若是則返回NULL；
③ 根據(jù)多播組各成員的物理位置，確定該多播組內(nèi)各成員的最近公共祖先所在的位置；
④ 若最近公共祖先位于L0或L1或L2層，則該公共祖先有且只有1個，記為root；
⑤ 若最近公共祖先位于L3層，則選擇頂層網(wǎng)絡(luò)中板tnid內(nèi)的第1個L3交換機(jī)做樹根root；
⑥ 以root為樹根，為mcg的每個成員都找出該成員到root的路徑，從而構(gòu)建出多播樹mct；
⑦ 檢查mct的每條鏈路中顏色color是否可用，若均為可用，則返回mct；
⑧ 否則，返回NULL./*需進(jìn)行合并操作*/
算法1步驟②用于檢查終端節(jié)點使用同一種顏色加入多個多播組的情況；若該顏色已被使用，則不能利用該顏色創(chuàng)建新的多播組，因此返回NULL，表示需要進(jìn)行合并操作.
算法1步驟③～⑤用于確定樹根，規(guī)則為：
1) 若多播組的成員都位于同一個L0交換機(jī)內(nèi)，則樹根即為該L0交換機(jī)；
2) 若多播組的成員均位于同一個CN內(nèi)，則樹根為生成樹在該CN內(nèi)的那個L1交換機(jī)；
3) 若多播組的成員位于不同CN內(nèi)(CN編號記為cnid)，且所有cnid/w相等，則樹根為生成樹中用于連接這些CN的那個L2交換機(jī)；
4) 其他情況下，選擇該生成樹中的第1個L3交換做樹根.
算法1步驟⑥⑦嘗試使用顏色color構(gòu)建多播樹.在胖樹結(jié)構(gòu)中，確定了樹根后，多播組的每個成員到樹根僅有1條鏈路，因此也就確定了多播樹.2個多播組使用同一棵生成樹時，有可能會共用同一條鏈路，從而會產(chǎn)生沖突，此時需要進(jìn)行合并操作，方法見2.4節(jié).
將多播組中成員個數(shù)記為S，則算法1的時間復(fù)雜度為O(S).
2.4 合并多播組
在算法1中，如果發(fā)現(xiàn)新構(gòu)造的多播樹與某個已經(jīng)創(chuàng)建的多播組使用了同一條鏈路，則需要進(jìn)行合并操作.方法如下：將算法1中構(gòu)建的多播樹記為tmpMct，檢查tmpMct的每條鏈路，若該鏈路中顏色color已被其他多播組使用，則根據(jù)式(3)這些多播組必定與新創(chuàng)建的多播組使用同一棵生成樹；將這些多播組的所有成員，連同新創(chuàng)建的多播組的成員一起，利用算法2構(gòu)建一個新的多播組，記為vmcg；然后利用算法1為vmcg創(chuàng)建多播樹.
算法2.合并算法.
輸入：互連網(wǎng)絡(luò)I=G(N,L)、多播組mcg；
輸出：虛擬多播組vmcg.
① 根據(jù)式(3)計算該多播組使用的顏色color、樹根所在的頂層網(wǎng)絡(luò)中板tnid；
② 采用算法1找到樹根root，并以root為樹根構(gòu)造多播樹tmpMct;
③ 檢查tmpMct的每條鏈路，將使用該鏈路且顏色為color的所有多播組，連同mcg合并在一起，形成虛擬多播組vmcg；
④ 返回vmcg.
算法2在尋找需要合并哪些多播組時，僅檢查了tmpMct使用的鏈路，而tmpMct的樹根可能是非L3層的交換機(jī).也就是說，算法2僅檢查了所用生成樹的一部分鏈路的使用情況.那么，算法2是否已經(jīng)合并了所有必須合并的多播組，從而保證一定能夠成功為vmcg構(gòu)建出多播樹呢？答案是肯定的，下面我們進(jìn)行證明.
引理1.利用算法1構(gòu)建多播樹時，如果某多播組需要進(jìn)行合并操作，則合并后產(chǎn)生的vmcg對應(yīng)的多播樹，其任意1條鏈路必定出現(xiàn)在某個被合并的多播組所對應(yīng)的多播樹內(nèi).
證畢.
定理2.利用算法1構(gòu)建多播樹時，如果某多播組需要進(jìn)行合并操作，則合并后產(chǎn)生的vmcg對應(yīng)的多播樹，與使用同一生成樹的其他多播組不共用任何鏈路.
證畢.
根據(jù)定理2，為vmcg構(gòu)建多播樹時，不會跟使用同一生成樹的其他多播組沖突，也就是說算法2已經(jīng)合并了所有必須合并的多播組.
由上述論述可知，合并多播組時，僅會在原來多播樹的基礎(chǔ)上添加部分鏈路，因而不會對原多播樹帶來影響.完整的C-MR4LMS路由算法見算法3.
算法3.C-MR4LMS.
輸入：互連網(wǎng)絡(luò)I=G(N,L)、多播組mcg；
輸出：多播樹mct.
① 利用算法1為mcg構(gòu)建多播樹mct；
② 若mct為NULL，則
③ 利用算法2進(jìn)行合并操作，將幾個多播組合并成1個虛擬的多播組vmcg；
④ 再次利用算法1為vmcg創(chuàng)建多播樹mct；
⑤ 更新mct每條鏈路中相應(yīng)顏色的使用情況；
⑥ 更新mct中每個交換機(jī)的多播路由表.
2.5 容錯多播路由
本文采用圖5所示的容錯策略：為每個多播組構(gòu)建多播路由時，選擇2個樹根并構(gòu)建2棵多播樹，兩者互為備份，數(shù)據(jù)包同時通過這2棵多播樹進(jìn)行傳輸.終端節(jié)點收到2份重復(fù)的數(shù)據(jù)包時，僅需丟棄其中1個.當(dāng)其中1棵多播樹因鏈路故障而無法使用時，數(shù)據(jù)包可以通過另一棵多播樹進(jìn)行傳輸，從而做到對用戶透明的容錯.
Fig. 5 Illustration of multicast routing with fault tolerance圖5 容錯多播路由示意圖
當(dāng)開啟容錯功能后，利用式(4)計算多播組使用的顏色及2棵多播樹樹根所在TN編號.該方法實際上是將每種顏色下的m棵生成樹分為2組，從每組分別選擇1棵生成樹使用.因此，系統(tǒng)支持的無沖突生成樹的個數(shù)會減為原來的1/2.
(4)
2.6 另一種選擇樹根的方法
如果多播組內(nèi)各成員的最近公共祖先位于L3層，則頂層網(wǎng)絡(luò)中板tnid內(nèi)每個L3交換機(jī)都可以做樹根.從中選擇哪個做樹根實際上有2種策略：一是算法1所采用的固定選擇第1個交換機(jī)的策略，由此產(chǎn)生的算法稱為C-MR4LMS-fixed；二是將所有L3交換機(jī)都作為備選樹根，從中選擇1個合適的做樹根(優(yōu)先選擇負(fù)載低的)，由此產(chǎn)生的算法稱為C-MR4LMS-dynamic.
這2種變體各有優(yōu)缺點.
1) 某些情況下，C-MR4LMS-dynamic可以通過選擇不同的L3交換機(jī)做樹根，使C-MR4LMS-fixed算法下原本有沖突的2個多播組不再沖突.如圖6所示，灰色陰影所示多播組與斜條紋所示多播組使用同一棵生成樹.C-MR4LMS-fixed算法下這2個多播組共用同一個L3交換機(jī)做樹根，因此在L2?L3鏈路上會產(chǎn)生沖突.而C-MR4LMS-dynamic算法下這2個多播組可以使用不同的L3交換機(jī)做樹根，從而避免產(chǎn)生沖突.
Fig. 6 Example for 2 MCGs using different L3 switches as root圖6 2個多播組使用不同L3交換機(jī)做樹根的例子
2) 需要進(jìn)行合并操作時，C-MR4LMS-dynamic下同一棵生成樹的幾個多播組可能使用不同的L3交換機(jī)做樹根，它們被合并到一起后，樹根會發(fā)生變化，從而導(dǎo)致被合并的多播組其多播路由發(fā)生變化，而C-MR4LMS-fixed不存在該問題.
Fig. 7 Illustration for merge algorithm fails to construct MCTs with C-MR4LMS-dynamic圖7 利用C-MR4LMS-dynamic算法構(gòu)建多播樹后合并算法失效的例子
3) C-MR4LMS-fixed算法下，利用算法2合并多播組時，已經(jīng)合并了所有必須合并的多播組，從而保證一定能夠成功為vmcg構(gòu)建出多播樹.而C-MR4LMS-dynamic算法下，利用算法2合并多播組時，可能會漏掉某些必須合并的多播組，從而導(dǎo)致為vmcg構(gòu)建多播樹失敗.如圖7所示(圖中省略了L0,L1層交換機(jī))，假設(shè)新創(chuàng)建的多播組需要經(jīng)過R2,R4這2個交換機(jī)，且無論選擇R0還是R1做樹根均跟已存在的多播組存在沖突，因此需要利用算法2進(jìn)行合并操作.假設(shè)在合并時，選擇R0做樹根，且需要合并R1?R4,R1?R5間鏈路所示的多播組.在進(jìn)行合并時，僅會檢查R0?R4,R0?R2鏈路；而合并后的vmcg對應(yīng)的多播樹會用R0?R5間鏈路，但該鏈路在檢查需要合并哪些多播組時并未被考慮到，實際上該鏈路可能被另外的多播組使用，因而為vmcg構(gòu)建多播樹會因沖突而失敗.出現(xiàn)該問題的原因是：R1?R4,R1?R5多播組使用了不同的L3交換機(jī)做樹根，導(dǎo)致原本未被vmcg內(nèi)任一多播組使用的鏈路R0?R5出現(xiàn)在了vmcg經(jīng)過的路徑上，從而使得C-MR4LMS-dynamic算法下引理1不再成立.也就是說，C-MR4LMS-dynamic算法下，上述合并算法不能保證合并了所有必須合并的多播組.
基于上述原因，使用C-MR4LMS-dynamic時，為vmcg構(gòu)建多播樹可能失敗，此時需要再進(jìn)行1次合并方可成功.
4) 在多播組個數(shù)較多時，C-MR4LMS-dynamic需要嘗試很多個L3交換機(jī)做樹根，時間開銷較大；而C-MR4LMS-fixed僅會嘗試1個L3交換機(jī)做樹根，時間開銷較小.
具體使用哪種策略，可以根據(jù)實際情況進(jìn)行選擇.一般來說，多播組個數(shù)不多時，可以采用C-MR4LMS-dynamic策略；而多播組個數(shù)很多而需要頻繁合并多播組時，比較適宜采用C-MR4LMS-fixed算法.
3 減少多播樹沖突的2種方法
MGID分配策略及節(jié)點分配策略都會影響C-MR4LMS算法的性能.例如，為某個多播組選擇不同的MGID，就會使用不同的生成樹；將多播組所在的作業(yè)映射到不同節(jié)點上，也會影響多播樹的分配.
本節(jié)將研究如何分配MGID及進(jìn)行節(jié)點映射，以達(dá)到減少多播樹沖突的目的.這些分配策略并不是C-MR4LMS的組成部分，目的是為了更好地發(fā)揮C-MR4LMS的性能.
3.1 分層的MGID分配策略
考慮每個終端節(jié)點可加入多個多播組的情況.1個終端加入多個多播組時，每個多播組需要使用不同的顏色，否則在終端節(jié)點與L0交換機(jī)間的鏈路上就會產(chǎn)生沖突.根據(jù)式(3)，如果不對用戶可用的MGID加以限制，就很容易出現(xiàn)1個終端加入的多個多播組時使用同一種顏色的情況.出現(xiàn)該情況后，需要將沖突的那些多播組合并.此時進(jìn)行的合并跟2.2節(jié)介紹的合并有很大不同.當(dāng)2個多播組因共用同一條交換機(jī)間鏈路而需要合并時，因為他們使用同一棵生成樹，只需在原多播樹的基礎(chǔ)上添加部分鏈路即可，不會影響原多播組的正常使用.而當(dāng)1個終端節(jié)點使用同一種顏色加入多個多播組時，這些多播組可能使用了不同的生成樹，其樹根位于不同TN內(nèi)，合并后多播組的樹根會發(fā)生變化，影響用戶使用.
基于上述原因，當(dāng)1個終端需要加入多個多播組時，我們需要對其使用的MGID加以限制.也就是說，根據(jù)式(3)計算color及tnid時，要么每個多播組都使用不同的顏色，要么2個多播組可以使用同一種顏色，但計算出的tnid必須相同，從而保證這2個多播組可以不用切換TN做樹根即可進(jìn)行合并.
用戶可以采用多種策略保證1個終端節(jié)點使用的多個MGID沒有顏色上的沖突.一種可行的策略是：根據(jù)每個終端可加入的多播組的個數(shù)將顏色劃分為不同的區(qū)間，每個區(qū)間稱為1個層，從而也就將MGID空間劃分成了多個互不重疊的層，稱為MGID層.在每個MGID層內(nèi)，1個終端節(jié)點最多可加入其中的1個多播組；加入多個多播組時，選擇不同的MGID層即可保證他們使用不同的顏色.
每個終端可加入的多播組的個數(shù)一般不會太多，例如，以2維網(wǎng)格方式劃分通信域時，假設(shè)每個終端上僅運(yùn)行1個通信進(jìn)程，則每個終端僅需加入3個多播組，包括1個全局通信域、1個用于行通信的子通信域以及1個用于列通信的子通信域.在此情況下，我們可以將MGID劃分為3個層，使得每個MGID層均使用不同的顏色，為哪個維度的多播組分配多播組，就從該維度對應(yīng)的MGID層中選擇1個MGID使用.
當(dāng)每個終端上可運(yùn)行多個通信進(jìn)程時，情況變得復(fù)雜，因為每個終端節(jié)點在每個維度方向上可能加入多個多播組.此時需要考慮通信域的劃分方式，并將每個通信域映射到合適的MGID層.MPI集合通信中，主要有2種通信域劃分方法[20-21]：一是劃分成2維或3維網(wǎng)格，其每個維度中每行或每列都是1個通信域，對應(yīng)1個多播組；二是劃分成層次結(jié)構(gòu)，例如樹型結(jié)構(gòu)，每層分成很多組，每個組構(gòu)成1個通信域，每個組再選出1個leader，形成更高層次的組.以層次結(jié)構(gòu)劃分通信域時，將通信域映射到MGID層的方法比較簡單，只需為每個通信域?qū)又付?個MGID層.
下面考慮3維網(wǎng)格劃分方式下將通信域映射到MGID層的方法，2維網(wǎng)格方式與此類似，不再贅述.如圖8所示，假設(shè)每個終端節(jié)點上有P個通信進(jìn)程，且它們在3維環(huán)網(wǎng)中的位置是連續(xù)的.例如，設(shè)3維環(huán)網(wǎng)x,y,z維長度分別為X,Y,Z，某終端節(jié)點上首進(jìn)程的坐標(biāo)為(a,b,c)，則該終端節(jié)點上第n個進(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é)點上不同進(jìn)程位置示意圖
給定坐標(biāo)為(a,b,c)的進(jìn)程，我們根據(jù)式(5)分別計算該進(jìn)程加入3個軸方向上的多播組時使用的MGID層號，其中l(wèi)ayerx,layery,layerz分別對應(yīng)x,y,z軸方向上的多播組.
(5)
定理3.以3維環(huán)網(wǎng)方式劃分通信域時，若每個終端節(jié)點上有P個通信進(jìn)程(P小于3維環(huán)網(wǎng)任一維的長度)，且這些進(jìn)程在3維環(huán)網(wǎng)中位置連續(xù)，則利用式(5)將每個進(jìn)程的3個多播組放入某個MGID層時，對任一終端節(jié)點而言，每個多播組均位于不同的MGID層內(nèi).
證明.首先，很容易看出，不同方向上的多播組位于不同的MGID層內(nèi).其次，我們證明，同一終端節(jié)點上同一方向上的多播組也位于不同的MGID層內(nèi).我們先列出同一終端節(jié)點上各個進(jìn)程的位置分布情況，包括：
1)P個進(jìn)程位于與x軸平行的同一條線上(如灰色陰影進(jìn)程所示)；
2)P個進(jìn)程不在同一條直線上，但位于與xoy平面平行的同一平面內(nèi)(如斜紋填充進(jìn)程所示)；
3)P個進(jìn)程不在同一平面內(nèi)(如橫紋填充進(jìn)程所示).
先看x軸方向上的多播組.情況1)中，P個進(jìn)程屬于同一個多播組.情況2)中，P個進(jìn)程屬于多個多播組，但它們具有相同的z坐標(biāo)，以及連續(xù)的y坐標(biāo)，因此根據(jù)式(5)得到的MGID層號必不相等.情況3)中，P個進(jìn)程屬于多個多播組；若2個多播組具有相同的z坐標(biāo)，則與情況2)一樣，根據(jù)式(5)得到的MGID層號必不相等；若2個多播組具有不同的z坐標(biāo)，則其中1個多播組的y坐標(biāo)必小于P-1，另一個多播組的y坐標(biāo)必大于等于P-1，根據(jù)式(5)得到的MGID層號也不相等.因此，上述3種情況下，根據(jù)式(5)得到的MGID層號都互不相等.
同理，y,z軸方向上的多播組根據(jù)式(5)得到的MGID層號也互不相等.
證畢.
利用式(5)，可以將3維環(huán)網(wǎng)中的多播組映射到不同的MGID層內(nèi)，保證每個終端節(jié)點在每個MGID層內(nèi)最多加入1個多播組，從而保證該終端節(jié)點加入多個多播組時，每個多播組都使用不同的顏色，也就避免在終端節(jié)點與L0交換機(jī)間的鏈路上產(chǎn)生沖突.每層內(nèi)的顏色數(shù)可以根據(jù)該層內(nèi)的多播組個數(shù)進(jìn)行分配.
3.2 相互無干擾的作業(yè)節(jié)點分配策略
根據(jù)定理1及2個推論，當(dāng)系統(tǒng)中多播組的個數(shù)少于C×m時，無需合并多播組即可完成多播樹的創(chuàng)建；而當(dāng)多播組的個數(shù)多于C×m時，很可能出現(xiàn)2個多播組使用同一棵生成樹的同一條鏈路的情況，從而導(dǎo)致沖突，此時需要將這2個多播組合并在一起.多播組合并會導(dǎo)致1個多播組發(fā)送的數(shù)據(jù)拷貝到另一個多播組內(nèi)，從而使得鏈路EFI指數(shù)變大，影響集合操作的性能.因此需要盡量避免這種情況的出現(xiàn).
通過優(yōu)化節(jié)點分配來減少作業(yè)間的相互干擾是提升應(yīng)用性能的重要手段[22-23].本文提出了一種作業(yè)分配策略，使不同作業(yè)使用的網(wǎng)絡(luò)資源彼此隔離，從而使得不同作業(yè)可以共用同一棵生成樹而沒有任何沖突.這樣每個作業(yè)都至少可以創(chuàng)建C×m個不沖突的多播組，從而使得系統(tǒng)中支持的多播組總數(shù)遠(yuǎn)遠(yuǎn)大于C×m.
首先根據(jù)作業(yè)使用的終端個數(shù)將作業(yè)分為下列類型：
1) T0作業(yè)，其終端個數(shù)小于等于m；
2) T1作業(yè)，其終端個數(shù)小于等于m2；
3) T2作業(yè)，其終端個數(shù)小于等于w×m2；
4) T3作業(yè)，其終端個數(shù)大于w×m2.
為作業(yè)分配終端節(jié)點時，必須遵循下列規(guī)則：
1) 1個節(jié)點僅能分配給1個作業(yè)使用；
2) T0作業(yè)使用的節(jié)點均位于同一L0交換機(jī)內(nèi)；
3) T1作業(yè)使用的節(jié)點均位于同一CN內(nèi)；
4) T2作業(yè)使用的節(jié)點，其計算網(wǎng)絡(luò)中板號cnid/w應(yīng)等于同一個值；
5) L0交換機(jī)可被多個T0作業(yè)共享，但最多只能被1個T1及以上規(guī)模的作業(yè)使用；
6) 1個計算網(wǎng)絡(luò)中板可以被多個T1作業(yè)共享，但最多只能被1個T2及以上規(guī)模的作業(yè)使用；
7) 編號為i×w,i×w+1,…,(i+1)×w-1的w個中板可以被多個T2作業(yè)共享，但最多只能被1個T3作業(yè)使用.
定理4.按規(guī)則1)～7)為作業(yè)分配節(jié)點時，任何2個作業(yè)不共用同一條鏈路.
證明. 首先考慮L0層交換機(jī).根據(jù)規(guī)則1)，L0交換機(jī)的下行鏈路只能被1個作業(yè)使用.根據(jù)規(guī)則2)，T0作業(yè)不會使用L0交換機(jī)的上行鏈路；而根據(jù)規(guī)則5)，L0交換機(jī)最多被1個T1及以上規(guī)模的作業(yè)使用，因此L0交換機(jī)的上行鏈路最多被1個作業(yè)使用.
再考慮L1層交換機(jī).同樣根據(jù)規(guī)則5)，其每條下行鏈路最多被1個作業(yè)使用；根據(jù)規(guī)則3)，T1作業(yè)不會使用L1交換機(jī)的上行鏈路；而根據(jù)規(guī)則6)，L1交換機(jī)最多被1個T2及以上規(guī)模的作業(yè)使用，因此L1交換機(jī)的上行鏈路最多被1個作業(yè)使用.
再考慮L2層交換機(jī).同樣根據(jù)規(guī)則6)，其每條下行鏈路最多被1個作業(yè)使用；根據(jù)規(guī)則4)，T2作業(yè)不會使用L2交換機(jī)的上行鏈路；而根據(jù)規(guī)則7)，L2交換機(jī)最多被1個T3作業(yè)使用，因此L2交換機(jī)的上行鏈路最多被1個作業(yè)使用.
最后考慮L3層交換機(jī).同樣根據(jù)規(guī)則7)，其每條下行鏈路最多被1個作業(yè)使用.
證畢.
由此可知，按規(guī)則1)～7)為作業(yè)分配節(jié)點時，來自不同作業(yè)的2個多播組使用同一棵生成樹創(chuàng)建多播樹時，不會產(chǎn)生沖突.因此，只要每個作業(yè)使用的多播組個數(shù)不超過C×m，就可以保證系統(tǒng)中所有的多播組不用合并就可成功創(chuàng)建多播樹.
4 ibsim下的性能評估
我們在OpenSM 3.3.22[24]中實現(xiàn)了C-MR4LMS，共有約2 000行代碼.對OpenSM源碼進(jìn)行了修改，使得每個交換機(jī)端口都有一份單獨的路由表.另外，還對加入、離開多播組的機(jī)制進(jìn)行了簡單的修改，以解決頻繁重算路由的問題.
4.1 實驗環(huán)境
本文使用ibsim-0.7[24]模擬了圖2所示的一棵4層胖樹，參數(shù)如下：交換機(jī)端口數(shù)為40，m=w=16，q=k=32，p=6.理論上，該網(wǎng)絡(luò)最大支持512個CN，96個TN，262 144個終端節(jié)點.但由于OpenSM及ibsim最多支持49 152個節(jié)點(包括交換機(jī)及終端)，因此僅使用了64個CN、96個TN；網(wǎng)絡(luò)中節(jié)點總數(shù)為40 448，其中交換機(jī)個數(shù)為7 680，終端節(jié)點數(shù)為32 768.
本文使用測試程序模擬發(fā)起加入或離開多播組的請求.OpenSM運(yùn)行在一臺48核Intel Xeon Silver 4214服務(wù)器上，頻率為2.20 GHz.需要指出的是，在ibsim下的測試結(jié)果跟在真實網(wǎng)絡(luò)環(huán)境下的測試結(jié)果是一樣的，因為EFI及運(yùn)行時間等性能數(shù)據(jù)跟是否使用ibsim模擬拓?fù)浣Y(jié)構(gòu)無關(guān).
MPI中將進(jìn)程劃分為子通信域時，可以采用層次結(jié)構(gòu)進(jìn)行劃分，也可以采用2維或3維網(wǎng)格方式進(jìn)行劃分.采用2維或3維網(wǎng)格方式劃分通信域時，會產(chǎn)生大量多播組，對多播表條目數(shù)的需求量更大.后面實驗中，采用2維及3維網(wǎng)格劃分進(jìn)程，以測試存在大量多播組時多播路由算法的性能.除此之外，還測試了進(jìn)程隨機(jī)加入某個多播組的通信模式.另外，既測試了每個終端運(yùn)行1個通信進(jìn)程的情況，也測試了每個終端運(yùn)行多個通信進(jìn)程的情況.
后面將要測試的2維或3維網(wǎng)格模式中，有些是按拓?fù)浣Y(jié)構(gòu)進(jìn)行劃分的，模擬拓?fù)涓兄耐ㄐ拍Ｊ剑挥行﹦澐殖烧叫位蛄⒎襟w形狀，模擬拓?fù)錈o感的通信模式.以每個終端節(jié)點上運(yùn)行1個通信進(jìn)程為例， 512×64通信模式下，第1維有64個多播組，每個組都位于同一個CN內(nèi)，因此通信模式與拓?fù)浣Y(jié)構(gòu)匹配；而181×181通信模式下，存在很多跨計算中板的多播組，因此通信模式與拓?fù)浣Y(jié)構(gòu)不匹配.
神威互連網(wǎng)絡(luò)中每個交換機(jī)端口最多支持32個多播表條目，因此后面測試中，將最大顏色數(shù)設(shè)為32，不沖突的生成樹的個數(shù)為512.設(shè)為其他值時，測試結(jié)果會有差異，但測試結(jié)論與顏色數(shù)為32時基本一致，因此不再贅述其測試數(shù)據(jù).另外，為了與MR4LMS對比，關(guān)閉了C-MR4LMS的容錯功能.
本文測試了原始MR4LMS算法及本文提出的2種多播路由算法(C-MR4LMS-fixed，C-MR4LMS-dynamic)在各種通信模式下的性能，其中每個終端節(jié)點上運(yùn)行1個通信進(jìn)程時的測試結(jié)果如圖9所示，每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時的測試結(jié)果如圖10所示.
Fig. 9 The performance of three algorithms with only one communication process on each terminal node圖9 每個終端節(jié)點上僅有1個通信進(jìn)程時3種算法的性能
Fig. 10 The performance of three algorithms with 4 communication process on each terminal node圖10 每個終端節(jié)點上4個通信進(jìn)程時3種算法的性能
4.2 不同通信模式下的鏈路EFI
最大EFI及平均EFI反映了各鏈路上多播樹的數(shù)量，一定程度上代表了多播路由算法的均衡程度.
4.2.1 每個終端上僅1個通信進(jìn)程
先分析每個終端節(jié)點上運(yùn)行1個通信進(jìn)程時的情況，結(jié)果如圖9(a)(b)所示.
1) 2維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的最大EFI及平均EFI均低于MR4LMS算法.出現(xiàn)該現(xiàn)象的原因是：MR4LMS算法在選擇樹根時根據(jù)負(fù)載情況從很多備選樹根中選擇1個；而在胖樹結(jié)構(gòu)中，所有的L3交換機(jī)均可作為備選樹根，因此會被輪流作為樹根使用.而2維環(huán)網(wǎng)下多播組的個數(shù)較少，因此MR4LMS僅用到了那些位置靠前的L3交換機(jī)，而那些位置靠后的L3交換機(jī)未被使用.這就導(dǎo)致MR4LMS算法僅使用了部分頂層網(wǎng)絡(luò)中板，進(jìn)而導(dǎo)致連接L1交換機(jī)與L2交換機(jī)的那些鏈路上EFI指數(shù)偏大.而C-MR4LMS算法會輪流使用不同頂層網(wǎng)絡(luò)中板做樹根，因此可以將多播組分散到不同頂層網(wǎng)絡(luò)中板內(nèi).隨著多播組個數(shù)的增多，C-MR4LMS算法會重用頂層網(wǎng)絡(luò)中板，此時C-MR4LMS的優(yōu)勢將會消失.另外，由于創(chuàng)建的多播組不多，2種C-MR4LMS算法的EFI差別不大，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
2) 3維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的表現(xiàn)有時比MR4LMS好，有時比MR4LMS差，這是因為隨著多播組個數(shù)的增大，MR4LMS算法會使用全部的頂層網(wǎng)絡(luò)中板，故3種算法均會將多播組分散到不同頂層網(wǎng)絡(luò)中板內(nèi)；而MR4LMS算法會根據(jù)負(fù)載情況選擇不同的交換機(jī)做樹根，因此大部分情況下MR4LMS算法具有更好的負(fù)載均衡性.2種C-MR4LMS算法比較，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
3) 進(jìn)程隨機(jī)加入某個多播組的模式下，MR4LMS算法明顯優(yōu)于2種C-MR4LMS算法.原因如下：C-MR4LMS算法下，多播組的個數(shù)已經(jīng)超過了不沖突的生成樹的個數(shù)，因而需要合并多播組，導(dǎo)致EFI偏大，而MR4LMS算法由于可以嘗試不同的交換機(jī)做樹根，不需要合并多播組，因而EFI指數(shù)小.后面將會看到，隨著多播組個數(shù)的進(jìn)一步增大，MR4LMS算法也會產(chǎn)生合并，此時其EFI指數(shù)也會明顯增加.需要指出的是，雖然2種C-MR4LMS算法的EFI明顯高于MR4LMS，但最大EFI為69，尚在可接受的范圍內(nèi).
4.2.2 每個終端上4個通信進(jìn)程
再分析每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時的情況，結(jié)果如圖10(a)(b)所示.
1) 2維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的最大EFI及平均EFI略高于MR4LMS算法.這與每個終端上僅1個通信進(jìn)程時3維環(huán)網(wǎng)通信模式下的情況類似，原因是進(jìn)程數(shù)增多后，多播組的個數(shù)也隨之增大，因而MR4LMS算法會使用全部的頂層網(wǎng)絡(luò)中板，故其表現(xiàn)優(yōu)于2種C-MR4LMS算法.
2) 3維環(huán)網(wǎng)模式下，2種C-MR4LMS算法的表現(xiàn)有時比MR4LMS好，有時比MR4LMS差.MR4LMS比2種C-MR4LMS算法差的原因是：隨著多播組個數(shù)的增大，3種算法需要進(jìn)行合并，但2種C-MR4LMS算法僅會合并使用同一生成樹的多播組，合并的多播組較少；而MR4LMS算法在選擇樹根時是根據(jù)負(fù)載情況動態(tài)選擇的，因此大量多播樹交錯在一起，合并時極端情況下可能需要合并很多個多播組.
3) 進(jìn)程隨機(jī)加入某個多播組的模式下，2種C-MR4LMS算法的表現(xiàn)優(yōu)于MR4LMS，原因與2)一樣.
4.2.3 結(jié)論
綜合上面分析，在EFI方面，有4點結(jié)論：
1) 當(dāng)多播組個數(shù)少于不沖突的生成樹個數(shù)時，2種C-MR4LMS算法一般情況下略優(yōu)于MR4LMS.
2) 當(dāng)多播組個數(shù)增大時，2種C-MR4LMS算法需要合并多播組，而MR4LMS算法不需要進(jìn)行合并操作，此時MR4LMS算法一般優(yōu)于2種C-MR4LMS算法.
3) 隨著多播組個數(shù)的繼續(xù)增大，從而使得3種算法都需要合并多播組時，2種C-MR4LMS算法一般情況下又會優(yōu)于MR4LMS算法.
4) 2種C-MR4LMS算法比較，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed；但大部分情況下，C-MR4LMS-fixed接近于C-MR4LMS-dynamic.
概括而言，依據(jù)圖9(a)、圖10(a)，當(dāng)多播組個數(shù)較少時，C-MR4LMS算法的最大EFI略高于MR4LMS算法，最多增大88；而當(dāng)多播組個數(shù)較多時，C-MR4LMS算法的最大EFI明顯低于MR4LMS算法，最多減少594.
4.3 不同通信模式下的TFI
多播樹的TFI表示有多少個多播組使用該多播樹.最大TFI及平均TFI反映了多播組的合并程度.
4.3.1 每個終端上僅1個通信進(jìn)程
先分析每個終端節(jié)點上運(yùn)行1個通信進(jìn)程時的情況，結(jié)果如圖9(c)～(e)所示.
1) MR4LMS算法下，所有通信模式下均未發(fā)生合并，因此TFI均為1.
2) 2種C-MR4LMS算法下，當(dāng)多播組個數(shù)小于生成樹個數(shù)時(如181×181,100×327)，因不需要合并，TFI均為1.隨著多播組個數(shù)的增多，需要合并多播組，TFI大于1.有幾個有趣的現(xiàn)象需要注意：
① 64×32×16以及32×32×32這2種通信模式下，C-MR4LMS-fixed的最大TFI分別為7和6；而C-MR4LMS-dynamic的最大TFI均為1，這表明通過選擇同一TN內(nèi)的不同L3交換機(jī)做樹根可以避免一些不必要的合并操作.
② 25×50×26以及3種隨機(jī)加入多播組的通信模式下，2種C-MR4LMS算法的最大TFI均大于1且相等，但從平均TFI方面看C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
③ 2種C-MR4LMS算法下，多播組發(fā)生合并后，剩余多播組的個數(shù)均不少于512(即系統(tǒng)中互不沖突的生成樹個數(shù)).
④ 隨機(jī)加入多播組的3種模式下，平均TFI接近于最大TFI，表明多播樹合并比較均勻.而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 每個終端上4個通信進(jìn)程
分析每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時的情況，結(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.這是因為每個終端節(jié)點上運(yùn)行4個通信進(jìn)程時，這幾種2維環(huán)網(wǎng)通信模式中的多播組個數(shù)均超過了512，因而需要共用同一棵生成樹，導(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算法在選擇樹根時是根據(jù)負(fù)載動態(tài)選擇的，因此大量多播樹交錯在一起，合并時極端情況下可能需要合并很多個多播組.以100×50×26通信模式為例，MR4LMS算法的最大TFI為168，而平均TFI僅為1.1，這表明大部分的多播組未被合并，而有168個多播組被合并到了一起.這也說明MR4LMS算法在需要合并多播組時，TFI波動較大.反觀2種C-MR4LMS算法，其最大TFI與平均TFI相比差別沒有這么明顯，特別是3種隨機(jī)加入多播組的模式下，平均TFI幾乎等于最大TFI，這是因為2種C-MR4LMS算法輪流使用不同的生成樹.
3) 從合并后剩余的多播組個數(shù)上看，某些通信模式下MR4LMS算法僅剩下少量多播組，例如1 000個隨機(jī)多播組模式下僅剩下32個多播組，這進(jìn)一步表明MR4LMS算法極端情況下會合并大量多播組.而2種C-MR4LMS算法下，剩余多播組的個數(shù)均不少于512，這是因為2種C-MR4LMS算法在合并時僅合并那些使用同一生成樹的多播組.
4.3.3 結(jié)論
綜合上面分析，在TFI方面，有下列結(jié)論：
1) 當(dāng)多播組個數(shù)較少時，MR4LMS 算法不需要合并多播組，其TFI為1，而2種C-MR4LMS算法的TFI可能大于1.
2) 隨著多播組個數(shù)的繼續(xù)增大，3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)都需要合并多播組時，2種C-MR4LMS算法一般情況下會優(yōu)于MR4LMS算法，且剩余多播組的個數(shù)均不少于512;而MR4LMS算法在極端情況下會剩余很少的多播組.
3) 2種C-MR4LMS算法比較，C-MR4LMS-dynamic略優(yōu)于C-MR4LMS-fixed.
概括而言，依據(jù)圖9(c)、圖10(c)，當(dāng)多播組個數(shù)較少時，C-MR4LMS算法的最大TFI略高于MR4LMS算法，最多增大25；而當(dāng)多播組個數(shù)較多時，C-MR4LMS算法的最大TFI明顯低于MR4LMS算法，最多減少148.
4.4 不同通信模式下的算法運(yùn)行時間
圖9(f)、圖10(f)分別顯示了每個終端節(jié)點上運(yùn)行不同數(shù)量的通信進(jìn)程時3種算法(C-MR4LMS,C-MR4LMS-dynamic,C-MR4LMS-fixed)的運(yùn)行時間.該時間僅包括計算路由的時間(選擇樹根、構(gòu)建多播樹、為多播樹染色等步驟的時間)，不包括發(fā)送加入多播組請求、分發(fā)路由等其他步驟的時間.
可以發(fā)現(xiàn)，2種C-MR4LMS算法的運(yùn)行時間明顯低于MR4LMS算法，最多下降94%.當(dāng)創(chuàng)建大量多播組而需要進(jìn)行合并的時候，兩者間的差異更加明顯.例如，圖10(f)所示100×50×26通信模式下，MR4LMS算法運(yùn)行時間超過575 s，而2種C-MR4LMS算法運(yùn)行時間均低于35 s，顯示出2種C-MR4LMS算法在減少運(yùn)行時間方面的巨大優(yōu)勢.MR4LMS算法需要嘗試大量的樹根及顏色，故其運(yùn)行時間較長，且受多播組大小、網(wǎng)絡(luò)中顏色使用情況等因素的影響；而2種C-MR4LMS算法直接根據(jù)MGID確定樹根及顏色，故其運(yùn)行時間固定，且時間較少.
另外，C-MR4LMS-dynamic運(yùn)行時間一般略高于C-MR4LMS-fixed，這是因為C-MR4LMS-dynamic需要嘗試同一TN內(nèi)的不同T3交換機(jī)做樹根.
5 基準(zhǔn)測試程序性能
本文在神威E級原型機(jī)上對C-MR4LMS算法的集合消息性能進(jìn)行了測試.神威E級原型機(jī)采用神威互連網(wǎng)絡(luò)，以硬件方式支持同步、規(guī)約、廣播等集合消息類型，相比點對點消息實現(xiàn)的集合操作具有更低的延時，其拓?fù)浣Y(jié)構(gòu)為4層胖樹.使用了600個終端節(jié)點進(jìn)行測試，這些終端節(jié)點分布在4個CN內(nèi)，每個節(jié)點上運(yùn)行6個通信進(jìn)程.共測試了4種集合通信類型，包括MPI_Barrier、8 B粒度的MPI_Allreduce、8 B及2 KB粒度的MPI_Bcast.通信模式如下：將所有進(jìn)程劃分為2維網(wǎng)格，為每行及每列均創(chuàng)建1個通信域；每個進(jìn)程先與同一行的所有進(jìn)程進(jìn)行1次集合通信，再與同一列的所有進(jìn)程進(jìn)行1次集合通信；所有進(jìn)程同時進(jìn)行通信，因此同一時刻有大量多播組在通信；共進(jìn)行5 000遍測試，由0號進(jìn)程記錄每遍測試中2次集合通信的總時間，2遍測試間不加同步；對每種進(jìn)程劃分方式、每種集合通信類型，本文均測試了4種路由算法的性能，包括全局廣播鏈、MR4LMS、C-MR4LMS-fixed及MR4LMS-dynamic.
5.1 關(guān)閉容錯時的集合消息性能
首先，測試關(guān)閉容錯時的性能.表1顯示了不同路由算法下的集合消息延遲中位值.另外，圖11以小提琴圖的形式顯示了60×60通信模式下的集合消息延遲分布和概率密度.小提琴圖的兩側(cè)反映了密度信息，越寬表示出現(xiàn)在該區(qū)間的測試數(shù)據(jù)越多.小提琴圖的中間部分以箱線圖方式顯示了延遲的中位數(shù)及上下四分位數(shù)，其中上四分位數(shù)記為Q3，下四分位數(shù)記為Q1，Q3與Q1之間的差值稱為四分位數(shù)差(interquartile range, IQR)，記為IQR.大于Q3+1.5×IQR或者小于Q1-1.5×IQR的值為異常值.IQR越小，表示數(shù)據(jù)越密集，波動性越小.為便于顯示，圖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%.另外，全局廣播鏈下，對同一種集合操作來說，不同通信模式下其延遲差異較大，這是因為不同通信模式下的多播組個數(shù)不同，而每個多播組都使用同一棵多播樹，導(dǎo)致不同通信模式下的鏈路EFI差異較大，測出的延遲差異也較大.相比而言，MR4LMS及2種C-MR4LMS-算法在不同通信模式下的延遲差異沒有這么明顯，這是因為這幾種算法可以將多播組分布到不同鏈路上.
2) 2種C-MR4LMS-算法的消息延遲與MR4LMS算法基本相當(dāng)，2 KB粒度的MPI_Bcast延遲甚至明顯低于MR4LMS.這與ibsim中的測試結(jié)果一致，即當(dāng)多播組個數(shù)較少時，C-MR4LMS算法的鏈路EFI低于MR4LMS算法，而2 KB粒度的集合消息對EFI較敏感.
3) C-MR4LMS-fixed與MR4LMS-dynamic算法的消息延遲差異不大，可以認(rèn)為是測試誤差及網(wǎng)絡(luò)噪音導(dǎo)致了這些差異.
4) 從圖11可以看出，4種路由算法在延遲數(shù)據(jù)的穩(wěn)定性方面差異不大.
本文也測試了3維環(huán)網(wǎng)及隨機(jī)加入多播組的情況，測試結(jié)果與表1及圖11類似，不再贅述.
綜上所述，當(dāng)大量多播組同時通信時，2種C-MR4LMS算法下集合消息的延遲明顯低于全局廣播鏈，而與MR4LMS算法相當(dāng).
5.2 開啟容錯時的集合消息性能
首先測試容錯功能的有效性.通過手工斷開某條鏈路制造故障，然后運(yùn)行上述基準(zhǔn)測試程序，發(fā)現(xiàn)全局廣播鏈、MR4LMS均存在收不到消息的情況，而2種C-MR4LMS算法下測試課題均能正常運(yùn)行.這表明開啟容錯功能后可以對網(wǎng)絡(luò)故障進(jìn)行透明容錯.
由于開啟容錯功能后，原來的1個多播數(shù)據(jù)包會被復(fù)制2份，可能會影響消息延遲.下面以C-MR4LMS-fixed為例分別測試關(guān)閉及打開容錯功能時的消息延遲，觀察容錯功能對消息性能的影響.圖12顯示了60×60通信模式下的測試結(jié)果.其中C-MR4LMS-fixed表示關(guān)閉容錯，C-MR4LMS-fixed-ft表示開啟容錯.可以發(fā)現(xiàn)：1)從延遲中位值的角度看，開啟容錯功能后MPI_Barrier,MPI_Allreduce的延遲略有下降，而MPI_Bcast的延遲略有上升.2)從分布范圍看，開啟容錯后延遲波動范圍略有降低，可以認(rèn)為有更低的尾延遲.
Fig. 12 Collective message latencies under C-MR4LMS-fixed with and without fault tolerance圖12 開啟及關(guān)閉容錯功能C-MR4LMS-fixed算法下的集合消息延遲
上述測試結(jié)果表明，多復(fù)制一份數(shù)據(jù)包并不會對消息延遲帶來顯著影響，反而會緩解因多個多播組相互干擾而帶來的性能波動.出現(xiàn)該現(xiàn)象的原因是：終端節(jié)點收到第1個數(shù)據(jù)包后就可做后續(xù)處理，因而可以忽略延后到達(dá)的多播包，一定程度上抵消網(wǎng)絡(luò)噪音對多播消息帶來的影響.
6 結(jié) 論
本文針對胖樹拓?fù)涮岢鲆环N高效實用的定制多播路由算法C-MR4LMS，在硬件僅支持很小的多播表時，能夠快速地為數(shù)千甚至數(shù)萬個多播組構(gòu)建多播路由.C-MR4LMS在構(gòu)建多播樹時，根據(jù)多播組的MGID靜態(tài)地將多播組映射到1棵生成樹中，這帶來了下列好處：1)可以快速選擇出樹根及顏色，從而快速完成多播樹的構(gòu)建；2)構(gòu)建出的多播樹是恒定不變的，重算多播路由不會改變多播樹；3)合并多播樹時，僅需合并使用同一生成樹的多播組，且僅需添加某些鏈路即可完成多播樹的合并，不會改變被合并的多播組的路由.而MR4LMS算法根據(jù)各多播鏈號的使用情況，動態(tài)創(chuàng)建多播樹，因而多播路由具有動態(tài)可變性，即在不同時刻、不同網(wǎng)絡(luò)狀態(tài)下為同一多播組構(gòu)建的多播樹可能不同.
實驗結(jié)果表明，當(dāng)多播組個數(shù)少于不沖突的生成樹個數(shù)時，C-MR4LMS算法在EFI,TFI方面與MR4LMS算法相當(dāng)，某些情況下甚至略優(yōu)于MR4LMS算法.隨著多播組個數(shù)的增多，C-MR4LMS算法需要進(jìn)行合并操作，而MR4LMS算法由于可以嘗試不同的樹根及顏色，不需要進(jìn)行大量合并操作，在EFI,TFI方面優(yōu)于C-MR4LMS算法.隨著多播組個數(shù)的進(jìn)一步增多，MR4LMS算法也需要進(jìn)行很多合并操作，此時C-MR4LMS算法大部分情況下又會優(yōu)于MR4LMS算法.可以認(rèn)為，很多情況下，C-MR4LMS算法在EFI,TFI方面優(yōu)于MR4LMS算法；而部分情況下，C-MR4LMS算法在EFI,TFI方面比MR4LMS算法差，但仍在可接受的范圍內(nèi).基準(zhǔn)測試程序也表明，在各種通信模式下，C-MR4LMS算法下的集合消息性能不比MR4LMS算法差，很多情況下還優(yōu)于MR4LMS算法；而在運(yùn)行時間方面，C-MR4LMS算法具有明顯的優(yōu)勢.
綜上所述，在胖樹中C-MR4LMS算法的性能可以匹敵MR4LMS算法，而其運(yùn)行時間相比MR4LMS算法有了顯著下降，能夠更好地滿足大規(guī)模并行應(yīng)用的需求.
另外，C-MR4LMS算法還有需要完善的地方：1)C-MR4LMS采用由用戶指定MGID的策略，因此需要用戶巧妙地選取MGID，這對用戶提出了很高的要求.未來，我們將提供工具幫助用戶完成該工作.2)目前C-MR4LMS面向拓?fù)湟阎呐謽洌绊懥似溥m用性.未來我們將做下列改進(jìn)：①自動感知網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，動態(tài)調(diào)整相關(guān)的網(wǎng)絡(luò)參數(shù)；②識別故障鏈路，并將使用該鏈路的生成樹標(biāo)記為不可用，從而在構(gòu)建多播路由時避開這些故障鏈路.但這會導(dǎo)致C-MR4LMS遇到與MR4LMS一樣的難題：多播路由受網(wǎng)絡(luò)狀態(tài)的影響，具有動態(tài)多變性，需要在多播路由的穩(wěn)定性與適用性這兩者間進(jìn)行適當(dāng)?shù)钠胶?
作者貢獻(xiàn)聲明：陳淑平提出研究思路，設(shè)計并實現(xiàn)算法，進(jìn)行試驗并對實驗數(shù)據(jù)進(jìn)行分析，撰寫并修改論文；李祎參與算法實現(xiàn)、實驗驗證和數(shù)據(jù)分析；何王全參與實驗數(shù)據(jù)分析，論文審閱與修訂；漆鋒濱對課題進(jìn)行監(jiān)管與指導(dǎo)，并審閱與修訂論文.
猜你喜歡
小學(xué)科學(xué)(學(xué)生版)(2021年10期)2021-12-28
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2021年9期)2021-10-14
少兒畫王（7-10）(2020年11期)2020-09-13
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2019年9期)2019-09-25
網(wǎng)絡(luò)安全和信息化(2019年7期)2019-07-10
電子制作(2019年24期)2019-02-23
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級)(2018年9期)2018-09-26
小溪流（畫刊）(2018年3期)2018-06-29
中國公共安全(2017年11期)2017-02-06
