一種在復雜環境中支持容錯的高性能規約框架

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

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

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

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

(1)

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

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

以上研究均建立在靜態計算資源模型之上，即假定在規約執行過程中，各計算節點的CPU性能、內存性能以及任意兩節點間網絡延遲皆固定不變。然而，在真實環境中，該假設在多數情況下難以成立，具體表現在以下幾方面：

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

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

3) 同時執行多個規約時，即并發規約，各規約之間會產生相互干擾。

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

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

1 分布式規約框架

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

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

圖2 分布式規約接口Fig.2 Distributed reduction interface

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

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

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

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

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

定義1原始數據，記為Oi，指Wi上的原始規約數據。

定義2中間數據，記為Di，指在規約過程中，Wi上的中間規約結果。

定義3規約數據，Oi或Di，指Wi上的原始數據或中間結果。

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

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

(2)

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

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

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

步驟1Worker端，Wi調用reduce接口，向Master發送規約消息，規約消息中的進程號為Wi，Pi={Wi}。

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

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

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

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

步驟6規約結束。

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

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

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

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

(3)

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

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

2) 在調度任務時，總是將任務調度給性能更高的節點，可進一步提高規約計算對復雜環境的適應能力。

3 運行時容錯

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

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

j=(i+1)%p

(4)

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

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

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

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

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

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

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

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

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

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

δ=1-

(5)

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

4 實驗與分析

分布式規約的實驗是在集群C1和集群C2上進行的，其中集群C1為測試集群，集群C2為生產集群。C1和C2均包含200個節點，C1和C2的每個節點配置為：128 GB內存，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均采用的是萬兆以太網。對比的MPI版本為MVAPICH，版本號為3.1.4。MVAPICH是高性能計算環境中最常用的MPI版本。所有的規約測試都是在C1或者C2的200個節點上運行的，每個規約性能結果都是重復運行9次后取平均值得到的。

4.1 理想環境中性能對比

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

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

圖6(b)給出了理想環境中分布式并發規約和MPI并發規約的性能對比圖，測試數據規模為8 MB，并發規約的數量從4遞增到28。從圖6(b)可以看出，在理想環境中，分布式并發規約的性能優于MPI并發規約的性能。

圖6 理想環境中規約性能及并發規約性能對比Fig.6 Comparison of reduction performance and concurrent reduction performance in ideal environment

4.2 受控復雜環境中性能對比

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

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

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

圖7 受控復雜環境中規約性能對比Fig.7 Comparison of reduction performance in controlled complex environment

圖8 受控復雜環境中并發規約性能對比Fig.8 Comparison of concurrent reduction performance in controlled complex environment

在受控復雜環境中，對比分布式并發規約和MPI并發規約的性能，規約數據量為8 MB，并發規約數量從4遞增到28，進行規約的進程數量為200。圖8分別給出了使用節點數為50、100、150和200運行PSDM時，MPI并發規約和分布式并發規約的性能對比結果?？梢钥闯?，在這4種情況下，分布式并發規約的性能均優于MPI并發規約的性能，分布式并發規約性能最高分別提升了0.72、2.21、2.41和3.28倍。

4.3 真實復雜環境中性能對比

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

圖9 真實復雜環境中規約性能及并發規約性能對比Fig.9 Comparison of reduction performance and concurrent reduction performance in real complex environment

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

4.4 Master端負載測試

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

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

表1 規約過程中各項指標的平均值

4.5 容錯實驗

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

表2 分布式規約的容錯實驗結果

5 結 論

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

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

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

3) 在真實復雜環境下連續7 d的測試中，分布式規約性能均優于MPI規約性能，分布式并發規約性能也均優于MPI并發規約性能。前者性能平均提升了1.67倍，后者性能平均提升了2.55倍。

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