盧宏生等

摘要：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ò)具有良好的Alltoall性能，接近Alltoall性能最好的K元N樹(shù)網(wǎng)絡(luò).

關(guān)鍵詞：K元N立方體；Alltoall通信；均勻跨步通信；節(jié)點(diǎn)重映射；消息分割

中圖分類(lèi)號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A

對(duì)于很多重要應(yīng)用而言，比如快速傅里葉變換等[1]，Alltoall通信都是非常重要的通信模式，是影響性能的關(guān)鍵所在[2].許多網(wǎng)絡(luò)設(shè)計(jì)的目標(biāo)就是獲得良好的Alltoall性能.標(biāo)準(zhǔn)的Alltoall通信可參考圖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)的Alltoall通信可能存在大量競(jìng)爭(zhēng)，包括網(wǎng)絡(luò)的競(jìng)爭(zhēng)，目標(biāo)的競(jìng)爭(zhēng)，從而導(dǎo)致性能大幅下降.

假設(shè)共計(jì)N個(gè)進(jìn)程{P0， P1， …， PN-1}.一種常用的優(yōu)化手段是將Alltoall通信過(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ù).這種方式有序化了Alltoall通信，降低了可能的阻塞，提升了整體Alltoall性能.上述每個(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)程Alltoall通信的階段劃分示意圖.

在高性能計(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均勻跨步通信性能分析

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

Kumar以IBM BlueGene系統(tǒng)為參考，給出了3D環(huán)網(wǎng)Alltoall性能的上限評(píng)估公式.但事實(shí)上，在設(shè)計(jì)高性能計(jì)算機(jī)網(wǎng)絡(luò)系統(tǒng)時(shí)，我們更關(guān)注其Alltoall性能的下限.因?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)鏈路吞吐率的下限公式為：

這是一個(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)Alltoall性能的下限對(duì)于網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)、各種網(wǎng)絡(luò)參數(shù)的選取具有重要的參考意義.由上述公式可見(jiàn)，在Alltoall通信性能方面，4元N立方體性能接近K元N樹(shù)性能.當(dāng)然上述情況的分析都是基于理想情況.后面將用模擬器檢查我們的分析是否準(zhǔn)確.

2均勻跨步通信性能模擬

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

為了更好地模擬網(wǎng)絡(luò)通信的性能，我們開(kāi)發(fā)了一款采用C++編寫(xiě)的節(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)系上.

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的Alltoall消息.每個(gè)Alltoall消息被劃分為15個(gè)階段完成.

圖5是 8×8 2D環(huán)網(wǎng)執(zhí)行不同長(zhǎng)度的Alltoall通信在63個(gè)階段的吞吐率.其中系列i，i=[1..12]，分別對(duì)應(yīng)長(zhǎng)度為512*2i-1 B的消息.每個(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)，采用確定性維序路由算法后，鏈路之間存在依賴(lài)關(guān)系.這種依賴(lài)關(guān)系使得鏈路沖突率進(jìn)一步加大.對(duì)于K元N立方體網(wǎng)絡(luò)，K越大，影響越大.第2節(jié)中預(yù)測(cè)的最低值更接近最低值的上限或Alltoall通信階段的平均值.

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

為此，我們編寫(xiě)了一個(gè)模擬程序，選擇8X8 2D環(huán)網(wǎng)進(jìn)行模擬，用A，B，C，D 4個(gè)矩陣分別記錄X+，Y+，X-，Y- 4個(gè)方向的鏈路，一個(gè)完整的Alltoall消息被分解為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)象是：完成完整的Alltoall通信后，所有X+，Y+，X-，Y- 4個(gè)方向共計(jì)256條鏈路，每條鏈路均被使用了64次.多次更換映射關(guān)系，現(xiàn)象依舊.實(shí)際上，由于我們面對(duì)K*K 2D環(huán)網(wǎng)是一個(gè)對(duì)稱(chēng)網(wǎng)絡(luò)，無(wú)論邏輯節(jié)點(diǎn)號(hào)和物理節(jié)點(diǎn)號(hào)如何映射，對(duì)于完整的Alltoall通信而言，都是每個(gè)節(jié)點(diǎn)都和其他所有節(jié)點(diǎn)完成一次通信.而我們采用的是均衡的先X后Y確定性維序路由算法，因此無(wú)論如何映射，每條鏈路使用的次數(shù)是固定的，只在每個(gè)階段有一定的差異.由于網(wǎng)絡(luò)的對(duì)稱(chēng)性，每條鏈路最終使用的次數(shù)都是相同的.但這并不意味著重新映射邏輯節(jié)點(diǎn)號(hào)與物理節(jié)點(diǎn)號(hào)無(wú)助于提升Alltoall通信性能.事實(shí)上，由于映射關(guān)系的不同，每種映射下每個(gè)階段的鏈路沖突率是不同的，最終所有階段疊加的結(jié)果就是Alltoall通信性能并不相同.

如圖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)的Alltoall通信劃分成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)有鏈路沖突，消息以滿(mǎn)帶寬傳輸.而映射關(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]）是Alltoall通信各階段平均最大鏈路權(quán)值.結(jié)果顯示，在映射關(guān)系1下，W1=1.在映射關(guān)系2下，W2=1.87.即4×4 2D 環(huán)網(wǎng)在映射關(guān)系1下Alltoall消息帶寬可以達(dá)到鏈路峰值，而在映射關(guān)系2下，Alltoall消息帶寬僅為鏈路峰值帶寬的1/W2=53%.

針對(duì)Alltoall通信，也有一些研究人員嘗試將長(zhǎng)消息分割成小消息，通過(guò)對(duì)小消息的調(diào)度降低網(wǎng)絡(luò)的沖突，從而提升性能[5].比如在InfiniBand 16元2樹(shù)網(wǎng)絡(luò)中通過(guò)將128 kB長(zhǎng)消息拆分成16 kB小消息，Alltoall性能提升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í)由于在Alltoall通信的各階段間沒(méi)有高效的同步機(jī)制，也容易造成目標(biāo)節(jié)點(diǎn)的沖突，從而增加性能隨消息長(zhǎng)度浮動(dòng)的變數(shù).

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

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

Alltoall性能的理論分析十分復(fù)雜.將Alltoall通信拆分成多個(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ò)有比較好的Alltoall性能.但最好的性能仍然屬于完全無(wú)沖突的K元N樹(shù)網(wǎng)絡(luò).在Alltoall通信方面，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)仍然是影響性能的第一要素.經(jīng)過(guò)模擬與分析，也指出通過(guò)節(jié)點(diǎn)重映射手段可提升K元N立方體網(wǎng)絡(luò)的Alltoall通信性能，而消息分割只在某些特定的系統(tǒng)中有效，并不具備普適性.

參考文獻(xiàn)

[1]YOGISH Sabharwal， SAURABH K Garg， RAHUL Garg， et al. 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]Alltoallcommunication[EB/OL]. [2014-4-9].http：//en.wikepedia.org/wiki/Alltoall_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， et al. Optimization of Alltoall 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ò)中Alltoall通信性能優(yōu)化[J]. 高性能計(jì)算發(fā)展與應(yīng)用， 2012（2）： 69-74.

CHEN Shuping， LU Deping， CHEN Zhongping. Optimization of Alltoall 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， et al. On generalized fat trees[C] // Proc of the 9th International Parallel Processing Symposium.Santa Barbara， California， 1995： 37-44.