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

盧宏生等

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

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

中圖分類號：TP301 文獻標識碼：A

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

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

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

1均勻跨步通信性能分析

Alltoall通信由于涉及很多因素，其性能的理論分析是十分復(fù)雜的.IBM的Kumar等人基于Bluegene/L系統(tǒng)3D環(huán)網(wǎng)結(jié)構(gòu)提出了一個針對多維環(huán)網(wǎng)的Alltoall通信模型性能公式[4].假設(shè)三維環(huán)網(wǎng)中每一維的處理器數(shù)量分別為Px，Py，Pz，系統(tǒng)中處理器的總數(shù)量為P=Px*Py*Pz，最長維處理器數(shù)量M=max（Px，Py，Pz），每個處理器發(fā)送m字節(jié)數(shù)據(jù)到其他處理器，單個字節(jié)在網(wǎng)絡(luò)中的傳輸時間為β，則在Alltoall通信模式下，網(wǎng)絡(luò)所傳輸?shù)臄?shù)據(jù)總量為P*P*m.每個包在最長維的平均步長為M/4，該維的鏈路總數(shù)為2P，因此完成Alltoall通信的時間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性能的上限評估公式.但事實上，在設(shè)計高性能計算機網(wǎng)絡(luò)系統(tǒng)時，我們更關(guān)注其Alltoall性能的下限.因為應(yīng)用與算法是多種多樣的，知道了網(wǎng)絡(luò)可能的性能下限，才能針對重大應(yīng)用選擇適應(yīng)性更好的網(wǎng)絡(luò)架構(gòu).下面從理論上初步分析均勻跨步的性能下限.K元N立方體網(wǎng)絡(luò)，共有KN個節(jié)點，網(wǎng)絡(luò)直徑為N*K/2，鏈路總數(shù)為N*2*KN條.對于均勻跨步消息，網(wǎng)絡(luò)鏈路沖突最大的情況是任一對通信節(jié)點間的步長均等于網(wǎng)絡(luò)直徑.所以理想情況下，需要的鏈路數(shù)為N*（K/2）*KN.所以我們得到系統(tǒng)鏈路吞吐率的下限公式為：

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

2均勻跨步通信性能模擬

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

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

2.2性能模擬

我們分別對4×4 2D環(huán)網(wǎng)和8×8 2D環(huán)網(wǎng)進行了模擬.針對4×4 2D環(huán)網(wǎng)的16個節(jié)點，我們分別模擬長度為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消息.每個Alltoall消息被劃分為15個階段完成.

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

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

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

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

如圖8所示，（a），（b）分別對應(yīng)4×4 2D環(huán)結(jié)構(gòu)下兩種邏輯處理器號和物理處理器號的映射關(guān)系.16個處理器的2D環(huán)網(wǎng)的Alltoall通信劃分成15個均勻跨步通信階段.（a.1），（a.2），（a.3），（a.4）表示映射關(guān)系1時階段1的X+，Y+，X-，Y- 4個方向鏈路的使用情況.（b.1），（b.2），（b.3），（b.4） 表示映射關(guān)系2時階段1的X+，Y+，X-，Y-4個方向鏈路的使用情況.定義一條鏈路的權(quán)值W為同一個階段傳輸?shù)南?shù)量.可以發(fā)現(xiàn)，映射關(guān)系1在階段1時最大鏈路權(quán)值為1，即意味著在此階段通信的16個消息沒有鏈路沖突，消息以滿帶寬傳輸.而映射關(guān)系2在階段1時最大鏈路權(quán)值為2，即意味這在此階段通信16個消息中有2個消息共享（1，1）到（2，1）號鏈路.因此消息性能將為峰值性能的一半.階段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消息帶寬可以達到鏈路峰值，而在映射關(guān)系2下，Alltoall消息帶寬僅為鏈路峰值帶寬的1/W2=53%.

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

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

4結(jié)束語

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

參考文獻

[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]. 高性能計算發(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.