基于排隊理論的動態(tài)任務(wù)調(diào)度模型及容錯

何王全　魏　迪　權(quán)建?！恰ァ∑徜h濱

1(江南計算技術(shù)研究所　江蘇無錫　214083)2　　　(國家并行計算機工程技術(shù)研究中心　北京　100080) (wangquan_he@163.com)

?

基于排隊理論的動態(tài)任務(wù)調(diào)度模型及容錯

何王全1魏迪1權(quán)建校1吳偉1漆鋒濱2

1(江南計算技術(shù)研究所江蘇無錫214083)2(國家并行計算機工程技術(shù)研究中心北京100080) (wangquan_he@163.com)

摘要高效的動態(tài)任務(wù)調(diào)度和容錯機制是高性能計算面臨的挑戰(zhàn)之一，已有的方法難以高效擴展到大規(guī)模環(huán)境.針對該問題，提出了基于N層排隊理論的高可擴展動態(tài)任務(wù)調(diào)度模型，為程序員提供簡潔的并行編程框架，有效降低了編程負擔；使用泊松過程相關(guān)理論分析了任務(wù)申請的平均等待時間，通過給定的閾值進行決策分層；結(jié)合局部感知的輕量級降級模型，可有效降低大規(guī)模并行課題的容錯開銷，提高系統(tǒng)的可用性.Micro Benchmark在神威藍光32 768核環(huán)境下測試表明，對于平均執(zhí)行時間為3.4 s的短任務(wù)，基于N層排隊理論的動態(tài)任務(wù)調(diào)度模型可擴展性很好，調(diào)度開銷是傳統(tǒng)模型的7.2%；藥物軟件DOCK在16 384核環(huán)境下的整體性能比該軟件原有的任務(wù)調(diào)度提升34.3%；局部感知的輕量級降級模型具有故障后損失小的特點，DOCK的測試表明比傳統(tǒng)容錯方法執(zhí)行時間減少3.75%～5.13%.

關(guān)鍵詞排隊理論；動態(tài)任務(wù)調(diào)度；編程框架；容錯；輕量級降級

近年來，高性能計算技術(shù)發(fā)展迅猛，高端并行系統(tǒng)的規(guī)模日益龐大，為大規(guī)模并行應(yīng)用課題的高效解算奠定了堅實基礎(chǔ).高性能計算系統(tǒng)可提供強大的計算能力，但其規(guī)模和復(fù)雜性給并行應(yīng)用的高效運行帶來了極大的挑戰(zhàn)，主要體現(xiàn)在可擴展性和容錯2個方面.

大規(guī)模并行應(yīng)用可分為數(shù)據(jù)并行和任務(wù)并行2大類.數(shù)據(jù)并行應(yīng)用通常根據(jù)擁有者計算的原則由數(shù)據(jù)分布產(chǎn)生計算劃分，其基本思想是讓左值擁有者進行計算，以減少非本地引用，降低通信開銷[1]；任務(wù)并行應(yīng)用是本文研究工作的主要對象，它通常將課題分解成眾多子任務(wù)，對數(shù)據(jù)集進行分割，通過將任務(wù)和對應(yīng)數(shù)據(jù)加載到不同計算資源上并行執(zhí)行[2].任務(wù)并行應(yīng)用廣泛存在于藥物篩選、基因研究、密碼分析、核模擬等領(lǐng)域，多數(shù)應(yīng)用的子任務(wù)間無相關(guān)性，但子任務(wù)的計算量可能存在顯著差異，在大規(guī)模環(huán)境下，高效的負載平衡機制是保證應(yīng)用性能的關(guān)鍵之一.

高端的并行系統(tǒng)資源數(shù)量龐大、設(shè)計復(fù)雜，很難保證長時間內(nèi)不出現(xiàn)故障，對于需要運行數(shù)日乃至數(shù)周的大規(guī)模并行應(yīng)用來說，低開銷的容錯機制能夠降低故障對并行應(yīng)用的影響，對提升并行應(yīng)用的健壯性、性能和系統(tǒng)的可用率都具有重要意義.

1國內(nèi)外研究現(xiàn)狀

1.1動態(tài)任務(wù)調(diào)度研究現(xiàn)狀

動態(tài)任務(wù)調(diào)度是實現(xiàn)負載平衡的重要手段，當今國內(nèi)外高性能計算領(lǐng)域動態(tài)任務(wù)調(diào)度方法的研究工作主要包含3種類型：

1) 嵌入式.嵌入式調(diào)度方法根據(jù)應(yīng)用的特點，在應(yīng)用程序中實現(xiàn)相應(yīng)的動態(tài)任務(wù)調(diào)度機制.這種方法需要程序員在精通并行應(yīng)用特點的基礎(chǔ)上，額外開發(fā)相應(yīng)的任務(wù)調(diào)度模塊，以實現(xiàn)應(yīng)用程序在目標平臺上高效的負載平衡[3-4].該方法通用性較差，在大規(guī)模環(huán)境下，通常需要針對不同應(yīng)用設(shè)計實現(xiàn)相應(yīng)的動態(tài)任務(wù)調(diào)度模塊，程序員開發(fā)負擔較重.

2) 過程遷移式.針對嵌入式調(diào)度方法用戶負擔較重的缺點，業(yè)界又提出了對用戶完全透明的過程遷移式調(diào)度方法，不需要修改應(yīng)用代碼.當調(diào)度系統(tǒng)發(fā)現(xiàn)負載不平衡時，就將負載較重進程的任務(wù)和數(shù)據(jù)遷移至負載較輕的進程.這方面的研究工作主要基于Charm++[5]展開，以Menon等人[6]實現(xiàn)的GrapevineLB系統(tǒng)以及Zheng等人[7]提出的層次式調(diào)度方式為典型代表.

過程遷移式調(diào)度方式的缺點在于需要交換負載信息和任務(wù)遷移，開銷大，不適合大規(guī)模系統(tǒng).

3) 框架式.框架式調(diào)度由并行語言或并行庫提供任務(wù)調(diào)度服務(wù)，其設(shè)計目標是將任務(wù)調(diào)度從用戶程序中分離出來，將復(fù)雜的調(diào)度工作交給系統(tǒng)軟件，保證任務(wù)調(diào)度方法的通用性，用戶只需對代碼進行少量的修改就可以實現(xiàn)任務(wù)調(diào)度.

早期的框架式的任務(wù)調(diào)度以UPC語言[8-9]為代表，采用循環(huán)語法擴充的方式基于數(shù)據(jù)親緣性進行任務(wù)調(diào)度，但存在負載不平衡的問題.

Kumar等人[10]提出的DLBL(dynamic load balancing library)采用面向迭代的調(diào)度策略，通過集中仲裁的方式，將迭代所需的數(shù)據(jù)在進程間遷移以獲得良好的負載平衡.Devine等人[11]開發(fā)Zoltan系統(tǒng)通過回調(diào)函數(shù)的形式和用戶程序進行交互，并預(yù)設(shè)了多種負載平衡策略，用戶可以自由嘗試多種策略，然后根據(jù)優(yōu)化效果選擇最優(yōu)策略.Zhang等人[12]實現(xiàn)的GLB(lifeline-based global load balancing library)在X10語言[13]的基礎(chǔ)上提供對用戶透明的任務(wù)調(diào)度服務(wù)，用戶只需要定義諸如處理算法、任務(wù)分割方式、任務(wù)歸并方式、結(jié)果處理方式等要素，在GLB內(nèi)部，當發(fā)現(xiàn)任務(wù)執(zhí)行完畢時，采用Work-Stealing[14]的方式從其他進程竊取任務(wù). Zhang等人[15]實現(xiàn)的AME(anyscale many-task computing engine)以及Krieder等人[16]實現(xiàn)的GeMTC(GPU-enabled many-task computing)，主要面向MTC(many-task computing)應(yīng)用，以應(yīng)對該類課題在計算資源調(diào)度、任務(wù)相關(guān)性處理、負載平衡、數(shù)據(jù)管理以及容錯等方面對高性能計算系統(tǒng)提出的挑戰(zhàn)，AME在計算資源調(diào)度、任務(wù)相關(guān)性處理以及數(shù)據(jù)管理3個方面做了很好的工作；GeMTC面向具有GPU加速部件的高性能計算平臺，用戶通過其提供的API接口，實現(xiàn)向加速器高效加載計算任務(wù).Xiao等人[17]針對MTC應(yīng)用提出了一種應(yīng)用級的優(yōu)先級調(diào)度算法，給出了針對異構(gòu)計算環(huán)境的粗粒度調(diào)度方案，首先分析應(yīng)用特點將作業(yè)分配到不同的資源上，然后在運行時根據(jù)作業(yè)的負載動態(tài)調(diào)整其優(yōu)先級.

框架式調(diào)度只需要用戶少量修改程序，但多數(shù)已有的框架式調(diào)度在大規(guī)模環(huán)境下，面臨可擴展性挑戰(zhàn).

1.2輕量級容錯研究現(xiàn)狀

對大型應(yīng)用來說，需要相應(yīng)的容錯措施來保證程序的健康高效運行，大規(guī)模環(huán)境下的容錯技術(shù)是近年來高性能計算領(lǐng)域的研究熱點之一.

保留恢復(fù)[18]是最常見的容錯模型，以檢查點為基礎(chǔ).程序正常執(zhí)行過程中，以一定的間隔在主存或磁盤中記錄程序執(zhí)行的內(nèi)存映像以及消息日志；當硬件資源出現(xiàn)故障時，通過上述2個要素恢復(fù)到距離當前最近的一個檢查點重新執(zhí)行.當前具有代表性的研究成果主要有BLCR[18](Berkeley lab’s Linux checkpointrestart)和SCR[19](scalable checkpointrestart).BLCR只提供單節(jié)點系統(tǒng)級的保留恢復(fù)支持，可作為并行運行時系統(tǒng)容錯功能開發(fā)的基礎(chǔ).SCR的基本思路則是基于簡潔API集合提供用戶級的保留恢復(fù)支持，專注于檢查點文件的快速存儲以及故障發(fā)生時作業(yè)的快速恢復(fù)，從而保證容錯功能的可擴展性.

雖然當今業(yè)界對于保留恢復(fù)容錯模型的研究依然是熱點，但是時空開銷較大的缺點也極大限制了其應(yīng)用前景.尤洪濤等人[20]針對任務(wù)并行課題提出了一種低開銷的降級容錯模型：當有個別計算資源出現(xiàn)故障時，丟棄故障資源并回收相關(guān)子任務(wù)，作業(yè)運行不被中斷，最終保證所有的子任務(wù)均被正確執(zhí)行.該方法的缺點是有故障時所有進程都要進行處理，性能影響較大.

不難發(fā)現(xiàn)，高性能計算領(lǐng)域?qū)討B(tài)任務(wù)調(diào)度方法和容錯技術(shù)的研究尚屬2個獨立的研究領(lǐng)域.本文在可擴展動態(tài)任務(wù)調(diào)度架構(gòu)的基礎(chǔ)上提出了輕量級降級容錯模型，保證并行程序以較小的容錯代價在計算資源出現(xiàn)故障時仍可穩(wěn)定運行.

2基于N層排隊理論的可擴展動態(tài)任務(wù)調(diào)度模型

對于子任務(wù)計算時間不均衡的應(yīng)用，采用動態(tài)任務(wù)調(diào)度是解決負載平衡問題的有效方法，最常見的執(zhí)行模型為Master-Slave模型,如圖1所示.在該模型中，多個Slave向Master申請任務(wù).

Fig. 1　Classic Master-Slave model.圖1　傳統(tǒng)的Master-Slave模型

Master-Slave模型的通信模式為典型的多對一通信，在大規(guī)模環(huán)境下(進程數(shù)量達到數(shù)萬以上)，可擴展性是該模型面臨的主要問題.針對該問題，本文提出了基于N層排隊理論的動態(tài)任務(wù)調(diào)度模型，并設(shè)計了簡潔的并行編程框架，可有效降低程序員的編程負擔，提高可擴展性，同時在容錯方面具有明顯的優(yōu)勢.

2.1N層排隊動態(tài)任務(wù)調(diào)度模型

多級Master-Slave模型采用層次式資源分配方法，設(shè)置Region-Master(以下簡稱R-M)，每個R-M向上一層申請任務(wù)和報告任務(wù)完成，并向下一層提供任務(wù)動態(tài)調(diào)度服務(wù)，以緩解多對一通信瓶頸問題.4層Master-Slave的調(diào)度模型如圖2所示，位于頂層的灰色小圈代表Master，位于最下方的白色小圈代表Slave，中間層條形小圈和格子小圈代表不同層次的R-M，計算資源向上級申請任務(wù)并報告完成情況，Master管理全局任務(wù)池.為了進一步提高任務(wù)分配的性能，根據(jù)資源數(shù)量和實際應(yīng)用中子任務(wù)的執(zhí)行情況，采用排隊論[21]的思想決定模型層數(shù)和R-M的數(shù)量.

對于各子任務(wù)執(zhí)行時間均衡的應(yīng)用，通常采用靜態(tài)任務(wù)調(diào)度策略(這類應(yīng)用不適合本文的模型).而對于各子任務(wù)執(zhí)行時間不均衡的應(yīng)用，在大規(guī)模環(huán)境下適合采用多級Master-Slave動態(tài)調(diào)度模型，該模型的每一層都是一個經(jīng)典的Master-Slave模型，可以用排隊理論描述，Master看作是服務(wù)窗口，Slave看作是顧客，Slave向Master申請任務(wù)看作是到窗口排隊等待服務(wù).泊松分布[22]常用于描述在任意一段固定的時間間隔內(nèi)，到某公共設(shè)施要求給予服務(wù)的顧客數(shù)量.Master-Slave模型中任務(wù)申請是一個時間連續(xù)、狀態(tài)離散的過程，下面論述采用泊松分布來描述任務(wù)申請的隨機性是合理的.

Fig. 2　Four layer Master-Slave model.圖2　4層Master-Slave模型示意圖

定義1[23].若計數(shù)過程{ξ(t),t≥0}滿足下列條件，則稱為具有參數(shù)λ(λ>0)的泊松過程.

1)ξ(0)=0；

2)ξ(t)是獨立、平穩(wěn)的增量過程；

3)ξ(t)滿足：

① 時間區(qū)間[t，t+Δt)內(nèi)發(fā)生1次的概率與Δt成正比，即P{ξ(t+Δt)-ξ(t)=1}=λ×Δt+o(Δt)；

② 時間區(qū)間[t，t+Δt)內(nèi)發(fā)生2次以上的概率是Δt的高階無窮小，即P{ξ(t+Δt)-ξ(t)≥2}=o(Δt).

任務(wù)并行類應(yīng)用在0單位時間內(nèi)不會出現(xiàn)任務(wù)請求，滿足定義1的條件1；由任務(wù)并行應(yīng)用的特性可知，子任務(wù)間沒有相關(guān)性，在不重疊的時間間隔內(nèi)Slave向Master提交的任務(wù)請求數(shù)量是相互獨立的，沒有后效性，因此滿足定義1的條件2；Master-Slave模型中任務(wù)申請過程存在網(wǎng)絡(luò)延遲等因素，在充分小的時間間隔內(nèi)最多有1個任務(wù)申請到達，不會或者以極小概率有2個或者2個以上的任務(wù)申請同時到達，而在區(qū)間[t，t+Δt)內(nèi)有1個任務(wù)請求到達的概率與時間t無關(guān)，而與區(qū)間長度Δt成正比，即滿足定義1的條件3.因此Master-Slave模型任務(wù)申請滿足參數(shù)為λ的泊松過程，即在[0，t)時間內(nèi)達到k個任務(wù)請求的概率為

Step1. 使用傳統(tǒng)的Master-Slave模型進行初始階段的任務(wù)分配；

Step2. Master對排隊情況進行采樣統(tǒng)計，采樣個數(shù)M根據(jù)各進程第1個任務(wù)的執(zhí)行時間來確定；

Step3. 根據(jù)采樣結(jié)果，采用極大似然法擬合確定課題任務(wù)申請過程中的排隊特性(獲取泊松分布的期望λ和方差σ2)；

Step4. 根據(jù)任務(wù)申請的排隊特性，決策動態(tài)任務(wù)分配模型的層數(shù).

在中小規(guī)模的系統(tǒng)上，采用傳統(tǒng)的Master-Slave 2層模型可以滿足要求；在Peta Flops級別的大規(guī)模系統(tǒng)上，需要采用3層模型；而未來的Exascale級別的系統(tǒng)，計算核心數(shù)量空前龐大，需要采用4層以上模型.基于N層排隊理論的動態(tài)任務(wù)調(diào)度模型由2.3節(jié)的并行任務(wù)調(diào)度框架自動實現(xiàn)，對應(yīng)用層透明，即應(yīng)用層不需要關(guān)心復(fù)雜的N層實現(xiàn)細節(jié)，由系統(tǒng)實現(xiàn)并行任務(wù)調(diào)度的高效可擴展，自動適應(yīng)各種規(guī)模的并行環(huán)境.

2.2模型性能分析

首先討論模型參數(shù)的確定.作業(yè)提交后，首先采用傳統(tǒng)的Master-Slave模型進行調(diào)度，在初始化階段Master主動給每個Slave分發(fā)1個任務(wù)，之后就進入任務(wù)的自由申請階段，各Slave在完成第一個任務(wù)后，主動向Master報告任務(wù)的完成，并申請新的任務(wù).在任務(wù)自由申請階段，令單位時間內(nèi)任務(wù)申請到達的個數(shù)為一個實驗樣本ξi，選取連續(xù)的M個樣本，采用泊松分布的極大似然估計法[22]，可獲得期望和方差的估計量：

動態(tài)任務(wù)調(diào)度的主要目標是要使計算資源的負載比較平衡，以及Slave的任務(wù)請求開銷Treq占用的比例盡量小.定義距離Slave最近的R-M或Master為該Slave的Parent，Slave的任務(wù)請求開銷Treq包含任務(wù)請求的網(wǎng)上傳輸時間Tmsg、請求到達Parent后的排隊等待時間Twait、因Parent本地任務(wù)池為空時向更上層請求任務(wù)的時間Ttop_req、Parent從本地任務(wù)池中分配任務(wù)的時間Tdispose以及任務(wù)請求響應(yīng)的網(wǎng)上傳輸時間Tmsg，即：

Treq=Tmsg+Twait+Ttop_req+Tdispose+Tmsg=2×Tmsg+Twait+Ttop_req+Tdispose.

在N層模型的實現(xiàn)中，R-M采用了預(yù)取等優(yōu)化策略，Ttop_req的開銷占的比例很小，幾乎可以忽略，因此Treq可以近似地表示為

Treq≈ 2×Tmsg+Twait+Tdispose.

在給定的系統(tǒng)中，任務(wù)請求或響應(yīng)的網(wǎng)絡(luò)傳輸延遲是確定的，即Tmsg可認為是一個常量；Tdispose與管理維護本地任務(wù)池有關(guān)，取決于CPU的計算能力，近似地認為是常量.因此要減少Slave的任務(wù)請求開銷，主要是減少Twait.為了方便表達，記Parent單位時間內(nèi)可處理請求的個數(shù)為μ，由泊松分布的性質(zhì)可知，單位時間內(nèi)到達的任務(wù)請求個數(shù)的期望值為λ，令：

當ρ>1時，系統(tǒng)的服務(wù)能力不足，不能達到穩(wěn)態(tài)，任務(wù)分配開銷占的比例大，此時，系統(tǒng)必須從N層變?yōu)镹+1層以減少任務(wù)等待時間Twait.

當ρ≤1時，系統(tǒng)可到達穩(wěn)態(tài)，文獻[22]給出了任務(wù)平均等待時間Twait可表示為

令Texe是單個任務(wù)的平均執(zhí)行時間，每個任務(wù)可能不同，完全由課題的特征決定，與負載平衡無關(guān).綜合上述，可計算出任務(wù)分配占作業(yè)執(zhí)行時間的百分比percentreq：

對于給定的調(diào)度開銷閾值C，若percentreq>C，則說明當前的動態(tài)任務(wù)調(diào)度的開銷過大，需要進行遞歸分層.

2.3動態(tài)任務(wù)調(diào)度并行編程框架

在很多應(yīng)用中，并行任務(wù)的動態(tài)調(diào)度由程序員使用消息接口編寫，在大規(guī)模環(huán)境下，簡單的Master-Slave模型可擴展性差，高效實現(xiàn)動態(tài)任務(wù)調(diào)度對普通程序員來說極具挑戰(zhàn)性.為此，本文提出了一種動態(tài)任務(wù)調(diào)度并行編程框架如下所示，適合子任務(wù)間無相關(guān)性的應(yīng)用：

while ((task_id=get_task_id(任務(wù)總量，檢查點文件名，通信子))≥0)

{

do_job(task_id);*用戶代碼 *

}

該編程框架以get_task_id()原語的形式提供給程序員，get_task_id()返回值代表任務(wù)的編號或結(jié)束標志(小于0表示任務(wù)分配結(jié)束)，檢查點文件記錄已完成的任務(wù)，通信子指出動態(tài)任務(wù)調(diào)度的范圍.動態(tài)任務(wù)調(diào)度并行編程框架在軟件棧的層次如圖3所示：

Fig. 3　Parallel dynamic task scheduling framework in the software stack.圖3　并行任務(wù)動態(tài)調(diào)度編程框架在軟件棧中的層次

采用該框架編程非常簡潔，復(fù)雜的調(diào)度工作、檢查點均由框架自動完成.框架實現(xiàn)中，所有的進程均參與計算，Master和R-M處理任務(wù)請求由輪詢線程實現(xiàn)，因此不會帶來明顯的計算資源損耗.框架中采用全局任務(wù)編號代表具體的任務(wù)，此方式具有2個特點：1)通信量少，任務(wù)申請和完成報告需要使用消息傳遞的數(shù)據(jù)非常少，可有效減少系統(tǒng)開銷；2)通用性，任務(wù)總量確定的任務(wù)并行應(yīng)用均可采用.在實際應(yīng)用中，并行任務(wù)通過函數(shù)f映射為一個整數(shù)；并行任務(wù)調(diào)度時，計算資源取到任務(wù)編號后，再根據(jù)任務(wù)編號由f-1還原出具體的任務(wù).

f:第i個任務(wù)|→任務(wù)編號i，f-1:任務(wù)編號i|→第i個任務(wù).

f和f-1的規(guī)則完全由程序員來定義，操作較為簡單.對于單個原始任務(wù)的運行時間極短的課題，可以將多個原始任務(wù)打包映射為一個任務(wù)，以在大規(guī)模環(huán)境下獲得良好的性能.

Fig. 5　Light-weight degradation model with dynamic task scheduling.圖5　結(jié)合動態(tài)任務(wù)調(diào)度的輕量級降級模型

3結(jié)合N層動態(tài)任務(wù)調(diào)度模型的輕量級容錯

降級模型如圖4所示，它將應(yīng)用程序分為課題初始化、子任務(wù)并行計算、資源重構(gòu)和結(jié)果處理3個階段.階段2是程序運行的主體，可以采用降級的方式進行容錯，當有計算資源故障時，在線隔離故障資源并回收故障節(jié)點的任務(wù)，重新分配給正常的節(jié)點進行計算.

Fig. 4　Fault-tolerant model of degradation.圖4　降級容錯模型

尤洪濤等人[20]提出的降級模型在計算資源出現(xiàn)故障時，需要中斷所有進程的執(zhí)行并等待容錯完成.我們對降級模型進行了改進，實現(xiàn)了局部感知的輕量級容錯，當有故障發(fā)生時，只需要通知少量相關(guān)進程，其他進程的執(zhí)行不受影響.

3.1局部感知的輕量級降級模型

在基于N層排隊的動態(tài)任務(wù)調(diào)度模型中，經(jīng)過邏輯劃分的每個Region實際上是一個相對獨立的任務(wù)調(diào)度子系統(tǒng)，R-M能夠掌握所轄區(qū)域內(nèi)進程的任務(wù)分配情況.結(jié)合動態(tài)任務(wù)調(diào)度模型，我們提出了基于局部故障感知技術(shù)的輕量級降級模型，將故障的影響有效控制在較小范圍內(nèi).

結(jié)合3層動態(tài)任務(wù)調(diào)度的輕量級容錯模型可以用圖5描述，在降級區(qū)內(nèi)計算資源發(fā)生故障后，相應(yīng)的容錯措施可以分為3類：

1) 當系統(tǒng)檢測到Slave出現(xiàn)故障，只需通知Region內(nèi)的所有進程，故障隔離后，由R-M回收已分配給故障資源但尚未完成的任務(wù)，并重新分配給健康資源計算，如圖5(a)所示；

2) 當系統(tǒng)檢測到R-M出現(xiàn)故障，只需通知Master和R-M，故障隔離后，Region內(nèi)重新選舉新的R-M，由Master回收已分配給故障資源但尚未完成的任務(wù)，并重新分配給健康資源計算，如圖5(b)所示；

3) 當系統(tǒng)檢測到Master出現(xiàn)故障，需通知所有的R-M和Master所在Region內(nèi)的進程，故障隔離后，重新選舉新的Master和R-M，由新Master回收已分配給故障資源但尚未完成的任務(wù)，并重新分配給健康資源計算，如圖5(c)所示.

當子任務(wù)并行計算完畢后，需要進行資源的重構(gòu)，完成作業(yè)的后續(xù)處理工作.

3.2輕量級降級模型性能分析

本文提出的輕量級降級模型，與故障后采用整個作業(yè)回卷的方式相比，作業(yè)的損失明顯要小.假設(shè)作業(yè)由P個進程執(zhí)行，共有n個子任務(wù)，執(zhí)行過程中共發(fā)生了g次故障，采用降級模型的損失為

其中，Di是第i次降級的處理時間，Ai是第i次降級處理影響的進程個數(shù)，Ri是第i次降級后作業(yè)繼續(xù)運行的時間，Ni是第i次降級減少的進程數(shù)量.

故障發(fā)生后，若采用回卷的容錯方式，損失的期望值為

作業(yè)退出時間+重新提交時間+初始化時間)≈

對大規(guī)模環(huán)境來說，Tquit+Tsub+Tinit的時間比較長，回卷會影響作業(yè)中所有計算資源執(zhí)行，因此L1會明顯小于L2.

采用輕量級的降級模型可以進行實時資源調(diào)配.當進程數(shù)為P的作業(yè)正在運行，需要調(diào)配出Q個進程的計算資源供其他作業(yè)使用時，只需要采用軟件措施標記擬調(diào)配的資源為“故障”狀態(tài)，可以在不停止作業(yè)的情況下劃走需要的資源，損失的期望值為L3.采用先停止作業(yè)再劃走資源的方式，損失的期望值為L4.

其中，Tadj是管理員調(diào)整資源的時間.

通常情況下，P通常是Q的數(shù)倍，因此L3明顯比L4小，從理論上來看采用降級模型具有明顯的優(yōu)勢.

4實驗結(jié)果

為了驗證本文提出的動態(tài)任務(wù)調(diào)度方法和輕量級容錯技術(shù)的有效性，利用國家超算濟南中心的神威藍光計算機系統(tǒng)進行了大規(guī)模測試，該系統(tǒng)每個節(jié)點由一顆申威-1600 16核CPU構(gòu)成(運行頻率1 GHz)，配備8 GB內(nèi)存，運行Linux操作系統(tǒng)，節(jié)點間采用Infiniband QDR網(wǎng)絡(luò)連接.我們使用了神威藍光計算機系統(tǒng)32 768核的計算資源進行測試.

4.1Micro Benchmark測試

為了方便地驗證本文模型的有效性，我們編寫了Micro Benchmark，并在神威藍光32 768核的環(huán)境下進行了驗證.該Micro Benchmark的并行任務(wù)執(zhí)行時間限定在[L,L+S](單位s)的范圍內(nèi)，由隨機數(shù)產(chǎn)生，任務(wù)之間相互獨立，平均每個核執(zhí)行100個任務(wù).

表1提供的測試數(shù)據(jù)可知，對2種不同計算時長的子任務(wù)進行了測試，其中子任務(wù)計算時間2～5 s(平均3.4 s)屬于極短任務(wù)，采用傳統(tǒng)Master-Slave模型，任務(wù)調(diào)度的開銷占執(zhí)行時間的50%以上.采用本文的模型，選取調(diào)度開銷的閾值C=10%，根據(jù)模型的分析和決策，使用3層實現(xiàn)，R-M的數(shù)量取128，任務(wù)調(diào)度開銷占測試程序執(zhí)行時間的6.88%，調(diào)度開銷僅為傳統(tǒng)模型的7.2%；AME[15]在16 384核環(huán)境下平均執(zhí)行4 s的任務(wù)，調(diào)度開銷超過10%.子任務(wù)計算時間為60～180 s屬于中等任務(wù)，采用傳統(tǒng)Master-Slave模型，調(diào)度開銷為2.81%，本文模型的開銷僅為0.32%.

Table 1　Estimate Value ofλ,σ2, and Time Costs for Different Task-size

圖6給出了任務(wù)執(zhí)行時間為2～5 s的情況下N層排隊模型與傳統(tǒng)Master-Slave模型的可擴展性對比.測試數(shù)據(jù)表明，采用傳統(tǒng)Master-Slave模型，任務(wù)調(diào)度開銷隨著進程數(shù)的增加上升非常快，說明Master是明顯的熱點，到32 768進程時任務(wù)申請已經(jīng)成為主要開銷.采用N層排隊模型，可以有效規(guī)避熱點，從1 024進程到32 768進程任務(wù)調(diào)度開銷增加不明顯，表明該方法可以有效擴展到大規(guī)模環(huán)境.

Fig. 6　Comparison of task requirement time costs for 2～5 s tasks.圖6　2～5 s極短隨機任務(wù)的任務(wù)申請開銷對比

4.2實際應(yīng)用測試結(jié)果

我們對實際應(yīng)用DOCK[24]進行了測試.DOCK是藥物設(shè)計領(lǐng)域應(yīng)用十分廣泛的分子對接計算模擬軟件，已經(jīng)成為藥物發(fā)現(xiàn)的核心工具之一，該軟件采用嵌入式的動態(tài)任務(wù)調(diào)度方法.原始DOCK程序的結(jié)果回收由主進程承擔，規(guī)模較大時主進程成為瓶頸，在測試之前我們對結(jié)果處理進行了優(yōu)化.

測試算例使用了24萬分子規(guī)模的化合物數(shù)據(jù)庫與疾病靶標進行分子對接模擬，每個靶標與分子的相互作用能(它們之間的自由能)計算就是一個計算任務(wù)，課題總共需要計算24萬次，單個任務(wù)的計算時間14～801 s，平均204 s.

仍然取調(diào)度開銷的閾值C=10%，表2給出了并行任務(wù)調(diào)度的測試結(jié)果.從表2看出，在1 024進程下，本文提出的并行框架采用2層調(diào)度模型實現(xiàn)，性能比原嵌入式調(diào)度方法提高4.9%，主要得益于網(wǎng)上傳送的消息量少；在16 384進程下，本文提出的并行框架經(jīng)決策采用3層調(diào)度模型，R-M的數(shù)量為128，緩解了Master端的壓力，比原嵌入式調(diào)度方法提高34.3%.課題從1 024擴展到16 384進程的加速比如圖7所示，DOCK原始的嵌入式任務(wù)調(diào)度方法加速比為12.37，采用本文的調(diào)度方法加速比達到了15.84，接近線性.根據(jù)理論分析可以預(yù)測，在更大的環(huán)境下采用多層調(diào)度模型將有更大的優(yōu)勢.

Table 2　Test Result of DOCK Application

Fig. 7　The speedup of DOCK application.圖7　DOCK應(yīng)用的加速比

表3給出了16 384進程下局部感知的降級效果，并與故障后回卷執(zhí)行的時間進行了對比，運行過程中的故障均采用手工制造的方式產(chǎn)生.Slave故障的處理開銷是5.2 ms，影響127進程，相比無故障執(zhí)行，運行時間增加了11.8 s；R-M故障的處理開銷是61.1 ms，影響127進程(未出故障的R-M和Master)，相比無故障執(zhí)行，運行時間增加了19.6 s；Master故障的處理時間較長，處理開銷是6.5 s，影響影響127進程(所有的R-M)，總執(zhí)行時間增加了55.5 s.采用故障后回卷執(zhí)行，比無故障運行的結(jié)果增加了175.6 s(任何一個點故障對回卷來說是同等的，因此回卷只測試了一次)，其中正在執(zhí)行的任務(wù)大約損失100 s，課題的中止、課題的重新提交和應(yīng)用初始化的時間之和大約是75 s.從測試數(shù)據(jù)看，局部感知的降級措施相對于故障后回卷，課題執(zhí)行時間減少3.75%～5.13%.若單個任務(wù)的執(zhí)行時間長，回卷執(zhí)行的損失更大，局部感知的降級措施的優(yōu)勢將更為明顯.

表4給出了16 384進程環(huán)境、作業(yè)正在執(zhí)行情況下，動態(tài)劃走4 096個進程計算資源的開銷對比.劃走計算資源，通常需要停止作業(yè)，完成資源整理后再重新提交作業(yè)，本作業(yè)所有計算資源上正在執(zhí)行的任務(wù)將重新執(zhí)行，在大規(guī)模環(huán)境下，作業(yè)停止時間、資源整理時間、作業(yè)重新提交的初始化時間都不短.采用本文的降級模型，可以進行人工造錯，在作業(yè)不停的情況下劃走需要的資源，主要損失是被劃走資源上正執(zhí)行的任務(wù)需重新執(zhí)行，其他進程的執(zhí)行不受影響.

Table 3Fault-tolerant Test for 16 384 Processes (Artificial

Fault when Executing 1 500 s)

表316 384進程環(huán)境下的容錯測試(程序執(zhí)行1 500 s時人工造錯)

TypeofFault-tolerantLight-weightDegradationModel∕sRoll-backModel∕sPercentageReductionofDegradationvsRoll-back∕%SlaveFault3031.83195.65.13R-MFault3039.63195.64.88MasterFault3075.53195.63.75

Table 4Comparison of Time Costs between Two Methods

when the Resources are Changed

表4　資源變動情況下2種方法的開銷對比測試

5結(jié)束語

本文針對大規(guī)模環(huán)境下并行任務(wù)動態(tài)調(diào)度的可擴展性和容錯問題，提出了基于N層排隊理論的高可擴展動態(tài)任務(wù)調(diào)度模型和方法.測試數(shù)據(jù)表明，該模型可以有效擴展到大規(guī)模環(huán)境，相比傳統(tǒng)的Master-Slave模型具有明顯的優(yōu)勢，可以滿足Peta Flops級別系統(tǒng)下的應(yīng)用需求，并可以推廣到未來的Exascale級別的系統(tǒng)；配套的并行編程框架能有效減輕程序員的負擔，并將任務(wù)調(diào)度產(chǎn)生的消息量通信開銷降至最低.

結(jié)合高可擴展動態(tài)任務(wù)調(diào)度方法，提出了基于局部感知技術(shù)的優(yōu)化降級模型，當發(fā)生故障時只影響部分進程的執(zhí)行，有效降低容錯開銷.測試數(shù)據(jù)表明，與傳統(tǒng)的容錯方法相比具有較為明顯的優(yōu)勢.

目前調(diào)度模型的分層是根據(jù)前M個采樣來決策的，下一步我們擬在運行過程中對模型的分層決策進行動態(tài)調(diào)整.

致謝我們向?qū)Ρ疚墓ぷ鹘o予指導和幫助的江南計算技術(shù)研究所的龔道永、宋長明、李祖華等人表示衷心地感謝!

參考文獻

[1]Wang Yiran, Chen Li, Feng Xiaobing, et al. Global partial replicate computation partitioning[J]. Journal of Computer Research and Development, 2006, 43(12): 2158-2165 (in Chinese)(王軼然, 陳莉, 馮曉兵, 等. 全局部分重復(fù)計算劃分[J]. 計算機研究與發(fā)展, 2006, 43(12): 2158-2165)

[2]Wang Lei, Cui Huimin, Chen Li, et al. Research on task parallel programming model[J]. Journal of Software, 2013, 24(1): 77-90 (in Chinese)(王蕾, 崔慧敏, 陳莉, 等. 任務(wù)并行編程模型研究與進展[J]. 軟件學報, 2013, 24(1): 77-90)

[3]Streitz F H, Glosli J N, Patel M V, et al. 100+TFlop solidification simulations on BlueGene/L[EB/OL]. [2014-11-02]. http://sc05.supercomp.org/schedule/pdf/pap307.pdf

[4]Koziar C, Reilein R, Runger G. Load imbalance aspects in atmosphere simulations[J]. International Journal of Computational Science and Engineering, 2005, 1(2): 215-225

[5]Kale L V. CHARM++: A portable concurrent object oriented system based on C++[C] //Proc of OOPSLA 1993. New York: ACM, 1993: 91-108

[6]Menon H, Kalé L. A distributed dynamic load balancer for iterative applications[C] //Proc of IEEE/ACM SC13. New York: ACM, 2013: 1-11

[7]Zheng G, Meneses E, Bhatele A, et al. Hierarchical load balancing for Charm++applications on large supercomputers[C] //Proc of the 39th Int Conf on Parallel Processing Workshops. Los Alamitos, CA: IEEE Computer Society, 2010: 436-444

[8]LBNL, UC Berkeley. Berkeley UPC-Unified Parallel C[EB/OL]. [2014-11-02]. http://upc.lbl.gov

[9]Chen Li, Huo Wei, Lu Xingjing, et al. Parallel programming languages on multi-core and many-core architectures[J]. Information Technology Letter, 2012, 10(1): 23-40 (in Chinese)(陳莉, 霍偉, 盧興敬, 等. 多核/眾核系統(tǒng)上的并行編程語言[J]. 信息技術(shù)快報, 2012, 10(1): 23-40)

[10]Kumar R, Tullsen D M, Ranganathan P, et al. Single-ISA heterogeneous multi-core architectures for multi-threaded workload performance[J]. Isca Proc of Annual International Symposium on Computer Architecture, 2004, 32(2): 64

[11]Devine K, Boman E, Heaphy R, et al. Zoltan data management services for parallel dynamic applications[J]. Computing in Science & Engineering, 2002, 4(2): 90-96

[12]Zhang W, Tardieu O, Grove D, et al. GLB: Lifeline-based global load balancing library in X10[C] //Proc of the 1st Workshop on Parallel Programming for Analytics Applications. New York: ACM, 2014: 31-40

[13]Tardieu O, Herta B, Cunningham D, et al. X10 at Petascale[C] //Proc of the 17th ACM SIGPLAN Symp on Principles and Practice of Parallel Programming. New York: ACM, 2012: 267-276

[14]Berger E, Browne J C. Scalable load distribution and load balancing for dynamic parallel programs[EB/OL]. [2014-11-02]. http://web.engr.illinois.edu/～lumetta/wcbc99/wcbc-99-beb.pdf

[15]Zhang Z, Katz D S, Ripeanu M, et al. AME: An anyscale many-task computing engine[C] //Proc of the 6th Workshop on Workflows in Support of Large-Scale Science. New York: ACM, 2011: 137-146

[16]Krieder S J, Wozniak J M, Armstrong T, et al. Design and evaluation of the GeMTC framework for GPU-enabled many-task computing[C] //Proc of HPDC 2014. New York: ACM, 2014: 153-164

[17]Xiao J, Zhang Y, Chen S, et al. An application-level scheduling with task bundling approach for many-task computing in heterogeneous environments[C] //Proc of the 9th IFIP Int Conf. Berlin: Springer, 2012: 1-13

[18]Hargrove P H, Duell J C. Berkeley lab checkpoint/restart (blcr) for Linux clusters[J]. Journal of Physics: Conference Series, 2006, 46(1): 494-499

[19]Moody A, Bronevetsky G, Mohror K, et al. Design, modeling, and evaluation of a scalable multi-level checkpointing system[C] //Proc of IEEE/ACM SC’10. Piscataway, NJ: IEEE, 2010: 1-11

[20]You Hongtao, Jiang Xiaocheng, Chen Zuoning. Design of degrade based on dynamic job assignment[J]. Microcomputer Information, 2006, 22(30): 72-75 (in Chinese)(尤洪濤, 姜小成, 陳左寧. 基于動態(tài)任務(wù)劃分的降級機制[J]. 微計算機信息, 2006, 22(30): 72-75)

[21]Tang Yinghui, Tang Xiaowo. Basis and Analysis Technology of Queuing Theory[M]. Beijing: Science Press, 2006 (in Chinese)(唐應(yīng)輝, 唐小我. 排隊論基礎(chǔ)與分析技術(shù)[M]. 北京: 科學出版社, 2006)

[22]Department of Mathematics and Mechanics at Zhongshan University. Probability Theory and Mathematical Statistics[M]. Beijing: Higher Education Press, 1985 (in Chinese)(中山大學數(shù)學力學系. 概率論及數(shù)理統(tǒng)計[M]. 北京: 高等教育出版社, 1985)

[23]Liu Cihua. Stochastic Processes[M]. 2nd ed. Wuhan: Huazhong University of Science and Technology Press, 2005 (in Chinese)(劉次華. 隨機過程[M]. 2版. 武漢: 華中科技大學出版社, 2005)

[24]UCSF. The official UCSF DOCK Web-site: DOCK 6[EB/OL]. [2014-11-02]. http://dock.compbio.ucsf.edu/DOCK_6/index.htm

He Wangquan, born in 1975. PhD candidate and senior engineer. Member of China Computer Federation. His main research interests include parallel programming language design, compiler optimization and runtime system.

Wei Di, born in 1984. Master and engineer. His main research interests include parallel progamming language design, runtime system and comunication system design (dididi888@chinaren.com).

Quan Jianxiao, born in 1983. Master and engineer. His main research interests include parallel progamming language design, complier optimization and runtime system (brightsky2007@163.com).

Wu Wei, born in 1984. Master and engineer. His main research interests include compiler design, compiler optimization, and parallel programming (ww7tc@sina.com).

Qi Fengbin, born in 1966. Senior engineer and PhD supervisor. Senior member of China Computer Federation. His main research interests include high performance computing architecture, compiler optimization and parallel algorithm (qifb116@sina.com).

Dynamic Task Scheduling Model and Fault-Tolerant via Queuing Theory

He Wangquan1, Wei Di1, Quan Jianxiao1, Wu Wei1, and Qi Fengbin2

1(JiangnanInstituteofComputingTechnology,Wuxi,Jiangsu214083)2(NationalResearchCenterofParallelComputerEngineering&Technology,Beijing100080)

AbstractThe design of efficient dynamic task scheduling and fault-tolerant mechanism is an issue of crucial importance in high-performance computing field. Most existing methods, however, can hardly achieve good scalability on large-scale system. In this paper, we propose a scalable dynamic task scheduling model viaN-level queuing theory, which dramatically reduces the programming burden by providing programmer with concise parallel programming framework. On one hand, we utilize the Poisson process theory to analyze the average wait time of tasks, and then decide the task layers according to threshold. On the other hand, we reduce the fault tolerance overhead using region-aware light-weight degradation model. Experimental results with Micro Benchmark on Bluelight system with 32 768 cores show that our method achieves good scalability when the tasks take 3.4 s on average and the overhead is just 7.2% of traditional model. Running on 16 384 cores, pharmacological application DOCK achieves performance improvement by 34.3% with our scheduling. Moreover, the results of DOCK show our fault-tolerant model achieves 3.75%～5.13% performance improvements over traditional mechanism.

Key wordsqueuing theory; dynamic task scheduling; programming framework; fault-tolerant; light-weight degradation

收稿日期：2014-12-30；修回日期：2015-08-17

基金項目：國家“八六三”高技術(shù)研究發(fā)展計劃基金項目(2012AA010903);計算機體系結(jié)構(gòu)國家重點實驗室基金項目(CARCH201403)

中圖法分類號TP391

This work was supported by the National High Technology Research and Development Program of China (863 Program) (2012AA010903) and the Foundation of State Key Laboratory of Computer Architecture (CARCH201403).