李超， 趙長海， 晏海華,*， 劉超， 文佳敏， 王增波

(1. 北京航空航天大學 計算機學院, 北京 100083；2. 中國石油集團東方地球物理勘探有限責任公司 物探技術研究中心, 北京 100088)

在高性能計算和并行計算領域中，規(guī)約是最常用的集合通信原語之一。規(guī)約的目標是將各進程上的數(shù)據(jù)按某種操作，如求和或求積，計算為最終結果，并將該結果存放在指定的進程上。存放結果的進程稱為根進程。目前，最廣泛使用的規(guī)約實現(xiàn)為MPI_Reduce[1]。Rabenseifner等[2]統(tǒng)計發(fā)現(xiàn)，在基于MPI實現(xiàn)的并行應用中，耗費在MPI_Reduce和MPI_Allreduce上的時間占所有MPI函數(shù)執(zhí)行時間的40%以上，而MPI_Allreduce又可分解為MPI_Reduce加MPI_Bcast。因此，規(guī)約的性能及可靠性對并行應用具有重要的意義。

在規(guī)約的性能優(yōu)化研究中，早期研究主要集中于在理想計算環(huán)境中達到最優(yōu)性能的規(guī)約算法。理想計算環(huán)境是指集群中每個計算節(jié)點配置均為一致，任意兩節(jié)點間的網(wǎng)絡延遲均相同，且并行應用在規(guī)約過程中獨占集群資源。文獻[3]提出了基于最小生成樹(MST)的規(guī)約算法，MPICH早期版本[4]的規(guī)約實現(xiàn)也采用該算法。文獻[5]提出了3種規(guī)約算法：向量對分和距離加倍(vector halving and distance doubling)、二元塊(binary blocks)以及環(huán)形(ring)算法。目前主流MPI版本，包括Open MPI、MPICH、MVAPICH等，所采用的規(guī)約算法是二項樹算法和Rabenseifner算法[5]。MST和二項樹算法的時間復雜度如式(1)中的T1所示，Rabenseifner算法的時間復雜度如式(1)中的T2所示。

(1)

式中:a為兩節(jié)點間的網(wǎng)絡通信延遲；β為傳輸一個字節(jié)所耗費的時間；n為消息長度；γ為對一個字節(jié)進行規(guī)約計算時所耗費的時間；p為進程總數(shù)。

實際環(huán)境中，各節(jié)點間的網(wǎng)絡延遲受網(wǎng)絡拓撲結構影響，不同節(jié)點間的網(wǎng)絡延遲可能不同。針對該問題，出現(xiàn)了一系列基于網(wǎng)絡拓撲感知的規(guī)約性能優(yōu)化研究。文獻[6]給出了一種網(wǎng)絡拓撲發(fā)現(xiàn)方法，該方法根據(jù)各節(jié)點間網(wǎng)絡延遲大小，構建了一個多級網(wǎng)絡拓撲結構，再根據(jù)該拓撲構建性能更優(yōu)的二項樹結構?；谙嗤芯克悸返倪€有文獻[7-11]。文獻[12]提出了一種在廣域網(wǎng)上優(yōu)化規(guī)約性能的方法，其核心思路是盡量將計算和通信局限在局域網(wǎng)內(nèi)部，以最大程度地降低需要通過廣域網(wǎng)傳輸?shù)臄?shù)據(jù)量。

以上研究均建立在靜態(tài)計算資源模型之上，即假定在規(guī)約執(zhí)行過程中，各計算節(jié)點的CPU性能、內(nèi)存性能以及任意兩節(jié)點間網(wǎng)絡延遲皆固定不變。然而，在真實環(huán)境中，該假設在多數(shù)情況下難以成立，具體表現(xiàn)在以下幾方面：

1) 在基于商用集群搭建的高性能計算環(huán)境中，為提高集群的資源利用率，多個并行應用通常會被調(diào)度至同一集群上。由于受其他應用干擾，導致規(guī)約在執(zhí)行過程中所依賴的計算資源的性能是動態(tài)變化的。

2) 對于非阻塞規(guī)約，由于應用的主體計算部分可以和規(guī)約同時執(zhí)行，主體計算引起的計算資源動態(tài)變化也會影響規(guī)約的執(zhí)行，且此種干擾無法避免。

3) 同時執(zhí)行多個規(guī)約時，即并發(fā)規(guī)約，各規(guī)約之間會產(chǎn)生相互干擾。

靜態(tài)計算資源模型假設的特殊性，導致傳統(tǒng)的規(guī)約性能優(yōu)化方法不能較好地適用于真實環(huán)境。除了動態(tài)變化的計算資源性能外，在真實計算環(huán)境中還需要考慮節(jié)點故障問題。隨著集群規(guī)模的不斷增大，集群的平均無故障時間(Mean Time Between Failures, MTBF)不斷下降，根據(jù)文獻[13-14]的統(tǒng)計數(shù)據(jù)，當集群規(guī)模達到數(shù)百節(jié)點時，集群的MTBF將降到6～7 h，這導致規(guī)約在運行過程中遇到節(jié)點故障的概率亦隨之增加。節(jié)點故障會直接導致該節(jié)點上的進程無法參與計算。傳統(tǒng)的基于檢查點/重啟[15-16]的容錯方法越來越不適用于大規(guī)模集群環(huán)境，這是因為檢查點/重啟需要應用進行停止、重新啟動、映像加載、狀態(tài)回滾等一系列操作，這些操作均會帶來較大開銷，嚴重影響應用的性能。FT-MPI[17]和MPI 3.0標準提供了一種為應用返回集合通信接口執(zhí)行狀態(tài)的機制，但并未嘗試如何在應用不退出的前提下，恢復遭遇節(jié)點故障的規(guī)約操作。而基于算法容錯的相關研究[18-20]，目前只能解決一些簡單的集合通信接口的容錯問題以及與矩陣計算相關的容錯問題，也未能解決規(guī)約的容錯問題。當規(guī)約過程中遇到節(jié)點故障時，如何在應用不退出的前提下，保證規(guī)約可以繼續(xù)進行，是一個亟待研究的重要問題。目前該問題尚未得到良好解決。

本文復雜環(huán)境是指，節(jié)點的計算資源性能是不斷動態(tài)變化的，且會出現(xiàn)節(jié)點故障。當前的規(guī)約算法和實現(xiàn)無法較好適應該類環(huán)境，無法實時地根據(jù)節(jié)點計算資源的性能對計算進行動態(tài)調(diào)整，也無法有效處理節(jié)點故障。本文以在動態(tài)復雜環(huán)境中提供高性能、高可靠的規(guī)約算法為目標，提出了一種基于任務并行的高性能分布式規(guī)約框架，實驗結果顯示，在復雜環(huán)境中，其具備更高的性能及更高的可靠性。

1 分布式規(guī)約框架

圖1為分布式規(guī)約框架的架構示意圖，框架采用Master/Worker結構組織所有進程，0號進程為Master。在分布式規(guī)約框架中，每個規(guī)約實例均被分解為一系列可并行執(zhí)行的獨立計算任務。Master節(jié)點上的規(guī)約調(diào)度器負責調(diào)度規(guī)約計算任務，Worker節(jié)點上的規(guī)約執(zhí)行器則負責執(zhí)行規(guī)約計算任務。在規(guī)約執(zhí)行過程中，由數(shù)據(jù)可靠性模塊負責保證原始規(guī)約數(shù)據(jù)的可靠性；容錯模塊負責故障節(jié)點的檢測、通知以及故障恢復；性能計數(shù)器實時統(tǒng)計各節(jié)點的性能狀態(tài)；調(diào)度器根據(jù)性能計數(shù)器和容錯模塊提供的信息，將計算任務實時調(diào)度到性能更高的無故障節(jié)點上。

圖1 分布式規(guī)約框架的架構Fig.1 Architecture of distributed reduction framework

圖2 分布式規(guī)約接口Fig.2 Distributed reduction interface

圖2為分布式規(guī)約框架的規(guī)約接口示意圖，應用可通過繼承ReducerBody自定義規(guī)約數(shù)據(jù)及具體的規(guī)約操作；使用規(guī)約接口時，可指定根進程、存儲規(guī)約結果的對象res、規(guī)約標識符以及參與規(guī)約的進程組；規(guī)約接口支持阻塞調(diào)用和非阻塞調(diào)用2種方式。規(guī)約接口調(diào)用后，會返回一個Future對象f。f將規(guī)約的阻塞模式和非阻塞模式統(tǒng)一為一個接口。應用可調(diào)用f的get接口進入阻塞模式，也可以在規(guī)約調(diào)用后安排其它計算操作，等計算完畢后再調(diào)用isDone查詢規(guī)約是否結束。最后，應用可根據(jù)返回值判斷規(guī)約操作是否成功。

2 基于任務并行的計算模式

傳統(tǒng)的基于二項樹算法實現(xiàn)的MPI規(guī)約有2個缺點。第一，進程間通信依賴關系是根據(jù)算法靜態(tài)確定的，無法適應動態(tài)的復雜環(huán)境。當某節(jié)點繁忙時，依賴于該節(jié)點的其他節(jié)點不得不等待，導致規(guī)約效率下降。第二，需要Send/Recv匹配[21]，如果不能匹配，則無法繼續(xù)計算。在分布式規(guī)約框架中，所有點對點通信均采用支持異步的單邊通信接口，可避免MPI中的Send/Recv配對問題。每個規(guī)約實例均被分解為一系列可并行執(zhí)行的獨立計算任務，由任務調(diào)度器動態(tài)的將計算任務調(diào)度到各節(jié)點上進行計算，從而動態(tài)地建立起規(guī)約樹。在整個過程中，根據(jù)各節(jié)點的實時性能，不斷調(diào)整規(guī)約樹的構建過程，從而有效適應復雜環(huán)境。分布式規(guī)約框架對容錯的支持亦建立在基于任務并行的基礎上。

圖3 基于任務的規(guī)約計算模式Fig.3 Task-based reduction computation pattern

在分布式規(guī)約框架中，記Wi為第i個Worker節(jié)點。圖3(a)為規(guī)約框架執(zhí)行規(guī)約計算的架構示意圖。對于每一個規(guī)約實例，Master端均對應存在一個規(guī)約隊列Q和規(guī)約調(diào)度器S。圖3(b)為規(guī)約計算流程的示意圖。為方便說明，作如下幾個定義：

定義1原始數(shù)據(jù)，記為Oi，指Wi上的原始規(guī)約數(shù)據(jù)。

定義2中間數(shù)據(jù)，記為Di，指在規(guī)約過程中，Wi上的中間規(guī)約結果。

定義3規(guī)約數(shù)據(jù)，Oi或Di，指Wi上的原始數(shù)據(jù)或中間結果。

定義4規(guī)約消息，指Wi上規(guī)約數(shù)據(jù)準備就緒時，向S發(fā)送的消息。消息包含當前進程號Wi以及規(guī)約路徑Pi。

定義5規(guī)約路徑，記為Pi，和規(guī)約數(shù)據(jù)一一對應，由進程號構成的集合。規(guī)約路徑Pi和Di的關系如式(2)所示，即通過對Pi中每個進程號對應的原始規(guī)約數(shù)據(jù)進行規(guī)約后可得到當前的中間數(shù)據(jù)Di。

(2)

式中：m為集合Pi中進程的數(shù)量；Pij為Pi進程集合中的第j個元素；∑通指具體的規(guī)約操作。

定義6規(guī)約任務，包含Wi、Pi、Wj和Pj4類信息，目的是將Wi和Wj上的規(guī)約數(shù)據(jù)進行規(guī)約。

基于任務并行的分布式規(guī)約算法的具體步驟如下：

步驟1Worker端，Wi調(diào)用reduce接口，向Master發(fā)送規(guī)約消息，規(guī)約消息中的進程號為Wi，Pi={Wi}。

步驟2Master端，所有的規(guī)約消息放置在隊列Q中。

步驟3Master端，S從Q中連續(xù)取出2條規(guī)約消息，如果取出的第1條規(guī)約消息中的規(guī)約路徑長度等于p，則廣播通知所有規(guī)約進程規(guī)約結束，跳轉步驟6。否則，進入步驟4。

步驟4Master端，設S得到的2條規(guī)約消息對應的進程號分別為Wi和Wj。根據(jù)這2條規(guī)約消息，生成規(guī)約任務。如果Wi和Wj中某個進程為根進程，則將任務調(diào)度給根進程；否則，根據(jù)性能計數(shù)器采集的每個進程最近一次完成規(guī)約任務的耗時，對比Wi和Wj的性能，將規(guī)約任務調(diào)度給耗時更低的進程，這里假設為Wi。

步驟5Worker端，Wi獲得規(guī)約任務后，向Wj請求規(guī)約數(shù)據(jù)。得到數(shù)據(jù)后，根據(jù)用戶自定義的規(guī)約操作進行規(guī)約計算。最后，向Master發(fā)送規(guī)約消息，其中，進程號為Wi，規(guī)約路徑Pi=Pi∪Pj。發(fā)送完成后，跳轉回步驟2。

步驟6規(guī)約結束。

從以上步驟中可以看出，Master根據(jù)Wi和Wj的規(guī)約消息，生成規(guī)約任務，并將規(guī)約任務調(diào)度給Wi和Wj中的某個進程執(zhí)行，從而將規(guī)約拆分為多個獨立的計算任務，且這些任務是可并行執(zhí)行的。結合圖4進行詳細說明，在圖4中，共有4個進程進行規(guī)約，進程號分別為0，1，2，3。其中，規(guī)約的根進程為1。開始規(guī)約后，這4個進程分別向Master的隊列發(fā)送規(guī)約消息，隊列中消息達到的順序為0，3，1，2。Master首先從隊首取出0和3對應的規(guī)約消息，根據(jù)0和3的規(guī)約消息生成規(guī)約任務1，根據(jù)性能調(diào)度策略，將任務1調(diào)度給進程3。然后繼續(xù)從隊列中取出1和2對應的規(guī)約消息，根據(jù)1和2的規(guī)約消息生成規(guī)約任務2，由于根進程為進程1，所以將任務2調(diào)度給進程1。進程1和進程3上的任務執(zhí)行完畢后，分別向隊列發(fā)送規(guī)約消息，Master根據(jù)1和3的規(guī)約消息生成規(guī)約任務3，又由于根進程為進程1，將任務3調(diào)度給進程1，由進程1完成最后的規(guī)約，并將規(guī)約結果保存在進程1上。在這個過程中，任務1和任務2是獨立的，而且是并行執(zhí)行的。因此，整個過程將規(guī)約拆分為一系列獨立且可并行執(zhí)行的計算任務。每個計算任務的具體執(zhí)行過程參照上述步驟5。

圖4 任務分解示例Fig.4 Example of task decomposition

分布式規(guī)約的時間復雜度T包含2部分，一部分為完成規(guī)約耗費的時間，另一部分為廣播規(guī)約結束信息所耗費的時間。該廣播信息包含2部分，一部分為規(guī)約標識符，另一部分為規(guī)約接口返回值，共4字節(jié)。分布式規(guī)約的時間復雜度如式(3)所示:

T=(a+nβ+nγ+2θ+2λ)lbp+(a+4β)lbp

(3)

式中:θ為發(fā)送一條規(guī)約消息或一個規(guī)約任務的時間；λ為每條規(guī)約消息的平均排隊和處理時間。和式(1)相比，分布式規(guī)約算法由于引入了額外的通信，所以在理想環(huán)境中，其性能低于二項樹算法以及Rabenseifner算法。但分布式規(guī)約算法可以適應復雜環(huán)境，具體表現(xiàn)在如下2個方面：

1) 基于任務的計算機制，可以確保優(yōu)先進入就緒狀態(tài)的規(guī)約數(shù)據(jù)優(yōu)先進行規(guī)約計算。和預先確定了進程間依賴關系的二項樹算法不同的是，在分布式規(guī)約框架中，進程間的依賴關系是根據(jù)到達隊列的先后順序動態(tài)確定的，從而降低了慢節(jié)點對整體性能的影響。這是因為，其余節(jié)點不需要等待慢節(jié)點，可優(yōu)先與已就緒節(jié)點進行計算。

2) 在調(diào)度任務時，總是將任務調(diào)度給性能更高的節(jié)點，可進一步提高規(guī)約計算對復雜環(huán)境的適應能力。

3 運行時容錯

若在規(guī)約過程中遭遇節(jié)點故障，分布式規(guī)約框架將嘗試在并行應用不退出的前提下修復故障。容錯是基于故障偵聽和數(shù)據(jù)可靠性存儲實現(xiàn)的。故障偵聽的實現(xiàn)原理是，Master周期性地向所有進程發(fā)送Ping消息，若某進程Wi在超過一定時間閾值后仍未反饋信息，則認為Wi故障，并將進程Wi廣播給所有其他進程[22]。

為恢復出故障進程丟失的中間數(shù)據(jù)，分布式規(guī)約框架對原始數(shù)據(jù)進行了可靠性存儲。Wi調(diào)用規(guī)約后，其原始數(shù)據(jù)將以雙副本的形式存儲在2個不同的計算節(jié)點的本地盤上。其中，一個節(jié)點為當前節(jié)點，即為Wi；另一個節(jié)點記為Wj，i和j的關系如式(4)所示：

j=(i+1)%p

(4)

在出現(xiàn)故障節(jié)點后，數(shù)據(jù)可靠性模塊會將故障節(jié)點上的數(shù)據(jù)副本在其他無故障節(jié)點上進行恢復。為降低容錯帶來的性能開銷，原始數(shù)據(jù)的可靠性存儲和規(guī)約計算是異步同時進行的。

由于采用基于任務并行的計算模式，從容錯處理的角度看，規(guī)約過程中各進程間的動態(tài)依賴關系可等價為S、Wi和Wj三者間的依賴關系。因此，容錯處理可在S、Wi和Wj構成的模型上進行描述，如圖5所示，Wi為獲得任務的進程，Wj提供數(shù)據(jù)給Wi進行規(guī)約。

圖5 故障位置說明Fig.5 Demonstration of fault location

在規(guī)約過程中，影響規(guī)約結果的故障位置共有3處：第1處是S在發(fā)送任務給Wi時，發(fā)現(xiàn)Wi故障；第2處是Wi在執(zhí)行任務的過程中，Wi出現(xiàn)故障；第3處是Wi在執(zhí)行任務的過程中，正在從Wj上獲取數(shù)據(jù)時，Wj出現(xiàn)故障。記Mi為在故障發(fā)生前Wi向S發(fā)送的最新規(guī)約消息，Mj為在故障發(fā)生前Wj向S發(fā)送的最新規(guī)約消息。Pi為Mi對應的規(guī)約路徑，Pj為Mj對應的規(guī)約路徑。下面給出容錯處理算法的詳細步驟：

步驟1Master端，Master得到某節(jié)點故障通知后，判斷故障類型。如果屬于故障1或故障2，令M=Mj，P=Pi。如果屬于故障3，令M=Mi，P=Pj。

步驟2Master端，Master將M重新放回到消息隊列Q中。

步驟3Master端，記m為集合P的元素數(shù)量。將P拆解為m條獨立的規(guī)約消息，第k條規(guī)約消息的進程號為Pk，規(guī)約路徑為{Pk}。其中，Pk表示集合P中的第k個元素值。對于每條規(guī)約消息，需要設置容錯標志。最后，將這m條規(guī)約消息放入到Q中等待被S調(diào)度。

步驟4Master端，調(diào)度器S在調(diào)度任務時，從Q中取出2條規(guī)約消息，仍記這2條規(guī)約消息對應的源進程分別為Wi和Wj。如果其中有一個為故障進程，則將任務調(diào)度給非故障進程。如果Wi和Wj都不是故障進程，但其中一個設置了容錯標志(假設為Wi)，則將任務調(diào)度給Wi。否則，按性能最優(yōu)的調(diào)度策略調(diào)度。

步驟5Worker端，對于設置了容錯標識的進程號，向數(shù)據(jù)可靠性模塊請求其對應的原始數(shù)據(jù)。數(shù)據(jù)可靠性模塊總是優(yōu)先從當前節(jié)點的本地盤上直接為規(guī)約提供原始數(shù)據(jù)。

這里對規(guī)約的可靠性進行分析，若Wi在將數(shù)據(jù)存儲到遠程節(jié)點之前發(fā)生故障，則故障無法恢復。規(guī)約的可靠性δ表達式為

δ=1-

(5)

從式(5)可以看出，進程數(shù)量p越大，規(guī)約的可靠性越高。這是由于規(guī)約時間和lbp成正比，而Oi的遠程副本存儲時間是常量，和進程數(shù)量無關。

4 實驗與分析

分布式規(guī)約的實驗是在集群C1和集群C2上進行的，其中集群C1為測試集群，集群C2為生產(chǎn)集群。C1和C2均包含200個節(jié)點，C1和C2的每個節(jié)點配置為：128 GB內(nèi)存，1塊1 TB SAS本地盤，2顆CPU，每顆CPU有8個物理核；其中C1的CPU型號為Intel Xeon E5-2667 3.2 GHz CPU，C2的為Intel Xeon E5-2670 2.6 GHz CPU。集群C1和C2均采用的是萬兆以太網(wǎng)。對比的MPI版本為MVAPICH，版本號為3.1.4。MVAPICH是高性能計算環(huán)境中最常用的MPI版本。所有的規(guī)約測試都是在C1或者C2的200個節(jié)點上運行的，每個規(guī)約性能結果都是重復運行9次后取平均值得到的。

4.1 理想環(huán)境中性能對比

理想環(huán)境是指，規(guī)約在運行過程中獨占集群計算資源，不受其他應用干擾，理想環(huán)境實驗采用的集群為C1,結果如圖6所示(DR表示分布式規(guī)約，DCR表示分布式并發(fā)規(guī)約)。

圖6(a)給出了理想環(huán)境中分布式規(guī)約和MPI規(guī)約的性能對比結果，其中測試數(shù)據(jù)的規(guī)模從128 KB(217B)以2倍遞增到128 MB(227B)，進行規(guī)約的進程數(shù)量為200。從圖6(a)可以看出，在理想環(huán)境中，MPI規(guī)約的性能優(yōu)于分布式規(guī)約的性能，但隨著數(shù)據(jù)量的增加，分布式規(guī)約和MPI規(guī)約的耗時比呈縮小趨勢。

圖6(b)給出了理想環(huán)境中分布式并發(fā)規(guī)約和MPI并發(fā)規(guī)約的性能對比圖，測試數(shù)據(jù)規(guī)模為8 MB，并發(fā)規(guī)約的數(shù)量從4遞增到28。從圖6(b)可以看出，在理想環(huán)境中，分布式并發(fā)規(guī)約的性能優(yōu)于MPI并發(fā)規(guī)約的性能。

圖6 理想環(huán)境中規(guī)約性能及并發(fā)規(guī)約性能對比Fig.6 Comparison of reduction performance and concurrent reduction performance in ideal environment

4.2 受控復雜環(huán)境中性能對比

受控復雜環(huán)境是指，在理想環(huán)境中人為引入干擾。首先在C1上運行大規(guī)模并行應用積分法疊前深度偏移(PreStack Depth Migration, PSDM)，PSDM在運行過程中，會對集群的CPU、網(wǎng)絡、內(nèi)存產(chǎn)生較大的負載壓力[23]。在該應用運行過程中，進行規(guī)約性能實驗，進行規(guī)約的進程數(shù)量為200。

圖7分別給出了使用節(jié)點數(shù)為50、100、150和200運行PSDM時，MPI規(guī)約和分布式規(guī)約的性能對比結果?？梢钥闯觯跀?shù)據(jù)規(guī)模較小時，MPI規(guī)約依然具有性能優(yōu)勢，這是由于數(shù)據(jù)規(guī)模較小時，規(guī)約耗時中網(wǎng)絡啟動時間占主要因素，干擾對規(guī)約數(shù)據(jù)的網(wǎng)絡傳輸和計算造成的影響不是很顯著。

當數(shù)據(jù)規(guī)模增加到4 MB以上時，分布式規(guī)約的性能明顯優(yōu)于MPI規(guī)約的性能。在這4種情況下，分布式規(guī)約的性能最高分別提升了5.59、2.09、3和5.15倍。

圖7 受控復雜環(huán)境中規(guī)約性能對比Fig.7 Comparison of reduction performance in controlled complex environment

圖8 受控復雜環(huán)境中并發(fā)規(guī)約性能對比Fig.8 Comparison of concurrent reduction performance in controlled complex environment

在受控復雜環(huán)境中，對比分布式并發(fā)規(guī)約和MPI并發(fā)規(guī)約的性能，規(guī)約數(shù)據(jù)量為8 MB，并發(fā)規(guī)約數(shù)量從4遞增到28，進行規(guī)約的進程數(shù)量為200。圖8分別給出了使用節(jié)點數(shù)為50、100、150和200運行PSDM時，MPI并發(fā)規(guī)約和分布式并發(fā)規(guī)約的性能對比結果?？梢钥闯觯谶@4種情況下，分布式并發(fā)規(guī)約的性能均優(yōu)于MPI并發(fā)規(guī)約的性能，分布式并發(fā)規(guī)約性能最高分別提升了0.72、2.21、2.41和3.28倍。

4.3 真實復雜環(huán)境中性能對比

真實復雜環(huán)境是指，集群C2上的真實生產(chǎn)環(huán)境，C2上長期運行著多個并行應用的生產(chǎn)作業(yè)，集群整體負載較高，較為繁忙。在真實復雜環(huán)境中，分別對比規(guī)約和并發(fā)規(guī)約的性能。實驗中，測試數(shù)據(jù)的規(guī)模為32 MB，進行規(guī)約的進程數(shù)量為200。在該集群上分別對規(guī)約和并發(fā)規(guī)約進行了連續(xù)7 d的對比測試。

圖9 真實復雜環(huán)境中規(guī)約性能及并發(fā)規(guī)約性能對比Fig.9 Comparison of reduction performance and concurrent reduction performance in real complex environment

圖9(a)給出了真實復雜環(huán)境中，MPI規(guī)約和分布式規(guī)約的性能對比結果。圖9(b)給出了該環(huán)境中，MPI并發(fā)規(guī)約和分布式并發(fā)規(guī)約的性能對比結果。從圖9可以看出，在連續(xù)7 d的時間內(nèi)，分布式規(guī)約的性能均優(yōu)于MPI規(guī)約的性能，分布式并發(fā)規(guī)約的性能也都優(yōu)于MPI并發(fā)規(guī)約的性能。規(guī)約性能最高提升了2.2倍，平均提升了1.67倍。并發(fā)規(guī)約性能最高提升了4倍，平均提升了2.55倍。

4.4 Master端負載測試

在C1集群上進行Master端的負載測試，以分析大規(guī)模節(jié)點數(shù)量下，頻繁的Master與Worker間通信對Master端的影響。實驗中，節(jié)點數(shù)為200，規(guī)約的數(shù)據(jù)規(guī)模從128 KB(217B)以2倍遞增到128 MB(227B)。C1集群中每個節(jié)點接收消息的最大峰值為79 365次/s，發(fā)送消息的最大峰值為106 383次/s，網(wǎng)絡接收數(shù)據(jù)的最大帶寬為812.7 MB/s，網(wǎng)絡發(fā)送數(shù)據(jù)的最大帶寬為812.7 MB/s。表1記錄了在規(guī)約過程中，Master端的接收消息數(shù)量，發(fā)送消息數(shù)量，接收數(shù)據(jù)量帶寬，發(fā)送數(shù)據(jù)量帶寬的平均值。表1中每行的4個值分別是用Master端在規(guī)約過程中的接收消息總量、發(fā)送消息總量、接收數(shù)據(jù)總量、發(fā)送數(shù)據(jù)總量除以規(guī)約時間得到的。

從表1可以看出，規(guī)約過程中，Master的接收消息數(shù)量、發(fā)送消息數(shù)量、接收帶寬、發(fā)送帶寬都遠低于Master作為單個節(jié)點時各項指標對應的峰值數(shù)據(jù)。因此，規(guī)約過程中，Master端受到的負載在可承受的范圍內(nèi)。這主要是因為在規(guī)約過程中，各個Worker節(jié)點和Master之間的通信內(nèi)容主要為規(guī)約信息和任務信息，而規(guī)約數(shù)據(jù)是在Worker節(jié)點之間進行通信的，不會經(jīng)過Master節(jié)點，所以對Master造成的開銷比較小。

表1 規(guī)約過程中各項指標的平均值

4.5 容錯實驗

在真實復雜環(huán)境中，對分布式規(guī)約的容錯進行實驗，測試數(shù)據(jù)規(guī)模為32 MB，進行規(guī)約的進程數(shù)量為200。每輪測試中，首先進行9次測試取得平均規(guī)約時間t，然后進行100次規(guī)約。選擇進程號為1的進程，每次規(guī)約時，在[0,t]內(nèi)隨機生成一個時間點，在該時間點上強制退出1號進程以模擬節(jié)點故障。每天進行一輪容錯實驗，連續(xù)進行7 d。表2給出了7 d的容錯實驗結果，在100次的容錯測試中，無法恢復的故障數(shù)量為0～3個，規(guī)約的容錯可靠性為98.43%。

表2 分布式規(guī)約的容錯實驗結果

5 結 論

規(guī)約是并行計算領域最常用的集合通信原語之一。傳統(tǒng)的規(guī)約實現(xiàn)在性能優(yōu)化方面沒有考慮真實環(huán)境中的干擾因素，也沒有解決規(guī)約過程中出現(xiàn)的節(jié)點故障問題。本文針對真實復雜環(huán)境，提出了一種基于任務并行的可適用于復雜環(huán)境且支持容錯的分布式高性能規(guī)約框架，結合實驗得出以下結論：

1) 基于任務并行的設計可有效解決干擾問題和容錯問題。以任務為粒度進行調(diào)度，可優(yōu)先執(zhí)行已就緒的任務，慢任務可稍晚執(zhí)行，但不會影響其他任務的執(zhí)行。以任務為粒度進行容錯，降低了容錯實現(xiàn)的復雜性。

2) 在受控復雜環(huán)境中，當數(shù)據(jù)量在4 MB以上時，分布式規(guī)約性能優(yōu)于MPI規(guī)約的性能。在4種干擾情況下，分布式規(guī)約的性能最高分別提升了5.59、2.09、3和5.15倍；分布式并發(fā)規(guī)約的性能最高分別提升了0.72、2.21、2.41和3.28倍。

3) 在真實復雜環(huán)境下連續(xù)7 d的測試中，分布式規(guī)約性能均優(yōu)于MPI規(guī)約性能，分布式并發(fā)規(guī)約性能也均優(yōu)于MPI并發(fā)規(guī)約性能。前者性能平均提升了1.67倍，后者性能平均提升了2.55倍。

4) 在真實復雜環(huán)境中，根據(jù)連續(xù)7 d的容錯測試結果可知，分布式規(guī)約的容錯可靠性可達到98%以上。