包簇框架中基于匈牙利算法的云計算能耗優化

陸 樂 陳世平,2

1(上海理工大學光電信息與計算機工程學院 上海 200093) 2(上海理工大學信息化辦公室 上海 200093)

0 引 言

云計算技術剛出現時，其主要方向是如何使其成為高性能計算的巨大數據中心，并通過按需使用來使得云服務商獲得報酬而從中獲利。然而，計算能力的日益普及也帶來了問題，特別是能源效率問題。

在為數據的處理、存儲和通信上，數據中心消耗了不可估量的能量，而消耗的能源對二氧化碳的消散具有巨大的影響，增加了溫室效應所形成的碳排放對生物和環境造成破壞性影響。據估計，世界總能源的約10%被互聯網消耗。數據中心的能源成本每五年翻一番。2011年，數據中心的能源消耗量約為10 000萬千瓦，已造成40 568 000噸的二氧化碳排放。另根據美國自然資源保護委員會(NRDC)的數據，到2020年將達到1 390億千瓦時[1]。

由此可知，在云計算中能耗問題是一個十分重要的研究方向,而對于能耗的優化，又有著不同的方向，例如計算機硬件的能源優化、虛擬化技術的提升、虛擬機放置策略以及云計算任務分配優化等。其中，虛擬機放置策略是非常重要的一個研究方向之一。現有的研究已經提出了一些十分有效的算法來實現虛擬機放置策略，用以提升服務器的使用率，從而使云計算更環保高效。

文獻[2]中提出了降低云計算基礎設施能耗的研究，該技術允許最大限度地減少物理服務器的數量，并允許虛擬機遷移到有限數量的服務器上，以便讓集中式物理服務器利用最大資源，將其他服務器設置為低功耗模式。然而該算法需要依靠許多參數例如CPU、內存和網絡帶寬等來判斷服務器過載或負載的時間。

此外，一般用于能耗優化算法的有能耗感知最佳適應遞減算法PABFD(Power Aware Best Fit Decreasing)[3]。PABFD算法的思想是按照當前CPU利用率的降序對所有虛擬機進行排序，然后將新虛擬機分配給物理機，從而使得物理機的能耗最小化。

啟發式算法也常常被用于解決此類問題。文獻[4]提出了一種適用于虛擬機放置策略的改進遺傳算法。文獻[5]使用模擬退火算法，文獻[6]使用粒子群算法進行節能的虛擬機放置。

除此之外，還有通過多目標的虛擬機放置策略來進行能耗優化。文獻[7]通過使用粒子群算法，使得不同資源得到有效利用，從而實現了能耗最小化。在文獻[8-9]中，通過使用遺傳算法來解決多目標虛擬機放置，盡可能減少了運行物理機的數量以及通信流量，同時最大化利用了數據中心內同時使用的不同資源。文獻[10]同樣使用了遺傳算法，通過最大限度地減少運行物理機數量并最大化資源使用效率來降低功耗。此外，文獻[11-12]中，還使用蟻群優化算法來最小化能耗、減少額外的資源浪費。文獻[13]通過蟻群算法重新放置虛擬機，以減少資源的能耗和負載平衡。在文獻[14]中，通過使用生物地理優化算法BBO(Biogeography-Based Optimization)來同時降低功耗、減少資源浪費、提升服務器均衡性，并減少了虛擬機間流量、存儲流量和遷移時間。

以上的研究方案均有以下的問題：其一是虛擬機與物理機的映射層次過于扁平，所有的映射關系都是在單個虛擬機與單個物理機之間進行，不但造成分配時間過長，而且一旦發生資源的變化，所有的映射關系都會重新分配。其二是能耗管理的靈活性不高，所有的能耗計算都是在物理機的基礎上計算，沒有更加高層次的精細化能耗管理方案，對于減少物理機集群節點的計算也不夠清晰。

基于以上的文獻總結，本文基于文獻[15]提出了一種新的云計算虛擬機放置策略——即包簇映射框架。在這個框架的基礎上，建立一個基于CPU使用率的能耗模型，并以最小化能耗為目標，通過不同的約束條件，使用改進的匈牙利算法進行虛擬機和物理機的高效分配，盡可能地提升分配速度并有效降低能耗，以滿足未來綠色云計算的趨勢。

1 問題描述

1.1 包簇概念

在包簇映射框架中，包(Package)和簇(Cluster)是兩個重要的概念，分別是對應虛擬機和物理機多級層次的抽象定義。在這里，把一個資源共享的虛擬機群組稱之為包，包的需求是需要根據云計算用戶的需求所定制的。同時，組成包的元素不僅僅是虛擬機，也可以是包，也即多個低級別的包可以被組成一個高級別的包。通過這樣的構建方式，可以由虛擬機、低級別包和高級別包組成一個具有清晰組織層次的需求結構。對簇來說也是一樣的定義，物理機組成低級別簇，低級別簇又可以組成高級別的簇，從而同樣組成一個多級別的層次結構。由此，虛擬機放置策略從原來的虛擬機與物理機之間扁平的映射關系轉換為包與簇之間的映射關系。這樣的好處就在于，把虛擬機與物理機之間的映射問題進一步降解規模，提高了虛擬機的分配效率以及資源共享，更易于實現對虛擬機和物理機的精細化管理。

1.2 包簇模型

有了以上的概述，就可以對包簇框架進行進一步定義。假設在包的層次結構中有一任意包γ，在包γ下可能存在M個虛擬機或子包v，在這里虛擬機或子包的數量限制為1≤v≤M。在包簇框架分配時，要將同級別的包γ分配給同級別的簇ρ，假設簇ρ下有M個服務器或子簇p，1≤p≤N。本文需要解決的是：在最小化能耗的前提下來將M個子包分配到N個子簇上，并且保證要使子包的子包(或虛擬機)映射到子簇的子簇(或物理機)上。

可以用一個資源分配矩陣表示包簇映射的框架關系：

(1)

式中：xv,p[t]代表在任意時間t中，子包v是否分配給子簇p。xv,p[t]=[1|0]也即xv,p[t]的取值只有0或1，當子包v分配給子簇p，則xv,p[t]=1，否則xv,p[t]=0。

在這里同時要求：

(2)

式(2)代表了在任意時間t內，每一個子包v都必須且只能分配一個子簇p上，但是一個子簇上可以承載多個子包，這是為了保證所有的需求包都可以獲取對應的資源。

此外，假設i代表一種資源，存在J種資源。這個資源代表了每一個子包所需的資源量，每一項代表一個類型，相應的子簇也同樣如此。

有了包簇映射的關系，還需要對其給予一些約束，即任意的子簇可用資源總量必須大于該子簇上所分配到的子包的需求總量：

(3)

式中:Rv,i[t]表示每一個子包v在時間t對資源i的需求總量。Ap,i[t]則表示每一個子簇p在時間t對資源i的可用總量，其中i=1,2,…,J。

1.3 能耗模型

服務器的能耗占數據中心的大部分總能耗，因此，本文的目標是最大限度地減少數據中心內所有物理機的總功耗。而物理機中的各個部分都會消耗功耗，如內存、網絡接口、磁盤存儲器、CPU、電源等，但能耗與CPU利用率之間存在線性關系[16-17]。所以可得：

Pph=k·Pmax+(1-k)·Pmax·uph,cpu

(4)

式中：Pph代表了物理機ph當前功率，k是空閑物理機運行所損耗功率的參數，Pmax則代表當前物理機在滿負荷的時候所產生的最大能耗，也即額定功率，uph,cpu代表CPU使用率，0≤uph,cpu≤1。當uph,cpu=1時，Pph=Pmax，即物理機能耗達到最大功率，即額定功率；當uph,cpu=0時，Pph=k·Pmax，代表達到物理機達到最小功率，即空閑功率。

但式(4)僅僅是用于表示物理機的能耗，在包簇框架下，任意一個簇包含了一個或多個子簇或服務器，每個服務器的CPU使用率是各不相同的，同時每一個CPU的k和Pmax又都有所差異，要滿足這些多樣化的條件，需要對式(4)做一些調整和補充：

(5)

式中:Pρ[t]代表在時間t中，子簇p的上層功率，當簇ρ是最底層簇時，直接使用物理機的能耗進行計算，kp代表物理機p的CPU運行時所損耗功率的參數，Pp,max代表物理機p在CPU滿負荷的時候所產生的最大能耗，up則代表物理機p的CPU使用率；當簇ρ不是最底層簇時，Pp代表子簇p的能耗，只需要將子簇p下的所有簇或物理機的能耗值相加，即可取得整個簇的能耗。

總能耗的公式為：

(6)

式中：t代表時間,1≤t≤T,M為子包V的個數，N為子簇W的個數，1≤V≤M,1≤W≤N。

在包簇框架下，包簇資源分配的目的就是使得能耗最小化：

(7)

約束條件為式(2)、式(3)。

可以看出，要使得能耗最小化，也就是盡可能降低CPU使用率，減少簇的個數，從而減少簇的能耗，同時又要保證每一個子包都分配到對應的子簇上，且需求的資源量沒有超過可用資源量。

2 基于包簇框架的虛擬機放置算法

2.1 匈牙利算法

匈牙利算法HM(Hungarian Method)一種用于解決多項式時間分配問題的組合優化算法。它的工作原理是將給定的成本矩陣(Costs Matrix)最小化為機會成本矩陣(Opportunity Costs Matrix)。如果能夠將成本矩陣最小化到每列和每行至少有一個0元素的程度，那么有可能做出更好的分配(機會成本都為0)。

匈牙利算法的一般數學模型是，存在N個資源，需要分配給N個對象，并保證總成本最低。公式如下：

Xi,j=[0|1]

(8)

式中:i=1,2,…,N,j=1,2,…,N，當Xi,j=0時，則說明資源i沒有分配給對象j，當Xi,j=1時，則說明資源i分配給對象j。

假設Ci,j是資源i分配給對象j的成本，那么數學模型可以表示為：

(9)

(10)

(11)

式(9)表示最小化資源分配給對象，式(10)和式(11)分別代表了一個資源只能分配給一個對象，且一個對象也只能接受一個資源，兩者之間是一一對應的關系。

對于匈牙利算法來說，雖然解決了分配問題，仍然存在以下問題：

(1) 分配問題，匈牙利算法只能是一個資源分配且只分配給一個對象，而在包簇映射框架中，多個包可以分配給一個簇；

(2) 匈牙利算法在大多數情況下是收斂的，但處理一些特殊情況，是無法找出最優解的，而且矩陣階數越多，越會存在不收斂的情況，在包簇映射框架中，高階分配矩陣是很常見的。

2.2 改進的匈牙利算法

根據上述的問題，本文參考了文獻[18]提出的快速降階匈牙利算法，在此基礎上通過改進算法，設計了改進的匈牙利算法IHM(Improved Hungarian Method)。

對于提出的第一個問題，在計算成本矩陣前，可以做如下的處理：

(1) 將成本矩陣的列數按照行數進行轉化，分割成一個行數和列數完全相等的矩陣。

(2) 如果分割的矩陣最后一個不滿足行數和列數相等，那么就用×補足。

而對于第二個問題，則需要對整個匈牙利算法進行改進：

(3) 逐行(列)的每個元素減去該行(列)最小值，如果步驟(2)中補足的是行，則順序相反。

(4) 逐行(列)檢查是否存在單獨的0元素，并且該0元素也是在列(行)上是單獨的0元素，如果存在，則選中它，并刪除該列和行的其他0元素。

(5) 如果同一行(列)存在0元素在其所在的列(行)是單獨的0元素，那么就進行如下步驟：

① 在其所在的列(行)中找到所有的次小元素，并找出最大值；

② 選中最大值所在的0元素，劃去所在的行和列；

③ 把剛才與其比較的行(列)減去自己行(列)的最小值。

(6) 如果列(行)存在單獨的0元素，而在行(列)上的其他0元素不是該列(行)上的單獨0元素，那么就選中這個0元素，劃去其他的0。

(7) 如果所有行(列)上，都不存在單獨的0元素，那么就任意選擇0元素最少的行(列)中的任意一個0，如果行(列)存在相同的情況，就進行列(行)的0元素個數對比，選擇最少的0元素。

(8) 重復步驟(3)至(7)，直到找出所有的0。

2.3 實例驗證

由于在包簇映射的框架中，經常會遇到包多于簇的情況發生(也即虛擬機的個數永遠大于等于物理機的個數)，現假定有7個包要分配到5個簇上，并且能夠保證5個簇上的資源足夠能滿足7個包所需要的資源(上層包簇所分配的必要條件)，它們之間的能耗矩陣如表1所示。

表1 分配7個包給5個簇的能耗矩陣

首先轉換為成本矩陣：

并用×元素補齊第二個矩陣中缺失的部分：

接下來對兩個矩陣進行改進的匈牙利算法求解：

矩陣1：

矩陣2：

所以，最后的分配方案為：

方案1：包1分配給簇5；包2分配給簇1；包3分配給簇2；包4分配給簇4；包5分配給簇3；包6分配給簇1；包7分配給簇4；

方案2：包1分配給簇5；包2分配給簇1；包3分配給簇4；包4分配給簇2；包5分配給簇3；包6分配給簇1；包7分配給簇4。

3 相關實驗

3.1 能耗模型

在進行實驗前，首先需要計算出式(4)中的Pmax和k。通過觀察可發現，兩者都是定值，也即k·Pmax代表了空閑功率。根據文獻[19]可知如下參數，表2是CPU類型為Intel Core 2 Duo 2.93 GHz 和Intel Core i5 2.5 GHz的服務器的能耗值，單位為W。

表2 不同CPU的服務器參數

3.2 仿真實驗

為了驗證本文IHM算法的有效性，在Cloudsim[20]上進行仿真實驗。要對比的算法分別是：基于包簇映射框架下改進的匈牙利算法IHMPC(Improved Hungarian Method based on Package-Cluster)，在引言中所提及的能耗感知最佳適應遞減算PABFD(Power Aware Best Fit Decreasing)[3]，以及混合遺傳算法HGA(Hybrid Genetic Algorithm)[4]。

實驗主要分為兩部分，實驗1是驗證三種算法的分配時間；實驗2是驗證三種算法在相同時間內的CPU使用率以及能耗變化情況。

實驗1分配時間

分別用不同數量的虛擬機和物理機進行分配時間的測試。在IHMPC算法中，包簇映射的層次結構為3層結構，頂層包之下各有10個包，二級包下的虛擬機個數分配為虛擬機總個數除以10；簇的分配個數比包少一半，但層次結構相同。例如，500臺虛擬機分配到150臺服務器上，包簇結構為1個頂層包，10個二級包，50個虛擬機；1個頂層簇，5個二級簇，50個服務器。

圖1是三種算法在不同虛擬機和服務器個數的情況下的分配時間。可以看出，前兩種算法在虛擬機和服務器數量變多的情況下，分配時間也逐漸變多，而IHMPC始終保持了比較良好的分配時間，在虛擬機數量、服務器數量超過600/220臺時，平均比PABFD算法快了將近56.2%，比HGA算法快了將近34.8%。

實驗2CPU使用率以及能耗

為了更好地模擬數據中心的龐大數據量，在實驗2中模擬了10 000臺服務器和15 000臺虛擬機。需要特別說明的是，在包簇映射框架下，需要對包的結構層次進行劃分，分為5層包結構，如圖2所示。

本次實驗共劃分了1個頂層包、3個二級包、5個三級包、10個四級包，在這里的四級包又稱為底層包，每一個底層包中又包含了100臺虛擬機。相應地，簇結構也要劃分為2個二級簇、10個三級簇、10個四級簇，每一個底層簇又包含了50個服務器。

圖3是在不同時間下，三者算法的CPU使用率，可以看出，在相同的條件下，本文提出的IHMPC算法，由于能夠使虛擬機較為平均地放置在物理機上，與前兩者相比，在CPU使用率上始終不超過68%，較好地保持了在較低的水平，實現了負載均衡。

圖4是在不同時間下，三者算法的能耗值曲線圖。從圖中可以看出，由于保持了較低的CPU使用率，使得改進算法的總能耗也比前兩種算法功耗更少，尤其在25分鐘至50分鐘左右的CPU使用高峰時段，平均比PABFD算法的總能耗降低了4.8%，比HGA算法的總能耗降低了3.7%。這證明所提出的IHMPC算法在能耗優化上有明顯的優勢，也滿足了云計算中虛擬機的快速分配以及服務器的負載均衡。

圖3 不同時間下的CPU使用率

圖4 不同時間下的能耗值

4 結 語

本文首先沿用了一種新的虛擬機放置策略，即基于包簇映射框架的資源分配結構，在此基礎上，設計了能耗模型和改進的匈牙利算法來進行能耗優化。所提出的算法同時滿足了分配速度和能耗。在虛擬機和物理機數量巨大的情況下，數據中心依然能夠較快地完成分配。在能耗上，始終保持CPU使用率在一個較平均的水平，以達到降低能耗的目標。實驗結果表明，與其他算法相比，該算法在相同條件下可以大大降低云計算系統的能耗。