魏振春， 朱 賽， 衛(wèi) 星， 韓江洪

（1.合肥工業(yè)大學 計算機與信息學院，安徽 合肥 230009；2.安全關鍵工業(yè)測控技術教育部工程研究中心，安徽 合肥 230009）

云計算被認為是下一代的IT服務模式，受到學術界和工業(yè)界的巨大關注［1］。社會對云計算需求的不斷擴大需要構建規(guī)模巨大的數(shù)據(jù)中心，而維護其運行需要大量的能量［2］。如何高能效地運行數(shù)據(jù)中心是一個亟待解決的問題。

目前，分布式并行計算系統(tǒng)的能耗優(yōu)化管理技術主要包括3類：關閉／休眠技術（resource hibernation）、電壓動態(tài)調整技術（dynamic voltage scaling，DVS）和虛擬化技術（virtualization）［3－4］。

關閉／休眠技術的相關研究通常是針對計算機或處理部件的關閉／休眠時機進行設定或預測。但是對于包含有眾多計算資源的云計算系統(tǒng)，如何根據(jù)單位時間到達的任務量決定要關閉的計算機數(shù)量以及關閉哪些計算機等問題，都給關閉／休眠技術賦予了新的研究難題。

電壓動態(tài)調整技術的核心思想是通過動態(tài)調整電壓使同一處理器具有不同的功率／性能“擋位”，用不同的“擋位”來處理不同類型、不同計算量的任務，在降低執(zhí)行能耗的同時又保證了執(zhí)行性能。但是在云計算系統(tǒng)中，電壓動態(tài)調整技術遇到以下幾個問題：① 計算任務到達的隨機性，難以預測下一個到達任務的類型；② 即使知道了任務類型，也很難準確分析該任務所適合的處理器電壓“擋位”；③ 電壓動態(tài)調整技術主要是用來降低計算機中處理器的能耗，對整臺計算機或整個云計算系統(tǒng)的能耗優(yōu)化存在一定的局限性。

虛擬化技術，特別是深層次的虛擬化本身也要付出高昂的效能代價，因為虛擬化技術是對底層硬件部件到高層服務應用的層層虛擬，每一級的虛擬都造成了效能的損失。

上述3種策略在節(jié)能方面都有一定的作用，但也有各自的不足，同時其節(jié)能效果也不明顯，因此本文針對云計算系統(tǒng)中的能耗浪費問題，從服務模式切換入手找出數(shù)據(jù)中心中的最優(yōu)離線調度算法。

1 模型建立

服務器的能耗包括操作能耗和切換能耗［5］。分配有工作負載的服務器處于活躍模式，沒有工作分配的服務器處于節(jié)能模式。為了使操作能耗最小化，服務器應盡可能處于空閑模式，這種操作稱為“關閉”。同時因為存在切換能耗，為了使總能耗最小化，服務器狀態(tài)切換不應太頻繁。因此，需要一種平衡使總能耗最小。

研究具有N臺同構服務器（每臺服務器具有相同容量C，即在一個時隙內服務器可承擔的最大工作數(shù)）的數(shù)據(jù)中心［6］。每個時隙開始時會估算平均負載并為每臺服務器調整負載分配。定義時間片t時的負載為λt，考慮T周期內，初始工作負載為λ0，結束工作負載為λT；服務器具有相同的操作能耗函數(shù)f（λ），其中λ∈［0，C］是分配的工作負載，并且有相同的切換能耗系數(shù)βon≥0、βoff≥0來打開或關閉服務器。服務器數(shù)量充足，即λt≤NC。對于每個時隙t，需要確定活躍服務器的數(shù)量xt和分配給第i臺服務器的負載λt，i，其中

記xt等于正的λt，i的數(shù)量，因而有：

其中，I（e）表示如果事件e發(fā)生，值為1，否則為0。因為λ0＝λT＞0且根據(jù)（1）式有：

并且根據(jù)（2）式有：

定義：

其中，t∈［0，T］；xton為在t時切換到打開狀態(tài)（即從空閑模式切換到活躍模式）服務器的數(shù)量。同時定義：

其中，t∈［0，T］；xtoff為t時切換到關閉狀態(tài)（即從活躍模式切換到空閑模式）服務器的數(shù)量。因此可以得到：

其中，λt，i為連續(xù)變量為整數(shù)變量；T、N、βon、βoff、λt、C 和λT，i等于0；x0＝xT＝0。

由于（7）式中雙重疊加過于煩瑣，下面將通過等量替換和數(shù)學推導來對其進行簡化。

首先定義標準化工作負載和一個新的能耗函數(shù)為：

其中，xλ，t為λt工作負載下的最小服務器數(shù)（不一定為整數(shù)）；θt，i為t時隙下第i臺服務器所承擔的工作負載占其所能承受最大負載的百分比；g（0）＝0。

將目標函數(shù)（7）式重新寫作：

其中，第1部分為所有服務器的操作能耗；第2部分為服務器的切換能耗。根據(jù)（8）式，第1部分重新改寫為：

由于g（0）＝0，且根據(jù)（3）式λT，i＝0，操作能耗可以重寫為：

其中，TNf（0）為一個常數(shù)，可以省略。根據(jù)（4）式x1off＝0且xoTn＝0，得到βoffx1off＝0和βonxoTn＝0。切換能耗可以改寫為：

由于g（x）是凸函數(shù)，對于每個處于活躍狀態(tài)的服務器，當θt，i＝xλ，t／xt時，對xt＞0有：

于是目標函數(shù)的操作能耗可以重寫為：

得到簡化后的目標函數(shù)為：

2 模型最優(yōu)特性分析

2.1 無切換成本的最優(yōu)解

首先考慮特殊情況，βon＝βoff＝0（無切換成本）。這種情況的結論可用于研究βon，βoff≥0時（一般情況下）的最優(yōu)算法。記

由于g（x）、F（x）都是凸函數(shù)，因而操作能耗可寫為：

進而問題變?yōu)椋?/p>

其中，xt為整數(shù)變量；T、xλ，t、N 為常量。這個問題可以拆成對于每個xt的T－1的子問題。對于xt的子問題，1≤t≤T－1，則有：

其中，xt為整數(shù)變量；xλ，t、N 為常量。

由于F（x）是凸函數(shù)，可以定義一個真值xF使在 x∈ ［1 ，N／xλ，t］區(qū) 間 內F（x）最 小，因 而，xFxλ，t使F （x／ xλ，t）在x∈［xλ，t，N］內最小。有最優(yōu)解，在約束條件下是綁定于xλ，t和N 的整數(shù)，特別有以下3種情況：① 當xFxλ，t≤xλ，t，則最優(yōu)解；② 當xFxλ，t＝N，則最優(yōu)解為xt＊＝N；③ 當xλ，t＜xFxλ，t＜N，則最優(yōu)解為xFxλ，t或xFxλ，t。

于λt，所以只取決于λt，以上解均為在線解。

2.2 最優(yōu)特性分析

一般地，即βon，βoff≥0時，考慮和

以上引理可以通過反證法證明。

根據(jù)以上引理，最優(yōu)解可描述為：必然存在一個整數(shù)τ≥0，使，因為在此周期內）曲線跟隨）曲線，所以稱［0，τ］是“跟隨”周期。

最優(yōu)解示例如圖1所示，其中τ＝1，跟隨區(qū)間為［0，1］。如果，由引理1可知，在和之間。根據(jù)引理2，可得到，直到這條平整線在時間處與曲線相交，即和在的不同側，則稱［τ＋1，］為“平周期”；圖1中，＝3時平區(qū)間為［2，3］。根據(jù)引理3必是和之間的值。如果，可以得到下一個跟隨區(qū)間和下一個平周期。否則將得到下一個平周期，如圖1中的下一個平周期［4，5］。由此將會得到許多跟隨周期和平周期，其中最后一個周期是跟隨周期，因為在t＝T時刻，圖1中得到的最后一個跟隨周期為［6，9］。

圖1 最優(yōu)解示例

根據(jù)以上3條引理，可得到從t＝T到t＝0時間段內最優(yōu)曲線）與曲線的關系。首先得到一個跟隨周期t∈［τ，T］，當t＝T時，；若，則，直到這條平整線與）曲線相交于點。［，τ－1］為一個平周期。同理得到下一個跟隨周期和平周期，最后的周期是跟隨周期，因為在t＝0時。

3 基于整數(shù)規(guī)劃的最優(yōu)算法

考慮λt（1≤t≤T）值是已知前提下設計的最優(yōu)算法［8］。

3.1 基于動態(tài)規(guī)劃的最優(yōu)離線算法

設計一個基于動態(tài)規(guī)劃的最優(yōu)離線算法，它伴隨著一個遞歸過程。定義一組子問題：在給定工作負載λτ和指定結束xt＝h≥xλ，t的條件下，考慮關于τ∈［0，t］上最小化整體能耗的子問題。定義這個子問題的整體最小能耗為c（t，h），其中t為系統(tǒng)運行到的當前時刻，h為在系統(tǒng)運行到t時刻時處于活躍狀態(tài)的服務器數(shù)量。對于目標問題，在（4）式中有xT＝0，因此目標問題的整體最小能耗定義為c（T，0）。

3.1.1 證明c（T，0）的遞推公式

根據(jù)（14）式和λT＝0，有，則定義t1為使（15）式成立的最小值。

圖2 計算c（T，0）時存在的2種情況

如果是情況①，整體能耗的最小值在t∈［0，t1］內為。對于t∈［t1，T］，有，因而可以計算出整體能耗（不包括t1時刻的操作能耗，因為此能耗已在中被計算過）。

如果是情況②，定義1是t∈［1，t1］上的最大值，故

由于，所以此1一直存在；進而可證明在t∈［1＋1，τ1－1］上。因此根據(jù)引理5有。但是由于，根據(jù)引理4（或引理6）可能不等于，也就是說平周期在1處結束，則可以認為（16）式中定義的1是高度為h1的平高線與曲線的交點。x?1的值固定為h1時，在區(qū)間上的整體能耗最小值為。由于在上且t∈［τ1，T］上，可計算出上的整體總能耗（不包括τ1時的操作能耗，因為此能耗已在c（1，h1）中被計算過），此能耗計作c（?1，h1），（T，0），因而有：

c（T，0）＝c（1，h1）＋c（1，h1），（T，0）。同時考慮2種情況，則有：

實際可以將情況① 和② 整合，因為前者是后者的特殊情況。由于1是根據(jù)定義的，且在（16）式中等于t1，則（17）式可以寫成：

（18）式給出了若干基于一些c（1，h1）值計算c（T，0）的遞推方法。

3.1.2 計算（18）式中特定的c1，h1）

定義t2為使（19）式成立的最小值，即

在c1，h1）的最優(yōu)解中必會出現(xiàn)以下2種情況之一：① 對于所有的，如圖3a所示；② 存在一個τ2∈［t2＋11－1］和，使得對于t∈［τ2，1－1］有，且，如圖3b所示。

如果是情況①，xt2固定為時，在t∈［0，t2］內總能耗的最小值為。由于在t∈［t2，1－1］上且1＜h1，可以計算出t∈［t2，1］上的總能耗（不包括t2時刻的操作能耗，此能耗已在）上被計算過）。

圖3 計算c1，h1）時存在的2種情況

如果是情況②，可以證明對于任意的h2＞都不能產(chǎn)生出最優(yōu)解。由于，定義2是［1，t2］上的最大值，使得：

綜合以上2種情況得：

（21）式給出了一個基于c（2，h2）值計算c1，h1）的遞推方法，其中h2和2已通過（20）式被定義。

3.1.3 其余步驟

若一些c2，h2）的值被確定，（21）式給出的計算c1，h1）的遞推公式可以繼續(xù)遞推過程。當需要確定在時ck，hk）的值時，過程終止，并且可以發(fā)現(xiàn)。對于這種情況，很容易證明在t∈［1，－1］上c（，hk）的最優(yōu)解是，且，因為此解使操作能耗和切換能耗同時最小。求出此解的總體能耗，由此得到c（，hk）值，終止遞推過程。

3.2 消除遞推過程

首先假設在c（T，0）的計算過程中所有的c（t，h）值都是確定的，整個遞推過程需要得到一些c（t，h）的值。t∈［1，t1］滿足以下3種情況中的一種：或。因此，對于一個特定的t，如果，則不用計算任何c（t，h）的值；如果，需要計算h∈上c（t，h）的值；如果，需要計算上c（t，h）的值。算法如下：

（3）對于（t＝1；t≤U1；t＋＋），若，計算c（t，h），，其中［1，t－1］，且。

（4）對于（t＝U1＋1；t≤UK；t＋＋），若，根據(jù)給定的c（·，·）計算c（t，h），其中h∈］，如（17）式；若，根據(jù)給定的c（·，·）計算c（t，h），其中如（20）式。

（5）根據(jù)給定的c（·，·）和（17）式計算c（T，0）。

記Li和Ui分別為第i時刻的局部最小和最大點，則有和。假設有K個局部最大點，則有K－1個局部最小點，且0＜U1＜L1＜…＜Lk－1＜Uk＝t1＜T。考慮被這些極點分割出的小的時間周期，對于第1個周期t∈［1，U1］，根據(jù)最優(yōu)算法，h可以是［1，］中的任意值，且每個h對應唯一一個t′，因此t∈［1，U1］上要計算的c（t，h）的數(shù)目為。對于第2個周期t∈［U1＋1，L1］，根據(jù)最優(yōu)算法，h可以是］范圍內的任意值，且每個h對應唯一一個t，因此t∈［U1＋1，L1］上要計算的c（t，h）的數(shù)目為。同理，t∈［Uk－1＋1，Lk－1］上是；上是。于是c（t，h）要被計算的總次數(shù)為：）＋…＋＋?？梢娺@仍是離線算法的空間復雜度。

在計算c（t，h）過程中，具有不同高度的平周期。由于h在［1，N］范圍內，這些高度最大個數(shù)為N，因此，計算c（t，h）的過程具有O（N）復雜度，所以總體復雜度O（KN）O（N）＝O（KN2），其中，K＜T為t∈［1，T］中局部最大點的數(shù)目。

4 數(shù)值分析及結果

仿真平臺使用C＃開發(fā)，根據(jù)設定的服務器數(shù)量和時間片數(shù)隨機生成工作量，并通過最優(yōu)離線算法給出服務器最優(yōu)配置策略。采用文獻［9］中的能耗定義，操作能耗函數(shù)為：

f（λ）＝λmax ｛1／（1－λ）－1.5，0｝＋1，

切換能耗系數(shù)為βon＝βoff＝6，服務器容量C＝1，工作量λt的取值范圍為［1，N］。

設定時間片數(shù)T＝100、服務器數(shù)N＝100，得到圖4所示的2組計算結果。

圖4 不同負載變化情況下活躍服務器數(shù)

圖4a中工作量變化比較平穩(wěn)，圖4b中工作量變化幅度較大。

由圖4可以看出，在工作量不同的情況下，都能夠通過本文算法得到更加平穩(wěn)的活躍服務器曲線，有效減少了服務器之間的切換量。

每個時間片結束時對應的能耗曲線如圖5所示。由圖5可以看出，使用離線算法后，數(shù)據(jù)中心服務器能耗明顯降低，通過對不同負載變化情況對比可知，當工作量變化幅度較大時，離線算法的優(yōu)化效果更為明顯。

圖6所示為平穩(wěn)工作負載和波動工作負載2種情況下總能耗及各種情況下切換能耗和操作能耗所占比例，可見負載波動較大情況下，經(jīng)離線算法優(yōu)化后切換能耗減少更為明顯。

圖5 不同負載變化情況各時間片能耗曲線

圖6 不同情況下的能耗比例

5 結束語

本文研究了通過調節(jié)服務器模式切換來最小化數(shù)據(jù)中心的能耗并提高數(shù)據(jù)中心的服務質量。首先，建立了數(shù)據(jù)中心能耗最小化模型，包括操作能耗和切換能耗；然后分析了最優(yōu)解的性質，并將這些性質應用到最優(yōu)算法的設計中，得到了一個基于動態(tài)規(guī)劃的離線算法，進而得到具有多項式復雜度的最優(yōu)離線算法。此算法不但降低了算法的空間復雜度，同時符合活躍服務器數(shù)量需為整數(shù)的要求。本文研究的是已知工作負載前提下的最優(yōu)算法，可為未知負載算法的研究提供參考。

［1］ Barroso L A，H¨olzle U.The case for energy－proportional computing［J］.IEEE Computer，2007，40（12）：33－37.

［2］ Li J，Shuang K，Su S，et al.Reducing operational costs through consolidation with resource prediction in the cloud［C］／／IEEE International Symposium on Cluster Computing and the Grid.IEEE，2012：793－798.

［3］ Beloglazov A，Buyya R，Lee Y C，et al.A taxonomy and survey of energy－efficient data centers and cloud computing systems［J］.Advances in Computers，2011，82（2）：47－111.

［4］ Gandhi A，Gupta V，Harchol－Balter M，et al.Optimality analysis of energy－performance trade－off for server farm management［J］.Performance Evaluation，2010，67（11）：1155－1171.

［5］ Guenter B，Jain N，Williams C.Managing cost，performance，and reliability tradeoffs for energy－aware server provisioning［C］／／International Conference on Computer Communications.IEEE，2011：1332－1340.

［6］ Guo Y，Member S，F(xiàn)ang Y.Electricity cost saving strategy in data centers by using energy storage［J］.IEEE Transactions on Parallel and Distributed Systems，2013，24（6）：1149－1160.

［7］ Garey M R，Johnson D S.Computers and intractability；a guide to the theory of NP－completeness［M］.San Francisco：W H Freeman and Company，1990：204－215.

［8］ Lin M，Liu Z，Wierman A，et al.Online algorithms for geographical load balancing［C］／／International Green Computing Conference.IEEE，2012：1－10.

［9］ Lin M，Wierman A，Andrew L L H，et al.Dynamic rightsizing for power－proportional data centers［J］.IEEE／ACM Transactions on Networking，2013，21（5）：1378－1391.