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

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

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

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2輕量級(jí)容錯(cuò)研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

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

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

1)ξ(0)=0；

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

3)ξ(t)滿足：

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

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

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

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

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

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

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

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

2.2模型性能分析

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

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

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

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

Treq≈ 2×Tmsg+Twait+Tdispose.

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

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

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

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

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

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

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

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

{

do_job(task_id);*用戶代碼 *

}

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

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

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

f:第i個(gè)任務(wù)|→任務(wù)編號(hào)i，f-1:任務(wù)編號(hào)i|→第i個(gè)任務(wù).

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

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

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

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

Fig. 4　Fault-tolerant model of degradation.圖4　降級(jí)容錯(cuò)模型

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

3.1局部感知的輕量級(jí)降級(jí)模型

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

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

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

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

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

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

3.2輕量級(jí)降級(jí)模型性能分析

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

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

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

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

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

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

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

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

4實(shí)驗(yàn)結(jié)果

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

4.1Micro Benchmark測(cè)試

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

表1提供的測(cè)試數(shù)據(jù)可知，對(duì)2種不同計(jì)算時(shí)長(zhǎng)的子任務(wù)進(jìn)行了測(cè)試，其中子任務(wù)計(jì)算時(shí)間2～5 s(平均3.4 s)屬于極短任務(wù)，采用傳統(tǒng)Master-Slave模型，任務(wù)調(diào)度的開銷占執(zhí)行時(shí)間的50%以上.采用本文的模型，選取調(diào)度開銷的閾值C=10%，根據(jù)模型的分析和決策，使用3層實(shí)現(xiàn)，R-M的數(shù)量取128，任務(wù)調(diào)度開銷占測(cè)試程序執(zhí)行時(shí)間的6.88%，調(diào)度開銷僅為傳統(tǒng)模型的7.2%；AME[15]在16 384核環(huán)境下平均執(zhí)行4 s的任務(wù)，調(diào)度開銷超過(guò)10%.子任務(wù)計(jì)算時(shí)間為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í)行時(shí)間為2～5 s的情況下N層排隊(duì)模型與傳統(tǒng)Master-Slave模型的可擴(kuò)展性對(duì)比.測(cè)試數(shù)據(jù)表明，采用傳統(tǒng)Master-Slave模型，任務(wù)調(diào)度開銷隨著進(jìn)程數(shù)的增加上升非?？?，說(shuō)明Master是明顯的熱點(diǎn)，到32 768進(jìn)程時(shí)任務(wù)申請(qǐng)已經(jīng)成為主要開銷.采用N層排隊(duì)模型，可以有效規(guī)避熱點(diǎn)，從1 024進(jìn)程到32 768進(jìn)程任務(wù)調(diào)度開銷增加不明顯，表明該方法可以有效擴(kuò)展到大規(guī)模環(huán)境.

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

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

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

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

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

Table 2　Test Result of DOCK Application

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

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

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

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

Fault when Executing 1 500 s)

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

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　資源變動(dòng)情況下2種方法的開銷對(duì)比測(cè)試

5結(jié)束語(yǔ)

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

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

目前調(diào)度模型的分層是根據(jù)前M個(gè)采樣來(lái)決策的，下一步我們擬在運(yùn)行過(guò)程中對(duì)模型的分層決策進(jìn)行動(dòng)態(tài)調(diào)整.

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

參考文獻(xiàn)

[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ì)算劃分[J]. 計(jì)算機(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ìn)展[J]. 軟件學(xué)報(bào), 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)上的并行編程語(yǔ)言[J]. 信息技術(shù)快報(bào), 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)(尤洪濤, 姜小成, 陳左寧. 基于動(dòng)態(tài)任務(wù)劃分的降級(jí)機(jī)制[J]. 微計(jì)算機(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)輝, 唐小我. 排隊(duì)論基礎(chǔ)與分析技術(shù)[M]. 北京: 科學(xué)出版社, 2006)

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

[23]Liu Cihua. Stochastic Processes[M]. 2nd ed. Wuhan: Huazhong University of Science and Technology Press, 2005 (in Chinese)(劉次華. 隨機(jī)過(guò)程[M]. 2版. 武漢: 華中科技大學(xué)出版社, 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

基金項(xiàng)目：國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目(2012AA010903);計(jì)算機(jī)體系結(jié)構(gòu)國(guó)家重點(diǎn)實(shí)驗(yàn)室基金項(xiàng)目(CARCH201403)

中圖法分類號(hào)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).