結合通信重排和消息合并的通信調度方法研究*

彭晉韜，楊 章,2,劉青凱,2,張 倩

(1.北京應用物理與計算數學研究所，北京 100088;2.中國工程物理研究院高性能數值模擬軟件中心，北京 100088)

1 引言

大規模數值模擬在武器物理、激光聚變等重大領域有著重要的作用。當前高性能計算機即將進入E級計算時代，更大的計算規模和更加復雜的網絡通信對數值模擬應用形成了新的挑戰。大量并行應用可能會由于網絡擁塞的發生而使通信性能下降[1]。所以，如何通過調度算法來減少擁塞從而提高網絡資源利用率，對并行應用有著重要意義。

有一種避免擁塞的通信優化方法是基于通信重排調度來實現的[2]。通信重排是通過重新排列每個通信請求的發出順序來達到改善網絡擁塞的效果。文獻[3]通過重排RDMA(Remote Direct Memory Access operations)通信請求的發出順序來改善網絡通信性能。這一工作研究了2個不同消息大小且不同目的地的RDMA請求的最佳排列順序，以更好地重疊通信初始化和網絡傳輸過程，并將其應用到多個通信請求的重排列算法中。而從預防擁塞角度來看，通信重排在2D-stencil通信模式中可以達到10%～50%的性能提升[4]。但是，通信重排對于小消息主導的通信的作用幾乎可以忽略，而且大量的小消息帶來的算法開銷此時又不可忽略，這成為了重排技術的重要缺陷。除了通信重排以外，在應用層緩解網絡擁塞的辦法還有限制節點同時傳輸的消息數量和正在通信的CPU核數。實驗表明,對于all-to-all模式的通信模式能達到2倍的通信性能提升[5]。

消息合并是一種經典的網絡通信優化方法。其主要原理是通過將細粒度的消息合并成1個大消息來減少網絡延遲對通信的影響。消息合并已經有了非常廣泛的應用并且很多應用取得了很好的成效[3，6 - 10]。文獻[7]在其PGAS(Partitioned Global Address Space)語言上對小消息的遠程內存訪問請求進行合并。但是，消息合并在大消息方面難以取得成果。因為一方面，當大消息主導通信時通信延遲的占比往往很低，所以使用消息合并優化延遲的意義不大；另一方面，對大消息進行消息合并帶來的合并開銷不可忽略，會占用很大的內存帶寬。

Figure 2 Technical route圖2 技術路線

所以，結合通信重排和消息合并的方法不僅可以解決重排技術對于小消息的無奈，而且還可以解決消息合并難以對大消息產生效果的困難。本文從通信調度的角度提出一個針對異步點對點通信的新的調度算法。該算法結合消息合并與通信重排來達到減緩擁塞和降低延遲的目的。基于“天河二號”超級計算機驗證了該算法對于幾個數值模擬應用的優化效果，實驗表明，本文算法最高可以提升41%的通信性能。

2 問題描述和技術路線

如圖1所示，本文的問題是給定1個點對點消息的集合，如何通過消息重排和消息合并減少該組消息的通信時間。點對點通信是并行應用中使用最廣泛的通信方式，在典型的BSP(Bulk Synchronous Parallel)模型中，進程在每個超級步都需要操作遠程數據，每個超級步都會產生一批異步點對點通信集合。本文的調度算法就是針對這樣的消息集合進行優化。

Figure 1 Problem description圖1 問題描述

圖2展示了本文算法采用的技術路線。本文算法分為2部分。第1部分為重排算法。即對于1組有序消息集合M=〈m1,m2,m3,…,mn〉，其初始順序為這組消息原本的調用順序。本文首先通過1個重排雙射映射f(x):{1,2,…,n}→{1,2,…,n}將原本的有序消息集合M轉化為M′=〈mf(1),mf(2),mf(3),…,mf(n)〉。第2部分為消息合并，即通過1個負責消息合并的滿射映射g(x):{1,2,…,n}→{1,2,…,m}(m≤n)將n個消息映射到m個消息，以完成合并。最后，在運行時進行流水線式消息合并，以掩蓋合并的開銷。

3 通信重排算法

本文的通信重排算法基于下述幾點啟發：

(1)關鍵通信應當盡早完成。

(2)更早發送的消息在通信競爭中占有優勢并且受到網絡擁塞的影響更小。

(3)短通信距離的消息有更高的優先級。

基于以上3點啟發，設計1個排序函數，從而決定消息發送的先后順序。

對于關鍵通信，如圖3所示，我們用有向圖表示進程通信圖，其中V為進程集合，E為消息集合。類似地，我們使用G′(V′,E′)表示節點間的通信集合，其中V′為節點集合，E′為節點間通信的集合。有向邊e(e∈E′)的權值為其連接的節點之間的總通信量。圖3為進程通信圖和節點通信圖的復合視圖。基于G和G′可以定義節點對NPs(Node Pairs)和進程對PPs(Process Pairs)表示1對有序節點/進程。關鍵通信在本文中是1個進程對PPmax(s,e)，其定義為在某一節點對內開始節點的總發出消息大小和接收節點的總接收消息大小的最大值。

Figure 3 Communication graph圖3 通信圖

結合啟發(2)和(3)，設計1個評估節點對的權重函數用于將短距離通信放在更高的優先級，并組合進程對間的權重函數形成排序所用的比較函數。對于1個節點對〈A,B〉,該節點對的通信距離定義為|A-B|。

基于關鍵通信和通信距離的定義，開始介紹算法的具體細節。本文算法偽代碼如算法1所示。

算法1通信重排算法

輸入：節點間通信圖G′,進程間通信圖G。

輸出：有序進程對排列OdrArr。

1. functionReorder(G,G′)

2.OdrArr=InitInternodeProcessPairs(G);

3.SORT(OdrArr,ProcPairCmp);

4. returnOdrArr

5. end function

6. functionProcPairCmp(PP1,PP2)/*PP1,PP2是進程對，ProcPairCmp為排序的比較函數*/

7.NP1=GetNodePair(PP1);/*獲取該進程對所在的節點對*/

8.NP2=GetNodePair(PP2);

9.W′1=NodePairWeight(NP1);

10.W′2=NodePairWeight(NP2);

11. ifW′1

12. return False;

13. else ifW′1>W′2then

14. return True;

15. else//當W′1=W′2時

16.WP1=ProcessPairWeight(PP1);

17.WP2=ProcessPairWeight(PP2);

18. end if

19. returnWP1≥WP2;

20.end function

21.functionProcessPairWeight(PP)/*進程對的權重函數*/

22.out=TotalSendMsgSize(PP.StartProcess);

23.in=TotalRecvMsgSize(PP.TargetNode);

24. returnMAX(out,in);

25.end function

26.functionNodePairWeight(NP)/*節點對的權重函數*/

27. return |NP.TargetNode-NP.StartNode|;

28.end function

圖4所示為本文算法流程圖。算法先利用消息集合初始化節點間通信圖和進程間通信圖。接下來則是排序過程。排序的核心是比較函數。從圖4中可以看出，比較函數首先根據進程對所在節點對的通信距離來決定粗粒度的消息順序，對于屬于同一節點對的消息則以其進程對的權重決定消息最后的傳輸順序。注意到排序之后屬于相同節點對的消息在發送順序上都是相鄰的。這有利于后續的消息合并。

Figure 4 Flow chart of rearrangement algorithm圖4 重排算法流程圖

4 基于優先級的消息合并

通過消息重排獲得了消息的優先級順序，該信息描述了進程發送消息請求的順序。在這一節，會以流水線的方式動態地合并和拆分消息。

雖然高性能計算機網絡經過了多年發展，但是網絡提升速度卻不及內存性能提升的速度，而內存提升的速度又落后于計算性能提升的速度。對于網絡自身而言，帶寬提升比例又高于延遲提升比例。對于一些在過去的高性能計算機上運行的并行程序而言，網絡性能提升落后于計算性能提升會導致通信開銷在應用程序開銷中占比提高。而帶寬提升速度高于延遲則會導致應用程序的通信開銷中延遲開銷占比提升。所以，消息合并的需求變得很重要。

傳統的消息合并是利用網絡延遲大小的時間來進行消息合并，以掩蓋延遲。本文消息合并的基本原理是利用節點的總內存帶寬和網絡帶寬的帶寬差來合并消息。內存總帶寬常常為網絡雙向帶寬的數倍，所以在前1個消息傳輸的時候進行消息合并，可以合并出1個比上1個發送的消息更大的消息。這樣做有2個優點：其一通過消息合并能降低延遲的占比；其二是進行流量整形，因為每次合并出來的消息大小都會等比地大于上次發出的消息，這使得消息大小呈指數型增長，越大的消息往往有著更高的網絡帶寬利用率。這種做法帶來的缺點是消息合并和拆分的內存帶寬占用會大于傳統的固定大小的消息合并的內存帶寬占用。

Figure 5 Diagram of message aggregation/restore space-time圖5 消息合并/拆分時空圖

具體而言，某一進程A的消息合并時空圖如圖5所示。進程A發送的第1個消息M1是按照優先級排列而來的第1個消息。消息M1的初始化需要部分內存帶寬和CPU資源。當完成M1的初始化后，M1交由網卡負責消息傳輸。M1在傳輸過程中占用了網卡和部分內存帶寬資源。此時CPU處于空閑，那么利用這段空閑的時間進行消息合并。按照排列好的消息順序依次合并消息。由于內存帶寬數倍于網絡帶寬，所以在M1傳輸期間能夠利用剩余的內存帶寬合并比M1大的消息。當消息M2合并完成時則開始M2消息的初始化。為了讓M2消息的合并和初始化過程充分與M1消息的傳輸過程重疊，M2的合并消息大小需要謹慎選擇，合并的消息太小會影響消息合并的效果，而合并太多的消息則會帶來過高的內存拷貝開銷。最合適的消息合并大小是能使得M1的傳輸時間和M2的合并以及初始化時間之和相等。本文采用的方法是指數級增大消息合并窗口。這里消息合并窗口即為圖5中淺灰色區域。如M2的合并窗口為|M2|,也就是消息M2的消息大小。對同一節點對〈i,j〉內連續合并后的2個消息滿足αij=|Ma|/|Ma-1|。其中αij為節點i和節點j之間的消息合并增長因子。Ma,Ma-1屬于節點對〈i,j〉之間的消息,或者Ma-1為節點對〈i,j〉間的第1個消息(注意到消息經過重排之后來自相同節點對之間的消息在發送順序上是相鄰的)。αij滿足以下公式:

αij=1.5+log2Max(NDOuti,NDlnj)

其中,NDOuti為節點i在節點間通信圖上的出度，NDlnj為節點j在節點間通信圖上的入度。可以看到，當節點i對外的出度或者節點j的入度很高時，由于更多的通信競爭，所以通信時間會變長，此時可以合并更多的消息。接收方對接收到的消息也進行流水線式拆分。當接收到第1個消息M1之后，經過一小段時間間隔接收節點開始拆分M1。與此同時，網卡仍然在接收消息M2，其流水線過程與發送消息類似。

5 實驗及結果

使用基于胖樹網絡的“天河二號”超級計算機作為實驗平臺。天河2的每個節點上有2顆Intel Xeon E5-2692 v2處理器并配備8通道DDR3內存,使用TH Express-2 互連網絡，該網絡能提供16 GB/s的雙向帶寬。

在通信負載的選擇上，基于幾個真實應用并收集它們的節點間點對點通信。這些收集而來的通信作為本文算法的輸入。本實驗使用的應用信息如下所示[11]：

(1)Ascent 軟件是1款PIC(Particle-In-Cell)軟件。它用于模擬慣性約束聚變黑腔中激光等離子體相互作用過程中的電子能量傳輸。

(2)Jems_td是1款三維時域全波電磁模擬應用。它主要應用于電磁環境模擬、電磁特性分析以及電磁兼容性分析等方面[5]。

(3)Jsnt 是1款三維中子-光子耦合離散縱標輸運軟件。這個軟件被用于反應堆屏蔽計算和堆芯物理分析。

(4)Lap3d是1個激光聚變應用軟件。該軟件可以模擬激光在等離子體中傳播造成的不穩定過程[5]。

(5)Lareds同樣是1個應用在激光聚變模擬中的軟件。主要用于模擬輻射流體力學界面不穩定性[5]。

(6)Moasp是1個分子動力學模擬軟件。該軟件已成功應用于反應堆包殼材料的輻照損傷模擬。

本文實驗設置了1組實驗組和對照組，如圖6所示，對照組直接調用通信接口完成數據傳輸，而實驗組則在重排之后使用基于優先級的消息合并進行數據傳輸。

Figure 6 Experimental group and control group圖6 實驗組與對照組

實驗結果如圖7和圖8所示，當使用4個節點的時候，結合通信重排與合并的方法實現了平均12.59%的通信性能提升；而在使用16個節點時，對6個應用平均實現了11.27%的通信性能提升。

Figure 7 Performance improvement and time overhead on 4 nodes圖7 4個節點上的性能提升和時間開銷

Figure 8 Performance improvement and time overhead on 16 nodes圖8 16個節點上的性能提升和時間開銷

6 結束語

本文研究了基于消息聚合和通信重排的方法，該方法一方面通過對大消息進行重排以減緩擁塞；另一方面對消息進行合并以降低延遲，從而實現了應用通信性能提升的目的。

接下來，將擴展本文工作，通過1個點對點通信模型在不同平臺上驗證通信重排對于網絡擁塞的影響。