基于CSP的能耗高效云計算資源調(diào)度模型與算法

林偉偉，劉波，朱良昌，齊德昱

(1. 華南理工大學(xué) 計算機科學(xué)與工程學(xué)院，廣東 廣州 510006；2. 華南師范大學(xué) 計算機學(xué)院，廣東 廣州 510631)

1 引言

隨著云計算技術(shù)的發(fā)展和云應(yīng)用的普及，云計算現(xiàn)在已經(jīng)被越來越多的企業(yè)接受，并同時對其展開了廣泛的研究[1]。最近幾年，隨著計算機系統(tǒng)電能消耗的不斷增加，能源的高效利用已經(jīng)成為現(xiàn)代計算機系統(tǒng)(如數(shù)據(jù)中心和云端)的一個非常重要的研究內(nèi)容[2]。近期，有一些關(guān)于云計算的資源提供與云計算資源管理的研究，其中GARG等[3]提出一種接近最優(yōu)的調(diào)度策略，該策略利用橫跨不同數(shù)據(jù)中心之間的數(shù)據(jù)為云提供者服務(wù)。他們考慮了許多影響能源效率的因素(例如：能源消耗、碳排放速度、工作量、CPU功耗效率)，這些因素依據(jù)其位置、結(jié)構(gòu)設(shè)計和管理系統(tǒng)的不同而在各個數(shù)據(jù)中心進行變化。為了解決這一問題，出現(xiàn)了一些基于裝箱問題部署虛擬服務(wù)器的優(yōu)化方法，在一些文獻中有其具體的描述[4～8]，關(guān)于虛擬機的部署問題就被建模為裝箱問題。然而，目前提出的面向能耗優(yōu)化的調(diào)度方法大部分是針對同構(gòu)服務(wù)器的調(diào)度[7,9～13]，但是，由于現(xiàn)有的數(shù)據(jù)中心服務(wù)器的采購時間不同、使用年限不同及品牌不同等異構(gòu)性，比如文獻[13]描述的數(shù)據(jù)中心的服務(wù)器往往是異構(gòu)的，因此，目前提出的大部分同構(gòu)服務(wù)器調(diào)度方法不能很好地應(yīng)用在一般的云計算數(shù)據(jù)中心的能耗管理中。

為此，本文針對異構(gòu)物理服務(wù)器的能耗優(yōu)化資源調(diào)度問題進行研究，利用約束滿足問題[14]對異構(gòu)物理服務(wù)器的能耗優(yōu)化資源調(diào)度問題建模，并基于Choco[15]約束編程求解建立的能耗優(yōu)化資源分配模型，能夠減少虛擬化的云數(shù)據(jù)中心的服務(wù)器能源消耗。然后，設(shè)計了資源調(diào)度算法來實現(xiàn)該優(yōu)化配置方案。最后，使用Choco模擬實驗進行算法評價，實驗結(jié)果表明提出的模型和算法在能耗方面明顯優(yōu)于已有的資源調(diào)度方法。

2 相關(guān)研究

減少能源的消耗對于資源供應(yīng)商減少成本和利潤最大化來說非常重要[16,17]。BELOGLAZOV等[18]提出了一種用于虛擬機化云計算數(shù)據(jù)中心的有效的資源管理系統(tǒng)，它可以減少運營成本并提供所需的服務(wù)質(zhì)量。節(jié)約能源是通過虛擬機不斷地依據(jù)當前的資源利用率以及虛擬機和熱狀態(tài)下的計算節(jié)點之間建立的虛擬拓撲網(wǎng)絡(luò)結(jié)構(gòu)來進行整合的。RODERO等[19]為高性能計算和虛擬化計算平臺提出了一種能量感知型的網(wǎng)絡(luò)配置方法。能源效率的提高是通過工作量的感知，恰到好處地動態(tài)配置機制以及通過關(guān)閉主機系統(tǒng)中沒有映射虛擬機的子系統(tǒng)方法來實現(xiàn)的。ABDELSALAM等[20]創(chuàng)建了一個用于云計算環(huán)境，主要服務(wù)于客戶的如Web服務(wù)一樣的交互式應(yīng)用的電力管理數(shù)學(xué)模型，這個數(shù)學(xué)模型計算服務(wù)器的最優(yōu)數(shù)量和它們應(yīng)該運行的頻率。文獻[21]中，作者提出了一個提供高效、綠色、強化的可擴展的云計算架構(gòu)的新框架。通過使用電力調(diào)度技術(shù)、可變的資源管理、實時調(diào)度和最小化的虛擬機設(shè)計等技術(shù)，使基于最小化云開銷的數(shù)據(jù)中心系統(tǒng)的整體功效得到了改善，CHANG等[22]對云資源的優(yōu)化配置進行了研究。他們制定了關(guān)于計算能力和其他資源的多樣性的資源分配問題。他們提出了一個可證明的在多項式時間內(nèi)得到接近最優(yōu)解的近似算法。然而現(xiàn)今的方法大都考慮的是給予的每個物理機節(jié)點上有著相同的物理參數(shù)，如CPU速度、硬盤容量、內(nèi)存等。

此外，絕大部分方法僅將處理器作為唯一值得考慮的資源，而拋棄了其他一些同樣很重要的資源，例如內(nèi)存和存儲空間。這樣就導(dǎo)致由于工作量大量聚集在同一個節(jié)點而形成瓶頸，導(dǎo)致性能的下降以及能量消耗的增加，這個在文獻[23]中有所提及。在運行時虛擬機實現(xiàn)再分配的能力，可以動態(tài)地配制工作量，同時可以使虛擬機實現(xiàn)重新部署，使運行的物理機節(jié)點達到最小，而空閑節(jié)點則切換為省電模式。然而虛擬機的遷移會導(dǎo)致時間延遲、額外的性能開銷以及功耗，所以需要通過仔細分析和智能技術(shù)消除這些因工作量變化而導(dǎo)致的非生產(chǎn)性的遷移[2]。

裝箱問題是一個著名的NP組合難題，已提出許多啟發(fā)式和貪心算法來解決這難題[9,24]。一些啟發(fā)式算法，例如first-fit decreasing (FFD)[10]、best-fit decreasing(BFD)[10]和modified best fit decreasing(MBFD)[25]都被提出來和應(yīng)用在數(shù)據(jù)中心的虛擬機調(diào)度中[4～8]。這些方法大部分是針對同構(gòu)服務(wù)器的調(diào)度，不能很好地應(yīng)用在一般的異構(gòu)云計算數(shù)據(jù)中心的資源調(diào)度和能耗管理中。CSP(約束滿足問題)[26]：由一個變量集合和一個約束集合組成；問題的一個狀態(tài)是由對一些或全部變量的一個賦值定義的；問題的解是滿足所有約束的完全賦值，或更進一步，使目標函數(shù)最大化。約束滿足問題作為人工智能研究的一個基本問題，在許多實際問題中都得到了廣泛的應(yīng)用，特別是調(diào)度中的資源分配問題。為此，本文主要是針對物理服務(wù)器異構(gòu)的云數(shù)據(jù)中心的資源調(diào)度問題進行研究，給出異構(gòu)物理服務(wù)器環(huán)境下的能耗優(yōu)化的資源調(diào)度模型和算法，減少云數(shù)據(jù)中心的能源消耗。

3 基于CSP的能耗優(yōu)化資源分配模型

3.1 問題描述

最直觀的節(jié)能減排方式就是關(guān)閉利用率不高的服務(wù)器，在傳統(tǒng)模式中，一個應(yīng)用運行在一個服務(wù)器上，關(guān)閉服務(wù)器就等于關(guān)閉了應(yīng)用；然而，服務(wù)器虛擬化為解除應(yīng)用與物理服務(wù)器的綁定提供了可能，在負載低谷期，管理員可以將原來運行在各個服務(wù)器上的應(yīng)用整合到較少的幾臺服務(wù)器上，關(guān)閉空閑的服務(wù)器，已達到綠色節(jié)能的目的。因而，一般能耗中的優(yōu)化問題就是最小化物理主機數(shù)；但是，在考慮物理主機異構(gòu)的情況，由于每個物理主機都有不同能耗，此時，能耗優(yōu)化的問題并不是最小物理主機數(shù)。下面舉個例子進行具體說明。

物理服務(wù)器和虛擬機的資源大小及能耗參數(shù)如圖1所示，其中Dy1～3表示當虛擬機VM1～3分配到該物理節(jié)點時產(chǎn)生的動態(tài)能耗。待部署的虛擬機以及其參數(shù)如圖2所示。假設(shè)需要將這3臺虛擬機部署在這3個物理節(jié)點上。如果采用最小主機數(shù)策略，3臺物理機都應(yīng)該分配到PM1上，這時的總能耗為650 W；若將VM1和VM2部署在PM2上，VM3部署在PM3上，則總能耗為420 W，可見，在物理主機異構(gòu)的情況下，能耗的優(yōu)化問題并不是最小物理主機數(shù)，而是綜合能耗最小。針對上述問題，本文提出了一個基于CSP的能耗優(yōu)化的云資源調(diào)度框架，該框架的系統(tǒng)架構(gòu)如圖2所示。

圖1 物理服務(wù)器與虛擬機的資源大小及能耗參數(shù)

圖2 基于CSP的能耗優(yōu)化的云資源調(diào)度框架

從圖2可以看出，提出的基于CSP的能耗優(yōu)化的云資源調(diào)度框架由應(yīng)用程序檢測、虛擬機配置和虛擬機部署3個模塊組成。本文將在3.2節(jié)～3.4節(jié)分別對各模塊進行詳細描述。在詳細描述之前，先對部分符號進行如下說明。

3.2 應(yīng)用程序監(jiān)測模塊

該模塊首先測出各應(yīng)用程序當前的負載，然后根據(jù)當前負載和 SLA目標確定分配給各應(yīng)用程序的資源(CPU、memory、network)。對于應(yīng)用程序ai，其分配的資源可以定義為當前負載和SLA目標的函數(shù)，即：Ri= fi(Li,Si)，其中，Li為應(yīng)用程序ai的當前負載，Si為應(yīng)用程序的SLA目標，Ri為分配給應(yīng)用程序的資源，它是(CPU、memory、network)三元組。對于分配給應(yīng)用程序ai的資源與其當前負載和SLA目標的函數(shù)關(guān)系fi，本文沒有做出基于經(jīng)驗的或基于實驗的假設(shè)，它可以由各數(shù)據(jù)中心的管理者根據(jù)相應(yīng)的管理政策、經(jīng)驗以及大量實驗數(shù)據(jù)而確定。

下面以 VAN等人[11]關(guān)于自動化虛擬資源管理研究中提到的一個基于實驗數(shù)據(jù)的經(jīng)驗主義的性能模型(如圖 3所示)為例，對應(yīng)用程序監(jiān)測模塊進行簡單說明。

圖3 性能模型

水平軸表示應(yīng)用程序每秒的請求量，即工作負載；垂直軸表示響應(yīng)時間；圖中的斜線表示特定CPU能力下響應(yīng)時間與每秒請求數(shù)的關(guān)系。假設(shè)應(yīng)用程序A是一個Web應(yīng)用程序，其SLA目標是請求的響應(yīng)時間，假設(shè)其值為100 ms，若此刻應(yīng)用程序A的負載為每秒300次請求，則根據(jù)圖3所示的關(guān)系可以得出分配給應(yīng)用程序A的CPU能力至少為10 000 MHz。

當然，上面只是一個可能的簡單示例，不同應(yīng)用程序的應(yīng)用程序有著不同的 SLA目標、不同類型的工作負載以及它們之間的不同函數(shù)關(guān)系。在提出的模型中，沒有對這些性質(zhì)做任何可能的假設(shè)，它們應(yīng)該由數(shù)據(jù)中心管理員根據(jù)不同類型的應(yīng)用程序，基于經(jīng)驗或?qū)嶒灁?shù)據(jù)對這些性質(zhì)進行描述與設(shè)定。

3.3 虛擬機配置模塊

該模塊根據(jù)應(yīng)用監(jiān)測程序模塊輸出的分配給各應(yīng)用程序的資源向量R=(R1,…, Rj,…, Rc)為各應(yīng)用程序分配虛擬機，使總的分配代價最小。換句話說，該模塊的目的是給出使目標函數(shù)(1)最小化的各應(yīng)用程序的虛擬機分配向量為

其中，m為應(yīng)用程序的數(shù)目，cost為虛擬機的操作開銷向量，每一項對應(yīng)于每一類虛擬機的分配開銷，Ni為分配給應(yīng)用程序i的虛擬機向量，并且Ni=（ni1,…,nij,…, nic），而nij為分配給應(yīng)用程序 i的第j類虛擬機的數(shù)量，cost·Ni則表示分配虛擬機向量Ni給應(yīng)用程序i的開銷。

根據(jù)本文的假設(shè)，數(shù)據(jù)中心中每類虛擬機的數(shù)目是有限的，即擁有一個上限閾值，下面定義各類虛擬機的閾值向量為：Nmax=(n1max,…, njmax,…, ncmax），且有如下關(guān)系

分配給各應(yīng)用程序資源量應(yīng)滿足應(yīng)用程序監(jiān)測模塊確定的資源要求，即

同時，部署在物理機上的所有虛擬機的資源總量不能超過所有物理機的資源總量，故有如下關(guān)系

采用約束編程的方法對上述模型進行求解，即可獲總花費最小的虛擬機分配向量，每一個虛擬機分配向量對應(yīng)于各應(yīng)用程序的虛擬機分配情況，即分配了哪類虛擬機及各類虛擬機分配的數(shù)量。

3.4 虛擬機部署模塊

虛擬機部署模塊將虛擬機分配模塊產(chǎn)生的虛擬機分配向量N作為輸入，然后將虛擬機分配向量N整合為表示當前所有需要運行的虛擬機集合的向量VM = (vm1,…,vmi,…,vmp)，其中，vmi= (vmiCPU, vmimemory,vminetwork)。同時數(shù)據(jù)中心提供每臺物理主機的動態(tài)能耗參數(shù)。在描述物理資源約束前，先給出虛擬機放置的定義。

位向量Hi的定義為：?pi∈P，Hi= (hi1,…,hij,…, hip)，hij=1當且僅當虛擬機vmj部署在物理機pi上。

對于每臺物理機和其上部署的虛擬機有如下的約束關(guān)系

根據(jù)文獻[28]可知，物理服務(wù)器的能耗為空閑時產(chǎn)生的能耗和其上運行的應(yīng)用所產(chǎn)生的能耗之和為E = Edynamic+ Estatic，其中 Estatic表示物理機空閑時的能耗（即沒有分配虛擬機時的能耗，物理服務(wù)器 pi上的空閑能耗用 Eistatic表示），假設(shè)物理機 pi上放置各虛擬機資源時新增能耗的向量為 Eidynamic=(ei1,… ,eik)，而 Edynamic為放置在物理服務(wù)器 pi上所有虛擬機新增能耗之和 H ?Edynamic。因此，可以建立異構(gòu)服務(wù)器的

i i能耗最優(yōu)（?。┑馁Y源調(diào)度模型為

其中，Ei為物理服務(wù)器 pi的能耗。由此可以得出關(guān)于能耗的約束條件為

其中， EiM

ax為物理服務(wù)器 pi所能承載的最大能耗值，即物理服務(wù)器ip的實際能耗大小必須小于等于MaxiE 。

4 算法設(shè)計

4.1 虛擬機配置算法

4.1.1 算法描述

虛擬機配置算法的基本思想是為需要部署的應(yīng)用搜索操作開銷最小的虛擬機，并輸出分配的虛擬機向量。首先將虛擬機配置問題表示成 CSP問題，采用最佳優(yōu)先和剪枝的策略對其進行搜索求解。對于任一待擴展節(jié)點，如果到達該節(jié)點的路徑對應(yīng)的花費大于或等于最小花費值，則停止對該節(jié)點的擴展；否則，則繼續(xù)擴展該節(jié)點，若該節(jié)點是最后的葉節(jié)點，則更新最小花費的值；最終返回使花費最小的虛擬機分配向量。

4.1.2 算法偽代碼

算法偽代碼如下所示。

1) Input ∶ pmList,vmList, AE,wights

2) Output ∶ allocation vector of VM

3) minCost MAX

4) queue new priority_queue()

5) root new node()

6) queue.push(root)

7) while queue is not empty do

8) parent queue.top()

9) queue.pop()

10) cost estimateCost(root);

11) if cost ＞ = minCost then continue

12) app the next application in AE

13) if app == NULL then

14) minCost cost

15) else

16) foreach vm in vmList do

17) if constraints are satisfied then

18) allocate vm to app

19) child new node(root,app)

20) queue.push(child)

21) return allocation vector of VM that minimizes allocation cost

4.1.3 算法性能分析

在虛擬機配置模塊中，假定應(yīng)用程序數(shù)為m，預(yù)定義的虛擬機種類數(shù)為 c，對于每一類虛擬機都有一個允許被分配的最大數(shù)目，設(shè)d是所有這些最大數(shù)目中的最大值，則對于每個應(yīng)用程序，可以分配的虛擬機數(shù)量最多為cd；根據(jù)式(2)～式(8)可知，一共有3m+c+1個約束條件；根據(jù)RIVIN等人關(guān)于CSP代數(shù)求解的研究[27]，對于一個有n個變量，每個變量取值數(shù)為m以及M個約束條件的CSP問題，其算法復(fù)雜度為O(nm·2M-n)，故虛擬機配置模塊的算法復(fù)雜度為O (cdm·22mfc)。

4.2 虛擬機部署算法

4.2.1 算法描述

虛擬機部署算法的基本思想是為需要創(chuàng)建的虛擬機搜索能耗最小的物理主機分配向量，并輸出分配的物理主機向量。將虛擬機部署模塊也表示成CSP問題，采用最佳優(yōu)先和剪枝的策略來對其進行求解。在搜索前，首先需要對虛擬機分配向量進行重整，使之成為包含所有待分配虛擬機的簡單向量。在搜索中，對于任一待擴展節(jié)點，如果到達該節(jié)點的路徑對應(yīng)的能耗大于或等于最小能耗值，則停止對該節(jié)點的擴展；否則，則繼續(xù)擴展該節(jié)點，若該節(jié)點是最后的葉節(jié)點，則更新最小能耗的值，最終返回使能耗最小的虛擬機放置向量。

4.2.2 算法偽代碼

算法偽代碼如下所示。

1) Input ∶ pmList, allocation vector N, dyList

2) Output ∶ placement vector of VM

3) VM collapses(N) //collapses N into a single vector VM = (vm1,…, vmp)

4) minPower upperbound(pmList,VM,dyList)

5) queue new priority_queue()

6) root new node()

7) queue.push(root)

8) while queue is not empty do

9) parent queue.top()

10) queue.pop()

11) power = estimatePower(root);

12) if power ＞ = minPower then continue

13) vm the next virtual machine in VM

14) if vm == NULL then

15) minPower power

16) else

17) foreach pm in pmList do

18) if constraints are satisfied then

19) allocate vm to pm 20) child new node(root, pm)21) queue.push(child)

22) return placement vector of VM that minimizes power consumption

4.2.3 算法性能分析

在虛擬機部署模塊中，假定要被分配的虛擬機數(shù)為 p，物理機數(shù)為 n，則對于每一個物理機，最多只能部署p個要被分配的虛擬機；根據(jù)式(9)～式(12)可知，一共有4n個約束條件；根據(jù)RIVIN等人關(guān)于CSP代數(shù)求解的研究[27]，對于一個有n個變量，每個變量取值數(shù)為m以及M個約束條件的CSP問題，其算法復(fù)雜度為O(nm·2M-n)，故虛擬機部署模塊的算法復(fù)雜度為O(pn·8n)。

5 實驗與結(jié)果

5.1 算法模擬實現(xiàn)

為了驗證提出的模型和算法，本文進行了模擬實驗。在提出的模型中，虛擬機配置和部署問題均被定義為約束滿足問題，然后使用基于JAVA的約束編程CHOCO對它們進行建模和求解，模擬實驗按如下步驟進行。

1) 在應(yīng)用程序監(jiān)測模塊，根據(jù)應(yīng)用程序當前負載和SLA目標，獲得各應(yīng)用程序所需的資源量，同時設(shè)置或調(diào)整各應(yīng)用程序的權(quán)重。

2) 根據(jù)應(yīng)用程序監(jiān)測模塊的輸出，虛擬機配置模塊反復(fù)探求所有可能的虛擬機分配方案，找出平均花費最小的分配方案。

3) 根據(jù)虛擬機配置模塊的輸出，虛擬機部署模塊以最小化數(shù)據(jù)中心能耗為目標，將需要被分配的虛擬機部署到物理節(jié)點上。

4) 增加應(yīng)用程序的數(shù)量，預(yù)定義虛擬機的種類數(shù)量以及數(shù)據(jù)中心物理機的數(shù)量，重復(fù)步驟 1)～3)的過程。

下面分別列出虛擬機配置模塊和虛擬機部署模塊中模型中約束的實現(xiàn)方法。

(a)虛擬機配置模塊

約束式(2)：addConstraint(Choco.leq(Choco.sum(dualpos[i]),VMMAX[i]));

約束式(3)～式(5)：addConstraint(Choco.geq(ACPU[i],APCPU[i]));addConstraint(Choco.geq(AMEM[i],APRAM[i]));addConstraint(Choco.geq(ABW[i],APBW[i]));

約束式(6)～式(8)：addConstraint(Choco.leq(Choco.sum(ACPU),CPUMAX));addConstraint(Choco.leq(Choco.sum(AMEM),RAMMAX));addConstraint(Choco.leq(Choco.sum(ABW),BWMAX));

(b) 虛擬機部署模塊

約束式(9)～式(12)：addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMCPU),PMCPU[i]));addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMRAM),PMRAM[i]));addConstraint(Choco.leq(Choco.scalar(dualpos[i],VMBW),PMBW[i]));addConstraint(Choco.leq(Choco.plus(DYNAMICPower[i],PMSTAPOWER[i]), PMax[i]));

5.2 實驗環(huán)境和實驗數(shù)據(jù)

為了驗證提出的能耗優(yōu)化資源分配算法（DY，dynamicpower），在物理主機不同異構(gòu)性的情況下進行了一些模擬實驗，對提出的算法DY與已有的算法 MinPM[4]、FFD[22]、BFD[22]在性能和能耗兩方面進行了比較。本文在16組不同資源數(shù)量的環(huán)境下進行算法模擬實驗，每組模擬實驗中的虛擬機數(shù)和物理機的數(shù)量為：10×實驗組號，即 16組實驗中虛擬機數(shù)和物理機的數(shù)量分別為：10，20，30，…，160。而且，分別在物理主機的能耗異構(gòu)性不同的2種情況下進行實驗。其中能耗異構(gòu)性的大小是根據(jù)物理機上的能耗參數(shù)決定的，如果一組中各物理主機能耗參數(shù)相差越大，則該組物理機的異構(gòu)性越大。實驗中物理主機的能耗參數(shù)數(shù)據(jù)的生成規(guī)則如下。

1) 異構(gòu)性小的物理主機能耗參數(shù)設(shè)置

空閑能耗：100～300之間。將其分為100～150,150～200, 200～250, 250～300 4 組，依據(jù)物理主機的資源大小，選擇其中一個組，隨機生成數(shù)據(jù)，選擇原則一般依照：資源大的，能耗較小。以下選擇的原則相同。

最大能耗：1 000～2 000之間。將其分為1 000～1 250, 1 250～1 500, 1 500～1 750, 1 750～2 000 4 組，同樣依據(jù)物理機主機的資源大小，選擇其中一組，隨機生成數(shù)據(jù)。

2) 異構(gòu)性大的物理主機能耗參數(shù)設(shè)置

空閑能耗：100～500之間。將其分為100～200,200～300, 300～400, 400～500 4 組，依據(jù)物理主機的資源大小，選擇其中一組，隨機生成數(shù)據(jù)。

最大能耗：800～3 500之間。 將其分為800～1 500,1 500～2 200, 2 200～2 900, 2 900～3 600 4組，依據(jù)物理主機的資源大小，選擇其中一組，隨機生成數(shù)據(jù)。

另外，實驗中物理主機和虛擬機的資源大小參數(shù)的設(shè)置如下。

1) 物理主機的資源參數(shù)設(shè)置PMCPU：2 ～32 GHz //CPU；PMRAM：2～32 GB//內(nèi)存；PMBW：100～500 M//帶寬。

2) 物理主機的資源參數(shù)設(shè)置VMCPU：256 MHz～10 GHz//CPU；VMRAM：256 MB～10 GB//內(nèi)存；VMBW：30 ～120 M//帶寬。

5.3 實驗結(jié)果

圖4(a)～圖4(d)分別是物理主機能耗異構(gòu)小與異構(gòu)大 2種實驗環(huán)境下 DynamicPower(DY)、MinPM、FFD、BFD 4個算法資源分配的能耗情況。其中，縱坐標為能耗（單位為Wh），橫坐標為實驗編號。從圖4中可以看出，本文提出的能耗優(yōu)化資源分配算法DY和MinPM算法，隨著物理主機數(shù)和虛擬機數(shù)的增加，能耗的節(jié)省要優(yōu)于FFD和BFD算法，這主要是因為FFD和BFD只是尋求一個合理的資源分配解，而不是尋求能耗最優(yōu)的資源分配解。就DY和MinPM 2種算法而言，DY要優(yōu)于MinPM，因為DY算法考慮虛擬機動態(tài)能耗求得綜合能耗最小的資源分配方式，而 MinPM 僅僅是求物理主機數(shù)的最小值，所以DY算法得到的能耗始終是小于MinPM的能耗。將圖4(a)～圖4(d)對比可以看出，當物理機的異構(gòu)性越大時DY算法的能耗減少得更明顯。

為了更好地分析物理主機的能耗異構(gòu)性大小對資源分配結(jié)果的影響，下面給出2種異構(gòu)環(huán)境下的能耗節(jié)能的比例情況，見圖 5(a)和圖 5(b)。其中，圖 5(a)和圖 5(b)分別表示圖4中各組實驗中4種算法的能耗與最大能耗相比所節(jié)省的能耗百分比。從圖中可以看出，異構(gòu)性大的環(huán)境下DY算法節(jié)省的能耗均在50%左右，而異構(gòu)性小的環(huán)境下DY算法節(jié)省的能耗在40%左右，即異構(gòu)性小環(huán)境下節(jié)能百分比明顯大于異構(gòu)性大環(huán)境下節(jié)能百分比。

(a) 物理主機異構(gòu)小環(huán)境的能耗1

(b) 物理主機異構(gòu)小環(huán)境的能耗2

(c) 物理主機異構(gòu)大環(huán)境的能耗1

圖4 能耗比較

除了能耗優(yōu)化的考慮外，還需要考慮算法的運行效率的問題。圖6是圖4中各算法在各組實驗中所對應(yīng)的運行時間。

圖5 節(jié)能百分比

圖6 算法運行時間比較

圖6 (a)和圖6(b)分別表示圖4中各組實驗的運行時間，縱坐標為運行時間，單位為毫秒(ms)。從上圖中均可以看出，隨著物理主機和虛擬機數(shù)的增加，DY和MinPM算法在運行時間上有比較明顯的增加，而FFD和BFD 2種算法相比之下在運行效率上則具有很明顯的優(yōu)勢，尤其是在物理機和虛擬機數(shù)量增加的情況下，這種優(yōu)勢越加明顯。DY的運行效率則略優(yōu)于 MinPM 算法，在物理主機異構(gòu)性較大的情況，則DY的運行效率的優(yōu)勢更大，這主要是因為DY算法約束條件相比MinPM算法更多，搜索空間更小，所以求解更快。

6 結(jié)束語

本文主要研究在物理服務(wù)器異構(gòu)情況下的能耗優(yōu)化的資源調(diào)度問題。由于物理主機資源和能耗的異構(gòu)，不同種類的虛擬機分配到同一物理主機上產(chǎn)生的動態(tài)能耗也不同。此時，能耗優(yōu)化的問題并不是最小物理主機數(shù)。針對該問題，提出了一個基于CSP的能耗最優(yōu)的資源調(diào)度模型，該模型支持異構(gòu)應(yīng)用程序和工作負載，并且同時支持增加資源到單節(jié)點的垂直伸縮方式和增加節(jié)點數(shù)的水平伸縮方式。在該模型中，將虛擬機的資源配置從虛擬機的動態(tài)部署中分離出來。虛擬機的資源配置模塊旨在根據(jù)用戶 SLA要求確定代價最小化的資源配置方案，虛擬機的動態(tài)部署旨在最優(yōu)化數(shù)據(jù)中心的能源消耗。本文將這2個問題建模為約束滿足問題，采用約束規(guī)劃的方法求解該優(yōu)化問題。模擬實驗的結(jié)果驗證了本文提出的能耗最優(yōu)模型與算法的有效性。本文提出的模型和算法可以應(yīng)用到云數(shù)據(jù)中心，不僅可以減少云數(shù)據(jù)中心的能耗和經(jīng)營成外，而且這項工作還具有重要的社會意義，因為它可以減少現(xiàn)代IT基礎(chǔ)設(shè)施CO2的釋放量和能源的消耗量。

[1] BUYYA R, YEO C S, VENUGOPAL S. Market oriented cloud computing∶ vision, hype, and reality for delivering IT services as computing utilities[A]. HPCC’08[C]. Dalian, China, 2008. 5-13.

[2] BELOGLAZOY A, BUYYA R, LEE C Y, et al. A taxonomy and survey of energy-efficient data centers and cloud computing systems[J]. Advances in Computers, 2011,(82)∶47-111.

[3] GARG S K, YEO C S, ANANDSIVAM A, et al. Environmentconscious scheduling of HPC applications on distributed cloud-oriented data centers[J]. Journal of Parallel and Distributed Computing, 2011,71(6)∶ 732-749.

[4] BICHLER M, SETZER T, SPEITKAMP B. Capacity planning for virtualized servers[A]. WITS’06[C]. Milwaukee, Wisconsin, USA, 2006.1-6

[5] KHANNA G, BEATY K, KAR G, et al. Application performance management in virtualized server environments[A]. NOMS 2006[C].Vancouver, BC, 2006. 373-381.

[6] VERMA A, AHUJA P, NEOGI A. pMapper∶ power and migration cost aware application placement in virtualized systems[A]. Middleware'08 [C]. New York, NY, USA∶ Springer-Verlag, 2008. 243-264.

[7] HERMENIER F, LORCA X, MENAUD J M, et al. Entropy∶ a consolidation manager for cluster[A]. VEE’09[C]. New York, NY,USA∶ ACM, 2009. 41-50.

[8] RIETZ J, MACEDO R, ALVES C, et al. Efficient lower bounding procedures with application in the allocation of virtual machines to data centers[J]. WSEAS Transactions on Information Science And Applications, 2011, 4(8)∶157-170.

[9] BATU R R T, WHITE P. Fast approximate PCPs for multidimensional bin-packing problem[J]. Lecture Notes in Computer Science, 1999,1671∶245-256.

[10] TIAGO C F, MARCO A S N, RODRIGO N C, et al. Server consolidation with migration control for virtualized data centers[J].Future Generation Comp Syst, 2011, 27(8)∶ 1027-1034.

[11] VAN H N, TRAN F D, MENAUD J M. SLA-aware virtual resource management for cloud infrastructures[A]. CIT’09[C]. Washington DC,USA, 2009.357-362.

[12] VON LAZEWSKI G, WANG L, YOUNGE A J, et al. Power-aware scheduling of virtual machines in DVFS-enabled clusters[A].CLUSTER’09[C]. New Orleans, LA, USA, 2009.1-10.

[13] LIU L, WANG H, LIU X, et al. Greencloud∶ a new architecture for green data center[A]. ICAC-INDST '09[C]. New York, NY, USA,ACM, 2009.29-38.

[14] HARALICK R, ELLIOTT G. Increasing tree search efficiency for constraint satisfaction problems[J]. Artificial Intelligence, 1980, 14(3)∶263-313.

[15] JUSSIEN N, ROCHART G , LORCA X. The CHOCO constraint programming solver[A]. OSSICP’08[C]. Paris, France, 2008.

[16] SRIKANTAIAH S, KANSAL A, ZHAO F. Energy aware consolidation for cloud computing[A]. HotPower'08[C]. Berkeley, CA,USA, 2009. 1-15.

[17] BERL A, GELENBE E, GIROLAMO M, et al. Energy-efficient cloud computing[J]. The Computer Journal, 2010, 53(7)∶ 1045-1051.

[18] BELOGLAZOV A, BUYYA R. Energy efficient resource management in virtualized cloud data centers[A]. CCGRID ‘10[C]. Washington DC,USA, 2010. 826-831.

[19] RODERO I, JARAMILLO J, QUIROZ A. Energy-efficient application-aware online provisioning for virtualized clouds and data centers[A]. GREENCOMP’10[C]. Washington DC, USA, 2010.[20] 3A1B-4D5E.LSALAM H S, MALY K, KAMINSKY D. Analysis of energy efficiency in clouds[A]. Computationworld '09[C]. Washington DC,USA, 2009.416-422.

[21] YOUNGE A J, LASZEWSKI G , WANG L. Efficient resource management for Cloud computing environments[A]. GREENCOMP’10[C].Washington DC, USA, 2010. 357-364.

[22] CHANG F, REN J, VISWANATHAN R. Optimal resource allocation in clouds[A]. CLOUD’10[C]. Washington DC, USA, 2010. 418-425.

[23] LEE Y C, ZOMAYA A Y. Energy efficient utilization of resources in cloud computing systems[J]. The Journal of Supercomputing, 2012,60(2)∶ 268-280.

[24] KARMARKAR N, KARP R M. An efficient approximation scheme for the one-dimensional bin-packing problem[A]. FOCS’82[C].Washington DC, USA, 1982. 312-320.

[25] BELOGLAZOV A, ABAWAJY J H, BUYYA R. Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing[J]. Future Generation Comp Syst, 2012, 28(5)∶755-768.

[26] KUMAR V. Algorithms for constraint satisfaction problems∶ a survey[J]. AI Magazine, 1992, 13(1)∶ 32-44.

[27] RIVIN I, ZABIH R. An algebraic approach to constraint satisfaction problem[A]. IJCAI'89[C]. San Francisco, CA, USA, 1989. 284-289.