云計算中最小化任務完工時間的多資源調度算法

楊 鵬 靳 丹 張 晟 徐 鑫 姚建國

1(國網甘肅省電力公司信息通信公司 甘肅 蘭州 730050)2(上海交通大學 上海 200240)

?

云計算中最小化任務完工時間的多資源調度算法

楊 鵬1靳 丹1張 晟2徐 鑫2姚建國2

1(國網甘肅省電力公司信息通信公司 甘肅 蘭州 730050)2(上海交通大學 上海 200240)

云計算中Hadoop平臺上默認調度方式FIFO是以公平性為目標，然而考慮單一因素會使資源利用率低下以及任務完成時間過長。在公平性和完成時間的權衡中，運行時間指標更為重要。據此，建立云計算下多資源和應用程序任務以及調度的數學模型和其目標函數，運用歸約方法和具有強大計算能力的工具MINI SAT SOLVER去求解問題。仿真實驗結果表明，在不同的資源供給條件下，基于MINI SAT SOLVER的次優算法比YARN(Yet Another Resource Negotiator)中默認的調度算法FIFO縮短了任務的完工時間，優化比率最高可以達到30%。

云計算 調度算法 NP完全問題 完工時間

0 引 言

云計算是基于互聯網的一種新型服務模式，用戶通過支付一定的金額，便可獲取到高性能、高保障性、高擴展性的服務資源。這種資源主要包括軟件服務資源、平臺服務資源、基礎設施服務資源等。由于云計算具有易用性，隨時部署，相對于傳統經濟所提供的服務更為可靠的這些特征，越來越多的企業和個人選擇將工作流放在云端執行，通過云進行大量的科學計算以及存儲[1]。隨著云服務處理數據量的攀升以及用戶對于云服務質量的提升，云服務提供商的計算機資源變得相對欠缺，經發現，傳統云服務中資源利用率比較低，可以通過提高云服務中的資源調度效率的方式，緩解或解決云服務中計算機資源稀缺的問題。

當前的云計算多租戶多資源調度算法中存在許多問題。面對不同租戶所要求的服務質量不一致，和不同工作流對于計算資源需求的不一致，傳統的一些調度算法難以針對性地完成調度任務。當前，工業界著手探索Hadoop平臺上所推出的基于多資源的管理框架——YARN，提出以資源集合——容器為粒度的調度，提高多資源利用率和相關評價指標[2]。

在YARN中，默認采用先進先出FIFO的調度算法，是按照先進先出的優先隊列原則選擇執行的任務[3]。然而，這種調度算法只考慮到了公平性這樣的單一因素，會使資源利用率低，并且極大地增加了任務的完工時間。本文認為，在公平性和完成時間的權衡中，運行時間指標更為重要。據此，本文采用具有強大計算能力的工具和歸約方法，研究了在云平臺多資源調度框架下的完工時間優化問題和解決方法。

1 云計算多資源問題的數學建模

1.1 云計算資源的建模以及任務模型的建模

我們定義一個云平臺擁有n臺服務器，其中某個節點擁有的資源可以表達成一組向量：

rw=〈k1,k2,…,km〉w≤n

(1)

其中m為總資源的分類,ki(1≤i≤m)表示第m資源的總資源量，r表示云平臺所有服務器資源的集合。

定義每個application可以表達成一個如下的向量：

va=〈pa,sa〉

(2)

其中p是一個正整數，表達了這個application的優先級，越大表示其優先級越高，下標a表示屬于的那個application編號。

sa定義了編號為a的應用的任務集合taskSet，所有application的task集合表示為{task}，簡寫為s，每個task可以表達成：

(3)

taskSet中的task有嚴格的先后關系，定義在taskSet中的全序關系Before表示成：

(4)

1.2 云計算調度算法相關建模

定義task執行序映射集合：

(t,n)?task,t∈N}

(5)

定義task是否處于running狀態的函數為：

(6)

定義task在時間t是否完成：

(7)

定義調度函數集合:

task,t∈N}

(8)

1.3 目標函數的定義

我們定義指標效率為一個調度算法在時間t的效率：

(9)

(10)

定義指標資源利用率為一個調度算法在時間t的資源利用率：

(11)

定義指標公平性為各個任務的進度方差：

(12)

定義一個調度算法的工作時長：

makeSpan(h,r,{task})=min(t)

s.t.∧taskisDone(h,r,task,{task},t)=true?task

(13)

1.4 調度算法在目標函數下的性質

我們定義對于指標A(不包括工作時長)在時間t下的最優調度函數為：

(14)

不同的優化指標有一定聯系，但同時具有一定的獨立性。事實上，不可能存在一種調度算法使得它同時是指標效率最優且是指標資源利用率最優，考慮反證法：

假設存在算法，如果它是指標資源率最優，取0時刻，這時尋找往后第一個不屬于其應用，只有一個任務且資源需求小于等于此時調度任務的任務，并調高對應所屬應用的優先級使其大于當前調用應用程序的優先級，稱此調度算法為S1。顯然有在時刻0，算法S在資源利用率上優于算法S1的，算法S1在效率上優于算法S的。

這說明了不存在一種調度算法在任何情況下都是最優的，即不同的算法設計應該對應不同的目標函數。

下面，我們將考慮云計算多資源調度問題在不同的目標函數下的復雜度。

證明在指標效率下的調度問題的復雜度為NPC，即判斷時間t，指標效率能否大于等于e，此算法的復雜度為NPC。

先證明，它屬于NP問題，首先給定e所生成的ta,l，顯然驗證e是否屬于schedSet只要多項式時間(O(a×1×T)，我們認為t有最大上限T)，計算指標效率也只需要多項式時間，總體需要多項式時間。

證明在指標資源利用率下的調度問題的復雜度為NPC，即是判斷時間t，指標效率資源利用率大于等于M，此算法的復雜度為NPC。

NP證明與在指標效率下的證明類似，故略去。

事實上，取特定的時刻，云計算中多資源調度問題屬于多維多背包問題。考慮時間因素，不考慮背包容量時，云計算中多資源多調度問題屬于排序調度變種問題。兩者都是NP完全問題，且沒有fptas近似算法。

2 基于MINI SAT SOLVER的次優算法

2.1 MINI SAT SOLVER

作為NPC問題的始祖，SAT問題一直是算法研究當中的重點。近幾年來，對于SAT問題研究的一個重大突破，即是高效的SAT SOLVER的誕生。SAT SOLVER結合了高效的回溯算法，如DPLL(Davis-Putnam-Logemann-Loveland)這種算法經過40年的驗證依然證明了其高效性，被廣泛運用于一階邏輯以及自動證明的基礎[4]。還有一些啟發式原理，如選擇滿足子式最多的賦值，選擇短子式并對其進行賦值等。

實踐上，SAT SOLVER在解決幾百萬子式數量級的問題時依然有不俗的性能表現，幾乎能在1秒內得出結果[6]。基于此，我們假設，如果有一個問題能有效地轉化為SAT問題，那么它的性能會有相對的保證。本文將在后文實驗中，會試圖對SAT SOLVER做一些性能測試來驗證其可接受輸入規模的范圍。

MINI SAT SOLVER作為SAT SOLVER的一種，具有開源，易于修改，輕巧等特點，它曾獲得三界工業界的獎杯，也獲得過2005年SAT COMPETTION的嘉獎。由于SAT SOLVER的高效性、準確性，本文決定采用MINI SAT SOLVER作為處理問題的工具方法。

2.2 典型問題描述

相比于YARN中默認的調度算法所考慮的公平性因素，我們認為最短工作時長指標更為重要，無論是以任務吞吐率，還是以資源利用率來說，都和它們有著千絲萬縷的聯系。最短工作時長的典型問題，面對同一任務集合，每個任務獨立需要占有相應的資源(App1先后需要單位時間的CPU，兩單位時間的Network和單位時間的IO資源，App2需要單位時間的Network，IO資源和CPU資源，App3需要單位時間的CPU，單位時間的IO和單位時間的Network資源)，那么存在兩種可行的調度方式，如表1和表2所示。但是其最大的不同是時間，顯然在指標工作時長最優的情況下，應該選擇總時長最短的調度方式，也就是第一種。我們要完成的算法，應要正確地得出時長最短的調度策略。

表1 同一任務集的第一種調度方法

表2 同一任務集的第二種調度方法

2.3 次優算法的描述

本文運用SAT SOLVER解決以最短時長為目標函數的云計算多資源環境下的調度問題可以分成兩個步驟，一是分配，二是約束。

分配步驟的原因是在于：為了適配于MINI SAT SOLVER，我們需要把同種資源但具有不同資源量的資源分解成不可分割的最小單位資源。但由于同種資源具有同質性，需要多個單位資源的任務的分配可能性過大，為(m×max(ki))Cmax(ki)。列舉其所有可能幾乎是不現實的做法，所以本文決定采用Late調度算法[7]的核心觀點：平均每個資源的工作時間。

分配步驟的具體算法描述為：

(1) 構造資源需要時間數組T[n][m][max(ki)]=0；

這樣就構成了初始分配，我們把各個任務所需的資源映射到各個不同的單位資源上。本質上，是按所需時間從小到大排列一遍，用來使各資源的利用時間差不多相同。

接下來，我們將使用約束算法。約束算法的主要思路是在指標工作時長的情況下，把云計算多資源調度問題歸約到SAT問題，用SAT問題解決調度任務的先后關系，我們將分配后的結果轉化成MIN SAT SOLVER的輸入。

約束算法：

定義A[r,t,s]表達是否在時間t把單位資源r分配給任務s。

定義應用程序任務流約束：

(15)

式(15)表示：如果應用程序的某一個任務所需求的資源被分配(即該任務被調度)，至少存在某一時刻，它的前驅任務所需求的所有資源被分配。

定義資源不可同時分配約束：

(16)

式(16)表示：如果應用程序的某一個任務所需的資源在時間t被分配，那么同時間，所有需要相同單位資源的任務都不被分配資源。

定義應用程序都完成約束:

(17)

式(17)表示：每個應用程序的最后一個任務所需的資源至少會在某個時間內分配。TIME是最長運行時長。

定義任務不可中斷約束:

(18)

式(18)表示：如果任務在時刻被分配所需資源，且此任務的時長不為零，則資源將一直配給此任務直至結束。

所以我們的總體算法為：

(1) 對所有任務所需求的資源進行分配；

(2) 設定TIME；

(3) 運行約束算法，生成MINI SAT SOLVER的輸入；

(4) 運行MINI SAT SOLVER，如果存在滿足的賦值且TIME符合要求，則返回各任務的調度時間，否則二分查找辦法調整TIME跳至(3)。

這樣，我們尋找到一種調度策略使工作時長盡可能短。

2.4 次優算法的算法復雜度

次優算法的分配算法的復雜度為O(N∪M(task)×|r|×log(|r|))。因為對于每一個任務需要對每個單位資源工作時間進行排序。約束算法的復雜度為(O((N∪M(task)2×T×|r|)2))。因為，為了對每個分配結果產生約束，最多需要遍歷整個分配空間。

2.5 次優算法的創新性分析

本文設計的基于MINI SAT SOLVER的次優算法的創新點體現在于：

1) 調度問題與SAT求解器的結合。相比于現在比較普遍的復雜調度問題的求解方法如整數規劃求解器(lpsolve、GLPK、yalmip等)，本文所使用的求解方法更加基礎，在理論上研究得相對透徹。整數規劃是比SAT可能要更難的問題，從而在求解專用性方面不如SAT求解器。同時在解的收斂性方面會存在不確定性，而SAT問題在定解方面會優于整數規劃問題。本文為了與SAT問題進行適配，創新地將問題劃分為分配和約束兩個步驟，對調度問題進行了規約，比較好地利用了SAT求解器的高效性，和其定解方面的優越性。

2) 調度所涉及的模型普適性更強。本文模型囊括了多運算節點多資源有依賴的任務模型，相比于傳統的單資源單運算節點有任務依賴的模型，如各種截止日期算法所針對的運算環境，和現在所研究的多運算節點多資源無任務依賴的模型，如map reduce框架下的LATE算法等。本文模型的適用面更加接近于真實環境，所研究的問題也更加復雜。所以本文創新性地做了嘗試，同時解決單運算節點下多資源的約束問題、多運算節點下任務的分配問題、多任務情況下依賴調度問題。

3 實驗結果與分析

3.1 測試平臺及數據說明

對于基于MINI SAT SOLVER的算法測試主要是分為三大部分：1) 算法正確性測試；2) 算法優化效率部分；3) 算法的本身的運行時間測試部分。

該算法的測試主要是運用一定量的隨機數據進行模擬測試，通過隨機數據來突出算法在各種可能的情況下的表現。本次測試實驗要模擬的數據為：

(1) 云計算多資源環境中各資源量的大小。

(2) 云計算多資源環境中所要調度的應用程序的數量。

(3) 應用程序所含任務數的大小。

(4) 各個任務本身所需要的不同資源的資源量和需要它們的時間。

本測試著重于在不同的情形中，如資源相對寬松、稀缺等，進行了評估與分析，將采用YARN默認的調度算法FIFO進行了對比，論證了其在指標工作時長下的優越性。

本測試模擬平臺為單機模擬平臺，主要是方便測試算法的性能。

3.2 次優算法的正確性驗證

本文所選取的算法正確性驗證主要方法是采取黑盒測試，輸入一些指定的情況，驗證其輸出的正確性，具體針對歸約算法里的約束算法正確性進行驗證。

本文具體測試了以下的用例：

(1) 在單獨一個應用程序的情況下，其中的任務，會按照任務的先后關系分配資源，即滿足應用程序任務流約束。

(2) 在單獨一個應用程序的情況下，其中的任務，對于所需求資源的時間不同，調度算法給出的分配答案，滿足了其分配資源的時長性和時間連續性。

(3) 在兩個應用程序的條件下，其中的任務，都在某一時刻前完成了，反映了調度算法滿足應用程序都完成的約束。

(4) 在兩個應用程序的條件下，其中的任務所需求的資源，不會在同一時刻重復分配，即滿足了資源不可同時分配約束。

(5) 測試了多組、多應用程序、多任務，資源需求不同、時長也不同的用例分配結果，驗證了它們同時滿足所有的約束。

以上的測試用例說明了基于MINI SAT SOLVER調度算法的正確性。

3.3 次優算法的實驗效果

本文選取的第一個測試用例為，云計算資源相對寬松的、各任務差異較小的情況。我們設定云包含多個資源，各資源量設定為100，應用程序數量設定為10，應用程序的任務數大小隨機分布于1至3之間。任務所需要的各資源的最大資源是云平臺所擁有資源的十分之一，最長任務的時長和最短任務的時長相差四倍。我們取最短任務時長為單位時長。

我們取了三組隨機數進行測試，我們的調度算法是以指標工作時長為目標函數的，完成時間越短，表示性能越好。從在資源寬松的情況下的調度結果(圖1)中，我們可以發現，基于MINI SAT SOLVER的調度函數優于YARN所默認的調度算法FIFO算法，平均優化的比率達到了11%左右，即完成所有任務的時間快了11%。我們認為速度上的提升是由于：1) 我們使每一個資源的平均利用時間大致相等；2) MINI SAT SOVLER求解能力的優越性。

圖1 資源寬松環境下基于MINI SAT SOLVER算法對比

本文選取的第二個測試為資源較為稀缺，不同任務差異較大的情況，應用程序數量設為30，應用程序的任務數大小隨機分布于1至5之間。任務所需要的各資源的最大資源是云平臺所擁有資源的三分之一，最長任務的時長和最短任務時長相差9倍。同樣地，我們取最短任務時長為單位時長。

從圖2的數據中，我們可以發現，基于MINI SAT SOLVER的次優算法遠遠優于YARN默認的調度算法。優化比率最高可以達到30%，如此高的優化比率得益于平均化的資源任務分配和MINI SAT SOLVER的計算能力，特別是在調度時，不同時刻對于任務時長和任務資源需求量之間選擇的正確性。

圖2 資源稀缺環境下基于MINI SAT SOLVER算法對比

3.4 基于MINI SAT SOLVER次優算法的運行時間

由于SAT SOLVER的技術有進一步拓展的空間，NPC難題在理論上并不能在多項式時間內解決。所以我們有必要對于SAT SOLVER的運行時間做出測試，以便確定最合理的問題規模大小。

我們認為問題規模正比于最大資源量，總任務數量的平方，以及最大任務時長的乘積。

從圖3中可以看出，隨著問題規模的增大，運行時間緩慢地遠離線性，偏向于指數級。在我們可以接受的運行時間范圍內，最好的問題規模就是介于資源寬松和資源稀缺環境下的假設規模。

圖3 MINI SAT SOLVER運行時間與問題規模的關系

4 結 語

在云計算現有的框架中，運行的應用程序包含多個任務，各個任務對資源的需求不同，并且占用資源的時間也不同。本文首先設計了云計算下資源、應用程序任務以及調度的數學模型，并對該調度模型建立了以最小化完工時間為目標的目標函數。為了對該模型進行求解，本文設計了基于MINI SAT SOLVER的次優算法，該算法有兩部分組成，第一部分是分配，第二部分約束。分配部分使同質資源平均工作時長相等，約束部分通過設定調度所要滿足的條件生成SAT表達式，通過求解滿足表達式的最小時間變量，解決調度問題。通過模擬仿真和實驗驗證，在云計算資源相對寬松或稀缺的環境下，在其任務完工時間上，基于MINI SAT SOLVER的次優算法優于YARN的默認調度算法FIFO，最大的優化比率可以達到30%。

[1] Buyya R,Yeo C S,Venugopal S.Market-Oriented Cloud Computing:Vision,Hype,and Reality for Delivering IT Services as Computing Utilities[C]//IEEE International Conference on High PERFORMANCE Computing and Communications.IEEE,2008:5-13.

[2] White T.Hadoop:The Definitive Guide[M].O’Reilly Media,Inc.,2012.

[3] Kc K,Anyanwu K.Scheduling hadoop jobs to meet deadlines[C]//Cloud Computing Technology and Science (CloudCom),2010 IEEE Second International Conference on.IEEE,2010:388-392.

[4] Nieuwenhuis R,Oliveras A,Tinelli C.Solving SAT and SAT Modulo Theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL (T)[J].Journal of the ACM (JACM),2006,53(6):937-977.

[5] Davis M,Putnam H.A computing procedure for quantification theory[J].Journal of the ACM (JACM),1960,7(3):201-215.

[6] Goldberg E,Novikov Y.BerkMin:A fast and robust SAT-solver[J].Discrete Applied Mathematics,2007,155(12):1549-1561.

[7] Zaharia M,Konwinski A,Joseph A,et al.Improving MapReduce Performance in Heterogeneous Environments[C]//OSDI’08 Proceedings of the 8th USENIX conference on Operating systems design and implementation. San Diego,California—December 08-10,2008:29-42.

A MULTI-RESOURCE SCHEDULING ALGORITHM FOR MINIMIZING MAKESPAN IN CLOUD COMPUTING

Yang Peng1Jin Dan1Zhang Sheng2Xu Xin2Yao Jianguo2

1(InformationandCommunicationCompany,StateGridGansuElectricPowerCompany,Lanzhou730050,Gansu,China)2(ShanghaiJiaoTongUniversity,Shanghai200240,China)

The default FIFO scheduling on the Hadoop platform in cloud computing is targeted at fairness, however, considering a single factor will make the resource utilization is low and the task is completed too long. The makespan is more important in trade-off between fairness and makespan. On this basis, we established the multi-resource and application tasks and the scheduling mathematical model and its objective function under cloud computing, and we used the reduction method and MINI SAT SOLVER with powerful computing ability to solve the problem. The simulation results show that the suboptimal algorithm based on MINI SAT SOLVER is shorter than the default scheduling algorithm FIFO in YARN under different resource supply conditions, and the optimization ratio can reach 30%.

Cloud computing Scheduling algorithm NP-Complete problem Makespan

2016-10-21。國家自然科學基金項目(61303013)。楊鵬，高工，主研領域：協議分析。靳丹，教授級高工。張晟，碩士生。徐鑫，碩士生。姚建國，副教授。

TP3

A

10.3969/j.issn.1000-386x.2017.07.001