基于粒子群優(yōu)化的云計算低能耗資源調(diào)度算法

賈嘉, 慕德俊

(西北工業(yè)大學(xué) 自動化學(xué)院, 陜西 西安 710072)

隨著對云計算需求的不斷擴大，幾大云計算服務(wù)提供商，如Amazon等，建立了越來越多的數(shù)據(jù)中心，以滿足云計算對基礎(chǔ)設(shè)施資源的需要。為了維護大規(guī)模的數(shù)據(jù)中心運行，需要大量能耗。這不僅提高了服務(wù)成本，也給相應(yīng)基礎(chǔ)設(shè)施帶來巨大壓力。有研究表明，數(shù)據(jù)中心的使用率一般在5%～20%[1-2]；而空閑服務(wù)器的電量消耗也超過滿負荷情況下的50%。能耗是云計算成本中重要一環(huán)。針對云環(huán)境中數(shù)據(jù)中心的能耗問題，本文研究了面向低能耗的基于粒子群優(yōu)化算法的數(shù)據(jù)中心資源分配算法。采用帕累托最優(yōu)解集合描述所有可行的最優(yōu)解。為了得到帕累托最優(yōu)解集合，采用粒子群優(yōu)化算法，對不同的分配方案迭代尋優(yōu)，并按存活周期隨機變異分配方案。通過比較不同分配方案下能耗，得到最優(yōu)的資源分配方案。

1 云計算與粒子群優(yōu)化

1.1 云計算概述

云計算作為一種新興的并行計算技術(shù)，是分布式處理、并行處理、網(wǎng)格計算的發(fā)展和延伸。它提供了更可靠、更安全的存儲和計算數(shù)據(jù)能力、簡化計算交付、降低成本、具有更高的擴展性和靈活性。云計算采用計時付費的形式，程序員只需關(guān)注應(yīng)用程序本身，關(guān)于集群的處理問題，則交由平臺處理。云計算重要特點之一是虛擬化。虛擬化技術(shù)范疇從簡單的硬件抽象逐漸發(fā)展成為虛擬云操作系統(tǒng)，云主機能夠大量根據(jù)用戶定義的服務(wù)質(zhì)量(quality of service,QoS)規(guī)范執(zhí)行應(yīng)用程序的VMs并行分享。

1.2 粒子群優(yōu)化

粒子群優(yōu)化(particle swarm optimization,PSO)算法[3]是一種模擬鳥群覓食行為的演化計算算法。因其結(jié)構(gòu)簡單、參數(shù)少、易實現(xiàn)，所以受到廣泛重視并被應(yīng)用到了許多自然科學(xué)和工程科學(xué)領(lǐng)域。標準的PSO的形式如下

2 云計算能耗模型

云計算體系下,數(shù)據(jù)服務(wù)需要滿足很多限制性條件,如相應(yīng)時間、吞吐量等。對于資源調(diào)度而言,這些指標構(gòu)成了調(diào)度算法的約束條件。本節(jié)首先研究了與調(diào)度相關(guān)的能耗模型,得到能耗的代價函數(shù)及約束條件;并指出,所求問題的解為帕累托最優(yōu)解集合。然后采用粒子群優(yōu)化算法對代價函數(shù)求取最優(yōu)解集合。

2.1 能耗模型

min∑mj=1∑ni=1fijxij3

(2)

(3)

約束條件為

xij∈{0,1},i=1,2,…,n;j=1,2,…,m

(4)

∑mj=1xij=1, ?i

(5)

(6)

∑ni=1fijxij≤maxFj, ?j

(7)

式中,xij=1表示第i個虛擬主機調(diào)度到第j個服務(wù)器,取0則否;fij表示第i個虛擬主機在第j個服務(wù)器上占用的頻率。

2個代價函數(shù)分別對應(yīng)了不同的能耗指標。代價函數(shù)(2)代表了所有虛擬主機總動態(tài)功耗之和最小;代價函數(shù)(3)表示盡可能提高某一臺服務(wù)器的利用率。代價函數(shù)(2)和(3)存在一定的沖突關(guān)系,從而構(gòu)成一個典型的多目標優(yōu)化問題。與之相關(guān),約束條件則反應(yīng)了虛擬主機與服務(wù)器的硬性關(guān)系。約束條件(4)中,xij=1表示虛擬主機i分配到服務(wù)器j上,而約束(5)表示虛擬主機只能被分配到1臺服務(wù)器;約束(6)指出每個虛擬主機占用頻率的上下限;約束(7)表示1臺服務(wù)器上所有虛擬主機占用的頻率和不能超過服務(wù)器負載。

決策變量x={xij}和f={fij}構(gòu)成了最終的解。x決定了虛擬主機在服務(wù)器上的分配;而f則指出該分配下虛擬主機使用的頻率大小。如前所述,代價函數(shù)(2)和(3)計算決策變量x和f是一個多目標優(yōu)化問題,傳統(tǒng)的最優(yōu)化算法難以求解。本節(jié)剩余部分討論了求解x和f的方法。

2.2 多目標優(yōu)化的帕累托最優(yōu)

一般而言,代價函數(shù)(2)和(3)是相互沖突的,所以不存在使二者同時達到最小的惟一解,而是產(chǎn)生一組解的集合。數(shù)學(xué)上,把這種沒有一個解比其他解更優(yōu)的最優(yōu)解集合稱為帕累托最優(yōu)解集或帕累托最優(yōu)前沿(Pareto optimal front, POF)。此時,對于(2)和(3)對應(yīng)的代價函數(shù),任意2個解f1和f2存在2種可能的關(guān)系:一個解優(yōu)于另一個解,或者兩者都不比對方優(yōu)。

本文采用帕累托占優(yōu)條件[4]來判斷解之間的關(guān)系。針對(2)和(3)對應(yīng)的代價函數(shù)的解f1和f2,當(dāng)f1的一個代價函數(shù)嚴格優(yōu)于f2,且另一個代價函數(shù)f1不嚴格劣于f2,則稱f1帕累托占優(yōu)f2,即當(dāng)滿足下式時,f1帕累托占優(yōu)f2。

?i:gi(f1)≤gi(f2)

?j:gj(f1)

(8)

式中,gi,i=1,2是代價函數(shù)(2)或(3)。在給定了一個服務(wù)器分配方案x后,由(8)可以評估任意2個頻率分配方案f1和f2。

3 基于粒子群優(yōu)化的低能耗資源調(diào)度算法

由第2節(jié)可知,待求的決策變量為x和f。由于需要指定一個服務(wù)器分配方案x后,才可能獲取一個頻率分配方案f,因此,本文首先隨機給出一個分配方案x;在該方案下,使用經(jīng)典的粒子群算法進行尋優(yōu),得到該方案對應(yīng)的帕累托最優(yōu)解集合;通過隨機改變方案,得到不同方案的最優(yōu)解集合,合并成為全局最優(yōu)解集合,并在該集合中尋找最終解。

3.1 頻率分配方案

首先隨機產(chǎn)生一個服務(wù)器分配方案xt。在xt下,按照約束條件隨機生成關(guān)于頻率分配ft的粒子群y={yi}。對于每個粒子yi,按照式(1)所示的迭代過程,進行尋優(yōu)。

1) 粒子群尋優(yōu)。對于每一個方案,按照經(jīng)典的粒子群算法(1),需要使用粒子的局部最優(yōu)解pi和全局最優(yōu)解pg。多目標最優(yōu)情況下,每個粒子yi存在多個局部最優(yōu),進而合并所有粒子將產(chǎn)生多個全局最優(yōu)。因此,本文算法中允許每個粒子最多產(chǎn)生的Nl個局部最優(yōu),即pi={pi,1,pi,2,…,pi,Nl,},而合并所有局部最優(yōu)得到的全局最優(yōu)集合,最多包含Ng個元素,即pg={pg,1,pg,2,…,pg,Ng}。對于多余的解,有不同的處理方法。與文獻[5]不同,本文算法采用隨機拋棄多余解的方法。顯然,這有利于提高算法的實時性。

2) 迭代終止條件。為了停止粒子群迭代尋優(yōu),本文設(shè)計依據(jù)服務(wù)器分配方案存活時間的服務(wù)器分配方案跳轉(zhuǎn)概率Px。Px具體的構(gòu)造方法在3.2節(jié)討論。發(fā)生跳轉(zhuǎn)時,算法存儲當(dāng)前xt及其對應(yīng)的全局最優(yōu)解ft=pg。取遍所有可能的組合xt及其對應(yīng)的ft,合并所有解得到最終的解集合x={xt}和f={ft}。

3) 3種帕累托最優(yōu)解集合。本文涉及到3種不同的帕累托最優(yōu)解集合,為了避免混淆,在此指明其相互關(guān)系。給定服務(wù)器分配方案xt下,最底層的集合是一個粒子yi迭代尋優(yōu)過程中產(chǎn)生的局部最優(yōu)解pi;合并局部最優(yōu)解,得到所有粒子y={yi}的全局最優(yōu)解集合ft=pg;對于不同的方案x={xt},所有ft將共同組成最終的解集合f={ft}。

3.2 服務(wù)器分配方案

本文采用服務(wù)器分配方案跳轉(zhuǎn)概率Px來終止3.1節(jié)所述的頻率分配尋優(yōu)。

本文使用分配方案的存活周期為自變量,對跳轉(zhuǎn)概率Px賦值。直觀而言,如果對一個服務(wù)器分配方案xt已經(jīng)進行了多次粒子群迭代尋優(yōu),則可以認為此時的結(jié)果已經(jīng)近似達到該方案下的最優(yōu)解,從而停止計算當(dāng)前的xt,轉(zhuǎn)而生成新的分配方案xt+1,重新進行尋優(yōu)。出于以上的考慮,令

Px=I/Nt

(9)

式中,I為粒子群迭代次數(shù);Nt為指定的參數(shù)。在3.1節(jié)所述粒子群尋優(yōu)時,每次迭代初始都產(chǎn)生一個[0,1]內(nèi)均勻分布的隨機數(shù),與Px進行比較,如果小于Px,則發(fā)生跳轉(zhuǎn)。

實際中,服務(wù)器的個數(shù)一般在102～103間,本文算法隨機抽取Nx個分配方案進行尋優(yōu)。遍歷所有Nx個服務(wù)器方案后,得到1組帕累托最優(yōu)解集合f={ft}。

根據(jù)決策者不同的需要,選擇最終的惟一解的方法也有所不同。本文采用類似文獻[5]的方法,計算每個解到理想最優(yōu)點的距離,以距離最小原則選取最終解,如圖1所示。圖1中,最終帕累托最優(yōu)解集合存在5個解,f1,f2,…,f5。解f1的動態(tài)能耗最小,為g1min,解f5的服務(wù)器空閑能量最小,為g2min。于是,理想最優(yōu)點為P點,對應(yīng)坐標(g1min,g2min)。計算每個最優(yōu)解到P點的距離,按照距離最小選取最終的解。圖1中,f2為選取的最優(yōu)解。

圖1 距離評價方法

4 實驗分析

本文采用Matlab模擬了云計算下服務(wù)器和虛擬主機。程序運行于1臺PC機,內(nèi)存1.75 GB,CPU為3.0 GHz。

4.1 參數(shù)設(shè)置

實驗中,本文所提算法使用了如下的參數(shù)。粒子群中,慣性權(quán)重ω=1,學(xué)習(xí)因子c1=c2=1.5;采用20個粒子進行迭代尋優(yōu)。每個粒子最多保留Nl=5個局部帕累托最優(yōu),而所有粒子共保留Ng=20個全局帕累托最優(yōu)。用于生成跳轉(zhuǎn)概率的Nt是關(guān)鍵參數(shù),較小的Nt將使算法更快結(jié)束,而較大的Nt則增加了每個方案的迭代尋優(yōu)次數(shù),從而提高得到該方案下最優(yōu)解的概率。文中取Nt=20。顯然,當(dāng)?shù)螖?shù)n=20時,按照(9)式所示,算法必然發(fā)生跳轉(zhuǎn),因此,Nt還起到了傳統(tǒng)粒子群算法中迭代次數(shù)最大值的作用。

4.2 不同服務(wù)器資源下對比實驗

通過調(diào)整服務(wù)器數(shù)量m和虛擬主機數(shù)量n,在不同的任務(wù)類型下進行了實驗。對比算法采用工業(yè)界普遍使用的輪詢調(diào)度方法。

首先驗證了在m=5個服務(wù)器和n=10個虛擬主機環(huán)境下算法的性能。圖2顯示了所提算法的調(diào)度結(jié)果。其中,圖2a)顯示了某個帕累托局部最優(yōu)解集合,而圖2b)展示了最終的所有帕累托全局最優(yōu)解。按照3.2節(jié)所述距離評價方法,算法最終選擇圖2b)中左下點對應(yīng)的決策變量作為最終解,其動態(tài)功耗為18.6 W,服務(wù)器空閑能量為1.157 W。在本實驗中,每個粒子群平均存活了5.4次迭代。算法的實時性基本滿足實際要求。采用輪詢算法,動態(tài)功耗為80 W,服務(wù)器空閑能量為20 W。

圖2 少量服務(wù)器/虛擬主機資源調(diào)度結(jié)果

在中量負載情況下,取m=100個服務(wù)器,n=300個虛擬主機,所提算法得到如圖3所示結(jié)果。此時,動態(tài)功耗為1 029 W,服務(wù)器空閑能量為566.3 W。采用輪詢算法,動態(tài)功耗為2 400 W,服務(wù)器空閑能量為1 600 W。在大量負載情況下,取m=1 000個服務(wù)器,n=2 500個虛擬主機,所提算法得到如圖4所示結(jié)果。此時,動態(tài)功耗為9 038 W,服務(wù)器空閑能量為3 657 W。采用輪詢算法,動態(tài)功耗為20 000 W,服務(wù)器空閑能量為10 000 W。

圖3 中量服務(wù)器/虛擬主機資源調(diào)度結(jié)果

圖4 大量服務(wù)器/虛擬主機資源調(diào)度結(jié)果

了驗證所提算法對變化的服務(wù)其數(shù)量及虛擬主機數(shù)量的魯棒性,取m={21,22,…,210}個服務(wù)器,對應(yīng)虛擬主機數(shù)量n為m的21+(t-1)/10倍,t=1,2,…,10隨序號依次增多。例如,當(dāng)m=210時,n=3 821。由于在4.1節(jié)參數(shù)設(shè)置中已經(jīng)指明,1臺服務(wù)器最多可以容納4臺虛擬主機,此時n/m=3.73已經(jīng)接近服務(wù)器飽和狀態(tài)。圖5顯示了對比結(jié)果。圖5a)為動態(tài)能耗對比圖,圖5b)為服務(wù)器空閑能量對比圖。出于可視化考慮,采用了log坐標系。

圖5 不同數(shù)量服務(wù)器下性能對比圖

由圖5可見,所提算法比輪詢調(diào)度算法在動態(tài)能耗和服務(wù)器空閑能量2個指標上,均取得更優(yōu)的結(jié)果。在全部10組實驗上,所提算法的動態(tài)能耗均小于輪詢調(diào)度的50%。

4.3 能耗優(yōu)先對比實驗

對比算法中,除了4.2節(jié)使用的輪詢調(diào)度外,還采用了文獻[6]中優(yōu)先受限的(precedence-constrained)并行應(yīng)用調(diào)度算法,以及文獻[7]采用的狀態(tài)轉(zhuǎn)移算法。

設(shè)定服務(wù)器數(shù)量m={80, 100, 120},對應(yīng)虛擬主機數(shù)量n={1,2,3}×m。為了直觀對比各算法的能耗,將輪詢調(diào)度的能耗指定為x,而其余算法的能耗相應(yīng)換算為輪詢調(diào)度的占比[8-9]。

表1展示了不同算法在n/m=1時的實驗結(jié)果。表2對應(yīng)n/m=2的結(jié)果;表3為n/m=3的結(jié)果。各表中,黑體標出了能耗最低的算法。

表1 不同算法能耗對比表,n/m=1 (%)

表2 不同算法能耗對比表,n/m=2 (%)

表3 不同算法能耗對比表,n/m=3 (%)

從表1～表3可見，輪詢調(diào)度的耗能最多，且普遍為智能算法能耗的2倍以上。在3種能耗相關(guān)的智能算法中，狀態(tài)轉(zhuǎn)移算法的表現(xiàn)一般，在不同服務(wù)器/虛擬機比例下，均沒有獲得最少的能耗。這是由于狀態(tài)轉(zhuǎn)移受限于其固有的模型假設(shè)，而實際中，轉(zhuǎn)移陣實時、動態(tài)的變化，往往給該算法帶來極強的擾動因素，造成算法性能下降。所提算法在7組實驗中取得最低的能耗。

5 結(jié) 論

針對云計算中能耗過高的問題，提出一種基于粒子群優(yōu)化的資源調(diào)度算法。首先給出了能耗模型，以虛擬主機在服務(wù)器上的分配方案和占用的頻率為決策指標，進行優(yōu)化。指出了該模型為多目標優(yōu)化問題，從而存在多個最優(yōu)解，即帕累托最優(yōu)解集合。采用粒子群優(yōu)化算法對于每個分配方案進行迭代尋優(yōu)，按照從屬關(guān)系逐次構(gòu)造了單粒子帕累托局部最優(yōu)解集合、粒子群帕累托全局最優(yōu)解集合和最終的跨分配方案的帕累托最優(yōu)解集合共3個集合。在最終的集合上，采用距離評價標準，自主選擇惟一的解。在不同數(shù)量的服務(wù)器和虛擬主機環(huán)境下進行了仿真實驗。實驗結(jié)果表明所提算法所需能耗低于輪詢算法的50%。

參考文獻：

[1] Ludwig Siegele. Let it Rise: A Special Report on Corporate IT[M]. Economist Newspaper, 2008

[2] Rangan Kash, Cooke A, Post J, et al. The Cloud Wars: ＄100+billion at stake[R]. Tech Rep, Merrill Lynch, 2008

[3] James Kennedy. Particle Swarm Optimization[M]. Encyclopedia of Machine Learning, Springer, 2010

[4] Abido M A. Multiobjective Particle Swarm Optimization for Environmental/Economic Dispatch Problem[J]. Electric Power Systems Research, 2009, 79(7): 1105-1113

[5] 劉靜,羅先覺. 采用多目標隨機黑洞粒子群優(yōu)化算法的環(huán)境經(jīng)濟發(fā)電調(diào)度[J]. 中國電機工程學(xué)報, 2010, 30(34): 105-111

Liu Jing, Luo Xianjue. Environmental Economic Dispatching Adopting Multi-Objective Random Black-Hole Particle Swarm Optimization Algorithm[J]. Proceedings of the CSEE, 2010, 30(34): 105-111 (in Chinese)

[6] Mezmaz M, Melab N, Kessaci Y, et al. A Parallel Bi-Objective Hybrid Metaheuristic for Energy-Aware Scheduling for Cloud Computing Systems[J]. Journal of Parallel and Distributed Computing, 2011, 71(11):1497-1508

[7] Lee Young Choon, Zomaya A Y. A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems[J]. IEEE Trans on Parallel and Distributed Systems, 2008, 19(9): 1215-1223

[8] Li Y, Chen M, Dai W, Qiu M. Energy Optimization with Dynamic Task Scheduling Mobile Cloud Computing[J]. IEEE Systems Journal, 2017, 11(1): 96-105

[9] Rimal B P, Maier M. Workflow Scheduling in Multi-Tenant Cloud Computing Environments[J]. IEEE Trans on Parallel and Distributed Systems, 2017, 28(1): 290-304