用于超大Infiniband網(wǎng)絡(luò)的負(fù)載均衡多播路由

陳淑平，周慧霖，何王全，漆鋒濱

1.江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083

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

近年來(lái)，隨著高性能計(jì)算即將邁入E級(jí)時(shí)代，超級(jí)計(jì)算機(jī)的規(guī)模變得越來(lái)越大，擁有的處理器數(shù)及核心數(shù)越來(lái)越多。例如，2020年6月份全球Top500排名第一的富岳系統(tǒng)[1-2]擁有7 299 072個(gè)核心。與之相應(yīng)，高性能計(jì)算應(yīng)用的性能越來(lái)越依賴于互連網(wǎng)絡(luò)的性能，尤其是集合通信的性能[3-5]。集合通信可以通過點(diǎn)對(duì)點(diǎn)消息實(shí)現(xiàn)，也可以通過專用的硬件集合操作實(shí)現(xiàn)。很長(zhǎng)一段時(shí)間以來(lái)，無(wú)論是在廣域網(wǎng)還是在數(shù)據(jù)中心網(wǎng)絡(luò)中，硬件支持的集合操作由于其復(fù)雜度、可擴(kuò)展性、容錯(cuò)等方面的原因，并未得到廣泛應(yīng)用。因此MPICH、MVAPICH、OpenMPI等[6-9]均基于點(diǎn)到點(diǎn)消息以軟件方式實(shí)現(xiàn)集合通信。但是，基于點(diǎn)到點(diǎn)消息實(shí)現(xiàn)的集合操作，其性能與硬件支持的集合操作相比存在不小的差距。一是同樣的數(shù)據(jù)包在某些鏈路上會(huì)傳輸多次，造成資源浪費(fèi)。二是缺乏獲取底層網(wǎng)絡(luò)拓?fù)湫畔⒌哪芰Γ沟眉喜僮鞯倪壿嫿Y(jié)構(gòu)不能適配底層網(wǎng)絡(luò)的物理結(jié)構(gòu)，導(dǎo)致其無(wú)法充分利用底層網(wǎng)絡(luò)的傳輸能力。隨著系統(tǒng)規(guī)模的不斷擴(kuò)大，以軟件方式實(shí)現(xiàn)的集合操作面臨越來(lái)越嚴(yán)重的性能問題。而硬件支持的集合操作具有性能高、CPU占用率低等優(yōu)點(diǎn)，正受到越來(lái)越多的關(guān)注。因此，近幾年出現(xiàn)了很多硬件集合通信技術(shù)，如Mellanox的SHARP技術(shù)[10]。

硬件支持的集合操作中，多播技術(shù)是重要的支撐。集合通信中的Bcast、Barrier、AllReduce、AllGather等操作需要將相同的數(shù)據(jù)分發(fā)給參與集合通信的不同進(jìn)程，它們均可通過硬件支持的多播進(jìn)行加速。多播路由算法對(duì)多播操作的性能具有至關(guān)重要的影響。Infiniband網(wǎng)絡(luò)中，子網(wǎng)管理OpenSM[11-12]負(fù)責(zé)生成多播表，基本原理是構(gòu)建一棵多播樹覆蓋參與多播操作的所有節(jié)點(diǎn)，利用多播樹實(shí)現(xiàn)多播功能。多播樹的高度及負(fù)載均衡性對(duì)多播消息的性能具有決定性的影響。多播路由算法的設(shè)計(jì)目標(biāo)包括：盡量降低多播樹高度，以降低多播操作延遲；在不同多播組間進(jìn)行負(fù)載均衡，以降低單條鏈路的負(fù)載；縮短計(jì)算路由的的時(shí)間，以滿足快速構(gòu)建大量多播組的需求。

OpenSM目前支持9種路由算法，它們使用的多播路由方法概括起來(lái)分為2類，分別是MINIHOP-MC及SSSP-MC。它們?cè)诖笠?guī)模互連網(wǎng)絡(luò)環(huán)境下均存在問題。MINIHOP-MC算法在構(gòu)建多播樹時(shí)根據(jù)最小跳表從所有交換機(jī)中選出一個(gè)到多播組內(nèi)各成員最大距離最小者作為多播樹的根，因此構(gòu)建出的多播樹高度必定是最低的；但該算法未考慮多播路由均衡性問題，會(huì)出現(xiàn)大量多播組共用同一條鏈路甚至同一個(gè)樹根的情況，嚴(yán)重影響多播消息的性能。而基于單源最短路徑的SSSP-MC算法雖然考慮了多播路由均衡性，但該算法不管多播組有多少個(gè)成員都需要計(jì)算樹根到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的最短路徑，因此構(gòu)建路由表的時(shí)間開銷很大，不能滿足存在大量多播組的應(yīng)用場(chǎng)景的需求。綜上所述，這兩種多播路由算法均不適用于大規(guī)模互連網(wǎng)絡(luò)環(huán)境。

為此，本文提出一種負(fù)載均衡的多播路由算法，試圖在大規(guī)模互連網(wǎng)絡(luò)環(huán)境中快速構(gòu)建負(fù)載均衡的多播路由。該算法采用2種負(fù)載均衡策略，根據(jù)局部負(fù)載信息進(jìn)行多播路由選擇，在保證多播樹高度最低的前提下，盡量將不同多播組分散到不同鏈路上，可應(yīng)用于存在大量多播組的超大規(guī)模互連網(wǎng)絡(luò)環(huán)境中。

1 概念及定義

1.1 基本概念

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

定義2（多播組，MCG）多播組是網(wǎng)絡(luò)節(jié)點(diǎn)集N的一個(gè)子集，其成員可以是終端節(jié)點(diǎn)，也可以是交換機(jī)。一個(gè)多播組中的成員發(fā)送的消息可以被同一多播組中的其他成員接收。每個(gè)多播組用multicast GID（MGID）標(biāo)識(shí)。

定義3（多播樹，MCT）多播樹是互連網(wǎng)絡(luò)有向圖的一個(gè)子圖，對(duì)應(yīng)互連網(wǎng)絡(luò)中的一棵樹。該樹內(nèi)的一個(gè)節(jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，會(huì)復(fù)制到該樹內(nèi)的所有節(jié)點(diǎn)中。

定義4（edge forwarding index，EFI）文獻(xiàn)[13-14]將EFI定義為經(jīng)過某鏈路的路由條數(shù)。在多播路由中，將其定義為經(jīng)過該鏈路的多播組個(gè)數(shù)。最大鏈路EFI記為一定程度上反映了路由均衡程度。π(G,R)越大，表示擁塞程度越高。鏈路EFI對(duì)多播操作性能具有重要影響，多播路由算法需要盡量降低鏈路EFI。

定義5（最小跳表）每個(gè)交換機(jī)都有一張最小跳表，邏輯上組織成二維表格形式，行號(hào)為i、列號(hào)為j的單元記錄了從該交換機(jī)的端口j出發(fā)到LID為i的目標(biāo)節(jié)點(diǎn)的最小跳步數(shù)。j為0時(shí)記錄的是所有端口中到LID為i的目標(biāo)節(jié)點(diǎn)的最小跳步數(shù)。在完成拓?fù)涮讲楹螅琌penSM利用獲取到的連接信息為每個(gè)交換機(jī)構(gòu)建最小跳表。

1.2 影響多播消息性能的因素

多播操作的性能受多播樹高度及鏈路EFI等的影響。僅考慮一個(gè)多播組時(shí)，多播樹高度對(duì)集合操作性能至關(guān)重要。當(dāng)網(wǎng)絡(luò)中有多個(gè)多播組同時(shí)收發(fā)消息時(shí)，鏈路EFI對(duì)集合操作的性能也有重大影響。下面將通過實(shí)驗(yàn)說明，多播樹高度及鏈路EFI都會(huì)對(duì)多播操作的性能產(chǎn)生重要影響。

1.2.1 多播樹高度

多播樹高度會(huì)影響集合操作的延遲。多播樹越高，多播數(shù)據(jù)包的傳輸路徑就越長(zhǎng)，其延遲就越大。構(gòu)建了如圖1所示的實(shí)驗(yàn)環(huán)境，分別進(jìn)行了2組測(cè)試。每組測(cè)試均使用4個(gè)進(jìn)程構(gòu)成的多播組進(jìn)行多播操作，但每組測(cè)試中的進(jìn)程距離不同。第一組測(cè)試中，4個(gè)進(jìn)程位于物理臨近的終端節(jié)點(diǎn)上，其對(duì)應(yīng)的多播樹高度為1。第二組測(cè)試中，4個(gè)進(jìn)程分散在不同交換機(jī)上，對(duì)應(yīng)的多播樹高度為2。在每組測(cè)試中都對(duì)各種長(zhǎng)度的消息進(jìn)行5 000次測(cè)試，分別計(jì)算平均延遲及99%消息尾延遲。其中99%消息尾延遲的計(jì)算方法為：對(duì)這5 000個(gè)消息的延遲進(jìn)行排序，取末尾第4 950（5 000×99%）個(gè)消息的延遲。

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

測(cè)試結(jié)果如表1所示。可以發(fā)現(xiàn)，無(wú)論是8 B長(zhǎng)度的小消息，還是2 KB長(zhǎng)度的大消息，第二組測(cè)試的延遲數(shù)據(jù)較第一組測(cè)試均有明顯增加。這表明多播樹高度對(duì)多播消息延遲具有不可忽視的影響。可以預(yù)見，隨著廣播樹高度的增大，延遲增加會(huì)更加明顯。另外，消息長(zhǎng)度不同，延遲增大的幅度略有差異，長(zhǎng)度較大的消息與長(zhǎng)度較小的消息相比，其延遲增長(zhǎng)幅度小。對(duì)8 B長(zhǎng)度的小消息來(lái)說，無(wú)論是平均值還是99%尾延遲都增長(zhǎng)了約20%；對(duì)2 KB長(zhǎng)度的消息來(lái)說，平均值及99%尾延遲增長(zhǎng)幅度均在15%左右。這是因?yàn)閷?duì)長(zhǎng)消息來(lái)說，增加的跳步數(shù)導(dǎo)致的時(shí)間開銷相比數(shù)據(jù)拷貝的時(shí)間開銷小。

表1 不同樹高下的多播消息延遲Table 1 Multicast message latency for different tree height μs

1.2.2 鏈路EFI

當(dāng)有大量多播組經(jīng)過同一條鏈路，從而使該鏈路的EFI變得很大時(shí)，集合操作的性能會(huì)受到較大影響。構(gòu)建了如圖2所示的實(shí)驗(yàn)環(huán)境，以說明鏈路EFI對(duì)多播消息性能的影響程度。該實(shí)驗(yàn)中，每4個(gè)相鄰的終端節(jié)點(diǎn)組成一個(gè)多播組，但所有多播組都使用粗線所示的同一棵多播樹，因此鏈路EFI等于創(chuàng)建的多播組的個(gè)數(shù)。例如，EFI為1，表示僅使用4個(gè)終端節(jié)點(diǎn)，創(chuàng)建1個(gè)多播組；EFI為128，表示使用512個(gè)終端節(jié)點(diǎn)，創(chuàng)建128個(gè)多播組。當(dāng)創(chuàng)建了多個(gè)多播組時(shí)，由于這些多播組共用同一棵多播樹，一個(gè)多播組發(fā)送的數(shù)據(jù)會(huì)復(fù)制到使用同一多播樹的其他多播組內(nèi)，從而對(duì)其他多播組的性能帶來(lái)影響。分別測(cè)試了不同EFI下多播操作的延遲，每種EFI下各多播組同時(shí)發(fā)送消息，均進(jìn)行5 000次測(cè)試，分別計(jì)算平均延遲及99%消息尾延遲。結(jié)果如表2所示。

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

表2 不同EFI下的多播消息延遲Table 2 Multicast message latency for different EFI μs

可以發(fā)現(xiàn)，對(duì)8 B長(zhǎng)度的小消息來(lái)說，隨著EFI的增加，延遲會(huì)略有增加，但是由于數(shù)據(jù)長(zhǎng)度很小，即使有多個(gè)廣播組經(jīng)過同一條鏈路，也不會(huì)對(duì)延遲造成很大影響。而對(duì)2 KB消息來(lái)說，由于數(shù)據(jù)較大，EFI增大帶來(lái)的影響會(huì)比較明顯。例如EFI為16時(shí)，平均延遲會(huì)增大約38%；EFI為128時(shí)，平均延遲會(huì)增大約1 066%。因此，鏈路EFI會(huì)對(duì)大量使用廣播操作的應(yīng)用程序性能帶來(lái)重要影響。

結(jié)合上面2個(gè)實(shí)驗(yàn)的結(jié)果，給出多播路由算法的設(shè)計(jì)目標(biāo)，包括：（1）最小化多播樹的高度，以降低多播消息延遲；（2）盡量降低鏈路EFI，使不同多播組盡量分布到不同鏈路上，降低不同多播組間的相互干擾；（3）構(gòu)建多播路由算法的時(shí)間開銷要盡量低，以滿足超大規(guī)模互連網(wǎng)絡(luò)中快速創(chuàng)建大量多播組的需求。對(duì)多播路由算法的評(píng)價(jià)也是從上述3個(gè)方面進(jìn)行的。

2 IB中現(xiàn)有的多播路由算法

OpenSM目前支持MINIHOP、UP/DN、DN/UP、FTREE、LASH[15-16]、DOR、TORUS-2QoS、NUE[17]、DFSSSP[18-19]等9種路由引擎。它們使用的多播路由算法概括起來(lái)分為2類，分別是MINIHOP-MC及SSSP-MC。兩者都是從樹根開始自頂向下構(gòu)建多播樹，區(qū)別在于MINIHOP-MC是基于最小跳表構(gòu)建多播樹，而SSSP-MC是基于單源最短路徑算法構(gòu)建多播樹。

2.1 MINIHOP-MC

MINIHOP-MC基于最小跳表構(gòu)建多播樹。為某個(gè)多播組構(gòu)建多播樹時(shí)，分為兩個(gè)步驟。

一是選擇一個(gè)交換機(jī)作為樹根，選擇的依據(jù)是樹根到多播組各成員的最大距離或平均距離在所有交換機(jī)中是最小的。

二是根據(jù)最小跳表，從樹根出發(fā)自頂向下遞歸地構(gòu)建一棵樹。具體過程如下：（1）從樹根開始，對(duì)多播組的每個(gè)成員mcm，都查詢樹根的最小跳表中對(duì)應(yīng)mcm的行，找出跳數(shù)最小的端口，然后將mcm加入該端口對(duì)應(yīng)的子樹，從而將各成員分到不同子樹中。（2）然后對(duì)每個(gè)子樹，遞歸進(jìn)行上述過程，將屬于該子樹的多播組成員劃分為更小的子樹，直到子樹不能再拆分為止。

偽代碼描述的構(gòu)建過程見算法1。

算法1 MINIHOP-MC

MINIHOP-MC產(chǎn)生的多播樹一定是高度最低的。另外，代碼第8行在選擇下行端口時(shí)，如果同時(shí)存在多個(gè)跳步數(shù)最少的端口，則只能選擇固定的一個(gè)端口，而不能通過負(fù)載均衡機(jī)制將多播包分發(fā)到多條路徑上，否則會(huì)形成環(huán)。MINIHOP-MC也沒有考慮多個(gè)多播組間的負(fù)載均衡問題，即多個(gè)多播組可能共用同一個(gè)根或同一條鏈路，在存在大量多播組時(shí)，這會(huì)帶來(lái)嚴(yán)重的性能問題。

2.2 SSSP-MC

SSSP-MC基于單源最短路徑算法構(gòu)建多播路由，一定程度上考慮了負(fù)載均衡問題。當(dāng)選擇樹根后，SSSP-MC以網(wǎng)絡(luò)中的所有交換機(jī)作為節(jié)點(diǎn)，以經(jīng)過各鏈路的多播組個(gè)數(shù)作為權(quán)重，利用單源最短路徑算法算法（如Dijkstra）計(jì)算樹根到所有節(jié)點(diǎn)的單源最短路徑，從而構(gòu)造出一棵樹。為保證從樹根到各節(jié)點(diǎn)的路徑都是最短路徑，需要為每個(gè)鏈路設(shè)置一個(gè)足夠大的初始權(quán)值，使得選擇長(zhǎng)路徑永遠(yuǎn)比選擇負(fù)載重的路徑代價(jià)高。偽代碼描述的SSSP-MC算法見算法2。

算法2 SSSP-MC

SSSP-MC可以將多播組分布到不同的鏈路上；缺點(diǎn)是運(yùn)行時(shí)間較長(zhǎng)，不適用于超大規(guī)模互連網(wǎng)絡(luò)。原因是不管多播組有多少個(gè)成員，SSSP-MC都需要計(jì)算樹根到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的最短路徑。因此對(duì)互連網(wǎng)絡(luò)G(N,C)來(lái)說，SSSP-MC算法的時(shí)間復(fù)雜度為Θ( ||C+ ||N lb ||N)，僅跟網(wǎng)絡(luò)規(guī)模有關(guān)，而跟多播組大小無(wú)關(guān)。

2.3 實(shí)際課題中多播組使用模式

MPI集合通信中，主要有2種通信域劃分方法，一是將所有進(jìn)程劃分成二維或三維網(wǎng)格，每個(gè)維度中每行都是一個(gè)通信域，對(duì)應(yīng)一個(gè)多播組。二是劃分成層次結(jié)構(gòu)，例如樹型結(jié)構(gòu)，每層分成很多組，每個(gè)組構(gòu)成一個(gè)通信域；每個(gè)組再選出一個(gè)leader，形成更高層次的組。在大規(guī)模互連網(wǎng)絡(luò)環(huán)境下，按上述兩種通信域劃分方法劃分進(jìn)程時(shí)，都會(huì)產(chǎn)生大量多播組，而每個(gè)多播組內(nèi)的成員個(gè)數(shù)卻較少。當(dāng)系統(tǒng)中存在大量規(guī)模較小的多播組時(shí)，MINIHOP-MC及SSSP-MC這兩種多播路由算法均存在問題。對(duì)MINIHOP-MC來(lái)說，由于沒有進(jìn)行負(fù)載均衡，存在大量多播組共用同一條鏈路的情況，從而導(dǎo)致嚴(yán)重的性能問題。對(duì)SSSP-MC來(lái)說，雖然多播組很小，仍需計(jì)算樹根到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的最短路徑，導(dǎo)致創(chuàng)建多播組的時(shí)間很長(zhǎng)，不能滿足大規(guī)模互連網(wǎng)絡(luò)的需求（后面實(shí)驗(yàn)將會(huì)看到，有時(shí)需要數(shù)幾分鐘才能完成所有多播組的創(chuàng)建）。因此，這兩種路由算法均不適用于大規(guī)模互連網(wǎng)絡(luò)環(huán)境。

需要一種適用于各種拓?fù)洌軌蜃詣?dòng)進(jìn)行負(fù)載均衡，且運(yùn)行速度足夠快的多播路由算法，以適應(yīng)大規(guī)模互連網(wǎng)絡(luò)中應(yīng)用程序的使用模式。

3 FULB-MC多播路由算法

本章將描述一種負(fù)載均衡的通用快速多播路由算法FULB-MC。與現(xiàn)有多播算法的重要區(qū)別在于，F(xiàn)ULBMC采用樹根輪換及鏈路輪換策略進(jìn)行負(fù)載均衡。另外，為了適應(yīng)HPC環(huán)境，提出了新的多播組加入、離開機(jī)制及協(xié)議。FULB-MC還采用自底向上構(gòu)建多播樹的方法，目的是在避免形成環(huán)的同時(shí)提升算法運(yùn)行速度。

3.1 自底向上的多播樹構(gòu)造方法

MINIHOP-MC及SSSP-MC均是從樹根開始自頂向下構(gòu)建多播樹。而FULB-MC在選擇樹根之后，采用自底向上構(gòu)建多播樹的策略，目的是在避免形成環(huán)的同時(shí)提升算法運(yùn)行速度。FULB-MC與MINIHOP-MC相似，均是基于最小跳表構(gòu)建多播樹。與MINIHOP-MC不同，F(xiàn)ULB-MC通過2種簡(jiǎn)單的策略在多個(gè)多播組間進(jìn)行負(fù)載均衡。

（1）樹根輪換策略：在選擇樹根時(shí)，如果有多個(gè)交換機(jī)滿足條件，則根據(jù)交換機(jī)的負(fù)載情況從中選擇一個(gè)負(fù)載最輕的。

（2）鏈路輪換策略：選擇樹根后，每次從多播組的一個(gè)成員出發(fā)，根據(jù)最小跳表選擇一條從該成員到樹根的最短路徑。每次經(jīng)過一個(gè)交換機(jī)選擇下一跳時(shí)，如果有多個(gè)端口都是跳步數(shù)最少的，則從中選擇一個(gè)負(fù)載最輕的。為避免產(chǎn)生環(huán)，在從葉子到樹根的前進(jìn)過程中，如果遇到了以前訪問過的節(jié)點(diǎn)，則重用以前構(gòu)建的該中間節(jié)點(diǎn)到樹根的路徑。

偽代碼描述的算法如下所示。hops是交換機(jī)的最小跳表，hops[root][0]記錄的是所有端口中到樹根的跳步數(shù)的最小值。代碼第1到19行選擇一個(gè)交換機(jī)作為樹根。第20到33行為每個(gè)多播組成員構(gòu)建一條到樹根的最短路徑。

算法3 FULB-MC

FULB-MC構(gòu)建的多播樹一定是高度最低的。另外，它使用貪心策略，無(wú)論是選擇樹根，還是選擇多播鏈路時(shí)，總是根據(jù)局部負(fù)載信息進(jìn)行負(fù)載均衡決策。而SSSP-MC算法則根據(jù)全局信息進(jìn)行負(fù)載均衡決策。后面的實(shí)驗(yàn)中將會(huì)看到，F(xiàn)ULB-MC算法雖然使用局部信息進(jìn)行負(fù)載均衡決策，仍可以達(dá)到很好的負(fù)載均衡效果。

FULB-MC算法的運(yùn)行時(shí)間與多播組的大小有關(guān)。當(dāng)存在大量規(guī)模很小的多播組時(shí)，相比SSSP-MC，這將節(jié)省大量計(jì)算時(shí)間。不考慮選擇樹根的時(shí)間，在最壞情況下，其運(yùn)行時(shí)間上限為O( ||E+ ||N)，即訪問每個(gè)節(jié)點(diǎn)及每條鏈路各一次。

3.2 多播成員加入/離開機(jī)制

IB協(xié)議中原有的多播機(jī)制并不適用于HPC領(lǐng)域。原因是：多播組成員可以動(dòng)態(tài)加入或離開多播組，導(dǎo)致每次多播組成員發(fā)生變化后都需要重新計(jì)算、更新路由，使多播路由處于暫時(shí)不可用狀態(tài)的概率大大增加。

針對(duì)高性能計(jì)算應(yīng)用的需求，設(shè)計(jì)了一套新的加入/離開多播組機(jī)制，以解決頻繁重算路由的問題。加入多播組時(shí)，不是每收到一個(gè)加入多播組的請(qǐng)求就計(jì)算路由，而是等收齊同一個(gè)多播組的所有請(qǐng)求之后再計(jì)算路由。一個(gè)成員離開多播組后，也不重算路由；僅當(dāng)所有成員均離開后，再刪掉該多播組。

如圖3所示，構(gòu)建一個(gè)多播組需要4個(gè)步驟：

圖3 加入多播組的過程Fig.3 Process used to join multicast group

（1）所有進(jìn)程都向Open SM發(fā)送Subn AdmSet（MCMemberRecord），以請(qǐng)求加入多播組。請(qǐng)求中攜帶了參與該多播組的成員個(gè)數(shù)。需要修改IB協(xié)議的McMemberRecord屬性，添加MemberCount字段，以記錄該多播組中的成員數(shù)量。

（2）OpenSM收到第一個(gè)請(qǐng)求后，創(chuàng)建多播組，但不會(huì)立即計(jì)算多播路由。僅當(dāng)收齊該多播組的所有請(qǐng)求后，才開始計(jì)算多播路由。

（3）0號(hào)進(jìn)程發(fā)出加入多播組的請(qǐng)求后，周期性地向OpenSM發(fā)送SubnAdmGet（MCGStateRecord）以查詢多播組狀態(tài)。需要對(duì)現(xiàn)有的IB協(xié)議進(jìn)行擴(kuò)展，增加MCGStateRecord屬性，用于報(bào)告多播組的狀態(tài)。多播組可處于下列狀態(tài)：①ReceivingJoinReq，表示正在接收加入多播組的請(qǐng)求；②ComputingRoutes，表示正在計(jì)算路由；③Ready，表示路由已計(jì)算完畢，可以使用該多播組發(fā)送數(shù)據(jù)；④ReceivingLeaveReq，表示正在接收離開多播組的請(qǐng)求；⑤Destroying，表示該多播組正在被銷毀。

OpenSM計(jì)算完多播路由后，向0號(hào)進(jìn)程返回SubnAdm-GetResp（MCGStateRecord）應(yīng)答，其狀態(tài)為Ready。

（4）0號(hào)進(jìn)程收到多播組可用的通知后，通過多播操作將通知轉(zhuǎn)發(fā)給其他進(jìn)程，從而完成多播組的構(gòu)建。每個(gè)進(jìn)程在收到該通知后，即可使用該多播組進(jìn)行通信。

OpenSM負(fù)責(zé)維護(hù)每個(gè)多播組的狀態(tài)，其狀態(tài)轉(zhuǎn)換圖見圖4。由于某個(gè)進(jìn)程崩潰或加入多播組的請(qǐng)求丟失而導(dǎo)致OpenSM不能在規(guī)定時(shí)間內(nèi)收齊加入多播組的請(qǐng)求時(shí)，該多播組則由ReceivingJoinRequest狀態(tài)轉(zhuǎn)到Destroying狀態(tài)，并開始銷毀該多播組。同樣，在ReceivingLeaveReq狀態(tài)下未在規(guī)定時(shí)間內(nèi)收齊離開多播組的請(qǐng)求，則轉(zhuǎn)為Destroying狀態(tài)，銷毀該多播組。

圖4 多播組狀態(tài)轉(zhuǎn)換示意圖Fig.4 State transition diagram for multicast group

4 實(shí)驗(yàn)評(píng)價(jià)

在OpenSM中實(shí)現(xiàn)了FULB-MC。本章將在不同拓?fù)浣Y(jié)構(gòu)下對(duì)FULB-MC的性能進(jìn)行測(cè)試，這些拓?fù)浣Y(jié)構(gòu)包括幾種典型的標(biāo)準(zhǔn)拓?fù)浣Y(jié)構(gòu)（包括標(biāo)準(zhǔn)胖樹[20-21]、3D環(huán)網(wǎng)、蜻蜓網(wǎng)絡(luò)[22]等），以及2個(gè)超算中心實(shí)際使用的拓?fù)洹Ｊ褂胕bsim-0.7模擬各種網(wǎng)絡(luò)拓?fù)洌褂脺y(cè)試程序模擬發(fā)起加入或離開多播組的請(qǐng)求。OpenSM的版本號(hào)為3.3.22，運(yùn)行在一臺(tái)x86服務(wù)器上，處理器為32核Intel Xeon E5-2630 v3，頻率為2.40 GHz。

實(shí)驗(yàn)中，每個(gè)處理器上運(yùn)行一個(gè)或多個(gè)進(jìn)程。與實(shí)際課題通信模式一樣，將這些進(jìn)程劃分成不同的通信組，為每個(gè)通信組建立一個(gè)多播組。一個(gè)進(jìn)程可同時(shí)參與多個(gè)通信組，例如，當(dāng)按三維網(wǎng)格結(jié)構(gòu)劃分通信組時(shí)，每個(gè)進(jìn)程將參與3個(gè)多播組。對(duì)每種拓?fù)浣Y(jié)構(gòu)，都測(cè)試了多種典型的多播通信模式，包括二維網(wǎng)格、三維網(wǎng)格，以及隨機(jī)產(chǎn)生的多播組。其中部分通信模式按拓?fù)浣Y(jié)構(gòu)劃分進(jìn)程，模擬拓?fù)涓兄耐ㄐ判袨椋硗獾耐ㄐ拍Ｊ絼t模擬拓?fù)錈o(wú)感的通信行為。

4.1 典型的標(biāo)準(zhǔn)拓?fù)浣Y(jié)構(gòu)

4.1.1 3層標(biāo)準(zhǔn)胖樹

采用40端口交換機(jī)構(gòu)建標(biāo)準(zhǔn)3層胖樹結(jié)構(gòu)，終端節(jié)點(diǎn)個(gè)數(shù)N=16 000。表3顯示了每個(gè)處理器上運(yùn)行1個(gè)進(jìn)程時(shí)各種多播路由算法的最大EFI。

表3 3層胖樹下各路由算法的最大EFITable 3 Maximum EFI of each algorithm under 3-layer FT

可以看出，在所有通信模式下，MINIHOP-MC及SSSP-MC的最大EFI都遠(yuǎn)遠(yuǎn)大于FULB-MC。出現(xiàn)該現(xiàn)象的原因是：MINIHOP-MC及SSSP-MC在選擇樹根時(shí)，總是使用第一個(gè)滿足樹高最低條件的交換機(jī)，導(dǎo)致大量多播組使用同一個(gè)樹根。另外，MINIHOP-MC與SSSP-MC在所有通信模式下最大EFI均相同。這是由標(biāo)準(zhǔn)胖樹的結(jié)構(gòu)決定的：葉子交換機(jī)與頂層交換機(jī)間僅有一條最短路徑，只要選擇的樹根相同，則它們構(gòu)建的多播樹完全相同。SSSP-MC雖然利用Dijkstra算法進(jìn)行了大量運(yùn)算，但最終效果跟MINIHOP-MC完全一樣。

后面測(cè)試中，對(duì)原始MINIHOP-MC及SSSP-MC算法進(jìn)行了修改：與FULB-MC一樣，在有多個(gè)根可供選擇時(shí)，從中選擇負(fù)載最輕的一個(gè)。修改后的算法分別稱為MINIHOP-MC-new及SSSP-MC-new。后面的測(cè)試中，原始MINIHOP-MC及SSSP-MC算法的最大EFI均很大，不再贅述其測(cè)試結(jié)果，而僅顯示改進(jìn)后的MINIHOPMC-new及SSSP-MC-new算法下的測(cè)試結(jié)果。標(biāo)準(zhǔn)胖樹中MINIHOP-MC-new及SSSP-MC-new算法在每種通信模式下的最大EFI與FULB-MC完全相同，不再顯示其結(jié)果。

表4顯示了每個(gè)處理器上運(yùn)行1個(gè)進(jìn)程時(shí)各路由算法的運(yùn)行時(shí)間。FULB-MC明顯低于SSSP-MC，由最大2.4 s縮短為低于0.2 s。需要指出的是，該時(shí)間僅包括計(jì)算路由的時(shí)間，不包括發(fā)送加入多播組請(qǐng)求、選擇樹根、分發(fā)路由等其他步驟的時(shí)間。

表4 3層胖樹下各路由算法的運(yùn)行時(shí)間Table 4 Runtime of each algorithm under 3-layer FT s

4.1.2 3D-Torus

構(gòu)造了30×20×20的3D-Torus網(wǎng)絡(luò)，每個(gè)交換機(jī)連接2個(gè)終端節(jié)點(diǎn)，終端節(jié)點(diǎn)個(gè)數(shù)為N=24 000。表5及表6分別顯示了每個(gè)處理器上運(yùn)行1個(gè)進(jìn)程時(shí)的最大EFI及運(yùn)行時(shí)間。在運(yùn)行時(shí)間方面，F(xiàn)ULB-MC遠(yuǎn)低于SSSP-MC-new，由最大24 s縮短為低于2.3 s。

表5 3D-Torus下各路由算法的最大EFITable 5 Maximum EFI of each algorithm under 3D-Torus

表6 3D-Torus下各路由算法的運(yùn)行時(shí)間Table 6 Runtime of each algorithm under 3D-Toruss

在3D-Torus中，多播組成員到樹根的最短路徑有多條，因此大部分通信模式下FULB-MC及SSSP-MC-new可以獲得低于MINIHOP-MC-new的最大EFI。但在240×100通信模式下，MINIHOP-MC-new的EFI反而低于另外2種負(fù)載均衡算法。這是因?yàn)樵撏ㄐ拍Ｊ脚c網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)正好匹配，使得MINIHOP-MC分配的多播樹正好是最優(yōu)的；而SSSP-MC-new及FULB-MC在做路由均衡時(shí)，不是從全局的角度優(yōu)化EFI，而僅僅是從當(dāng)前新創(chuàng)建多播組的角度優(yōu)化EFI，在某些時(shí)刻會(huì)選擇非最優(yōu)的路徑。

以一個(gè)例子進(jìn)行更直觀的解釋。如圖5所示，淺灰色交換機(jī)是某個(gè)多播組的成員，深黑色交換機(jī)是其樹根，（a）、（b）分別是兩棵多播樹。可以看出（a）經(jīng)過的鏈路數(shù)較少，（b）經(jīng)過的鏈路數(shù)較多。SSSP-MC-new及FULB-MC在做路由均衡時(shí)，可能構(gòu)造出如（b）所示的多播樹，進(jìn)而導(dǎo)致EFI升高。而MINIHOP-MC-new使用固定的一條路徑，有可能恰好避開這些代價(jià)高的路徑。實(shí)際上，MINIHOP-MC-new也有可能固定使用圖5（b）所示的多播樹，從而恰好每次都選擇代價(jià)高的路徑。徑則經(jīng)過2條全局鏈路，選擇后面那條路徑可能會(huì)導(dǎo)致全局鏈路的擁塞，從而出現(xiàn)了SSSP-MC-new及FULBMC的EFI略高于MINIHOP-MC-new的情況。但是，如果修改MINIHOP-MC-new的實(shí)現(xiàn)，使其優(yōu)先使用編號(hào)大的端口，則MINIHOP-MC會(huì)使用第二條路徑，導(dǎo)致其最大EFI大于另外兩種路由算法。出現(xiàn)該現(xiàn)象的根本原因在于SSSP-MC-new及FULB-MC在做路由均衡時(shí)，不是從全局的角度優(yōu)化EFI。

圖5 3D環(huán)網(wǎng)下為同一個(gè)多播組構(gòu)建的兩棵多播樹Fig.5 Two multicast trees for same MCG in 3D-Torus

4.1.3 蜻蜓網(wǎng)絡(luò)

配置參數(shù)為a=18,p=h=9，即每個(gè)組中有18個(gè)交換機(jī)，每個(gè)交換機(jī)連接9個(gè)處理器，有9條全局鏈路，終端節(jié)點(diǎn)個(gè)數(shù)N=26 406。最大EFI及運(yùn)行時(shí)間分別見表7、表8。與前面測(cè)試結(jié)果一樣，在運(yùn)行時(shí)間方面，F(xiàn)ULB-MC遠(yuǎn)低于SSSP-MC-new。

表7 蜻蜓網(wǎng)絡(luò)下各路由算法的最大EFITable 7 Maximum EFI of each algorithm under DF network

表8 蜻蜓網(wǎng)絡(luò)下各路由算法的運(yùn)行時(shí)間Table 8 Runtime of each algorithm under DF networks

蜻蜓網(wǎng)絡(luò)中，多播組成員到樹根的最短路徑可能有多條。但很多情況下，MINIHOP-MC-new的EFI反而比另外2種算法略低。例如，在81×27×12模式下，MINIHOP-MC-new的最大EFI為41，而FULB-MC達(dá)到了54。這是由蜻蜓網(wǎng)絡(luò)特殊的拓?fù)浣Y(jié)構(gòu)導(dǎo)致的。如圖6所示，Group 0內(nèi)交換機(jī)B下連接的終端節(jié)點(diǎn)與Group 1內(nèi)交換機(jī)X下連接的終端節(jié)點(diǎn)通信時(shí)，有2條最短路徑，分別為B→D→E→X以及B→A→C→X。本文的實(shí)現(xiàn)中，MINIHOP-MC優(yōu)先使用編號(hào)小的端口，而B→D的鏈路使用的端口號(hào)小于B→A的鏈路使用的端口號(hào)，因此MINIHOP-MC-new使用第一條路徑。而SSSP-MC-new及FULB-MC輪流使用這兩條路徑；但實(shí)際上，在這兩條路徑間進(jìn)行負(fù)載均衡有時(shí)不會(huì)帶來(lái)好處，因?yàn)榈谝粭l路徑僅經(jīng)過一條全局鏈路，而第二條路

圖6 蜻蜓網(wǎng)絡(luò)下B到X的兩條路徑Fig.6 Two paths from B to X in Dragonfly network

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

上面測(cè)試中，已經(jīng)驗(yàn)證了樹根輪轉(zhuǎn)策略可以顯著降低最大EFI。但由于多播組成員到樹根間的冗余路徑不多，沒有發(fā)揮鏈路輪轉(zhuǎn)策略的作用。本節(jié)將在裁剪胖樹結(jié)構(gòu)下對(duì)上述3種路由算法進(jìn)行測(cè)試，以驗(yàn)證鏈路輪轉(zhuǎn)策略的有效性。獲得了2個(gè)超算中心的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，包括“神威藍(lán)光”計(jì)算機(jī)及“神威太湖之光”計(jì)算機(jī)，它們均采用裁剪胖樹結(jié)構(gòu)。

4.2.1“神威藍(lán)光”計(jì)算機(jī)下的實(shí)驗(yàn)結(jié)果

“神威藍(lán)光”計(jì)算機(jī)[23]安裝于濟(jì)南超算中心，包含8 704個(gè)運(yùn)算處理器，采用裁剪胖樹結(jié)構(gòu)，每個(gè)葉子交換機(jī)與最頂層交換機(jī)間都有8條最短路徑。

表9、表10分別顯示了每個(gè)處理器上運(yùn)行4個(gè)進(jìn)程時(shí)的最大EFI及運(yùn)行時(shí)間。有下列現(xiàn)象：

表9 神威藍(lán)光下各路由算法的最大EFITable 9 Maximum EFI of each algorithm under Sunway BlueLight

表10 神威藍(lán)光下各路由算法的運(yùn)行時(shí)間Table 10 Runtime of each algorithm under Sunway BlueLight s

（1）MINIHOP-MC-new的最大EFI明顯高于另外兩種多播路由算法。這表明除了根輪換策略外，SSSP-MC及FULB-MC采用的負(fù)載均衡策略可以進(jìn)一步降低鏈路EFI。

（2）大部分情況下FULB-MC與SSSP-MC的最大EFI及平均EFI相比沒有明顯增加。這表明FULB-MC雖然使用局部信息進(jìn)行負(fù)載均衡，仍然能夠獲得跟SSSP-MC類似的負(fù)載均衡結(jié)果。

（3）SSSP-MC的運(yùn)行時(shí)間明顯高于其他兩種算法，特別是當(dāng)存在大量小的多播組時(shí)，差異更加明顯。FULB-MC的運(yùn)行時(shí)間與MINIHOP-MC相當(dāng)。

4.2.2“神威太湖之光”的實(shí)驗(yàn)結(jié)果

“神威太湖之光”計(jì)算機(jī)[24]安裝于無(wú)錫超算中心，包含40 960個(gè)運(yùn)算處理器，是目前世界上規(guī)模最大的IB網(wǎng)絡(luò)，其互連網(wǎng)絡(luò)與“神威藍(lán)光”類似，但規(guī)模更大。每個(gè)葉子交換機(jī)與最頂層交換機(jī)都有2條路徑。三種多播路由算法的性能測(cè)試結(jié)果如表11、表12所示。

表11 神威太湖之光下各路由算法的最大EFI Table 11 Maximum EFI of each algorithm under Sunway TaihuLight

表12 神威太湖之光下各路由算法的運(yùn)行時(shí)間Table 12 Runtime under of each algorithmSunway TaihuLights

最大EFI方面，F(xiàn)ULB-MC明顯優(yōu)于MINIHOP-MCnew，而與SSSP-MC-new接近。另外，F(xiàn)ULB-MC的最大EFI最大下降為MINIHOP-MC的1/2左右；而神威藍(lán)光中，F(xiàn)ULB-MC的最大EFI最大下降為MINIHOP-MC的1/6左右。這是因?yàn)樯裢{(lán)光中，葉子交換機(jī)與頂層交換機(jī)間有更多的冗余路徑。

在運(yùn)行時(shí)間方面，F(xiàn)ULB-MC明顯優(yōu)于SSSP-MCnew。值得注意的是，很多通信模式下，SSSP-MC-new的運(yùn)行時(shí)間超過了10 s，最大達(dá)到了48 s；而FULB-MC的運(yùn)行時(shí)間均低于3 s。加上發(fā)送加入多播組請(qǐng)求、選擇樹根等時(shí)間，SSSP-MC-new的運(yùn)行時(shí)間很可能超過1 min。可以預(yù)見，隨著網(wǎng)絡(luò)規(guī)模的進(jìn)一步擴(kuò)大，以及多播組個(gè)數(shù)的進(jìn)一步增多，SSSP-MC-new的運(yùn)行時(shí)間會(huì)進(jìn)一步增加。因此，在超大規(guī)模互連網(wǎng)絡(luò)中，從運(yùn)行時(shí)間角度看，F(xiàn)ULB-MC是可接受的，而SSSP-MC-new的運(yùn)行時(shí)間是不可接受的。

4.3 實(shí)驗(yàn)小結(jié)

EFI方面，有下列結(jié)論：

（1）各種拓?fù)浣Y(jié)構(gòu)下，F(xiàn)ULB-MC的最大EFI相比MINIHOP-MC及SSSP-MC均大大下降，表明樹根輪轉(zhuǎn)策略可以有效降低鏈路EFI。

（2）將樹根輪轉(zhuǎn)策略應(yīng)用于MINIHOP-MC及SSSPMC后，在裁剪胖樹結(jié)構(gòu)下，F(xiàn)ULB-MC的最大EFI明顯低于MINIHOP-MC-new，表明鏈路輪轉(zhuǎn)策略可以進(jìn)一步降低鏈路EFI。

（3）標(biāo)準(zhǔn)胖樹結(jié)構(gòu)下，MINIHOP-MC-new、SSSPMC-new、FULB-MC這3種多播路由算法的最大EFI完全相同。

（4）3D-Torus中，大部分情況下FULB-MC的最大EFI低于MINIHOP-MC-new，而與SSSP-MC-new基本相當(dāng)。

（5）蜻蜓網(wǎng)絡(luò)中，有些通信模式下SSSP-MC-new和FULB-MC的最大EFI大于MINIHOP-MC-new，原因是該拓?fù)浣Y(jié)構(gòu)下多播組成員與樹根間可能有多條最短路徑，但其中有些路徑經(jīng)過兩條全局鏈路，而SSSP-MCnew和FULB-MC可能會(huì)選中該路徑。通過添加額外的規(guī)則，F(xiàn)ULB-MC可以避免選擇這樣的路徑，從而保證最大EFI不大于MINIHOP-MC-new。

（6）FULB-MC雖然使用局部負(fù)載信息進(jìn)行路由選擇，但在各種拓?fù)浣Y(jié)構(gòu)、各種通信模式下，其最大EFI與SSSP-MC-new基本相當(dāng)。

在運(yùn)行時(shí)間方面，F(xiàn)ULB-MC明顯低于SSSP-MC，例如，有些通信模式下，SSSP-MC需要約48 s，而FULB-MC僅需不到3 s。

5 結(jié)束語(yǔ)

IB現(xiàn)有的多播路由算法中，要么沒有采取任何負(fù)載均衡措施，要么采取負(fù)載均衡措施后運(yùn)行時(shí)間很長(zhǎng)，均不適用于大規(guī)模互連網(wǎng)絡(luò)環(huán)境。本文提出一種用于大規(guī)模IB網(wǎng)絡(luò)的負(fù)載均衡通用快速多播路由算法FULB。FULB利用最小跳表構(gòu)建多播樹，采用2種策略將多個(gè)多播組盡量均衡地分布到不同的鏈路上。另外，對(duì)加入/離開多播組的機(jī)制進(jìn)行了改進(jìn)，以適應(yīng)高性能計(jì)算應(yīng)用的需求。在典型的人造拓?fù)浼俺阒行膶?shí)際使用的拓?fù)渲袑?duì)FULB的性能進(jìn)行了測(cè)試，結(jié)果表明，在運(yùn)行時(shí)間方面，F(xiàn)ULB-MC顯著低于SSSP-MC，由SSSPMC下最長(zhǎng)的48 s縮短為FULB-MC下的3 s；在鏈路EFI指數(shù)方面，F(xiàn)ULB-MC明顯優(yōu)于MINIHOP-MC，而與SSSP-MC基本相當(dāng)。因此，F(xiàn)ULB-MC可用于存在大量多播組的超大規(guī)模互連網(wǎng)絡(luò)環(huán)境，為廣泛使用硬件支持的多播操作提供支撐。

FULB-MC也有不足之處。一是它采用局部信息進(jìn)行路徑選擇，有些通信模式下最大EFI比SSSP-MC有所增加。二是選擇樹根時(shí)仍需遍歷所有交換機(jī)，當(dāng)系統(tǒng)中存在大量交換機(jī)時(shí)，時(shí)間開銷較大。下一步將針對(duì)這些不足做進(jìn)一步的改進(jìn)。