基于改進(jìn)差分進(jìn)化算法的云計(jì)算任務(wù)調(diào)度策略*

林 濤, 王 昊, 李 鵬

(河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院,天津 300130)

0 引 言

云計(jì)算是一種基于分布式計(jì)算、并行計(jì)算和網(wǎng)格計(jì)算的新型的商業(yè)計(jì)算模式[1]。云計(jì)算采用服務(wù)的方式為用戶提供動態(tài)虛擬化資源池[2],可以將用戶提交的任務(wù)分配給分布式計(jì)算機(jī)資源池進(jìn)行合理調(diào)度。由于資源是有限的,因此云計(jì)算系統(tǒng)服務(wù)是有償?shù)腫3,4],在海量數(shù)據(jù)面前,云計(jì)算任務(wù)的調(diào)度成為影響云計(jì)算系統(tǒng)性能的關(guān)鍵因素,也決定了完成用戶任務(wù)的成本,因此,如何充分利用云中資源對任務(wù)進(jìn)行高效調(diào)度是云計(jì)算中的重點(diǎn)和難點(diǎn)。

近幾年,一些人工智能算法已經(jīng)被廣泛的應(yīng)用到任務(wù)調(diào)度問題中。文獻(xiàn)[5]提出了一種完全多項(xiàng)式的在線算法,并采用整數(shù)規(guī)劃方式減少應(yīng)用程序延遲,優(yōu)化云計(jì)算任務(wù)的卸載和調(diào)度策略,從而最大化節(jié)約資源。文獻(xiàn)[6]將網(wǎng)絡(luò)存儲感知和貪心算法相結(jié)合,提出了一種貪心改進(jìn)算法,大幅減少了數(shù)據(jù)在數(shù)據(jù)鏈路層所消耗的時(shí)間。文獻(xiàn)[7]提出了一種多目標(biāo)調(diào)度方案,即MOCS,實(shí)現(xiàn)了云計(jì)算環(huán)境下的低功耗和調(diào)度效率的優(yōu)化。文獻(xiàn)[8]針對資源虛擬化環(huán)境中的混合型負(fù)載調(diào)度問題,采用“最小能耗比例優(yōu)先”的策略進(jìn)行調(diào)度,在“調(diào)度偏差”和“相對能效”兩方面優(yōu)勢明顯。但這些方法在處理海量任務(wù)調(diào)度方面的效果均不夠理想,且考慮影響因素過于單一。

本文通過分析云計(jì)算任務(wù)資源分配問題,綜合考慮任務(wù)完成時(shí)間和執(zhí)行能耗等因素,采用改進(jìn)的差分進(jìn)化算法制定合適的任務(wù)調(diào)度機(jī)制,以期快速而高效地為虛擬機(jī)資源盡可能地均衡分配任務(wù)。仿真實(shí)驗(yàn)的結(jié)果表明,本文提出的基于改進(jìn)差分進(jìn)化算法的云計(jì)算任務(wù)調(diào)度算法有效減少了云計(jì)算任務(wù)的完成時(shí)間,并大幅降低了任務(wù)的執(zhí)行能耗。

1 云計(jì)算獨(dú)立任務(wù)調(diào)度模型

云計(jì)算平臺是在“需求付費(fèi)”的原則下可同時(shí)為多個(gè)用戶提供服務(wù),且滿足用戶的多服務(wù)質(zhì)量(quality of service,QoS)目標(biāo)約束條件[9,10],但云計(jì)算在滿足用戶的同時(shí),還應(yīng)提高云服務(wù)提供商的收益。該調(diào)度模型著重考慮用戶所關(guān)心的完成時(shí)間以及云服務(wù)提供商在意的能耗。

1.1 變量描述

任務(wù)調(diào)度是根據(jù)一定的約束規(guī)則將應(yīng)用任務(wù)集與可用資源集建立的一種合理映射的關(guān)系。云環(huán)境下的任務(wù)分配目標(biāo)是將M個(gè)任務(wù)合理的派發(fā)給云服務(wù)器上N個(gè)可利用的資源進(jìn)行執(zhí)行,盡可能減少任務(wù)的執(zhí)行時(shí)間和執(zhí)行能耗。R為資源節(jié)點(diǎn)rj的集合j∈[1,n],其中,n為云服務(wù)器可利用的資源數(shù)量；T為應(yīng)用任務(wù)ti的集合,i∈[1,m],m為待調(diào)度計(jì)算任務(wù)的數(shù)量。通常,在任務(wù)調(diào)度過程中可用資源節(jié)點(diǎn)數(shù)量遠(yuǎn)遠(yuǎn)小于參與調(diào)度的任務(wù)數(shù)量,即r?m。

將云計(jì)算任務(wù)調(diào)度問題用一個(gè)四元數(shù)組∑:(T,P,TIME,E)進(jìn)行描述,其中，T為待調(diào)度的計(jì)算任務(wù)集合；P為m×n的任務(wù)分配矩陣,矩陣P中的元素pij=1表示計(jì)算任務(wù)ti在資源節(jié)點(diǎn)rj上執(zhí)行,否則pij=0；時(shí)間執(zhí)行矩陣TIME是一個(gè)m×n的矩陣,其元素timeij表示計(jì)算任務(wù)ti在資源節(jié)點(diǎn)rj上的執(zhí)行時(shí)間；E為m×n的能量消耗矩陣,其元素eij表示任務(wù)ti在資源節(jié)點(diǎn)rj上執(zhí)行消耗的能量。

1.2 任務(wù)建模

任務(wù)完成時(shí)間是指任務(wù)提交到任務(wù)完成,并將調(diào)度完成后的結(jié)果反饋給用戶的時(shí)間間隔。由于計(jì)算任務(wù)是并行執(zhí)行的,因此任務(wù)完成時(shí)間定義為所有計(jì)算任務(wù)中完成時(shí)間最長的任務(wù)所用時(shí)間

(1)

執(zhí)行能耗是指任務(wù)執(zhí)行完后,每個(gè)虛擬資源因執(zhí)行任務(wù)而消耗的能量。每個(gè)調(diào)度方案中所有任務(wù)執(zhí)行完成后所消耗的能耗定義為

(2)

式中eij為任務(wù)在云服務(wù)器上的執(zhí)行能耗,eij=Ecpu·timeij。其中，Ecpu為云服務(wù)器CPU能耗,該執(zhí)行能耗與CPU的利用率呈線性關(guān)系[11],Ecpu=αcpu·ucpu+γcpu。其中，ucpu為CPU利用率,αcpu和γcpu分別為CPU能耗公式中的固定系數(shù)。

以降低執(zhí)行能耗與任務(wù)完成時(shí)間為目標(biāo),得到的云計(jì)算的任務(wù)調(diào)度目標(biāo)函數(shù)可以稱為最小化問題

minf(x)=λ1*AllTime(x)+λ2*EC(x)

(3)

式中λ1,λ2分別為任務(wù)完成時(shí)間、執(zhí)行能耗的權(quán)重,且滿足λ1+λ2=1,λ1>0,λ2>0。

2 改進(jìn)的差分進(jìn)化算法

本文提出了一種改進(jìn)的差分進(jìn)化算法,基于Levy分布的自適應(yīng)差分進(jìn)化(Levy-based adaptive differential evolution,LADE)算法,并將其應(yīng)用于求解云計(jì)算任務(wù)調(diào)度問題。

2.1 染色體編碼

本文結(jié)合云計(jì)算任務(wù)調(diào)度的特點(diǎn),采用資源—任務(wù)的間接編碼方式,用戶的計(jì)算任務(wù)總數(shù)量為染色體長度,每個(gè)基因代表一個(gè)計(jì)算任務(wù),該基因位的位值代表該計(jì)算任務(wù)分配到相應(yīng)資源的資源編號。染色體最終編碼格式如圖1所示,ti表示任務(wù)編號,i∈[1,m],rj表示資源編號,j∈[1,n]。

圖1 染色體編碼格式

按照上圖的編碼方式可以得到對應(yīng)的解碼為r3:{t1},r1:{t2},r2:{t3},…,rn:{tm}，由此可以得出,每一條染色體對應(yīng)一種任務(wù)的調(diào)度方案。

2.2 變異操作

本文采用隨機(jī)選取種群中兩個(gè)不同的個(gè)體與待變異個(gè)體進(jìn)行向量合成,產(chǎn)生中間個(gè)體Vi(g+1),即

vi(g+1)=xi(g)+F[i]×(xp1(g)-xp2(g))

(4)

式中g(shù)為進(jìn)化代數(shù),xi(g)為第g代種群中第i個(gè)個(gè)體,xp1(g),xp2(g)分別為第g代種群中隨機(jī)選取的兩個(gè)不同個(gè)體。F[i]為每個(gè)個(gè)體特定的縮放因子,滿足取值范圍為[0,1]的柯西分布[12]

Fi=CauchyRandom(μF,0.1)

(5)

μF的更新方式

μF=(1-c)·μF+c·meanL(SF)

(6)

式中SF為所有成功變異的個(gè)體的F值的集合,meanL(?)為Lehmer均值[12]

meanL(SF)=∑FeSFF2∑FeSFF

(7)

2.3 交叉操作

對第g代個(gè)體{xi(g)}及其變異的中間體{vi(g+1)}進(jìn)行交叉操作

(8)

式中jrand為[1,2,…,D]為的隨機(jī)整數(shù)。每個(gè)個(gè)體i均有特定的交叉概率CR[i],滿足Levy分布,其概率密度函數(shù)[13]

(9)

式中α,γ為Levy分布的2個(gè)特征參數(shù)；0<α≤2,γ>0。

2.4 貪婪選擇

DE采用貪婪算法來選擇進(jìn)入下一代種群的個(gè)體,選取適應(yīng)值更好的個(gè)體進(jìn)入下一代,本文中,由于任務(wù)調(diào)度問題屬于最小化問題,因此,選取適應(yīng)值較小的個(gè)體進(jìn)入下一代

(10)

2.5 DE任務(wù)調(diào)度算法的總流程

結(jié)合前文建立的多用戶任務(wù)調(diào)度模型,得到改進(jìn)之后的DE算法流程圖如圖3所示。

圖3 算法流程

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

設(shè)計(jì)了2個(gè)實(shí)驗(yàn)方案：一是選取測試函數(shù)對比其他算法,驗(yàn)證本算法尋優(yōu)的優(yōu)越性；二是在Windows操作系統(tǒng)下,主頻為2.5 GHz,采用Cloudsim-3.0.2[14]云計(jì)算模擬平臺對本文算法的實(shí)際調(diào)度性能進(jìn)行模擬仿真,并與傳統(tǒng)DE[15]算法和jDE[16]算法進(jìn)行比較。實(shí)驗(yàn)中通過改變?nèi)蝿?wù)參數(shù)來測試在不同計(jì)算任務(wù)數(shù)下算法的表現(xiàn)性能。

3.1 尋優(yōu)測試

采用3個(gè)準(zhǔn)測試函數(shù)：Sphere、Rosenbrock和Rastrigin對傳統(tǒng)DE算法、jDE算法和LADE算法的性能進(jìn)行了對比測試,所有算法的運(yùn)行結(jié)果如圖4所示。

圖4 三種算法對三個(gè)準(zhǔn)函數(shù)的尋優(yōu)收斂曲線

對圖4的分析可以看出,對3個(gè)準(zhǔn)測試函數(shù),LADE算法的性能均優(yōu)于其他兩個(gè)算法,對比結(jié)果表明,不管對于單峰函數(shù)還是多峰函數(shù),LADE算法在迭代次數(shù)范圍內(nèi)表現(xiàn)出了良好的性能,目標(biāo)函數(shù)值曲線下降速度快,尋優(yōu)精度高,在一定程度彌補(bǔ)了算法易陷入局部最優(yōu)的不足。

3.2 云計(jì)算調(diào)度測試

將設(shè)計(jì)的LADE算法在云計(jì)算模擬平臺Cloudsim上進(jìn)行模擬仿真。實(shí)驗(yàn)時(shí)所用的具體參數(shù)設(shè)置如表1。

為了盡量避免誤差,本文將每組實(shí)驗(yàn)都進(jìn)行10次,實(shí)驗(yàn)結(jié)果如圖5。

表1 仿真實(shí)驗(yàn)各種類數(shù)據(jù)參數(shù)

圖5 不同任務(wù)數(shù)量下三種調(diào)度策略任務(wù)仿真結(jié)果

由圖5中可以看出,在計(jì)算資源不變的情況下,任務(wù)數(shù)量很小時(shí),LADE和標(biāo)準(zhǔn)DE、jDE算法的差別不大,都能找到近似最優(yōu)解。但隨著任務(wù)數(shù)量的增多,調(diào)度復(fù)雜度也隨之上升,LADE算法相比其他兩個(gè)調(diào)度算法的優(yōu)勢愈加明顯,說明LADE算法在任務(wù)數(shù)量多,復(fù)雜度高的環(huán)境下依然具有良好的調(diào)度性能。

表2顯示了DE、jDE和LADE等3種算法分別在任務(wù)數(shù)為100,200,300,400,500時(shí)得到的適應(yīng)值的均值、最大值、最小值、中值、標(biāo)準(zhǔn)差的對比結(jié)果。由表2可以看出,相較于其他兩種算法,LADE得到的適應(yīng)值對于所有的任務(wù)數(shù)都表現(xiàn)出了它的優(yōu)勢。當(dāng)任務(wù)數(shù)為100時(shí),LADE取得的適應(yīng)值均值為1.74×103,其中最優(yōu)的適應(yīng)值為1.65×103,而其他兩種算法最優(yōu)的適應(yīng)值為1.92×103；隨著任務(wù)數(shù)的不斷增加,當(dāng)任務(wù)數(shù)為500時(shí),LADE取得的適應(yīng)值均值為9.38×103,其中,最優(yōu)的適應(yīng)值為9.21×103,而其他兩種算法最優(yōu)的適應(yīng)值為1.06×104。可以看出,LADE在進(jìn)化初期就有著很強(qiáng)的全局搜索能力,隨著任務(wù)數(shù)越來越多,難度的提高,適應(yīng)值相差也越來越多,LADE的優(yōu)勢也就越加明顯。

另外,由表2還可以看出,隨著任務(wù)數(shù)的不斷增加,適應(yīng)值也越來越大,這是因?yàn)槿蝿?wù)數(shù)增加,相應(yīng)的執(zhí)行時(shí)間和執(zhí)行能耗也會增加,對應(yīng)的適應(yīng)值也會隨之增大。但是,對于不同的任務(wù)數(shù)量,LADE均表現(xiàn)出其明顯優(yōu)勢。

表2 三種算法適應(yīng)值對比結(jié)果

4 結(jié)束語

實(shí)驗(yàn)結(jié)果證明：相對于傳統(tǒng)DE算法和jDE算法,本文算法在計(jì)算資源有限,復(fù)雜度高的情況下的計(jì)算任務(wù)調(diào)度具有較明顯的優(yōu)勢,能大幅減少任務(wù)的完成時(shí)間和執(zhí)行能耗,在現(xiàn)代大規(guī)模云計(jì)算中有著廣泛的應(yīng)用前景。