基于負(fù)載感知和QoS的多中心作業(yè)調(diào)度算法

馮鳴夏，伍衛(wèi)國，邸德海

(1.西安交通大學(xué) 電子與信息工程學(xué)院，陜西 西安 710049；2.西安交通大學(xué) 管理學(xué)院，陜西 西安 710049)

0 引 言

隨著高性能計算的高速發(fā)展，超級計算機(jī)的發(fā)展進(jìn)入了一個蓬勃發(fā)展的新時代。由國內(nèi)自主研發(fā)的神威太湖之光[1]實(shí)現(xiàn)了處理器核心全部國產(chǎn)化，整個系統(tǒng)擁有1 000萬核，處理速度達(dá)到了每秒12.5億億次，在2017年11月的top500排名中再次位居世界第一。高性能計算是戰(zhàn)略性、前沿性的高新技術(shù)，是世界各國爭奪的戰(zhàn)略制高點(diǎn)，是國家創(chuàng)新體系的重要組成部分。國內(nèi)已經(jīng)擁有了由19個高性能計算中心組成的中國國家網(wǎng)格[2]，計算資源能力位居世界前列。

高性能計算中心都運(yùn)行著獨(dú)立的作業(yè)調(diào)度系統(tǒng)如OpenPBS,Slurm,Condor等。主流的資源管理系統(tǒng)主要由資源管理和作業(yè)管理兩個部分組成。資源管理服務(wù)主要負(fù)責(zé)對計算中心的計算資源進(jìn)行管理，為被調(diào)度的作業(yè)分配計算資源。作業(yè)管理服務(wù)主要維護(hù)用戶的作業(yè)隊(duì)列，根據(jù)調(diào)度策略選擇合適的作業(yè)進(jìn)行提交。目前對大規(guī)模作業(yè)調(diào)度系統(tǒng)的研究主要集中在單計算中心內(nèi)部的作業(yè)調(diào)度策略，這些調(diào)度算法的設(shè)計主要考慮到系統(tǒng)吞吐率、利用率和公平性。N.Rathore等[3]通過網(wǎng)格內(nèi)作業(yè)遷移實(shí)現(xiàn)計算中心內(nèi)的負(fù)載均衡；李榮盛等[4]提出了基于價值密度和相對截止期的作業(yè)調(diào)度算法以提高資源利用率；梁毅等[5]提出的RB-FIFT策略有效地減少了資源碎片；Niu Shuangcheng等[6]提出的基于檢查點(diǎn)的回填策略提高了作業(yè)響應(yīng)時間；Dan Tsafrir等[7]通過系統(tǒng)產(chǎn)生作業(yè)預(yù)測時間提高作業(yè)回填調(diào)度的準(zhǔn)確性；蔣江等[8]研究了單集群內(nèi)基于多種資源的負(fù)載均衡算法；曹宗雁等[9]提出的基于用戶評價的集群作業(yè)優(yōu)先級調(diào)度提高了用戶服務(wù)質(zhì)量。這些調(diào)度策略只能盡量保證計算中心內(nèi)部資源的高效利用，并不能保證各個計算中心的負(fù)載均衡。于珊珊等[10]針對多數(shù)據(jù)中心任務(wù)調(diào)度，提出了基于SLA的最大化收益任務(wù)調(diào)度算法。這種調(diào)度算法僅適用于云計算數(shù)據(jù)中心，而對于高性能計算中心并不完全適用。

在國家高性能計算環(huán)境中，由于網(wǎng)絡(luò)帶寬和地域等因素，可能會造成不同計算中心資源忙閑不均[11]。針對多計算中心作業(yè)調(diào)度，采用基于負(fù)載感知和QoS的多中心作業(yè)調(diào)度策略，充分考慮各個計算中心的負(fù)載情況和用戶對作業(yè)的QoS需求，對作業(yè)進(jìn)行分流，以提高計算中心的服務(wù)水平。

1 基于排隊(duì)論的多計算中心服務(wù)性能分析

圖1 多中心作業(yè)服務(wù)示意圖

任務(wù)到達(dá)間距遵循參數(shù)為λ的泊松分布，任務(wù)的服務(wù)時間遵循參數(shù)為μ的負(fù)指數(shù)分布，這樣的假設(shè)是合理的，并且在許多研究文獻(xiàn)中都支持這種假設(shè)。

(1)

(2)

(3)

根據(jù)式1～3可得：

(4)

單個計算中心的服務(wù)滿足M/M/1的排隊(duì)論模型。根據(jù)little公式可知：

計算中心Ci的等待隊(duì)長為：

(5)

多計算中心排隊(duì)總長度為：

(6)

計算中心Ci的等待時間為：

(7)

多計算中心平均等待時間為：

(8)

2 計算中心負(fù)載模型

2.1 計算節(jié)點(diǎn)負(fù)載模型

高性能計算節(jié)點(diǎn)的負(fù)載包括CPU的負(fù)載、內(nèi)存使用率等。與此同時，節(jié)點(diǎn)溫度也是負(fù)載的重要指標(biāo)。定義一個負(fù)載指數(shù)load_index衡量物理節(jié)點(diǎn)的綜合負(fù)載程度。

2.2 計算中心負(fù)載模型

對計算中心的負(fù)載進(jìn)行劃分：

(1)輕載：當(dāng)空閑節(jié)點(diǎn)比例超過α?xí)r，表示該計算中心處于輕載狀態(tài)。

(2)正常：當(dāng)正常節(jié)點(diǎn)的比例超過β時，表示該計算中心處于正常狀態(tài)。

(3)過載：當(dāng)過載節(jié)點(diǎn)的比例超多γ時，表示該計算中心處于過載狀態(tài)。

在計算中心內(nèi)部負(fù)載正常的情況下，作業(yè)直接分配給最近計算中心完成，如果計算中心處于過載或者故障狀態(tài)，這個作業(yè)就會分配給其他計算中心完成。

3 基于負(fù)載感知和QoS的作業(yè)調(diào)度算法

3.1 用戶的QoS目標(biāo)約束

QoS服務(wù)質(zhì)量是來源于網(wǎng)絡(luò)性能機(jī)制的參數(shù)，但在計算中心用QoS表示用戶提交的作業(yè)所需求的各種服務(wù)特征參數(shù)。用戶在向計算中心提交作業(yè)時，對于計算平臺的服務(wù)質(zhì)量有一定的要求。用戶可能將成本的開銷、完成時間、響應(yīng)時間、平臺可靠性等作為QoS目標(biāo)約束。滿足用戶對QoS參數(shù)的要求，可以提高計算中心的用戶滿意度。因此，計算中心保證QoS，對于它向用戶提供的服務(wù)至關(guān)重要。用戶每次提交作業(yè)時，可能會根據(jù)作業(yè)的特點(diǎn)對QoS的屬性有不同的偏好。用戶在提交作業(yè)時，同時會對本次作業(yè)的QoS屬性的偏好進(jìn)行選擇。選取計算中心5個服務(wù)質(zhì)量屬性作為目標(biāo)約束。

(1)計算價格(P)。

用戶將要執(zhí)行的作業(yè)和數(shù)據(jù)上傳到計算中心，并提交作業(yè)到作業(yè)調(diào)度系統(tǒng)等待獲取可計算資源，計算中心會根據(jù)作業(yè)請求的計算核數(shù)以及作業(yè)的執(zhí)行時間收取費(fèi)用。計算中心的計算資源通常按照核每小時進(jìn)行收費(fèi)。

(2)排隊(duì)時間(Q)。

當(dāng)用戶提交作業(yè)到計算中心的作業(yè)調(diào)度系統(tǒng)，如果當(dāng)前計算中心的資源無法滿足作業(yè)提交時申請的資源時，作業(yè)會進(jìn)入排隊(duì)狀態(tài)。當(dāng)有空閑資源時，調(diào)度系統(tǒng)會重新調(diào)度作業(yè)，給作業(yè)分配資源。

(3)計算能力(C)。

不同的計算中心可能采用不同的硬件資源和不同的網(wǎng)絡(luò)拓?fù)洹Ｓ嬎阒行牡挠嬎隳芰Υ嬖诓町悺Ｈ绻鳂I(yè)對計算能力有要求，用戶可能會選擇計算能力強(qiáng)的計算中心。

(4)上行傳輸速度(Bin)。

用戶使用計算中心資源時，首先需要將程序執(zhí)行需要的運(yùn)行數(shù)據(jù)上傳到計算中心的登錄節(jié)點(diǎn)。對于大輸入應(yīng)用，生物計算領(lǐng)域，如BLAST[12]，計算數(shù)據(jù)主要由比對文件和比對數(shù)據(jù)庫兩部分組成。比對數(shù)據(jù)庫文件通常很大，用戶上傳需要很長的時間。

(5)下行傳輸速度(Bout)。

當(dāng)用戶的程序執(zhí)行結(jié)束后，用戶需要下載程序執(zhí)行結(jié)果時，需要從計算中心的存儲節(jié)點(diǎn)下載到本地。對于大輸出應(yīng)用，選擇分子動力學(xué)和工程學(xué)中用于產(chǎn)生運(yùn)動軌跡的應(yīng)用軟件。如Fluent[13]，隨著計算步數(shù)的增加輸出數(shù)據(jù)會明顯增加。

用戶根據(jù)作業(yè)的性質(zhì)，對各個屬性進(jìn)行打分。分?jǐn)?shù)的范圍設(shè)置為0～10。當(dāng)用戶對某一項(xiàng)評分為0時，表示不關(guān)心此QoS屬性。

3.2 計算中心QoS屬性向量

在一個計算中心Ci中，計算價格是由計算中心的管理人員制定的，在一段時間內(nèi)不會發(fā)生改變；計算能力由硬件資源和網(wǎng)絡(luò)拓?fù)錄Q定，在一段時間內(nèi)不會發(fā)生改變；上行傳輸速度和下行傳輸速度由當(dāng)前網(wǎng)絡(luò)環(huán)境決定，需要定時測量；影響排隊(duì)時間的因素主要由計算中心內(nèi)排隊(duì)的隊(duì)長決定。

計算中心Ci的計算價格屬性維度為：

(9)

計算中心Ci的排隊(duì)時間屬性維度為：

(10)

計算中心Ci的計算能力屬性維度為：

(11)

計算中心Ci的上行傳輸速度屬性維度為：

(12)

計算中心Ci的下行傳輸速度屬性維度為：

(13)

該方法實(shí)現(xiàn)對原始數(shù)據(jù)的等比例縮放，其中X_norm為歸一化后的數(shù)據(jù)，X為原始數(shù)據(jù)，Xmax、Xmin分別為原始數(shù)據(jù)集的最大值和最小值。

3.3 算法描述

多中心作業(yè)調(diào)度算法首先考慮各個計算中心的負(fù)載情況，當(dāng)作業(yè)到來時，首先將輕載或負(fù)載正常的計算中心作為備選計算中心。在此基礎(chǔ)上，考慮用戶作業(yè)對服務(wù)質(zhì)量的需求，對作業(yè)和計算中心進(jìn)行QoS匹配，通過計算作業(yè)提交的QoS屬性向量和計算中心QoS屬性向量的余弦值，找到與作業(yè)親和度Affinity最高的計算中心。算法描述如下：

算法：基于負(fù)載反饋和QoS約束的多中心作業(yè)調(diào)度算法

輸入：用戶對QoS屬性的打分，計算價格(s1)，排隊(duì)時間(s2)，計算能力(s3),上行傳輸速度(s4),下行傳輸速度(s5)

輸出：最優(yōu)計算中心

1.for each hub in hubsList do

2.getcurrentState(hub);//獲取每一個計算中心的負(fù)載

3.if(hub.state==idle||hub.state==normal)then

4.candidatesList.add(hub);

5.end if

6.end for

7.for each candidate in candidatesList do

8.tmpAffinity=calculteCos(s1,s2,s3,s4,s5);//計算作業(yè)和計算中心的親和度

9.if(Affinity

10.bestSelect=candidate;

11.tmpAffinity=Affinity;

12.end if

13.end for

14.return bestSelect

4 基于檢查點(diǎn)的多中心間作業(yè)遷移容錯策略

隨著系統(tǒng)規(guī)模不斷擴(kuò)大，系統(tǒng)的故障率也在不斷增加，需要在多中心作業(yè)調(diào)度系統(tǒng)中添加作業(yè)遷移容錯機(jī)制，以保證用戶作業(yè)得到更好的服務(wù)。基于檢查點(diǎn)的多中心間作業(yè)遷移容錯策略一方面支持傳統(tǒng)的用戶手動的檢查點(diǎn)恢復(fù)功能，另一方面解決大量長時應(yīng)用在作業(yè)運(yùn)行時出現(xiàn)異常中斷的問題。一些科學(xué)計算作業(yè)通常都采用并行處理，需要多個計算節(jié)點(diǎn)協(xié)同完成。在作業(yè)任務(wù)量比較大的情況下，需要較長的時間開銷。如果在運(yùn)行過程中出現(xiàn)異常中斷，只能從頭開始計算。即使作業(yè)支持檢查點(diǎn)機(jī)制，也需要用戶顯示地恢復(fù)作業(yè)，這就造成了系統(tǒng)吞吐率下降，影響作業(yè)的響應(yīng)時間。

當(dāng)計算中心遇到例行維護(hù)等工作時，系統(tǒng)會將正在運(yùn)行的作業(yè)掛起，當(dāng)系統(tǒng)恢復(fù)正常時再重新執(zhí)行掛起的作業(yè)。定期將程序檢查點(diǎn)文件遷移到災(zāi)備計算中心。目前在計算中心的調(diào)度系統(tǒng)中，如果某一個計算節(jié)點(diǎn)出現(xiàn)問題而導(dǎo)致整個作業(yè)被中斷，必須重新被調(diào)度從頭開始運(yùn)行，當(dāng)作業(yè)運(yùn)行時間較長時，非常耗費(fèi)資源且無法保證用戶的服務(wù)體驗(yàn)。多中心間作業(yè)遷移是指將一個計算中心的作業(yè)遷移到另一計算中心運(yùn)行的方法。作業(yè)遷移可以提高計算中心的負(fù)載均衡，實(shí)現(xiàn)高效的容錯，為用戶提供更加優(yōu)質(zhì)的服務(wù)。

檢查點(diǎn)技術(shù)廣泛應(yīng)用于程序運(yùn)行中間狀態(tài)的保存和運(yùn)行狀態(tài)的恢復(fù)。當(dāng)前該技術(shù)并未應(yīng)用在多中心作業(yè)遷移的容錯策略中。根據(jù)用戶設(shè)定的檢查點(diǎn)同步時間間隔，當(dāng)檢查點(diǎn)同步時間到期時，主計算中心將當(dāng)前作業(yè)檢查點(diǎn)數(shù)據(jù)同步到災(zāi)備計算中心，檢查點(diǎn)的網(wǎng)絡(luò)傳輸和作業(yè)運(yùn)行是并行的，并不會對作業(yè)產(chǎn)生多余的時間開銷。當(dāng)災(zāi)備計算中心在一定時間內(nèi)沒有收到主計算中心的同步信號時，則災(zāi)備計算中心根據(jù)作業(yè)檢查點(diǎn)信息重新提交用戶作業(yè)，當(dāng)作業(yè)獲取調(diào)度器分配的資源時，作業(yè)從檢查點(diǎn)處恢復(fù)作業(yè)的執(zhí)行。

4.1 多中心間作業(yè)遷移

在源計算中心，作業(yè)遷移發(fā)送模塊根據(jù)用戶作業(yè)提交的信息，設(shè)定作業(yè)檢查點(diǎn)遷移周期和災(zāi)備計算中心。當(dāng)檢查點(diǎn)遷移周期到期時，作業(yè)遷移發(fā)送模塊檢查作業(yè)的運(yùn)行狀態(tài)，如果作業(yè)沒有運(yùn)行結(jié)束，遷移模塊壓縮作業(yè)的檢查點(diǎn)文件并將其同步傳輸?shù)侥繕?biāo)計算中心。

在災(zāi)備計算中心，作業(yè)遷移接收模塊定期會收到源計算中心的心跳信息和保存作業(yè)的檢查點(diǎn)文件，當(dāng)遷移接收模塊在一段時間內(nèi)沒有收到心跳信息，則認(rèn)為源計算中心發(fā)生故障。遷移接收模塊將從檢查點(diǎn)處提交作業(yè)。

4.2 多中心系統(tǒng)的可用性分析

系統(tǒng)可用性(Availability)是信息工業(yè)界用來衡量一個信息系統(tǒng)提供持續(xù)服務(wù)的能力，表示在給定時間系統(tǒng)或者系統(tǒng)某一能力在特定環(huán)境中能夠滿意工作的概率。其計算方法為：

(14)

MTTF(mean time to failure，平均無故障時間)，指系統(tǒng)無故障運(yùn)行的平均時間，取所有從系統(tǒng)開始正常運(yùn)行到發(fā)生故障之間的時間段的平均值。即使每一個零件有很高的可靠性，但組成的系統(tǒng)的MTTF值會驟然下降。MTTR(mean time to repair，平均修復(fù)時間)，指系統(tǒng)從發(fā)生故障到維修結(jié)束之間的時間段的平均值。

在目前的作業(yè)調(diào)度系統(tǒng)中，如果計算節(jié)點(diǎn)發(fā)生故障，在節(jié)點(diǎn)上運(yùn)行的作業(yè)都會異常退出。用戶需要等待計算中心故障修復(fù)，然后重新從檢查點(diǎn)提交作業(yè)。從用戶角度，從作業(yè)異常退出到作業(yè)再次提交的這段時間內(nèi)，計算中心的計算節(jié)點(diǎn)不可用屬于MTTR。MTTR取決于用戶發(fā)現(xiàn)故障的時間和計算中心故障修復(fù)的時間。多計算中心作業(yè)遷移容錯機(jī)制保證了災(zāi)備計算中心第一時間發(fā)現(xiàn)用戶作業(yè)發(fā)生故障，遷移調(diào)度模塊自動根據(jù)作業(yè)的檢查點(diǎn)信息重新提交作業(yè)，大大縮短了由于源計算中心故障修復(fù)和用戶發(fā)現(xiàn)故障不及時帶來的時間開銷。在多中心間作業(yè)遷移容錯模型中，當(dāng)災(zāi)備計算中心探測到源數(shù)據(jù)中心發(fā)生故障時，將根據(jù)作業(yè)檢查點(diǎn)信息重新提交作業(yè)，減少了人為故障探測和等待計算中心故障修復(fù)的時間代價。整個遷移容錯過程大大降低了MTTR，從而提高了系統(tǒng)的可用性。基于檢查點(diǎn)的作業(yè)遷移流程如圖2所示。

圖2 多中心作業(yè)遷移容錯示意圖

檢查點(diǎn)生成之后，源中心的遷移發(fā)送模塊需要將檢查點(diǎn)文件傳輸?shù)綖?zāi)備計算中心，檢查點(diǎn)的傳輸和作業(yè)的運(yùn)行是異步進(jìn)行的，影響程序執(zhí)行的主要因素是作業(yè)檢查點(diǎn)的開銷。由于一些作業(yè)生成的檢查點(diǎn)文件較大，需要在傳輸前進(jìn)行壓縮處理。壓縮可以有效地減少傳輸帶來的開銷。

5 仿真實(shí)驗(yàn)分析與比較

仿真工具使用GridSim[14]，它是澳大利亞墨爾本大學(xué)開發(fā)的基于Java離散事件的網(wǎng)格仿真工具，基于SimJava開發(fā)。該工具支持對網(wǎng)格資源、用戶和應(yīng)用的仿真和建模。它提供了創(chuàng)建應(yīng)用任務(wù)和網(wǎng)格資源管理調(diào)度的方法。仿真結(jié)束后，用戶可以調(diào)用GridSim中稱為GridStatisties的庫函數(shù)來收集各種模擬的統(tǒng)計資料。

利用GridSim構(gòu)建了4個計算中心，計算中心的資源情況如表1所示。

仿真使用的實(shí)驗(yàn)數(shù)據(jù)集是由捷克國家電網(wǎng)基礎(chǔ)設(shè)施MetaCentrum提供的Zewura工作日志[15]。Zewura日志包含五個月的執(zhí)行工作(2012年1月-5月)從TORQUE跟蹤生成的數(shù)據(jù)集。該日志包括17 257個作業(yè)。

將提出的Laq算法和兩種主流的負(fù)載均衡算法Random、RoundRobin分別從作業(yè)總完成時間、作業(yè)平均響應(yīng)時間、作業(yè)平均等待時間、計算中心平均負(fù)載等多個維度進(jìn)行比較，如圖3所示。

圖3 多計算中心服務(wù)性能比較

由仿真結(jié)果可得，相比Random和RoundRobin，Laq算法顯著降低了多計算中心作業(yè)的完成時間、平均響應(yīng)時間、平均等待時間。在Laq算法的作業(yè)調(diào)度策略下使各個計算中心保持相對平均的負(fù)載，合理利用和分配計算資源，提高了資源利用率。

6 結(jié)束語

針對分布在不同地域的計算中心存在計算資源忙閑不均，缺少統(tǒng)一調(diào)度和管理的問題，提出了一種基于負(fù)載感知和QoS的多中心作業(yè)調(diào)度算法。該算法根據(jù)各個計算中心的負(fù)載情況將需要處理的作業(yè)分配給負(fù)載較輕的計算中心，充分考慮到用戶的QoS需求,將作業(yè)盡量調(diào)度到符合用戶QoS需求的計算中心，從而提高計算中心的服務(wù)水平。通過與Random和RoundRobin的仿真對比，證明了該算法的有效性。