K元N立方體網(wǎng)絡(luò)均勻跨步通信模式的性能分析與優(yōu)化

盧宏生，施得君，黃永勤，胡舒凱

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

K元N立方體網(wǎng)絡(luò)均勻跨步通信模式的性能分析與優(yōu)化

盧宏生?，施得君，黃永勤，胡舒凱

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

K元N立方體網(wǎng)絡(luò)是高性能計(jì)算機(jī)常用的一種網(wǎng)絡(luò)結(jié)構(gòu).均勻跨步通信是高性能計(jì)算最重要的通信模式之一.針對(duì)K元N立方體網(wǎng)絡(luò)均勻跨步通信模式，推導(dǎo)出其性能下限的理論公式，采用自行開(kāi)發(fā)的網(wǎng)絡(luò)模擬器模擬了多種結(jié)構(gòu)、多種跨步值和多種消息長(zhǎng)度的傳輸性能.最后針對(duì)節(jié)點(diǎn)重映射和消息分割兩種優(yōu)化措施進(jìn)行了模擬和分析.模擬結(jié)果顯示，4元N立方體網(wǎng)絡(luò)具有良好的All-to-all性能，接近All-to-all性能最好的K元N樹(shù)網(wǎng)絡(luò).

K元N立方體；All-to-all通信；均勻跨步通信；節(jié)點(diǎn)重映射；消息分割

對(duì)于很多重要應(yīng)用而言，比如快速傅里葉變換等[1]，All-to-all通信都是非常重要的通信模式，是影響性能的關(guān)鍵所在[2].許多網(wǎng)絡(luò)設(shè)計(jì)的目標(biāo)就是獲得良好的All-to-all性能.標(biāo)準(zhǔn)的All-to-all通信可參考圖1所示的MPI_AlltoAll的定義[3]，每個(gè)進(jìn)程都向其他所有進(jìn)程發(fā)送數(shù)據(jù)，這意味著每個(gè)進(jìn)程也同時(shí)接收來(lái)自其他進(jìn)程的數(shù)據(jù).由于標(biāo)準(zhǔn)的All-to-all通信可能存在大量競(jìng)爭(zhēng)，包括網(wǎng)絡(luò)的競(jìng)爭(zhēng)，目標(biāo)的競(jìng)爭(zhēng)，從而導(dǎo)致性能大幅下降.

圖1 MPI_AlltoAll功能示意圖

假設(shè)共計(jì)N個(gè)進(jìn)程{P0,P1, …,PN-1}.一種常用的優(yōu)化手段是將All-to-all通信過(guò)程分解成N-1個(gè)階段.階段i，i=[1, …,N-1]，每個(gè)進(jìn)程Pk只向進(jìn)程P(k+i)%N發(fā)送數(shù)據(jù)，這意味著每個(gè)進(jìn)程Pk同時(shí)在接收P(k+N-i)%N發(fā)送的數(shù)據(jù).這種方式有序化了All-to-all通信，降低了可能的阻塞，提升了整體All-to-all性能.上述每個(gè)階段的通信都屬于均勻跨步模式.所謂均勻跨步模式就是參與通信的所有進(jìn)程對(duì)，其目標(biāo)進(jìn)程號(hào)和源發(fā)送進(jìn)程號(hào)差值都相同.這種均勻跨步模式是許多重要應(yīng)用中的通信基礎(chǔ)模式，是超級(jí)計(jì)算機(jī)網(wǎng)絡(luò)結(jié)構(gòu)設(shè)計(jì)中的重要參考指標(biāo).圖2是一個(gè)4進(jìn)程All-to-all通信的階段劃分示意圖.

圖2 All-to-all階段劃分

在高性能計(jì)算中，每種通信模式的性能都和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)有著重要的關(guān)系.其中K元N立方體結(jié)構(gòu)一直是網(wǎng)絡(luò)結(jié)構(gòu)研究的熱點(diǎn)，是高性能計(jì)算機(jī)常用的一種拓?fù)浣Y(jié)構(gòu).典型的系統(tǒng)包括IBM Blue Gene，Cray Gemini等.本文重點(diǎn)研究K元N立方體網(wǎng)絡(luò)均勻跨步模式的性能及其優(yōu)化.

1 均勻跨步通信性能分析

All-to-all通信由于涉及很多因素，其性能的理論分析是十分復(fù)雜的.IBM的Kumar等人基于Bluegene/L系統(tǒng)3D環(huán)網(wǎng)結(jié)構(gòu)提出了一個(gè)針對(duì)多維環(huán)網(wǎng)的All-to-all通信模型性能公式[4].假設(shè)三維環(huán)網(wǎng)中每一維的處理器數(shù)量分別為Px,Py,Pz，系統(tǒng)中處理器的總數(shù)量為P=Px*Py*Pz，最長(zhǎng)維處理器數(shù)量M=max(Px,Py,Pz)，每個(gè)處理器發(fā)送m字節(jié)數(shù)據(jù)到其他處理器，單個(gè)字節(jié)在網(wǎng)絡(luò)中的傳輸時(shí)間為β，則在All-to-all通信模式下，網(wǎng)絡(luò)所傳輸?shù)臄?shù)據(jù)總量為P*P*m.每個(gè)包在最長(zhǎng)維的平均步長(zhǎng)為M/4，該維的鏈路總數(shù)為2P，因此完成All-to-all通信的時(shí)間T=P2*m*M/4*b/(2P)=P*(M/8)*m*β.該公式反映了All-to-all模式下3D環(huán)網(wǎng)的最好性能.如引言中所述，All-to-all通信可分解成若干步均勻跨步通信，因此分析均勻跨步通信模式的性能具有重要意義.

以圖3所示8元1維環(huán)網(wǎng)為例，不同的均勻跨步形式有不同的性能.比如當(dāng)以源目標(biāo)對(duì)(P0→P1,P1→P2,P2→P3,P3→P4,P4→P5,P5→P6,P6→P7,P7→P0)進(jìn)行通信時(shí)，由于所有路徑均不存在鏈路沖突，因此該均勻跨步方式下通信性能可以達(dá)到100%.8元1維環(huán)網(wǎng)的網(wǎng)絡(luò)直徑為4，當(dāng)以(P0→P4,P1→P5,P2→P6,P3→P7,P4→P0,P5→P1,P6→P2,P7→P3)進(jìn)行通信時(shí)，每個(gè)消息的步長(zhǎng)均為4，存在鏈路沖突，會(huì)導(dǎo)致通信性能的下降.假設(shè)8元1維環(huán)網(wǎng)采用均衡的確定性路由算法，即當(dāng)步長(zhǎng)為4時(shí)，源節(jié)點(diǎn)號(hào)為偶數(shù)的通信采用向右路由方式，源節(jié)點(diǎn)號(hào)為奇數(shù)的通信采用向左路由方式.這種按奇偶分配路由方向的策略可以保障最大化的路由均衡.

圖3 8元1維環(huán)網(wǎng)

通過(guò)一個(gè)路徑矩陣我們?cè)敿?xì)分析該情況下的鏈路沖突情況.如圖4所示，8×8矩陣A，第i行表示以Pi為源點(diǎn)發(fā)起的消息.第i行向量(bi0,bi1,bi2,bi3,bi4,bi5,bi6,bi7)，bij=+1表示從左到右到達(dá)j，bij=-1表示從右到左到達(dá)j，bij=0表示不經(jīng)過(guò)該路徑.通過(guò)矩陣我們發(fā)現(xiàn)2個(gè)現(xiàn)象.第1個(gè)現(xiàn)象是8個(gè)消息所占用的鏈路沖突率為50%.即每條鏈路最多被2個(gè)消息所使用；第2個(gè)現(xiàn)象是雖然1條鏈路被2個(gè)消息所使用，但由于可能沖突的消息的起點(diǎn)是錯(cuò)開(kāi)的，因此當(dāng)消息長(zhǎng)度特別短時(shí)，并沒(méi)有沖突發(fā)生.上述事實(shí)說(shuō)明，均勻跨步的消息性能和消息發(fā)送的源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的映射關(guān)系、消息的長(zhǎng)度都有重要的關(guān)系.

p0p1p2p3p4p5p6p7p00+1+1+1+1000p1-10000-1-1-1p2000+1+1+1+10p3-1-1-10000-1p4+10000+1+1+1p50-1-1-1-1000p6+1+1+10000+1p7000-1-1-1-10

圖4 8元1維環(huán)網(wǎng)鏈路使用矩陣

Fig.4Linkutilizationarrayon8-nodering

Kumar以IBMBlueGene系統(tǒng)為參考，給出了3D環(huán)網(wǎng)All-to-all性能的上限評(píng)估公式.但事實(shí)上，在設(shè)計(jì)高性能計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)時(shí)，我們更關(guān)注其All-to-all性能的下限.因?yàn)閼?yīng)用與算法是多種多樣的，知道了網(wǎng)絡(luò)可能的性能下限，才能針對(duì)重大應(yīng)用選擇適應(yīng)性更好的網(wǎng)絡(luò)架構(gòu).下面從理論上初步分析均勻跨步的性能下限.K元N立方體網(wǎng)絡(luò)，共有KN個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)直徑為N*K/2，鏈路總數(shù)為N*2*KN條.對(duì)于均勻跨步消息，網(wǎng)絡(luò)鏈路沖突最大的情況是任一對(duì)通信節(jié)點(diǎn)間的步長(zhǎng)均等于網(wǎng)絡(luò)直徑.所以理想情況下，需要的鏈路數(shù)為N*(K/2)*KN.所以我們得到系統(tǒng)鏈路吞吐率的下限公式為：

min(2N*KN/(N*(K/2)*KN),1)=min(4/K,1)

這是一個(gè)十分有趣的公式.它顯示，對(duì)于K元N立方體而言，均勻跨步通信的吞吐率下限與維數(shù)無(wú)關(guān)，僅和每一維的長(zhǎng)度相關(guān).當(dāng)K≤8時(shí)，均勻跨步通信吞吐率超過(guò)50%；特別當(dāng)長(zhǎng)度K=4時(shí)，即4元N立方體在進(jìn)行均勻跨步模式通信時(shí)，吞吐率可以達(dá)到100%．了解一種網(wǎng)絡(luò)結(jié)構(gòu)All-to-all性能的下限對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)、各種網(wǎng)絡(luò)參數(shù)的選取具有重要的參考意義.由上述公式可見(jiàn)，在All-to-all通信性能方面，4元N立方體性能接近K元N樹(shù)性能.當(dāng)然上述情況的分析都是基于理想情況.后面將用模擬器檢查我們的分析是否準(zhǔn)確.

2 均勻跨步通信性能模擬

2.1 網(wǎng)絡(luò)模擬器

為了更好地模擬網(wǎng)絡(luò)通信的性能，我們開(kāi)發(fā)了一款采用C++編寫的節(jié)拍級(jí)網(wǎng)絡(luò)模擬器netsim.該模擬器支持K元N立方體、K元N樹(shù)等多種網(wǎng)絡(luò)結(jié)構(gòu).我們重點(diǎn)模擬了K元2立方體網(wǎng)絡(luò)，即2D環(huán)網(wǎng).該2D環(huán)網(wǎng)基于5端口路由器實(shí)現(xiàn).路由器采用從輸入緩沖經(jīng)交叉開(kāi)關(guān)到輸出緩沖的傳統(tǒng)的路由器結(jié)構(gòu).之所以沒(méi)有采用目前比較主流的高階路由器結(jié)構(gòu)，主要是考慮構(gòu)建2D環(huán)網(wǎng)所需路由器的端口比較少，同時(shí)這種結(jié)構(gòu)的差異對(duì)我們研究的影響很小.我們研究的重點(diǎn)在于消息長(zhǎng)度、通信模式和網(wǎng)絡(luò)拓?fù)溟g的關(guān)系上.

模擬過(guò)程中的基本參數(shù)如表1所示．

模擬過(guò)程中無(wú)如特別說(shuō)明，每個(gè)消息包長(zhǎng)為64個(gè)flit，每個(gè)flit8B.鏈路帶寬8B/周期.根據(jù)上述數(shù)據(jù)可知，1個(gè)節(jié)點(diǎn)向其相鄰節(jié)點(diǎn)發(fā)送一個(gè)512B的消息包，最快需要的時(shí)間是T=Ts+2*Trn+2*Trou+Trr+Tr+63=113(周期).

表1 模擬器主要參數(shù)表

2.2 性能模擬

我們分別對(duì)4×4 2D環(huán)網(wǎng)和8×8 2D環(huán)網(wǎng)進(jìn)行了模擬.針對(duì)4×4 2D環(huán)網(wǎng)的16個(gè)節(jié)點(diǎn)，我們分別模擬長(zhǎng)度為512 B,1 kB,2 kB,4 kB,8 kB,16 kB,32 kB,64 kB,128 kB,256 kB,512 kB,1 MB的All-to-all消息.每個(gè)All-to-all消息被劃分為15個(gè)階段完成.

表2中橫向表示消息長(zhǎng)度，縱向代表階段，表項(xiàng)為相應(yīng)長(zhǎng)度消息在該階段時(shí)傳輸所用時(shí)間.通過(guò)研究發(fā)現(xiàn)，在4×4 2D環(huán)網(wǎng)中，All-to-all通信的每個(gè)階段，無(wú)論哪種消息長(zhǎng)度，每對(duì)源目之間的消息傳輸延時(shí)都和該對(duì)源目之間點(diǎn)到點(diǎn)消息傳輸時(shí)的延時(shí)相同，即不存在因鏈路沖突所產(chǎn)生的延時(shí)，吞吐率均可達(dá)到100%，和我們第2節(jié)的分析是完全吻合的.

表2 4×X4 2D環(huán)網(wǎng)不同消息長(zhǎng)度消息性能表

圖5是 8×8 2D環(huán)網(wǎng)執(zhí)行不同長(zhǎng)度的All-to-all通信在63個(gè)階段的吞吐率.其中系列i，i=[1..12]，分別對(duì)應(yīng)長(zhǎng)度為512*2i-1B的消息.每個(gè)階段p，p=[1..63]，坐標(biāo)(X，Y)的節(jié)點(diǎn)向坐標(biāo)((X+dx)%8，(Y+dy)%8)的節(jié)點(diǎn)發(fā)送消息，dx=p%8,dy=p/8.結(jié)果顯示，各個(gè)階段的吞吐率有很大的差別.部分階段，無(wú)論消息長(zhǎng)度，吞吐率均達(dá)到100%，這主要得益于上述階段不存在鏈路沖突；還有部分階段吞吐率很低，最低的僅為14%，遠(yuǎn)低于我們預(yù)測(cè)的8×8 環(huán)網(wǎng)50%的吞吐率下限.這主要是因?yàn)槲覀兊念A(yù)測(cè)中僅從鏈路數(shù)量需求方面考慮了沖突的情況，但實(shí)際上作為環(huán)網(wǎng)，采用確定性維序路由算法后，鏈路之間存在依賴關(guān)系.這種依賴關(guān)系使得鏈路沖突率進(jìn)一步加大.對(duì)于K元N立方體網(wǎng)絡(luò)，K越大，影響越大.第2節(jié)中預(yù)測(cè)的最低值更接近最低值的上限或All-to-all通信階段的平均值.

階段號(hào)

圖6是8×8 2D環(huán)網(wǎng)不同消息長(zhǎng)度完整的All-to-all通信時(shí)所有階段吞吐率的平均值.隨著消息長(zhǎng)度的增加，鏈路沖突的影響就越明顯，表現(xiàn)為吞吐率在不斷下降.隨著消息長(zhǎng)度不斷增長(zhǎng)，下降趨勢(shì)趨緩，和我們預(yù)測(cè)的50%的吞吐率有10%的差距.利用相同的模擬參數(shù)，我們還構(gòu)建了7端口路由器模型，模擬了4×4×4和8×8×8 3D環(huán)網(wǎng)All-to-all通信各階段的情況.結(jié)果和2D環(huán)網(wǎng)類似.4×4×4環(huán)網(wǎng)吞吐率達(dá)到100%，而8×8×8環(huán)網(wǎng)在消息長(zhǎng)度為32 kB時(shí)，平均吞吐率為40%.

長(zhǎng)度類別

3 All-to-all性能優(yōu)化

在很多應(yīng)用中，All-to-all性能都是性能的關(guān)鍵.優(yōu)化All-to-all通信性能也一直是研究的熱點(diǎn).將All-to-all通信分解為N-1個(gè)均勻跨步過(guò)程是一種比較常見(jiàn)的優(yōu)化方法.在前面的分析和模擬中，我們發(fā)現(xiàn)均勻跨步的性能和網(wǎng)絡(luò)的結(jié)構(gòu)有很大的依賴關(guān)系，而應(yīng)用程序看到的跨步通常是邏輯上的概念.比如進(jìn)程號(hào)，它并不等同代表網(wǎng)絡(luò)中物理位置的物理號(hào).真正影響通信性能的是物理號(hào).是否可以通過(guò)變換邏輯和物理的映射關(guān)系改變均勻跨步的性能，從而提升All-to-all通信性能呢？

為此，我們編寫了一個(gè)模擬程序，選擇8X8 2D環(huán)網(wǎng)進(jìn)行模擬，用A,B,C,D 4個(gè)矩陣分別記錄X+,Y+,X-,Y- 4個(gè)方向的鏈路，一個(gè)完整的All-to-all消息被分解為63個(gè)階段，分別記錄每個(gè)階段所有鏈路的使用情況.

圖7(a)代表了一個(gè)邏輯節(jié)點(diǎn)號(hào)到物理節(jié)點(diǎn)號(hào)的映射關(guān)系.圖7(b)中的4個(gè)圖分別表示在階段9即p[i]進(jìn)程向p[(i+9)%64]進(jìn)程(i=[0..63])通信時(shí)X+,Y+,X-,Y-4個(gè)方向共計(jì)256條鏈路的使用情況.圖7(c)中的4個(gè)圖則分別表示在階段31即p[i]進(jìn)程向p[(i+31)%64]進(jìn)程(i=[0..63])通信時(shí)X+,Y+,X-,Y- 4個(gè)方向共計(jì)256條鏈路的使用情況.很容易發(fā)現(xiàn)，2個(gè)階段的鏈路情況并不相同，這和我們前面的分析是吻合的.一個(gè)有趣的現(xiàn)象是：完成完整的All-to-all通信后，所有X+,Y+,X-,Y- 4個(gè)方向共計(jì)256條鏈路，每條鏈路均被使用了64次.多次更換映射關(guān)系，現(xiàn)象依舊.實(shí)際上，由于我們面對(duì)K*K2D環(huán)網(wǎng)是一個(gè)對(duì)稱網(wǎng)絡(luò)，無(wú)論邏輯節(jié)點(diǎn)號(hào)和物理節(jié)點(diǎn)號(hào)如何映射，對(duì)于完整的All-to-all通信而言，都是每個(gè)節(jié)點(diǎn)都和其他所有節(jié)點(diǎn)完成一次通信.而我們采用的是均衡的先X后Y確定性維序路由算法，因此無(wú)論如何映射，每條鏈路使用的次數(shù)是固定的，只在每個(gè)階段有一定的差異.由于網(wǎng)絡(luò)的對(duì)稱性，每條鏈路最終使用的次數(shù)都是相同的.但這并不意味著重新映射邏輯節(jié)點(diǎn)號(hào)與物理節(jié)點(diǎn)號(hào)無(wú)助于提升All-to-all通信性能.事實(shí)上，由于映射關(guān)系的不同，每種映射下每個(gè)階段的鏈路沖突率是不同的，最終所有階段疊加的結(jié)果就是All-to-all通信性能并不相同.

如圖8所示，(a),(b)分別對(duì)應(yīng)4×4 2D環(huán)結(jié)構(gòu)下兩種邏輯處理器號(hào)和物理處理器號(hào)的映射關(guān)系.16個(gè)處理器的2D環(huán)網(wǎng)的All-to-all通信劃分成15個(gè)均勻跨步通信階段.(a.1),(a.2),(a.3),(a.4)表示映射關(guān)系1時(shí)階段1的X+,Y+,X-,Y- 4個(gè)方向鏈路的使用情況.(b.1),(b.2),(b.3),(b.4) 表示映射關(guān)系2時(shí)階段1的X+,Y+,X-,Y-4個(gè)方向鏈路的使用情況.定義一條鏈路的權(quán)值W為同一個(gè)階段傳輸?shù)南?shù)量.可以發(fā)現(xiàn)，映射關(guān)系1在階段1時(shí)最大鏈路權(quán)值為1，即意味著在此階段通信的16個(gè)消息沒(méi)有鏈路沖突，消息以滿帶寬傳輸.而映射關(guān)系2在階段1時(shí)最大鏈路權(quán)值為2，即意味這在此階段通信16個(gè)消息中有2個(gè)消息共享(1,1)到(2,1)號(hào)鏈路.因此消息性能將為峰值性能的一半.階段i的最大權(quán)值記為Wi.W=∑Wi/15(i∈[0..15])是All-to-all通信各階段平均最大鏈路權(quán)值.結(jié)果顯示，在映射關(guān)系1下，W1=1.在映射關(guān)系2下，W2=1.87.即4×4 2D 環(huán)網(wǎng)在映射關(guān)系1下All-to-all消息帶寬可以達(dá)到鏈路峰值，而在映射關(guān)系2下，All-to-all消息帶寬僅為鏈路峰值帶寬的1/W2=53%.

圖7 8×8 2D環(huán)網(wǎng)鏈路使用矩陣

圖8 兩種映射關(guān)系下的4×4 2D 環(huán)網(wǎng)鏈路使用矩陣

針對(duì)All-to-all通信，也有一些研究人員嘗試將長(zhǎng)消息分割成小消息，通過(guò)對(duì)小消息的調(diào)度降低網(wǎng)絡(luò)的沖突，從而提升性能[5].比如在InfiniBand 16元2樹(shù)網(wǎng)絡(luò)中通過(guò)將128 kB長(zhǎng)消息拆分成16 kB小消息，All-to-all性能提升10%.但事實(shí)上，InfiniBand網(wǎng)絡(luò)采用的是確定性路由，排除消息非常短的情況，無(wú)論消息長(zhǎng)度多長(zhǎng)，鏈路的使用情況是相同的.之所以通過(guò)將長(zhǎng)消息拆分成短消息性能有所提升，主要是由InfiniBand HCA的消息發(fā)送機(jī)制造成的.HCA在發(fā)送消息時(shí)以時(shí)間片為單位，在一個(gè)時(shí)間片內(nèi)連續(xù)調(diào)度同一個(gè)QP上的數(shù)據(jù)包，導(dǎo)致消息發(fā)射的頻率并不恒定，從而導(dǎo)致網(wǎng)絡(luò)擁塞.同時(shí)由于在All-to-all通信的各階段間沒(méi)有高效的同步機(jī)制，也容易造成目標(biāo)節(jié)點(diǎn)的沖突，從而增加性能隨消息長(zhǎng)度浮動(dòng)的變數(shù).

總體來(lái)說(shuō)，在理想情況下，這里的理想條件包括合理的消息發(fā)送機(jī)制、合理的NI，ROUTER均衡的緩沖配置、均衡的路由算法、足量的VC數(shù)量，決定All-to-all通信性能的關(guān)鍵首先是網(wǎng)絡(luò)固有的屬性即網(wǎng)絡(luò)拓?fù)?良好的映射關(guān)系將有助于減少網(wǎng)絡(luò)鏈路的沖突率，從而提升All-to-all通信的性能.因此在作業(yè)分配時(shí)，合理地配置節(jié)點(diǎn)資源或者在算法設(shè)計(jì)時(shí)緊耦合網(wǎng)絡(luò)拓?fù)錉顩r將大大提升All-to-all通信的性能.由于K元N樹(shù)網(wǎng)絡(luò)能夠保證所有源和目標(biāo)間的一一映射均不存在鏈路沖突[6]，因此其任意均勻跨步模式的通信性能均可達(dá)到鏈路有效性能的100%，即等同于點(diǎn)到點(diǎn)通信性能.因此樹(shù)型網(wǎng)絡(luò)作為支持All-to-all通信的理想拓?fù)浣Y(jié)構(gòu)，是K元N立方體網(wǎng)絡(luò)在All-to-all通信性能方面優(yōu)化的重要標(biāo)尺.

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

All-to-all性能的理論分析十分復(fù)雜.將All-to-all通信拆分成多個(gè)階段的均勻跨步通信是一種提升性能的簡(jiǎn)單高效的方法.這種方法避免了目標(biāo)的沖突.本文給出了一種K元N立方體網(wǎng)絡(luò)中均勻跨步通信模式最低性能的估計(jì)值，這對(duì)高性能計(jì)算機(jī)網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)具有一定的參考價(jià)值.本文的公式顯示其性能和一維的長(zhǎng)度成反比.特別是當(dāng)K=4時(shí)，4元N立方體網(wǎng)絡(luò)有比較好的All-to-all性能.但最好的性能仍然屬于完全無(wú)沖突的K元N樹(shù)網(wǎng)絡(luò).在All-to-all通信方面，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)仍然是影響性能的第一要素.經(jīng)過(guò)模擬與分析，也指出通過(guò)節(jié)點(diǎn)重映射手段可提升K元N立方體網(wǎng)絡(luò)的All-to-all通信性能，而消息分割只在某些特定的系統(tǒng)中有效，并不具備普適性.

[1] YOGISH Sabharwal, SAURABH K Garg, RAHUL Garg,etal. Optimization of fast fourier transforms on the blue Gene/L supercomputer[C] // Proc of 15th International Conference on High Performance Computing．Bangalore, India, 2008: 309-322.

[2] All-to-allcommunication[EB/OL]. [2014-4-9].http://en.wikepedia.org/wiki/All-to-all_communication.

[3] MPI_Alltoall[EB/OL]. [2014-4-9].http://www.mpich.org/static/docs/v3.1/www3/MPI_Alltoall.html.

[4] SAMEER Kumar, YOGISH Sabharwal, RAHUL Garg,etal. Optimization of All-to-all communication on the blue Gene/L supercomputer[C] // Proc of 37th International Conference on Parallel Processing, Portland, Oregon, 2008: 320-329.

[5] 陳淑平, 盧德平, 陳忠平. InfiniBand網(wǎng)絡(luò)中All-to-all通信性能優(yōu)化[J]. 高性能計(jì)算發(fā)展與應(yīng)用, 2012(2): 69-74.

CHEN Shu-ping, LU De-ping, CHEN Zhong-ping. Optimization of All-to-all performance in InfiniBand network[J]. Development and Application of High Performance Computing, 2012(2):69-74.(In Chinese)

[6] SABINE R ?hring, MAXIMILIAN Ibel, SAJAL K Das,etal. On generalized fat trees[C] // Proc of the 9th International Parallel Processing Symposium．Santa Barbara, California, 1995: 37-44.

Performance Analysis and Optimization of Uniform Stride Communication onK-aryN-cube Network

LU Hong-sheng?, SHI De-jun, HUANG Yong-qin, HU Shu-kai

(Jiangnan Institute of Computer Technology, Wuxi,Jiangsu 214083, China)

K-aryN-cube is a widely used network architecture for high performance computer. Uniform stride communication is one of the most important communication models for high performance computing. This paper gave the theoretical lowest limit performance of uniform stride communication inK-aryN-cubeand and achieved a series of performance simulations in a self-developed network simulator. The simulation parameters include network arrays, stride values and message lengths. We also simulated and analyzed two optimized methods, node remapping and message division. As a result, 4-ary N-cube has very good All-to-all performance that approaches the performance ofK-aryN-tree, which has the best All-to-all performance.

K-aryN-cube; All-to-all communication; uniform stride communication；noderemapping; message division

1674-2974(2015)02-0134-07

2014-09-16

國(guó)家“863”高科技研究發(fā)展計(jì)劃項(xiàng)目(2014AA01A301)

盧宏生(1972-)，廣東廣州人，江南計(jì)算技術(shù)研究所高級(jí)工程師?通訊聯(lián)系人，E-mail:lu_hongsheng@126.com

TP301

A