楊 波，陳智俐，杜瑞鋒，劉文彬

（湖南財政經(jīng)濟學院信息管理系，湖南長沙410205）

組合能耗優(yōu)化與QoS的異構(gòu)集群負載分配方法

楊 波，陳智俐，杜瑞鋒，劉文彬

（湖南財政經(jīng)濟學院信息管理系，湖南長沙410205）

計算能效比的異構(gòu)性使得集群系統(tǒng)在進行任務分配時，權(quán)衡服務質(zhì)量與能耗優(yōu)化變得更復雜.為此，針對異構(gòu)集群的任務分配問題，建立能耗優(yōu)化任務分配模型，然后提出一個任務分配算法(LAOE算法)，該算法在不違背任務最大平均響應時間的前提下，將任務優(yōu)先分配到能效比最高的服務器.實驗結(jié)果表明：LAOE算法能顯著節(jié)省能耗，并能保持相對穩(wěn)定的平均響應時間，具有更廣泛的異構(gòu)環(huán)境適應性及計算復雜度開銷小等優(yōu)點.

異構(gòu)集群；計算能效比；能耗優(yōu)化；任務分配

隨著大數(shù)據(jù)時代的到來，僅僅依靠幾臺強大的服務器去完成大數(shù)據(jù)這座金礦的開采，已經(jīng)成為歷史.當前，對大數(shù)據(jù)的處理大多是由集群計算系統(tǒng)通過任務的并行化來加速完成的，如以數(shù)據(jù)中心、網(wǎng)格等為代表的此類系統(tǒng).它們通常是由一些廉價的工作站或服務器組成，從幾十臺到上千臺不等[1].但由此帶來一個不可回避的問題，集群計算系統(tǒng)的能耗開銷已成為最大運營成本[2-3].高的能源消耗不僅提高了計算成本，還會引發(fā)系統(tǒng)的不穩(wěn)定和環(huán)境的污染.提倡綠色計算，是經(jīng)濟可持續(xù)發(fā)展的需要，因此，能耗問題已成為時下最熱門的研究問題之一.

集群計算平臺在初建時，采購的基礎(chǔ)設備基本都是相同的，但是隨著發(fā)展，必然會依次進行設備更新，長期來看，集群計算系統(tǒng)的基礎(chǔ)運營環(huán)境必然是異構(gòu)的.當前，集群能耗方面的研究主要集中在從虛擬機配置角度進行能耗優(yōu)化[4-5]、采用動態(tài)電壓/頻率調(diào)節(jié)方法優(yōu)化能耗[6-7]、采用動態(tài)開啟/關(guān)閉服務器的方法節(jié)省能耗[8-9]等這幾個方面.它們的研究背景在假設異構(gòu)時，都認為設備是基于同代技術(shù)生產(chǎn)的產(chǎn)品，而事實上分布式計算集群的異構(gòu)是一個更廣泛的概念，其中就包括不同代技術(shù)所生產(chǎn)的產(chǎn)品的異構(gòu)性，而且是廣泛存在的.眾所周知，不同代技術(shù)或生產(chǎn)工藝生產(chǎn)的產(chǎn)品，擁有不同的能效比，先進技術(shù)或工藝使單位能耗可提供更多的計算能力[10].如直接采用以同代技術(shù)（具有相同能效比）為應用背景的節(jié)能方法來處理以異構(gòu)能效比為應用背景的集群系統(tǒng)能耗優(yōu)化問題，將難獲得令人滿意的效果.系統(tǒng)的服務質(zhì)量（QualityofService，QoS）將影響到用戶的體驗感，而能耗則直接影響到系統(tǒng)的成本，以較低的運營成本獲得較好的系統(tǒng)響應時間是當前集群計算提供機構(gòu)所追求的目標.因此，本文將以異構(gòu)能效比為應用環(huán)境，結(jié)合服務質(zhì)量，設計一個任務分配算法來優(yōu)化異構(gòu)集群計算系統(tǒng)的能耗.

1 系統(tǒng)模型

1.1 任務調(diào)度模型

任務分配模型如圖1所示，采用集中任務分配模式，由任務調(diào)度器來決定任務在各個服務器上的分配，在本文采用M/G/1排隊模型來模擬各個服務器節(jié)點，其任務到達率服從泊松分布，服務器處理時間服從任意的概率分布.之所以選擇該排隊模型，是因為該模型比較貼近集群系統(tǒng)的任務特性，在一定的時間段期間，任務的到達率是符合泊松分布原理的，也就是說到達時間不確定，但是均值是固定的；同時，不同的任務對系統(tǒng)資源的需求也是差異化的，如對CPU、I/O等資源的需求不同，會導致它們在服務器上的處理時間也不同，故模型中服務器的處理時間服從任意概率分布.本文假設任務是彼此不相關(guān)的，即所有任務可以獨立并行運行.

圖1 任務調(diào)度模型

其中hi與ρi分別為服務器i的平均處理時間和平均負載率，var(T)為服務器i的處理時間方差.當服務器的服務時間概率分布確定后，由式（1）很容易求出服務器節(jié)點的任務平均響應時間.設系統(tǒng)中總的任務到達率為λ,它等于分布在各個服務器上的任務之和，表示如下：

1.2 服務器能耗模型

處理器的功率主要由空閑功率與運行功率組成，空閑功率主要用于維持處理器處于準備狀態(tài)，運行功率是指當有負載加載在處理器時的功率.在服務器中，功耗主要產(chǎn)生在處理器、內(nèi)存以及IO設備中，而內(nèi)存和IO設備所產(chǎn)生的功率都與處理器的功率模型相近，故第i個服務器能耗模型表示如下：

其中ρi為服務器上所接納的任務量與處理速率的比值，即負載率.式（3）右邊的第一項表示空閑功率，第二項為運行時功率.

2 問題描述

處理器所消耗的能耗與處理器的功率和使用時間是成正比的，即E=P×t,這意味著完成相同的任務，如果能夠減少時間開銷或者降低功率，就可以達到減少能耗的目的.本文所采用的排隊模型，考慮的任務量都是在一個固定時間段內(nèi)的平均到達率，處理速率也是在一個固定時間下的平均處理速率，即意味著，在本文的系統(tǒng)模型下，時間是一個固定值.從式（3）可知負載的分配方案能夠影響到功率的取值，進而影響到系統(tǒng)的能耗，故問題可以用如下的公式來表示：

約束于：

式(5)是一個守恒約束，分配到各服務器的任務量與任務總量相等.其中，TQoS為保證QoS的最大平均響應時間，式(6)是保證服務質(zhì)量的約束，約定了每個服務節(jié)點所能接納的最大服務數(shù)量.

3 任務分配算法

3.1 服務器處理時間計算

在執(zhí)行任務分配之前，需要知道各個服務器的平均處理速率，有必要統(tǒng)計出各個服務器處理時間的均值與方差，但是，它們的計算與集群系統(tǒng)所處理的任務特征有一定的相互關(guān)聯(lián)，任務的特征不同對計算資源的需求也是不同的，因此，在同一臺服務器上，不同的任務完成時間是不相同的.在本文，對任務的分類采用k-means方法，設任務i的特征表示為si(cpu,memory,io),分別表示任務占用的處理器、內(nèi)存、I/O的量.C=(c1,c2,...,ck)表示任務的特征種類，當任務i屬于cl時，則任務i為第l類特征任務.對于k-means方法來說，就是使下式的值最?。?/p>

假定在服務器 j上，種類為cl的任務出現(xiàn)的概率為因此服務器 j有在本文設中央調(diào)度器采用一定的概率（概率的計算將在下節(jié)給出），將任務隨機分發(fā)到各個服務節(jié)點，在分發(fā)的過程中并不考慮任務的種類，因此可認為同種任務在各個服務器上的分布概率是相同的.在獲得任務的種類之后，再在各服務器上測試各種類任務的運行時間，由全概率公式就可求得各服務器處理時間的均值E(T)及方差var(T),進而由均值E(T)計算出各個服務器的平均處理速率

3.2 算法設計

由系統(tǒng)模型的中央控制特性所決定，本文所設計的任務分配方法將是一個中心控制算法.首先由中央調(diào)度器接納所有的任務，然后采用適合的分配策略將任務分配到各個服務節(jié)點.其任務分配目標是使得系統(tǒng)在完成所有任務時，所消費的總能耗最少，同時又能保證一定的服務質(zhì)量.在問題描述中，定義的問題是一個帶不等式的線性歸劃問題，直接求解，計算成本較高，因而有必要考慮一個近似求解方法.

基于能耗的最優(yōu)化目標來分配任務，一個最樸素的方法，就是將任務分配到能效比最高的機器上來執(zhí)行任務.因此，在進行任務分配前，首先要考慮所有服務節(jié)點的單位能效比，即消耗單位能量所能夠提供的處理速率，例如第i個服務節(jié)點的單位能效比表示為將各個服務節(jié)點按能效比進行降序排序，也就是說如果有 i＜j，那必有接著計算每個服務器節(jié)點在保證最大任務響應時間的情況下，可以接納的最大任務量；然后將任務按順序依次分配到各服務節(jié)點，每個服務節(jié)點所獲得的最大任務量不能超過該服務節(jié)點的最大接納量，直到將所有的任務分配完畢.基于上述分析，本文將提出的算法命名為LAOE算法（loadallocationofenergy-awarealgorithm），具體過程描述如下：

LAOEAlgorithm

Input:λ,系統(tǒng)的總?cè)蝿盏竭_率;m,總的服務器數(shù)量

TQoS,最大平均響應時間各服務器的處理速率與功率

(b)由式(1)、(6)與TQOS計算出各個服務器所能接納的最大任務數(shù)

(c)設定時間片值interval

(d)λtotal=λ

(x)等待設定時間片值interval消耗完畢，轉(zhuǎn)到(c)

在LAOE算法中，總是假設系統(tǒng)的負載率ρ＜1,即系統(tǒng)總是能夠提供比需求更多的計算能力，因為當負載率超過1時，系統(tǒng)的任務響應時間將變?yōu)闊o限長，這是不可容忍的.從LAOE算法的描述過程中可以看出，算法的開銷比較小，其復雜度與服務器的數(shù)量成線性比例關(guān)系.從算法中可以發(fā)現(xiàn)任務將被優(yōu)先分配到能效比最高的機器上，因此，當系統(tǒng)的負載率較低時，有部分低能效比機器的分配概率將為0，即不會被分配任務，為了極大地降低整個系統(tǒng)的能耗，這部分機器可以關(guān)閉或轉(zhuǎn)入休眠狀態(tài)，因此，可以設定一個閥值來確定將要關(guān)閉或休眠的服務器數(shù)量；同時，在任務到達率上升時，系統(tǒng)需要更多的服務器來滿足QoS，則需要開啟/喚醒一定數(shù)量的服務器來提供服務.

由中央任務調(diào)度管理器來執(zhí)行LAOE算法，當任務到達率固定不變時，任務分配策略也維持不變；當任務到達率改變時，由任務管理器重新執(zhí)行LAOE算法，更新任務分配方案.為減少系統(tǒng)負載的波動性，可周期性評估當前任務到達率的變化情況，采取合適的預測策略應對未來任務的變化.其中，比較有效的預測方法有類似于TCP/IP擁塞控制的任務指數(shù)平滑法、線性回歸法等等.

4 實驗

由于本系統(tǒng)的目標平臺是大規(guī)模的集群計算系統(tǒng)，然而要在這樣的系統(tǒng)上進行可重復的實驗是極端困難的，因此，本文將采用仿真實驗，驗證不同條件下，LAOE算法的能量消耗值，并將與比例調(diào)度算法PS進行比較.選取2009-2014年不同企業(yè)生產(chǎn)、不同代技術(shù)制造的四組服務器參與實驗測試，各服務器的能效比值及相關(guān)參數(shù)如表1所示.

表1 服務器的相關(guān)參數(shù)

從表1可以看出，集群系統(tǒng)在處理速率、單位能效比上有著顯著的異構(gòu)性，不同于同代技術(shù)的異構(gòu)性，它們的服務速率差異化達到十倍左右，能效比的差異度達到五倍左右.

4.1 負載率的影響

使用表1設置服務器的參數(shù)，參與實驗的機器總數(shù)量為150臺，QoS最大平均響應時間設為640μs.通過變化系統(tǒng)負載的到達率，觀察不同負載率下，對LAOE算法和PS方法的影響，如圖2所示.

圖2 平均消耗功率與負載率

從圖2可看出，PS方法與系統(tǒng)負載成比例關(guān)系，是一條直線，其功率隨著系統(tǒng)負載的增加而線性增加.而LAOE方法呈現(xiàn)出的是一條曲線，位于PS方法的下面，在負載率較低或較高時，與PS方法接近，而差異最大的地方是在負載率為30%～70%這一變化區(qū)域.這說明LAOE算法在中等負荷狀態(tài)下，能取得顯著優(yōu)于PS方法的調(diào)度能耗，在負荷量較低時或較高時，相對于PS方法在節(jié)能方面的效果接近.

4.2 平均響應時間

本部分實驗，將測試兩種方法的任務完成時間值.由于任務的到達服從泊松分布，因此，采用平均響應時間值來度量，其值由各個服務器的任務平均響應時間及其所分得的任務比例之積的累加和所表示，計算方法采用如（7）的公式：

實驗參數(shù)設置同上，從圖3可以看到，隨著負載率的變化，LAOE算法的平均響應時間一直保持著直線，這與算法理論是一致的，從LAOE算法的描述可知，盡管每個服務器能力有差異，但是每個開啟的服務器平均響應時間是相近的，算法保證了平均響應時間的穩(wěn)定性.

圖3 平均響應時間與負載率

從直覺上看，在低負載時，PS方法的平均響應時間應該要優(yōu)于LAOE方法，但是結(jié)果卻相反.這主要是因為PS方法考慮系統(tǒng)負載的平均性，將任務按比例于服務器能力的方式分配給每個服務器，所以每個服務器的負載率都是相同的，由式（1）可知，當負載率相同時，如果兩臺服務器的能力相差兩倍，低性能服務器的平均響應時間將近似于高性能服務器的兩倍，這種方法使得低性能服務器的平均響應時間大大高于高性能服務器，致使整體性能下降.

4.3 QoS的影響

本部分實驗，測試不同的QoS對LAOE方法的影響，使用表1來設置服務器參數(shù)，參與實驗的機器總數(shù)量為150臺，QoS最大平均響應時間的變化范圍設為1200μs、480μs和20μs三個級別，負載值的取值變化范圍為集群計算總有效服務能力的10%～90%.實驗結(jié)果如圖4所示.

圖4 QoS與平均功率

從實驗結(jié)果可以看出，LAOE方法隨著QoS最大平均響應時間的減少，平均功率在增加，但是增加的幅度不顯著，這主要是由于QoS最大平均響應時間的限制，在高能效服務器上可接受的任務量減少，這部分任務被分配到低能效的服務器上，導致總的平均功率增加.另外可以看到在負載率相對不高的情況下，不同的QoS級別消耗的功率值幾乎相同，這主要是因為本實驗選擇最高能效比機器占據(jù)了較大的總體服務能力比例.實驗結(jié)果表明，當QoS變化較大時，其功率的變化并不顯著，說明LAOE方法在功耗方面對QoS的變化具有較好的適應能力.

5 結(jié)語

本文針對多代制造技術(shù)的異構(gòu)集群計算系統(tǒng)的能耗優(yōu)化進行研究，建立了該類系統(tǒng)的能耗問題模型，提出了一個低計算復雜度的方法來分配系統(tǒng)任務，使得集群系統(tǒng)在固定的時間片內(nèi)消耗的功率最小.并從負載率、QoS、服務能力等幾個方面的變化來驗證LAOE算法的性能，實驗結(jié)果表明LAOE的算法具有較好的節(jié)能效果和較強的異構(gòu)環(huán)境適應性，能夠在負載波動下保持相對穩(wěn)定的平均響應時間.

虛擬化技術(shù)有力推進了分布式集群計算系統(tǒng)的發(fā)展，隨著規(guī)模的增長，未來的集群系統(tǒng)，如云計算，將會越來越復雜，基于虛擬機的資源分配對異構(gòu)性集群系統(tǒng)的能耗與性能權(quán)衡管理提出很大的挑戰(zhàn)，這將是我們未來的研究重點.

[1]林闖,田源,姚敏.綠色網(wǎng)絡和綠色評價:節(jié)能機制,模型和評價[J].計算機學報,2011,34(4):593-612.

[2]RENS,HEY,XUF.Provably-efficientjobschedulingforenergy andfairnessingeographicallydistributeddatacenters[C]∥Distrib?utedComputingSystems(ICDCS),2012IEEE32ndInternational Conferenceon.IEEE,2012:22-31.

[3]LEEYC,ZOMAYAAY.Energyefficientutilizationofresources incloudcomputingsystems[J].TheJournalofSupercomputing, 2012,60(2):268-280.

[4]李銘夫,畢經(jīng)平,李忠誠.資源調(diào)度等待開銷感知的虛擬機整合[J].軟件學報,2014,25(7):1388-1402.

[5]GOUDARZIH,GHASEMAZARM,PEDRAMM.Sla-basedopti?mizationofpowerandmigrationcostincloudcomputing[C]∥Clus?ter,CloudandGridComputing(CCGrid),201212thIEEE/ACMIn?ternationalSymposiumon.IEEE,2012:172-179.

[6]LIK.Optimalpowerallocationamongmultipleheterogeneousserv?ersinadatacenter[J].SustainableComputing:InformaticsandSys?tems,2012,2(1):13-22.

[7]CAOJ,LIK,STOJMENOVICI.OptimalPowerAllocationand LoadDistributionforMultipleHeterogeneousMulticoreServerPro?cessorsacrossCloudsandDataCenters[J].Computers,IEEETrans?actionson,2014,63(1):45-58.

[8]MAZZUCCOM,DYACHUKD.Optimizingcloudprovidersreve?nuesviaenergyefficientserverallocation[J].SustainableComput?ing:InformaticsandSystems,2012,2(1):1-12.

[9]GANDHIA,HARCHOL-BALTERM,RAGHUNATHANR,etal. Autoscale:Dynamic,robustcapacitymanagementformulti-tierda?tacenters[J].ACMTransactionsonComputerSystems(TOCS), 2012,30(4):14.

[10]YEOS,LEEH-HS.Usingmathematicalmodelinginprovisioning aheterogeneouscloudcomputingenvironment[J].IEEEComputer, 2011,44(8):55-62.

【編校：李青】

ALoadAllocationMethodCombinedwithEnergyOptimizationandQoSforHeterogeneousCluster System

YANGBo,CHENZhili,DURuifeng,LIUWenbing
(DepartmentofInformationandManagement,HunanUniversityofFinanceandEconomics,Changsha,Hunan410205,China)

Theheterogeneityofcomputingefficiencyratiooftheclustersystemmadethebalanceofservicequalityand energyconsumptionmorecomplexinassigningtaskallocation.Forthetaskallocationofheterogeneousclusters,ataskal?locationmodelbasedonenergyoptimizationwasrepresented,andataskallocationalgorithm(LAOEalgorithm)waspro?posed.Usingthisalgorithm,withoutviolatingthemaximummeanresponsetimeoftasks,thetaskwaspreferentiallyas?signedtotheserverwithhighestenergyefficiencyratio.TheexperimentalresultsshowthatLAOEalgorithmcansignifi?cantlysaveenergyconsumption,andmakethemeanresponsetimerelativelystable.Thisalgorithmhasmoreextensive heterogeneousenvironmentadaptabilityandlowercomputingcomplexityoverhead.

heterogeneousclusters;computingefficiencyratio;energyoptimization;taskallocation

TP393

A

1671-5365(2015)12-0036-05

楊波，陳智俐，杜瑞鋒，等.組合能耗優(yōu)化與QoS的異構(gòu)集群負載分配方法[J].宜賓學院學報,2015,15(12):36-40.

YANGB,CHENZL,DURF,etal.ALoadAllocationMethodCombinedwithEnergyOptimizationandQoSforHeterogeneous ClusterSystem[J].JournalofYibinUniversity,2015,15(12):36-40.

2015-04-21修回：2015-06-10

湖南省教育廳高等學?？茖W研究項目（13C094）

楊波（1974-），男，講師，博士研究生，研究方向為云計算、智能算法

時間：2015-07-0110:15

http://www.cnki.net/kcms/detail/51.1630.Z.20150701.1015.003.html