楊 鵬 靳 丹 張 晟 徐 鑫 姚建國

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

?

云計(jì)算中最小化任務(wù)完工時(shí)間的多資源調(diào)度算法

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

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

云計(jì)算中Hadoop平臺(tái)上默認(rèn)調(diào)度方式FIFO是以公平性為目標(biāo)，然而考慮單一因素會(huì)使資源利用率低下以及任務(wù)完成時(shí)間過長(zhǎng)。在公平性和完成時(shí)間的權(quán)衡中，運(yùn)行時(shí)間指標(biāo)更為重要。據(jù)此，建立云計(jì)算下多資源和應(yīng)用程序任務(wù)以及調(diào)度的數(shù)學(xué)模型和其目標(biāo)函數(shù)，運(yùn)用歸約方法和具有強(qiáng)大計(jì)算能力的工具M(jìn)INI SAT SOLVER去求解問題。仿真實(shí)驗(yàn)結(jié)果表明，在不同的資源供給條件下，基于MINI SAT SOLVER的次優(yōu)算法比YARN(Yet Another Resource Negotiator)中默認(rèn)的調(diào)度算法FIFO縮短了任務(wù)的完工時(shí)間，優(yōu)化比率最高可以達(dá)到30%。

云計(jì)算 調(diào)度算法 NP完全問題 完工時(shí)間

0 引 言

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

當(dāng)前的云計(jì)算多租戶多資源調(diào)度算法中存在許多問題。面對(duì)不同租戶所要求的服務(wù)質(zhì)量不一致，和不同工作流對(duì)于計(jì)算資源需求的不一致，傳統(tǒng)的一些調(diào)度算法難以針對(duì)性地完成調(diào)度任務(wù)。當(dāng)前，工業(yè)界著手探索Hadoop平臺(tái)上所推出的基于多資源的管理框架——YARN，提出以資源集合——容器為粒度的調(diào)度，提高多資源利用率和相關(guān)評(píng)價(jià)指標(biāo)[2]。

在YARN中，默認(rèn)采用先進(jìn)先出FIFO的調(diào)度算法，是按照先進(jìn)先出的優(yōu)先隊(duì)列原則選擇執(zhí)行的任務(wù)[3]。然而，這種調(diào)度算法只考慮到了公平性這樣的單一因素，會(huì)使資源利用率低，并且極大地增加了任務(wù)的完工時(shí)間。本文認(rèn)為，在公平性和完成時(shí)間的權(quán)衡中，運(yùn)行時(shí)間指標(biāo)更為重要。據(jù)此，本文采用具有強(qiáng)大計(jì)算能力的工具和歸約方法，研究了在云平臺(tái)多資源調(diào)度框架下的完工時(shí)間優(yōu)化問題和解決方法。

1 云計(jì)算多資源問題的數(shù)學(xué)建模

1.1 云計(jì)算資源的建模以及任務(wù)模型的建模

我們定義一個(gè)云平臺(tái)擁有n臺(tái)服務(wù)器，其中某個(gè)節(jié)點(diǎn)擁有的資源可以表達(dá)成一組向量：

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

(1)

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

定義每個(gè)application可以表達(dá)成一個(gè)如下的向量：

va=〈pa,sa〉

(2)

其中p是一個(gè)正整數(shù)，表達(dá)了這個(gè)application的優(yōu)先級(jí)，越大表示其優(yōu)先級(jí)越高，下標(biāo)a表示屬于的那個(gè)application編號(hào)。

sa定義了編號(hào)為a的應(yīng)用的任務(wù)集合taskSet，所有application的task集合表示為{task}，簡(jiǎn)寫為s，每個(gè)task可以表達(dá)成：

(3)

taskSet中的task有嚴(yán)格的先后關(guān)系，定義在taskSet中的全序關(guān)系Before表示成：

(4)

1.2 云計(jì)算調(diào)度算法相關(guān)建模

定義task執(zhí)行序映射集合：

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

(5)

定義task是否處于running狀態(tài)的函數(shù)為：

(6)

定義task在時(shí)間t是否完成：

(7)

定義調(diào)度函數(shù)集合:

task,t∈N}

(8)

1.3 目標(biāo)函數(shù)的定義

我們定義指標(biāo)效率為一個(gè)調(diào)度算法在時(shí)間t的效率：

(9)

(10)

定義指標(biāo)資源利用率為一個(gè)調(diào)度算法在時(shí)間t的資源利用率：

(11)

定義指標(biāo)公平性為各個(gè)任務(wù)的進(jìn)度方差：

(12)

定義一個(gè)調(diào)度算法的工作時(shí)長(zhǎng)：

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

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

(13)

1.4 調(diào)度算法在目標(biāo)函數(shù)下的性質(zhì)

我們定義對(duì)于指標(biāo)A(不包括工作時(shí)長(zhǎng))在時(shí)間t下的最優(yōu)調(diào)度函數(shù)為：

(14)

不同的優(yōu)化指標(biāo)有一定聯(lián)系，但同時(shí)具有一定的獨(dú)立性。事實(shí)上，不可能存在一種調(diào)度算法使得它同時(shí)是指標(biāo)效率最優(yōu)且是指標(biāo)資源利用率最優(yōu)，考慮反證法：

假設(shè)存在算法，如果它是指標(biāo)資源率最優(yōu)，取0時(shí)刻，這時(shí)尋找往后第一個(gè)不屬于其應(yīng)用，只有一個(gè)任務(wù)且資源需求小于等于此時(shí)調(diào)度任務(wù)的任務(wù)，并調(diào)高對(duì)應(yīng)所屬應(yīng)用的優(yōu)先級(jí)使其大于當(dāng)前調(diào)用應(yīng)用程序的優(yōu)先級(jí)，稱此調(diào)度算法為S1。顯然有在時(shí)刻0，算法S在資源利用率上優(yōu)于算法S1的，算法S1在效率上優(yōu)于算法S的。

這說明了不存在一種調(diào)度算法在任何情況下都是最優(yōu)的，即不同的算法設(shè)計(jì)應(yīng)該對(duì)應(yīng)不同的目標(biāo)函數(shù)。

下面，我們將考慮云計(jì)算多資源調(diào)度問題在不同的目標(biāo)函數(shù)下的復(fù)雜度。

證明在指標(biāo)效率下的調(diào)度問題的復(fù)雜度為NPC，即判斷時(shí)間t，指標(biāo)效率能否大于等于e，此算法的復(fù)雜度為NPC。

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

證明在指標(biāo)資源利用率下的調(diào)度問題的復(fù)雜度為NPC，即是判斷時(shí)間t，指標(biāo)效率資源利用率大于等于M，此算法的復(fù)雜度為NPC。

NP證明與在指標(biāo)效率下的證明類似，故略去。

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

2 基于MINI SAT SOLVER的次優(yōu)算法

2.1 MINI SAT SOLVER

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

實(shí)踐上，SAT SOLVER在解決幾百萬子式數(shù)量級(jí)的問題時(shí)依然有不俗的性能表現(xiàn)，幾乎能在1秒內(nèi)得出結(jié)果[6]?；诖?，我們假設(shè)，如果有一個(gè)問題能有效地轉(zhuǎn)化為SAT問題，那么它的性能會(huì)有相對(duì)的保證。本文將在后文實(shí)驗(yàn)中，會(huì)試圖對(duì)SAT SOLVER做一些性能測(cè)試來驗(yàn)證其可接受輸入規(guī)模的范圍。

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

2.2 典型問題描述

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

表1 同一任務(wù)集的第一種調(diào)度方法

表2 同一任務(wù)集的第二種調(diào)度方法

2.3 次優(yōu)算法的描述

本文運(yùn)用SAT SOLVER解決以最短時(shí)長(zhǎng)為目標(biāo)函數(shù)的云計(jì)算多資源環(huán)境下的調(diào)度問題可以分成兩個(gè)步驟，一是分配，二是約束。

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

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

(1) 構(gòu)造資源需要時(shí)間數(shù)組T[n][m][max(ki)]=0；

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

接下來，我們將使用約束算法。約束算法的主要思路是在指標(biāo)工作時(shí)長(zhǎng)的情況下，把云計(jì)算多資源調(diào)度問題歸約到SAT問題，用SAT問題解決調(diào)度任務(wù)的先后關(guān)系，我們將分配后的結(jié)果轉(zhuǎn)化成MIN SAT SOLVER的輸入。

約束算法：

定義A[r,t,s]表達(dá)是否在時(shí)間t把單位資源r分配給任務(wù)s。

定義應(yīng)用程序任務(wù)流約束：

(15)

式(15)表示：如果應(yīng)用程序的某一個(gè)任務(wù)所需求的資源被分配(即該任務(wù)被調(diào)度)，至少存在某一時(shí)刻，它的前驅(qū)任務(wù)所需求的所有資源被分配。

定義資源不可同時(shí)分配約束：

(16)

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

定義應(yīng)用程序都完成約束:

(17)

式(17)表示：每個(gè)應(yīng)用程序的最后一個(gè)任務(wù)所需的資源至少會(huì)在某個(gè)時(shí)間內(nèi)分配。TIME是最長(zhǎng)運(yùn)行時(shí)長(zhǎng)。

定義任務(wù)不可中斷約束:

(18)

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

所以我們的總體算法為：

(1) 對(duì)所有任務(wù)所需求的資源進(jìn)行分配；

(2) 設(shè)定TIME；

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

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

這樣，我們尋找到一種調(diào)度策略使工作時(shí)長(zhǎng)盡可能短。

2.4 次優(yōu)算法的算法復(fù)雜度

次優(yōu)算法的分配算法的復(fù)雜度為O(N∪M(task)×|r|×log(|r|))。因?yàn)閷?duì)于每一個(gè)任務(wù)需要對(duì)每個(gè)單位資源工作時(shí)間進(jìn)行排序。約束算法的復(fù)雜度為(O((N∪M(task)2×T×|r|)2))。因?yàn)?，為了?duì)每個(gè)分配結(jié)果產(chǎn)生約束，最多需要遍歷整個(gè)分配空間。

2.5 次優(yōu)算法的創(chuàng)新性分析

本文設(shè)計(jì)的基于MINI SAT SOLVER的次優(yōu)算法的創(chuàng)新點(diǎn)體現(xiàn)在于：

1) 調(diào)度問題與SAT求解器的結(jié)合。相比于現(xiàn)在比較普遍的復(fù)雜調(diào)度問題的求解方法如整數(shù)規(guī)劃求解器(lpsolve、GLPK、yalmip等)，本文所使用的求解方法更加基礎(chǔ)，在理論上研究得相對(duì)透徹。整數(shù)規(guī)劃是比SAT可能要更難的問題，從而在求解專用性方面不如SAT求解器。同時(shí)在解的收斂性方面會(huì)存在不確定性，而SAT問題在定解方面會(huì)優(yōu)于整數(shù)規(guī)劃問題。本文為了與SAT問題進(jìn)行適配，創(chuàng)新地將問題劃分為分配和約束兩個(gè)步驟，對(duì)調(diào)度問題進(jìn)行了規(guī)約，比較好地利用了SAT求解器的高效性，和其定解方面的優(yōu)越性。

2) 調(diào)度所涉及的模型普適性更強(qiáng)。本文模型囊括了多運(yùn)算節(jié)點(diǎn)多資源有依賴的任務(wù)模型，相比于傳統(tǒng)的單資源單運(yùn)算節(jié)點(diǎn)有任務(wù)依賴的模型，如各種截止日期算法所針對(duì)的運(yùn)算環(huán)境，和現(xiàn)在所研究的多運(yùn)算節(jié)點(diǎn)多資源無任務(wù)依賴的模型，如map reduce框架下的LATE算法等。本文模型的適用面更加接近于真實(shí)環(huán)境，所研究的問題也更加復(fù)雜。所以本文創(chuàng)新性地做了嘗試，同時(shí)解決單運(yùn)算節(jié)點(diǎn)下多資源的約束問題、多運(yùn)算節(jié)點(diǎn)下任務(wù)的分配問題、多任務(wù)情況下依賴調(diào)度問題。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 測(cè)試平臺(tái)及數(shù)據(jù)說明

對(duì)于基于MINI SAT SOLVER的算法測(cè)試主要是分為三大部分：1) 算法正確性測(cè)試；2) 算法優(yōu)化效率部分；3) 算法的本身的運(yùn)行時(shí)間測(cè)試部分。

該算法的測(cè)試主要是運(yùn)用一定量的隨機(jī)數(shù)據(jù)進(jìn)行模擬測(cè)試，通過隨機(jī)數(shù)據(jù)來突出算法在各種可能的情況下的表現(xiàn)。本次測(cè)試實(shí)驗(yàn)要模擬的數(shù)據(jù)為：

(1) 云計(jì)算多資源環(huán)境中各資源量的大小。

(2) 云計(jì)算多資源環(huán)境中所要調(diào)度的應(yīng)用程序的數(shù)量。

(3) 應(yīng)用程序所含任務(wù)數(shù)的大小。

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

本測(cè)試著重于在不同的情形中，如資源相對(duì)寬松、稀缺等，進(jìn)行了評(píng)估與分析，將采用YARN默認(rèn)的調(diào)度算法FIFO進(jìn)行了對(duì)比，論證了其在指標(biāo)工作時(shí)長(zhǎng)下的優(yōu)越性。

本測(cè)試模擬平臺(tái)為單機(jī)模擬平臺(tái)，主要是方便測(cè)試算法的性能。

3.2 次優(yōu)算法的正確性驗(yàn)證

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

本文具體測(cè)試了以下的用例：

(1) 在單獨(dú)一個(gè)應(yīng)用程序的情況下，其中的任務(wù)，會(huì)按照任務(wù)的先后關(guān)系分配資源，即滿足應(yīng)用程序任務(wù)流約束。

(2) 在單獨(dú)一個(gè)應(yīng)用程序的情況下，其中的任務(wù)，對(duì)于所需求資源的時(shí)間不同，調(diào)度算法給出的分配答案，滿足了其分配資源的時(shí)長(zhǎng)性和時(shí)間連續(xù)性。

(3) 在兩個(gè)應(yīng)用程序的條件下，其中的任務(wù)，都在某一時(shí)刻前完成了，反映了調(diào)度算法滿足應(yīng)用程序都完成的約束。

(4) 在兩個(gè)應(yīng)用程序的條件下，其中的任務(wù)所需求的資源，不會(huì)在同一時(shí)刻重復(fù)分配，即滿足了資源不可同時(shí)分配約束。

(5) 測(cè)試了多組、多應(yīng)用程序、多任務(wù)，資源需求不同、時(shí)長(zhǎng)也不同的用例分配結(jié)果，驗(yàn)證了它們同時(shí)滿足所有的約束。

以上的測(cè)試用例說明了基于MINI SAT SOLVER調(diào)度算法的正確性。

3.3 次優(yōu)算法的實(shí)驗(yàn)效果

本文選取的第一個(gè)測(cè)試用例為，云計(jì)算資源相對(duì)寬松的、各任務(wù)差異較小的情況。我們?cè)O(shè)定云包含多個(gè)資源，各資源量設(shè)定為100，應(yīng)用程序數(shù)量設(shè)定為10，應(yīng)用程序的任務(wù)數(shù)大小隨機(jī)分布于1至3之間。任務(wù)所需要的各資源的最大資源是云平臺(tái)所擁有資源的十分之一，最長(zhǎng)任務(wù)的時(shí)長(zhǎng)和最短任務(wù)的時(shí)長(zhǎng)相差四倍。我們?nèi)∽疃倘蝿?wù)時(shí)長(zhǎng)為單位時(shí)長(zhǎng)。

我們?nèi)×巳M隨機(jī)數(shù)進(jìn)行測(cè)試，我們的調(diào)度算法是以指標(biāo)工作時(shí)長(zhǎng)為目標(biāo)函數(shù)的，完成時(shí)間越短，表示性能越好。從在資源寬松的情況下的調(diào)度結(jié)果(圖1)中，我們可以發(fā)現(xiàn)，基于MINI SAT SOLVER的調(diào)度函數(shù)優(yōu)于YARN所默認(rèn)的調(diào)度算法FIFO算法，平均優(yōu)化的比率達(dá)到了11%左右，即完成所有任務(wù)的時(shí)間快了11%。我們認(rèn)為速度上的提升是由于：1) 我們使每一個(gè)資源的平均利用時(shí)間大致相等；2) MINI SAT SOVLER求解能力的優(yōu)越性。

圖1 資源寬松環(huán)境下基于MINI SAT SOLVER算法對(duì)比

本文選取的第二個(gè)測(cè)試為資源較為稀缺，不同任務(wù)差異較大的情況，應(yīng)用程序數(shù)量設(shè)為30，應(yīng)用程序的任務(wù)數(shù)大小隨機(jī)分布于1至5之間。任務(wù)所需要的各資源的最大資源是云平臺(tái)所擁有資源的三分之一，最長(zhǎng)任務(wù)的時(shí)長(zhǎng)和最短任務(wù)時(shí)長(zhǎng)相差9倍。同樣地，我們?nèi)∽疃倘蝿?wù)時(shí)長(zhǎng)為單位時(shí)長(zhǎng)。

從圖2的數(shù)據(jù)中，我們可以發(fā)現(xiàn)，基于MINI SAT SOLVER的次優(yōu)算法遠(yuǎn)遠(yuǎn)優(yōu)于YARN默認(rèn)的調(diào)度算法。優(yōu)化比率最高可以達(dá)到30%，如此高的優(yōu)化比率得益于平均化的資源任務(wù)分配和MINI SAT SOLVER的計(jì)算能力，特別是在調(diào)度時(shí)，不同時(shí)刻對(duì)于任務(wù)時(shí)長(zhǎng)和任務(wù)資源需求量之間選擇的正確性。

圖2 資源稀缺環(huán)境下基于MINI SAT SOLVER算法對(duì)比

3.4 基于MINI SAT SOLVER次優(yōu)算法的運(yùn)行時(shí)間

由于SAT SOLVER的技術(shù)有進(jìn)一步拓展的空間，NPC難題在理論上并不能在多項(xiàng)式時(shí)間內(nèi)解決。所以我們有必要對(duì)于SAT SOLVER的運(yùn)行時(shí)間做出測(cè)試，以便確定最合理的問題規(guī)模大小。

我們認(rèn)為問題規(guī)模正比于最大資源量，總?cè)蝿?wù)數(shù)量的平方，以及最大任務(wù)時(shí)長(zhǎng)的乘積。

從圖3中可以看出，隨著問題規(guī)模的增大，運(yùn)行時(shí)間緩慢地遠(yuǎn)離線性，偏向于指數(shù)級(jí)。在我們可以接受的運(yùn)行時(shí)間范圍內(nèi)，最好的問題規(guī)模就是介于資源寬松和資源稀缺環(huán)境下的假設(shè)規(guī)模。

圖3 MINI SAT SOLVER運(yùn)行時(shí)間與問題規(guī)模的關(guān)系

4 結(jié) 語

在云計(jì)算現(xiàn)有的框架中，運(yùn)行的應(yīng)用程序包含多個(gè)任務(wù)，各個(gè)任務(wù)對(duì)資源的需求不同，并且占用資源的時(shí)間也不同。本文首先設(shè)計(jì)了云計(jì)算下資源、應(yīng)用程序任務(wù)以及調(diào)度的數(shù)學(xué)模型，并對(duì)該調(diào)度模型建立了以最小化完工時(shí)間為目標(biāo)的目標(biāo)函數(shù)。為了對(duì)該模型進(jìn)行求解，本文設(shè)計(jì)了基于MINI SAT SOLVER的次優(yōu)算法，該算法有兩部分組成，第一部分是分配，第二部分約束。分配部分使同質(zhì)資源平均工作時(shí)長(zhǎng)相等，約束部分通過設(shè)定調(diào)度所要滿足的條件生成SAT表達(dá)式，通過求解滿足表達(dá)式的最小時(shí)間變量，解決調(diào)度問題。通過模擬仿真和實(shí)驗(yàn)驗(yàn)證，在云計(jì)算資源相對(duì)寬松或稀缺的環(huán)境下，在其任務(wù)完工時(shí)間上，基于MINI SAT SOLVER的次優(yōu)算法優(yōu)于YARN的默認(rèn)調(diào)度算法FIFO，最大的優(yōu)化比率可以達(dá)到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。國家自然科學(xué)基金項(xiàng)目(61303013)。楊鵬，高工，主研領(lǐng)域：協(xié)議分析。靳丹，教授級(jí)高工。張晟，碩士生。徐鑫，碩士生。姚建國，副教授。

TP3

A

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