基于負載感知和QoS的多中心作業調度算法

馮鳴夏，伍衛國，邸德海

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

0 引 言

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

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

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

1 基于排隊論的多計算中心服務性能分析

圖1 多中心作業服務示意圖

任務到達間距遵循參數為λ的泊松分布，任務的服務時間遵循參數為μ的負指數分布，這樣的假設是合理的，并且在許多研究文獻中都支持這種假設。

(1)

(2)

(3)

根據式1～3可得：

(4)

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

計算中心Ci的等待隊長為：

(5)

多計算中心排隊總長度為：

(6)

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

(7)

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

(8)

2 計算中心負載模型

2.1 計算節點負載模型

高性能計算節點的負載包括CPU的負載、內存使用率等。與此同時，節點溫度也是負載的重要指標。定義一個負載指數load_index衡量物理節點的綜合負載程度。

2.2 計算中心負載模型

對計算中心的負載進行劃分：

(1)輕載：當空閑節點比例超過α時，表示該計算中心處于輕載狀態。

(2)正常：當正常節點的比例超過β時，表示該計算中心處于正常狀態。

(3)過載：當過載節點的比例超多γ時，表示該計算中心處于過載狀態。

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

3 基于負載感知和QoS的作業調度算法

3.1 用戶的QoS目標約束

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

(1)計算價格(P)。

用戶將要執行的作業和數據上傳到計算中心，并提交作業到作業調度系統等待獲取可計算資源，計算中心會根據作業請求的計算核數以及作業的執行時間收取費用。計算中心的計算資源通常按照核每小時進行收費。

(2)排隊時間(Q)。

當用戶提交作業到計算中心的作業調度系統，如果當前計算中心的資源無法滿足作業提交時申請的資源時，作業會進入排隊狀態。當有空閑資源時，調度系統會重新調度作業，給作業分配資源。

(3)計算能力(C)。

不同的計算中心可能采用不同的硬件資源和不同的網絡拓撲。計算中心的計算能力存在差異。如果作業對計算能力有要求，用戶可能會選擇計算能力強的計算中心。

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

用戶使用計算中心資源時，首先需要將程序執行需要的運行數據上傳到計算中心的登錄節點。對于大輸入應用，生物計算領域，如BLAST[12]，計算數據主要由比對文件和比對數據庫兩部分組成。比對數據庫文件通常很大，用戶上傳需要很長的時間。

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

當用戶的程序執行結束后，用戶需要下載程序執行結果時，需要從計算中心的存儲節點下載到本地。對于大輸出應用，選擇分子動力學和工程學中用于產生運動軌跡的應用軟件。如Fluent[13]，隨著計算步數的增加輸出數據會明顯增加。

用戶根據作業的性質，對各個屬性進行打分。分數的范圍設置為0～10。當用戶對某一項評分為0時，表示不關心此QoS屬性。

3.2 計算中心QoS屬性向量

在一個計算中心Ci中，計算價格是由計算中心的管理人員制定的，在一段時間內不會發生改變；計算能力由硬件資源和網絡拓撲決定，在一段時間內不會發生改變；上行傳輸速度和下行傳輸速度由當前網絡環境決定，需要定時測量；影響排隊時間的因素主要由計算中心內排隊的隊長決定。

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

(9)

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

(10)

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

(11)

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

(12)

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

(13)

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

3.3 算法描述

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

算法：基于負載反饋和QoS約束的多中心作業調度算法

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

輸出：最優計算中心

1.for each hub in hubsList do

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

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);//計算作業和計算中心的親和度

9.if(Affinity

10.bestSelect=candidate;

11.tmpAffinity=Affinity;

12.end if

13.end for

14.return bestSelect

4 基于檢查點的多中心間作業遷移容錯策略

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

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

檢查點技術廣泛應用于程序運行中間狀態的保存和運行狀態的恢復。當前該技術并未應用在多中心作業遷移的容錯策略中。根據用戶設定的檢查點同步時間間隔，當檢查點同步時間到期時，主計算中心將當前作業檢查點數據同步到災備計算中心，檢查點的網絡傳輸和作業運行是并行的，并不會對作業產生多余的時間開銷。當災備計算中心在一定時間內沒有收到主計算中心的同步信號時，則災備計算中心根據作業檢查點信息重新提交用戶作業，當作業獲取調度器分配的資源時，作業從檢查點處恢復作業的執行。

4.1 多中心間作業遷移

在源計算中心，作業遷移發送模塊根據用戶作業提交的信息，設定作業檢查點遷移周期和災備計算中心。當檢查點遷移周期到期時，作業遷移發送模塊檢查作業的運行狀態，如果作業沒有運行結束，遷移模塊壓縮作業的檢查點文件并將其同步傳輸到目標計算中心。

在災備計算中心，作業遷移接收模塊定期會收到源計算中心的心跳信息和保存作業的檢查點文件，當遷移接收模塊在一段時間內沒有收到心跳信息，則認為源計算中心發生故障。遷移接收模塊將從檢查點處提交作業。

4.2 多中心系統的可用性分析

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

(14)

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

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

圖2 多中心作業遷移容錯示意圖

檢查點生成之后，源中心的遷移發送模塊需要將檢查點文件傳輸到災備計算中心，檢查點的傳輸和作業的運行是異步進行的，影響程序執行的主要因素是作業檢查點的開銷。由于一些作業生成的檢查點文件較大，需要在傳輸前進行壓縮處理。壓縮可以有效地減少傳輸帶來的開銷。

5 仿真實驗分析與比較

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

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

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

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

圖3 多計算中心服務性能比較

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

6 結束語

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