李超， 趙長(zhǎng)海， 晏海華,*， 劉超， 文佳敏， 王增波

(1. 北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院, 北京 100083；2. 中國(guó)石油集團(tuán)東方地球物理勘探有限責(zé)任公司 物探技術(shù)研究中心, 北京 100088)

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

2 基于任務(wù)并行的計(jì)算模式

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

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

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

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

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

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

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

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

(2)

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

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

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

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

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

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

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

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

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

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

圖4 任務(wù)分解示例Fig.4 Example of task decomposition

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

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

(3)

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

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

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

3 運(yùn)行時(shí)容錯(cuò)

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

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

j=(i+1)%p

(4)

在出現(xiàn)故障節(jié)點(diǎn)后，數(shù)據(jù)可靠性模塊會(huì)將故障節(jié)點(diǎn)上的數(shù)據(jù)副本在其他無(wú)故障節(jié)點(diǎn)上進(jìn)行恢復(fù)。為降低容錯(cuò)帶來(lái)的性能開(kāi)銷，原始數(shù)據(jù)的可靠性存儲(chǔ)和規(guī)約計(jì)算是異步同時(shí)進(jìn)行的。

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

圖5 故障位置說(shuō)明Fig.5 Demonstration of fault location

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

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

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

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

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

步驟5Worker端，對(duì)于設(shè)置了容錯(cuò)標(biāo)識(shí)的進(jìn)程號(hào)，向數(shù)據(jù)可靠性模塊請(qǐng)求其對(duì)應(yīng)的原始數(shù)據(jù)。數(shù)據(jù)可靠性模塊總是優(yōu)先從當(dāng)前節(jié)點(diǎn)的本地盤上直接為規(guī)約提供原始數(shù)據(jù)。

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

δ=1-

(5)

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

4 實(shí)驗(yàn)與分析

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

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

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

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

圖6(b)給出了理想環(huán)境中分布式并發(fā)規(guī)約和MPI并發(fā)規(guī)約的性能對(duì)比圖，測(cè)試數(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ī)約性能對(duì)比Fig.6 Comparison of reduction performance and concurrent reduction performance in ideal environment

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

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

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

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

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

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

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

4.3 真實(shí)復(fù)雜環(huán)境中性能對(duì)比

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

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

圖9(a)給出了真實(shí)復(fù)雜環(huán)境中，MPI規(guī)約和分布式規(guī)約的性能對(duì)比結(jié)果。圖9(b)給出了該環(huán)境中，MPI并發(fā)規(guī)約和分布式并發(fā)規(guī)約的性能對(duì)比結(jié)果。從圖9可以看出，在連續(xù)7 d的時(shí)間內(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端負(fù)載測(cè)試

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

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

表1 規(guī)約過(guò)程中各項(xiàng)指標(biāo)的平均值

4.5 容錯(cuò)實(shí)驗(yàn)

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

表2 分布式規(guī)約的容錯(cuò)實(shí)驗(yàn)結(jié)果

5 結(jié) 論

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

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

2) 在受控復(fù)雜環(huán)境中，當(dāng)數(shù)據(jù)量在4 MB以上時(shí)，分布式規(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) 在真實(shí)復(fù)雜環(huán)境下連續(xù)7 d的測(cè)試中，分布式規(guī)約性能均優(yōu)于MPI規(guī)約性能，分布式并發(fā)規(guī)約性能也均優(yōu)于MPI并發(fā)規(guī)約性能。前者性能平均提升了1.67倍，后者性能平均提升了2.55倍。

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