武林平，景翠萍，劉 旭，田鴻運

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

“塊同步并行”(Bulk Synchronous Parallel,BSP)模式(如圖1所示)的理想運行情況下，為滿足負載平衡需求，任務被均勻地分配到并行程序的每個進程，從而保證每個進程都具有相同的計算性能、通信性能、訪存性能，進而使得所有進程均在相同的時刻到達同步點。然而，在實際運行情況下，并行程序本身的算法特征、系統(tǒng)噪音的擾動等因素將破壞這種負載平衡，使得各計算進程不能在同一時刻到達同步點(并行程序的實際運行過程如圖2所示)，從而引起進程間的相互等待現(xiàn)象[1]。對于阻塞式的點對點通信而言，通信接收方的執(zhí)行進度將依賴于通信發(fā)送方的進度，在這個過程中，通信接收方從啟動數(shù)據接收操作到實際開始接收數(shù)據的這段時間稱為通信等待時間[2]。聚合通信過程也類似，因為它的完成需要每個進程參與，當少數(shù)進程未能及時到達同一個聚合通信點時，將引起所有參與進程的相互等待現(xiàn)象。

相關研究表明，MPI并行程序在運行過程中，通信等待時間將構成大規(guī)模并行程序通信時間的主要部分[2]。特別是將通信密集型應用程序擴展到大規(guī)模處理器核數(shù)時，這種通信等待現(xiàn)象將加劇，對實現(xiàn)高性能的并行應用程序提出了嚴峻的挑戰(zhàn)。

圖1 BSP并行程序的理想運行過程Fig.1 Ideal state of BSP parallel program

圖2 BSP并行程序的實際運行過程Fig.2 Real state of BSP parallel program

1 通信等待問題的診斷方法相關研究

1.1 MPI通信等待模式

通常，MPI并行程序中通信等待現(xiàn)象最初是由同步點之前的計算負載不均衡或通信不均衡等原因引發(fā)的。但各類因素之間的相互干擾及傳播效應，將造成通信等待現(xiàn)象存在于MPI并行程序的全部運行過程中。這種“現(xiàn)象”與“原因”之間的復雜關聯(lián)關系，使得定位導致通信等待問題的根本原因的診斷過程變得非常復雜。例如某個計算過程在某段時間內計算負載不均衡，但下個時刻這種負載不均衡現(xiàn)象可能與其他計算過程的負載不均衡現(xiàn)象相互抵消，這種負載不均衡現(xiàn)象并不會導致MPI通信等待問題。

因此，分析通信等待現(xiàn)象如何形成、在何處形成，對于快速準確地找到其根本原因從而消除通信等待現(xiàn)象至關重要。文獻[2]詳細分析了MPI并行程序中點對點通信、聚合通信以及同步過程中可能出現(xiàn)的各種通信等待模式。文獻[3]提出了一種名為FACT的Trace分析技術，可在小規(guī)模系統(tǒng)上低開銷地獲取大規(guī)模并行程序的通信軌跡數(shù)據，采用人工分析方法可識別MPI并行程序中的通信等待模式。參考MPI-3標準，MPI通信過程中主要存在以下幾種常見的通信等待模式[2]：

1)點對點通信過程中：存在2種典型的通信等待模式，包括晚發(fā)送模式和晚接收模式，分別如圖3(a)和圖3(b)所示。

2)同步過程(MPI_Barrier)中：同步過程中出現(xiàn)的通信等待問題主要是因為進程不能及時到達同步點產生的，主要形成過程如圖3(c)所示，稱為早同步模式。

3)聚合通信過程中：存在多種典型的通信等待模式，包括晚廣播模式、早規(guī)約模式以及全局交換模式等，其中早規(guī)約模式如圖3(d)所示。在早規(guī)約模式下，進程過早參與聚合通信，導致這些進程上出現(xiàn)通信等待現(xiàn)象。以此類推，其他聚合通信等待模式的形成過程也是類似的。

(a) 晚發(fā)送模式(a) Late sender pattern

(b) 晚接收模式(b) Late receiver pattern

(c) 早同步模式(c) Early barrier pattern

(d) 早規(guī)約模式(d) Early reduce pattern圖3 常見的MPI通信等待模式Fig.3 Scheme of MPI communication waiting

1.2 通信等待模式的量化分析方法

針對以上幾種常見的通信等待模式，相關研究主要從原因定位、通信等待時間量化分析、通信等待問題診斷模型(Diagnostic Model for Communication Waiting Problem, CWP-DM)3個方面，詳細分析了MPI并行程序中通信等待問題形成的原因以及可能產生的影響。

為了更加清楚地闡述該問題，下面首先給出超時時間、等待時間、同步間隔這3個關鍵詞的具體含義。

1)超時時間：特指造成通信等待現(xiàn)象的原因，例如某代碼段在進程p上的運行時間遠超平均值，超出平均值的時間即為超時時間。一般來講，MPI并行程序的超時時間將存在于多個代碼段，這些超時時間將逐步累加，最終導致通信等待現(xiàn)象的發(fā)生。

2)等待時間：指進程已參與MPI通信但仍處于空閑等待狀態(tài)的時間，是通信等待現(xiàn)象的表現(xiàn)形式。

3)同步間隔：進程p和進程q的兩個相鄰同步點之間的時間間隔稱為一個同步間隔。在一個同步間隔內，進程p和進程q之間沒有其他同步點。

1.2.1 通信等待問題形成的原因

圖4以點對點通信等待模式為例，采用時間線圖描述MPI并行程序中由于計算負載不均衡、通信不均衡等引發(fā)的通信等待現(xiàn)象[4]。其中，不同進程上執(zhí)行的函數(shù)都以不同顏色的矩形方框表示，矩形方框的長度表示每個函數(shù)的執(zhí)行時間，進程間帶箭頭的線段表示進程間的通信關系或同步關系。例如，S1表示進程1上執(zhí)行的MPI_Send函數(shù)，S2表示進程2上執(zhí)行的MPI_Send函數(shù)，R1表示進程2上執(zhí)行的MPI_Recv函數(shù)，comp表示計算函數(shù)。

圖4 MPI并行程序中通信等待問題的時間線圖Fig.4 Time-line diagram of communication waiting in MPI parallel program

在圖4中，進程2和進程3都出現(xiàn)了通信等待現(xiàn)象，顯示為進程2和進程3上的陰影區(qū)域。MPI并行程序中通信等待現(xiàn)象可分為直接等待現(xiàn)象和間接等待現(xiàn)象。由于某個進程上函數(shù)的執(zhí)行時間超時直接引發(fā)另一個進程上出現(xiàn)的等待現(xiàn)象稱為直接等待現(xiàn)象，產生的等待時間稱為直接等待時間；直接等待現(xiàn)象進一步傳播而引發(fā)的通信等待現(xiàn)象稱為間接等待現(xiàn)象，由此產生的等待時間稱為間接等待時間[5]。在圖4示例中，進程2上的通信函數(shù)R1產生了直接等待時間，它是由進程1上執(zhí)行的函數(shù)comp計算超時引起的。與此同時，進程2上出現(xiàn)的直接等待現(xiàn)象又進一步引發(fā)進程3上出現(xiàn)間接等待現(xiàn)象，因此進程3上產生了間接等待時間。除此之外，進程3上還產生了直接等待時間，這是由于進程2上的通信函數(shù)R1執(zhí)行時間超時引起的。

1.2.2 通信等待時間量化分析

通常采用Trace分析技術檢測MPI并行程序中的通信等待時間。文獻[6]針對MPI并行程序中點對點通信和聚合通信，提出了一種測量通信等待時間的方法：首先記錄MPI通信和同步操作在每個進程上的執(zhí)行時間，然后計算時間位移從而獲取通信等待時間。文獻[7]針對MPI單邊通信，提出了一種測量通信等待時間的方法，該方法借鑒了文獻[4]中的研究思路。

本文中，用二元組(p,i)來描述進程p上執(zhí)行的函數(shù)i。理想情況下，參與通信的進程應同時開始執(zhí)行相應的通信函數(shù)。如果進程p上的通信函數(shù)(p,i)的完成取決于另一個進程q上執(zhí)行的函數(shù)(q,k)，并且進程p在進程q開始執(zhí)行函數(shù)(q,k)之前開始執(zhí)行函數(shù)(p,i)，則這兩個函數(shù)形成了一個同步點。因此，同步點S=((p,i),(q,k))是函數(shù)(p,i)和函數(shù)(q,k)的二元組，并且同步點的形成需要滿足以下條件[8]：

1)函數(shù)(p,i)的完成取決于函數(shù)(q,k)；

2)函數(shù)(p,i)比函數(shù)(q,k)開始執(zhí)行得早，即Enter(p,i)

3)兩個函數(shù)存在重疊的執(zhí)行時間，即Exit(p,i)>Enter(q,k)。

因此，對于進程p上執(zhí)行函數(shù)(p,i)和進程q上執(zhí)行函數(shù)(q,k)的這段時間內，進程p上執(zhí)行的函數(shù)(p,i)出現(xiàn)通信等待現(xiàn)象。其中，等待時間可量化[9]為：

w(p,i)=Enter(q,k)-Enter(p,i)

(1)

式(1)不僅適用于點對點通信等待模式，而且適用于同步等待模式和聚合通信等待模式。對于后者，進程q特指最晚參與同步過程或最晚參與聚合通信的進程。

1.2.3 通信等待問題診斷模型

通?；谕ㄐ诺却龁栴}診斷模型可定位導致通信等待問題的關鍵函數(shù)，然后人工分析這些關鍵函數(shù)的詳細執(zhí)行行為，最終定位導致通信等待問題的根本原因。文獻[9]中提出了一種通信等待問題診斷模型，給出了在所有同步間隔中某個函數(shù)調用路徑導致的直接等待時間和間接等待時間，見式(2)：

(2)

該診斷模型考慮了多方面因素的影響，分析了直接等待時間和間接等待時間形成的根本原因，并且需要對MPI并行程序中所有函數(shù)調用路徑展開詳細的測量與分析[10]。然而，在實際應用過程中，測量發(fā)現(xiàn)這種診斷模型耗費的內存開銷較大，比如LARED集成程序[11]在1024核運行時單進程的內存開銷高達16 GB，測量數(shù)據見表1。文獻[8]中還指出，將上述模型應用到Sweep3D程序中，測量時間和內存開銷隨著并行規(guī)模的擴大將快速增長。除此之外，過大的測量開銷將導致性能數(shù)據出現(xiàn)偏差，從而導致診斷算法誤報率增大。對于內存受限的高性能計算機系統(tǒng)(例如平均單核內存少于2 GB)，上述模型引入的測量開銷甚至可能造成診斷失效。

表1 LARED程序運行1000個時間步單進程的內存開銷Tab.1 Memory overhead for LARED program running in 1000 time steps

2 基于熱點函數(shù)的通信等待問題診斷方法

2.1 診斷模型

根據以上分析，考慮測量開銷可控、診斷算法誤報率低的實際需求，需要精簡通信等待問題診斷模型，降低測量與分析開銷。對于MPI并行程序，定位間接等待現(xiàn)象產生的原因將會帶來額外的開銷，并且直接等待現(xiàn)象消除后，間接等待現(xiàn)象也隨之消除。因此，本文建立的通信等待問題診斷模型不再考慮直接等待現(xiàn)象的傳播對程序性能的間接影響，只定位導致直接等待現(xiàn)象的計算超時或通信超時函數(shù)。另外，程序的性能瓶頸大多是由于性能熱點函數(shù)引發(fā)的，為了更精準定位通信等待問題，本文建立的通信等待問題診斷模型首先從熱點函數(shù)引發(fā)的通信等待時間入手。例如，可選取執(zhí)行時間大于1%的函數(shù)作為熱點函數(shù)。

在一個同步間隔內，進程p上的函數(shù)(p,c)的執(zhí)行時間由式(3)計算給出。為了準確反映每個函數(shù)對MPI并行程序的通信等待時間形成的影響，式(3)排除了直接等待現(xiàn)象的傳播對程序性能產生的間接影響。

t(p,c)=Exit(p,c)-Enter(p,c)-w(p,c)

(3)

在一個同步間隔內，進程p上執(zhí)行的函數(shù)(p,c)的超時時間則是由函數(shù)c在進程q和進程p上的執(zhí)行時間之間的差值計算得出，見式(4)。在一個同步間隔內，由于執(zhí)行時間差為負數(shù)的函數(shù)不會引起進程p出現(xiàn)通信等待現(xiàn)象，因此這部分時間忽略不計。

(4)

根據以上分析，針對MPI并行程序，建立基于熱點函數(shù)的通信等待問題診斷模型(Diagnostic Model for Communication Waiting Problem based on Hotspots, H-CWP-DM)，見式(5)。

(5)

該診斷模型通過比較一個同步間隔內各熱點函數(shù)的執(zhí)行時間來定位超時時間較大的函數(shù)，從而確定導致通信等待問題的關鍵函數(shù)，并可給出這些關鍵函數(shù)產生的通信等待時間。通過該診斷模型，可定位產生通信等待時間比較大的關鍵函數(shù)，然后分析這些關鍵函數(shù)的詳細執(zhí)行行為，最終可以定位產生通信等待問題的根本原因。除此之外，式(5)建立的診斷模型不僅適用于點對點通信等待模式，而且適用于同步等待模式和聚合通信等待模式。對于后者，進程q特指最晚參與同步活動或最晚參與聚合通信的進程，并且選取最早參與同步活動或最早參與聚合通信活動的進程p來分析進程p上產生通信等待現(xiàn)象的根本原因。

2.2 診斷流程

基于H-CWP-DM診斷模型，總結出精簡版、更實用的通信等待問題診斷流程，主要包括以下步驟：

步驟1：測量并分析MPI并行程序運行時的性能熱點函數(shù)。

步驟2：測量MPI并行程序的通信等待時間，確定通信等待時間對應的同步間隔。

步驟3：根據H-CWP-DM診斷模型，定位產生通信等待時間比較大的關鍵函數(shù)。

步驟4：從計算、訪存、通信等方面分析關鍵函數(shù)的詳細執(zhí)行行為，明確產生通信等待問題的根本原因。

3 實際應用

3.1 高性能計算平臺

圖5 并行程序運行時行為測量軟件平臺Fig.5 Software of performance measurement for parallel applications at run time

為了獲取H-CWP-DM診斷模型需要的各種性能數(shù)據，在某并行機系統(tǒng)上基于主流性能分析工具形成了可用的并行程序運行時行為測量軟件平臺，如圖5所示。該軟件平臺可用于測量并行程序在系統(tǒng)上的不同層次、不同方面的性能數(shù)據，包括性能熱點函數(shù)、計算時間、通信時間及等待時間等。

所有測量在一臺包含1050個雙路16核計算節(jié)點的并行機上進行(共33 600個處理器核)，計算節(jié)點操作系統(tǒng)使用Linux；處理器為Intel Xeon系列，每顆處理器包含128 MB的共享三級Cache，內存控制器集成在處理器內部，配置為NUMA結構，單節(jié)點共享64 GB內存。

3.2 MPI并行程序

上述診斷方法目前已應用到LARED-S、二維LARED集成、LAP3D等數(shù)十個實際生產性數(shù)值模擬程序的性能問題診斷過程中。這些程序都是基于MPI實現(xiàn)的大規(guī)模并行程序，可以成功擴展到上萬處理器核[11]。測量發(fā)現(xiàn)這些程序都存在通信等待問題，采用上述方法診斷優(yōu)化后，這些程序的性能都提升了15%以上。下面主要以LARED-S程序的性能問題診斷為例，詳細介紹診斷過程，其他程序的診斷過程類似，這里不再詳述。

3.3 LARED-S程序的性能診斷

根據第2.2節(jié)給出的通信等待問題的診斷流程，LARED-S程序的性能問題診斷過程如下：

步驟1：測量并分析程序運行時的性能熱點函數(shù)。LARED-S程序是歐拉網格下的二維、三維并行多介質輻射流體力學模擬程序，主要用于慣性約束聚變等領域中輻射流體界面不穩(wěn)定性模擬[12]。該程序采用960個進程運行時的性能熱點函數(shù)分布如圖6所示。其中，通信時間占程序執(zhí)行時間的49.4%，計算時間占42.6%。

圖6 LARED-S程序的性能熱點函數(shù)分布Fig.6 Performance hotspots distribution of LARED-S program

步驟2：測量LARED-S程序中通信等待時間，確定通信等待時間對應的同步間隔。測量發(fā)現(xiàn)MPI_Allreduce通信過程中通信等待時間占99%。MPI_Allreduce的通信時間及等待時間在各進程上的分布見圖7，運行3個時間步的最大等待時間之和達125 s，平均每時間步最大等待時間達41.6 s。

圖7 MPI_Allreduce的通信時間及等待時間分布Fig.7 Communication time and waiting time distribution of MPI_Allreduce

步驟3：根據H-CWP-DM診斷模型，定位產生通信等待時間比較大的關鍵函數(shù)。根據式(5)測量并分析性能數(shù)據，定位出導致MPI_Allreduce通信等待時間開銷大的關鍵函數(shù)如圖8所示。測量發(fā)現(xiàn)，在一個時間步內，EOS_Match函數(shù)的EOS_Match_If_970代碼段和EOS_Match_If_946代碼段在聚合通信過程中產生的通信等待時間較大，二者等待時間之和為30 s。在一個時間步內，優(yōu)化前MPI_Allreduce通信過程中產生的通信等待時間為41.6 s；如果EOS_Match_If_970和EOS_Match_If_946代碼段優(yōu)化負載平衡算法后， MPI_Allreduce的執(zhí)行時間最多可減少30 s。由上述數(shù)據可知，這2個代碼段改進后MPI_Allreduce的等待時間可縮短72%(30 s/41.6 s)。

圖8 計算超時導致的等待時間Fig.8 Waiting time caused by excess computation

步驟4：分析關鍵代碼段的詳細執(zhí)行行為，明確產生通信等待問題的根本原因。找到關鍵代碼段之后，需要分析EOS_Match函數(shù)的2個代碼段的詳細執(zhí)行行為。圖9和圖10分別是代碼段EOS_Match_If_970在不同時間步(Step)和不同進程上的執(zhí)行時間和執(zhí)行次數(shù)分布。其中，最大執(zhí)行時間為11 s，平均執(zhí)行時間為2 s，最小執(zhí)行時間0 s；最大執(zhí)行次數(shù)為1.3E+06，平均執(zhí)行次數(shù)為3.3E+05，最小執(zhí)行次數(shù)為0。比較圖9、圖10發(fā)現(xiàn)，該代碼段在時間維度、空間維度的執(zhí)行時間與執(zhí)行次數(shù)分布特征基本吻合。除此之外，測量發(fā)現(xiàn)EOS_Match_If_946代碼段也有類似的規(guī)律，這里不再贅述。

(a) Step=0

(b) Step=1

(c) Step=99

(d) Step=100圖9 EOS_Match_If_970代碼段的執(zhí)行時間分布Fig.9 Execution time distribution of EOS_Match_If_970

(a) Step=0

(b) Step=1

(c) Step=99

(d) Step=100圖10 EOS_Match_If_970代碼段的執(zhí)行次數(shù)分布Fig.10 Visits distribution of EOS_Match_If_970

因此，可推斷代碼段EOS_Match_If_970和EOS_Match_If_946在不同進程上的執(zhí)行次數(shù)分布不均衡是導致聚合通信過程出現(xiàn)通信等待問題的根本原因。據此，開發(fā)人員對EOS_Match函數(shù)進行了2步優(yōu)化：首先根據物理模擬需求精簡了該函數(shù)的計算量，其次通過調整網格剖分策略實現(xiàn)相關代碼段執(zhí)行次數(shù)的均衡分布。優(yōu)化后的LARED-S程序在相同運行條件下性能提升32%，MPI_Allreduce的等待時間縮短44%(18.1s/41.6 s)。

除此之外，本文測量分析了該程序分別采用CWP-DM診斷模型和H-CWP-DM診斷模型所需的診斷開銷，見表2。相比于CWP-DM診斷模型，采用H-CWP-DM診斷模型所耗費的時間開銷和內存開銷都相對較低。由于測量所用的并行機的計算節(jié)點可用主內存為64 GB，而CWP-DM診斷模型單進程所需的內存開銷高達115 GB，因此造成該診斷方法失效。

表2 LARED-S程序運行3個時間步的性能診斷開銷Tab.2 Diagnostic overhead for LARED-S program running in 3 time steps

4 結論

通過對現(xiàn)有通信等待問題診斷方法的深入分析，同時考慮測量開銷可控、診斷算法誤報率低的實際需求，建立了H-CWP-DM診斷模型，并基于該診斷模型總結出精簡版、更實用的通信等待問題診斷方法。將本診斷方法應用到LARED-S、二維LARED集成、LAP3D等數(shù)十個實際生產性數(shù)值模擬程序的通信等待問題診斷過程。實際應用結果表明本診斷方法可精確定位導致通信等待問題的關鍵代碼段，給出的優(yōu)化方案及性能提升空間對于后續(xù)的程序改進具有參考價值。其中，優(yōu)化后的LARED-S程序性能提升32%，通信等待時間縮短44%。

除此之外，針對通信等待問題，未來的研究將立足于下列2個問題：

1)實現(xiàn)通信等待問題的自動化診斷。將本診斷方法集成到并行程序運行時行為測量軟件平臺中，可自動生成通信等待問題的診斷報告，降低人工測量與分析時間。

2)將本診斷方法應用到更大規(guī)模的MPI并行程序中，甚至是超過百萬核運行規(guī)模的應用程序。