Alltoall通信性能模型研究*

羅紅兵，張曉霞，魏　勇

北京應用物理與計算數(shù)學研究所 高性能計算中心，北京 100094

1　引言

MPI（message passing interface）通信性能是影響并行應用程序性能的關鍵，特別是MPI集合通信性能對于應用的可擴展性往往具有決定性的作用。在MPI集合通信中，Alltoall是讓所有參與通訊的進程彼此進行數(shù)據(jù)交換的集合通信操作，對于采用該通信模式的應用，例如三維快速傅里葉變換[1]和量子力學分子動力學模擬CPMD（Car-Parrinello molecular dynamics）[2]，Alltoall性能對應用軟件性能的影響非常大。為此，Alltoall相應的評估和優(yōu)化研究一直是并行計算領域的研究熱點，包括對Alltoall等集合通信的詳細分析[3-5]，針對當前多核CPU的Alltoall的優(yōu)化[6-7]，在通信算法層[8]針對特定高性能計算機[9]對Alltoall進行的優(yōu)化等。

已有的研究結果[5]顯示：Alltoall的理論預估值與實際測試值的差別往往較大，尤其在超大規(guī)模情況下，實測值甚至是理論值的數(shù)倍，反映出對Alltoall集合通信性能的理論建模仍然是值得深入研究的問題。如何利用理論模型解釋Alltoall的性能，是MPI通信算法設計、評估和優(yōu)化，乃至高性能計算機優(yōu)化中必須要面對的問題。當前，對于Alltoall集合通訊的性能建模[10-11]大都基于基本的通訊模型進行，其中被廣泛使用的通信性能模型是LogP（latency,overhead,gap，and processor）模型[12]，該模型是一個針對分布式存儲的多處理器模型，處理器間采用點對點通信。LogGP模型[13]在LogP模型的基礎上增加了一個參數(shù)G，該參數(shù)可以描述在傳遞長消息時獲得的帶寬。從現(xiàn)有的研究和實驗結果看，某些因素未在模型中準確地體現(xiàn)，導致Alltoall性能理論預測在大規(guī)模情況下的失真。

針對超大規(guī)模情況下Alltoall的理論性能模型存在的不足，本文從MPI通信的基本特征和Alltoall實現(xiàn)算法和模型兩方面予以分析，希望刻畫出實際互連網絡系統(tǒng)中的某些特征，以期建立更為精確的Alltoall性能模型。

2　Alltoall實現(xiàn)算法分析

MPI的開源實現(xiàn)版本mpich中對Alltoall的實現(xiàn)涉及4個算法，分別面向不同的消息長度和進程數(shù)規(guī)模，具體為：

（1）對于短消息（缺省是不大于256 B）且MPI進程數(shù)大于等于8，采用存儲前進算法，以多傳輸數(shù)據(jù)來減少通信延遲的影響，算法需執(zhí)行l(wèi)bp步，單進程的數(shù)據(jù)傳輸量增加到原傳輸量的lbp/2倍。

（2）對于中等規(guī)模的消息（缺省為不大于32 KB）且MPI進程數(shù)小于8，以同時進行irevs和isends，再進行一次waitall的方式實現(xiàn)，其中需避免所有進程在同一時刻向同一進程進行irevs和isends。

（3）對于長消息且進程數(shù)為2的冪，使用配對交換算法，需p-1個傳輸步。

（4）對于長消息且進程數(shù)不為2的冪，以第i步，每個進程從rank-1收消息，向rank+1發(fā)消息的流程進行，需p-1個傳輸步。

對于大規(guī)模的Alltoall通信，分別在短消息時用算法（1），在其余長度的消息時使用算法（3）和算法（4）。用k表示消息塊的大小，p表示進程數(shù)，α表示通信延遲，β表示通信帶寬的倒數(shù)，Alltoall時間開銷分別可以表示為：

從以上算法體現(xiàn)的Alltoall時間開銷看，Alltoall通信性能建模依賴于通信延遲和通信帶寬的準確刻畫。由于通信延遲和通信帶寬一方面依賴于高性能計算機互連網絡的實現(xiàn)技術，一方面依賴于系統(tǒng)負載情況，其性能的準確刻畫并非易事。Alltoall涉及到p個進程同時進行通信，當p的數(shù)量達到一定規(guī)模時，其通信性能不可避免地有所差別，這也是在Aalltoall性能建模時需要考慮的。

3　Alltoall通信性能模型

Alltoall通信性能模型依賴于互連網絡通信性能模型，考慮到大規(guī)?；ミB通信網絡中通信性能模型的復雜性，本文首先選擇一個實際系統(tǒng)進行評測，以期總結其性能特征。在此基礎上，結合Alltoall的特點，建立一個較為合理的性能模型，然后在此基礎上設計Alltoall通信性能模型。

3.1　測試平臺

測試平臺選擇某國產并行機（簡稱BXJ），該系統(tǒng)的每個計算節(jié)點包含2顆英特爾微處理器，每顆微處理器包含6個計算核心；互連系統(tǒng)采用自主設計的高階路由芯片（network route chip，NRC）和高速網絡接口芯片（network interface chip，NIC），實現(xiàn)光電混合的二層胖樹結構高階路由網絡互連。NRC采用了16×16高階網絡交換部件，計算節(jié)點最大跳轉次數(shù)為3，工作主頻為312.5 MHz，時鐘周期為3.2 ns，基本傳輸單位為256 bit。BXJ并行機通信系統(tǒng)的性能參數(shù)詳見表1，NRC路由交換芯片的基本參數(shù)詳見表2。

Table 1　Basic parameters for communication system of BXJ parallel computer表1　BXJ并行機通信系統(tǒng)基本參數(shù)

Table 2　Basic parameters for NRC interconnection表2　NRC互連基本參數(shù)

3.2　基本通信性能分析

選用Intel IMB測試程序，測試BXJ上16至8 192個MPI進程執(zhí)行Sendrecv操作的通信延遲和通信帶寬情況。與Alltoall類似，測試程序中的每個MPI進程同時執(zhí)行Sendrecv操作，都參與數(shù)據(jù)通信。測試含單計算節(jié)點啟動8個MPI進程和12個MPI進程2組測試。表3和表4是有關通信延遲的部分測試結果，圖1是測試中出現(xiàn)的通信延遲抖動（通信延遲的最大波動幅度與通信延遲的平均值之比）與進程數(shù)間的關系。其中的趨勢線顯示：通信延遲的抖動幅度隨著進程數(shù)的增多明顯呈增大的趨勢。

Fig.1　Relationship between latency and the number of processes圖1　通信延遲抖動與進程數(shù)間的關系

表3和表4是16～8 192進程時，通信延遲的具體結果，其中單MPI進程的消息塊分別是4 KB和16 KB。表3和表4中的數(shù)據(jù)顯示：無論是單計算節(jié)點啟動8個MPI進程，還是單計算節(jié)點啟動12個MPI進程，這種通信延遲的抖動都在一定程度上存在。計算節(jié)點啟動的MPI進程較多時，抖動的幅度更大。

圖2和圖3是BXJ上16進程至8 192進程下的通

信帶寬情況。圖2和圖3的數(shù)據(jù)顯示：計算節(jié)點的通信帶寬隨消息塊的增大而增加，直到達到最大值，不同進程數(shù)下節(jié)點的增長趨勢基本一致；單節(jié)點上所有MPI進程分享通信帶寬，啟動的MPI進程數(shù)越多，分享的帶寬越少。

Table 3　Relationship between latency and the number of processes(8 processes per node)表3　通信延遲與進程數(shù)的關系（單節(jié)點8個MPI進程）

Table 4　Relationship between latency and the number of processes(12 processes per node)表4　通信延遲與進程數(shù)的關系（單節(jié)點12個MPI進程）

Fig.2　Relationship between communication bandwidth of single MPI process and the size of messages圖2　單進程時MPI通信帶寬與數(shù)據(jù)傳輸量間的關系

Fig.3　Relationship between cumulative communication bandwidth of single node and the size of messages圖3　單計算節(jié)點通信帶寬與數(shù)據(jù)傳輸量間的關系

基于以上對大規(guī)模并行情況下通信延遲和通信帶寬情況的分析，可以得出以下基本結論：

（1）通信延遲的準確刻畫并非易事，隨著進程數(shù)和數(shù)據(jù)傳輸量的增加，網絡傳輸會存在競爭，導致通信延遲的變化和性能抖動。

（2）對于通信帶寬，利用MPI進程實測通信帶寬基本可以反映其特征。

3.3　Alltoall性能模型

已有的研究[14]顯示，通信性能與負載有關。評估互連網絡性能需要定義負載模型，涉及目的分布、注入速率和消息長度等。

對于Alltoall集合通信而言，目的分布是均勻的，數(shù)據(jù)注入規(guī)律簡單，消息長度固定，因而評估其通信延遲時可以在已有通信性能模型[15]上簡化?？紤]到互連網絡的多樣性，本文僅僅針對多級互連網絡（multistage interconnection networks，MINs）進行建模，這是當前使用最為普遍的網絡類別。

通常來說，實現(xiàn)N個計算節(jié)點互連的N×NMIN互連網絡由L=logkN級k×k交換單元構成。為便于描述，假定網絡完全由k×k交換部件構成，k×k交換部件含k個輸入端口和k個輸出端口，每個輸出端口在單時鐘周期內分別可以接受一個報文。為防止阻塞，每個輸出端口的buffer實現(xiàn)為FIFO（first input first output）隊列。到達的報文直接進入到與目的輸出端口對應的buffer，不同的buffer之間不會有沖突。

對于以上理想的交換單元，令其時鐘周期為tc，tT為從交換單元到下一交換單元的傳輸時間。假定在每個時鐘周期，報文到達每個輸入端口的可能性為ρ，令vn表示在時刻n加入到一個輸出隊列的報文的數(shù)目，那么v1,v2,…,vn為獨立的符合伯努利分布的隨機變量。到達報文數(shù)量的數(shù)學期望E=其方差令q為n時刻n在隊列中的報文數(shù)目，qn和vn有如下關系式：

上面排隊關系可以用M/G/1隊列系統(tǒng)描述[16-17]，相應地，到達輸出端口報文數(shù)的數(shù)學期望為：

報文通過交換部件的時間的數(shù)學期望為：

報文通過交換部件的等待時間的數(shù)學期望為：

求出E和V代入上式，可以得到：

將式（3）引入到式（2），可以得到增加了網絡競爭因素的Alltoall性能模型：

其中，kp是網絡最小傳輸單位（報文）的大??；nhop是報文需要經過的交換單元數(shù)目。

4　模型驗證和評估

由于BXJ測試平臺處于生產性運行狀態(tài)，實際測試時沒有機會占用全系統(tǒng)，以下相關測試的最大并行規(guī)模為8 192個MPI進程，Alltoall的實測采用Intel IMB測試程序獲得。

4.1　傳統(tǒng)Alltoall性能模型評估

首先，評估實測值與采用傳統(tǒng)模型時理論估值的對比情況，圖4和圖5是對比結果圖。其中，理論值按照實際實現(xiàn)算法估算，在128 B短消息時使用Bruck算法，在16 KB消息時下使用Long算法，涉及的通信延遲α和通信帶寬β分別使用系統(tǒng)標稱的理論值和實測值。圖中，Alltoall的實測值用Real標注，另外標注中的8和12表示單節(jié)點啟動的MPI進程數(shù)；理論值用“算法名＋數(shù)字＋字母”標注，例如：Long8B表示理論值按Long算法估算，單節(jié)點啟動8個MPI進程，字母B表示通信延遲α和通信帶寬β采用理論值；Bruck12A表示理論值按Bruck算法估算，通信延遲α和通信帶寬β采用實測值。

Fig.4　Comparison of actual value and predicted value by differentAlltoall models on BXJ(16 KB message)圖4　BXJ上Alltoall傳統(tǒng)模型估值與實測值對比（16 KB消息）

Fig.5　Comparison of actual value and predicted value by differentAlltoall models on BXJ(128 B message)圖5　BXJ上Alltoall傳統(tǒng)模型估值與實測值對比（128 B消息）

考慮到同一消息塊不同進程數(shù)下Alltoall的實測值與傳統(tǒng)模型理論估值的差別太大，為方便比較，圖4和圖5中延遲值是實際數(shù)的對數(shù)值（2為冪）。圖4和圖5中的結果顯示：（1）相比使用通信延遲和通信帶寬的理論值，以實測值為參數(shù)，Alltoall理論值更接近于實測值；（2）即便以實測值為參數(shù)，Alltoall理論值的準確性有所提高，但僅在MPI進程數(shù)小于128時有效，超過128進程后實測值基本上是理論值的數(shù)倍，顯示出傳統(tǒng)的Alltoall模型在大規(guī)模并行時對于Alltoall的性能評估存在明顯缺陷。

4.2　新Alltoall性能模型評估

表5和表6分別是4 KB消息塊和16 KB消息塊時Alltoall實測性能（延遲值）與理論預估的對比，分為單計算節(jié)點啟動8個MPI進程和12個MPI進程兩組，MPI并行規(guī)模從512進程至最大8 192進程。表中“原模型”為利用式（2）的估算結果，“新模型”為式（4）的估算結果。

Table 5　Comparison of actual value and predicted value by differentAlltoall models(4 KB message)表5　Alltoall實測性能與理論值對比（4 KB消息塊）

Table 6　Comparison of actual value and predicted value by differentAlltoall models(16 KB message)表6　Alltoall實測性能與理論值對比（16 KB消息塊）

在理論估算中，通信延遲α，使用表1中的MPI通信延遲值和MPI單向通信帶寬值，計算通信數(shù)據(jù)量時考慮單計算節(jié)點啟動8個MPI進程和12個MPI進程對應到單個通信端口數(shù)據(jù)量的差別。在使用新模型時，依照數(shù)量傳輸量換算公式（3）的p值，其余參數(shù)選擇表2中的數(shù)據(jù)。

表5和表6中的數(shù)據(jù)顯示：（1）引入網絡競爭后的Alltoall性能預估值與實測值非常接近，體現(xiàn)出網絡競爭是可以預測的；（2）從數(shù)值上看，影響大規(guī)模Alltoall性能的主要因素是網絡競爭開銷，而網絡的基本傳輸延遲和傳輸帶寬的占比很小；（3）Alltoall性能實測時有時會有很大的波動，如表5中2 048個進程（單節(jié)點啟動8個MPI進程）時Alltoall實測值存在明顯的跳躍，這種現(xiàn)象是由于突發(fā)的網絡擁塞造成的。

5　小結

綜合以上測試和分析，不難看出：

（1）MPI通信性能對于底層互連通信系統(tǒng)性能的依賴性很強，并且與負載有關。尤其是對于Alltoall這種讓所有參與通訊的進程進行彼此數(shù)據(jù)交換的集合通信操作，其性能對于底層互連通信系統(tǒng)的要求最高，最難實現(xiàn)非常好的可擴展性。

（2）預估Alltoall通信的理論值時，需要考慮網絡競爭的影響，否則，無論是采用MPI的通信延遲和通信帶寬的理論，還是采用實測值，都不一定能夠反映出Alltoall的真實特性，尤其是面對大規(guī)模Alltoall操作。

（3）在大規(guī)模并行時，主導Alltoall性能的主要因素是網絡競爭開銷，而不是網絡的基本傳輸延遲和傳輸帶寬。

[1]Luszczek P,Dongarra J,KoesterD,et al.Introduction to the HPC challenge benchmark suite[R].Springfield:Lawrence Berkeley National Laboratory,2005.

[2]The CPMD Consortium.CPMD:Car-Parrinello molecular dynamics,Version3.15.3[EB/OL].(2015)[2016-07-30].http://cpmd.org/downloadable-files-authentication/manual.pdf.

[3]Rao Li,Zhang Yunquan,Li Yucheng.Performance test and analysis of Alltoall collective communication on domestic hundred trillion times cluster system[J].Computer Science,2010,37(8):186-188.

[4]Liu Yang,Cao Jianwen,Li Yucheng.Testing and analyzing of collective communication models[J].Computer Engineering andApplications,2006,42(9):30-33.

[5]Luo Hongbing,Zhang Xiaoxia.Analysis of scalability for MPI collective communication[J].Journal of Frontiers of Computer Science and Technology,2017,11(2):252-261.

[6]Xu Cong,Venkata M G,Graham R L,et al.SLOAVx:scalable logarithmic AlltoallV algorithm for hierarchical multicore systems[C]//Proceedings of the 13th International Symposium on Cluster,Cloud,and Grid Computing,Delft,May 13-16,2013.Washington:IEEE Computer Society,2013:369-376.

[7]Li Qiang,Sun Ninghui,Huo Zhigang,et al.Optimizing MPI Alltoall communications in multicore clusters[J].Journal of Computer Research and Development,2013,50(8):1744-1754.

[8]Bruck J,Ho C T,Kipnis S,et al.Efficient algorithms for all-to-all communications in multiport message-passing systems[J].IEEE Transactions on Parallel and Distributed Systems,1997,8(11):1143-1156.

[9]Kumar S,Mamidala A,Heidelberger P,et al.Optimization of MPI collective operations on the IBM blue gene/Q supercomputer[J].International Journal of High Performance ComputingApplications,2014,28(4):450-464.

[10]Mamadou H N,Nanri T,Murakami K,et al.Performance analysis and linear optimization modeling of all-to-all collective communication algorithms[C]//Proceedings of the 19th Symposium on Computer Architecture and High Performance Computing,Gramado,Oct 24-27,2007.Washington:IEEE Computer Society,2007:203-210.

[11]Chan E,Heimlich M,Purkayastha A,et al.Collective communication:theory,practice,and experience[J].Concurrency and Computation:Practice and Experience,2007,19(13):1749-1783.

[12]Culler D E,Karp R M,Patterson D,et al.LogP:a practical model of parallel computation[J].Communications of the ACM,1996,39(11):78-85.

[13]Alexanddrov A,Ionescu M F,Schauser K E,et al.LogGP:incorporating long messages into the LogP model-one step closer towards a realistic model for parallel computation[C]//Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures,Santa Barbara,Jul 17-19,1995.New York:ACM,1995:95-105.

[14]Duato J,Yalamanchili S,Ni L.Interconnection network:an engineering approach[M].Xie Lunguo,Zhang Minxuan,Dou Qiang,et al.Beijing:Publishing House of Electronics Industry,2004:341-345.

[15]Garofalakis J,Stergiou E.An analytical model for the performance evaluation of multistage interconnection networks with two class priorities[J].Future Generation Computer Systems,2013,29(1):114-129.

[16]Kruskal C P,Snir M.The performance of multistage interconnection networks for multiprocessors[J].IEEE Transactions on Computers,1983,32(12):1091-1098.

[17]Agarwal A.Limits on interconnection network performance[J].IEEE Transactions on Parallel and Distributed Systems,1991,2(4):398-412.

附中文參考文獻：

[3]饒立,張云泉,李玉成.國產百萬億次機群系統(tǒng)Alltoall性能測試與分析[J].計算機科學,2010,37(8):186-188.

[4]劉洋,曹建文,李玉成.聚合通信模型的測試與分析[J].計算機工程與應用,2006,42(9):30-33.

[5]羅紅兵,張曉霞.MPI集合通信性能可擴展性研究與分析[J].計算機科學與探索,2017,11(2):252-261.

[7]李強,孫凝暉,霍志剛,等.MPI Alltoall通信在多核機群中的優(yōu)化[J].計算機研究與發(fā)展,2013,50(8):1744-1754.

[14]Duato J,YalamanchiliS,Ni L.并行計算機互連網絡技術:一種工程方法[M].謝倫國,張民選,竇強,譯.北京:電子工業(yè)出版社,2004:341-345.