吳俊偉 姜春茂

摘要：在云計算提供高效，便捷等強大服務的背后，是日益攀升的能耗問題。準確的預測云平臺的負載（如CPU，內(nèi)存的使用）在任務調(diào)度，云能效方面具有重要意義。在以往研究中，線性自回歸算法在預測請求資源的粒度上存在不足，本文提出一種基于BP神經(jīng)網(wǎng)絡與遺傳算法混合的負載預測方法，結(jié)合遺傳算法良好的全局搜索能力與神經(jīng)網(wǎng)絡強大的非線性擬合能力，建立CPU資源的請求預測模型。實驗通過Google的云平臺數(shù)據(jù)作為訓練，測試集。實驗結(jié)果表明該方法有效的預測了CPU資源請求量，進而可以在此基礎上調(diào)整服務資源，實現(xiàn)綠色調(diào)度。

引言

在云平臺提供的強大功能背后，是巨大的能源消耗問題。一個占地500平方米的數(shù)據(jù)中心每天消耗的電力就高達38000度，這一數(shù)字超過了3500戶歐洲家庭日用電量的總和。到2020年，預計數(shù)據(jù)中心的建設規(guī)模幾乎將是2010年的兩倍。從上述數(shù)字明顯可以看出，為云計算設計高能效的解決方案迫在眉睫。

云能耗的優(yōu)化可以從云任務和云平臺的兩個角度進行研究。

從云任務的角度，主要是分析云任務的多維屬性，并利用算法來對云任務進行優(yōu)化調(diào)度。云任務包括有靜態(tài)屬性和動態(tài)屬性。靜態(tài)屬性如需要的CPU數(shù)量，任務的開始時間，截止時間，任務的類型等。動態(tài)屬性如訪問頻率，存儲要求，時間分布，用戶請求模型等。挖掘出任務與能耗之間的關(guān)系將有助于提前預測負載，降低能耗。

從云平臺的角度包括服務器，軟件以及網(wǎng)絡。從服務器角度來看，云能耗來源于處理器與數(shù)據(jù)中心兩個層面，處理器的能耗的主要影響因素是應用程序的使用模式，而數(shù)據(jù)中心面臨的是不斷增長的主機數(shù)量與低使用率帶來的能源浪費，據(jù)統(tǒng)計分析，云數(shù)據(jù)中心服務器的使用率一般在11%?50%之間。因此，如果能夠較好的預測云平臺cro的使用情況對于關(guān)閉部分服務器，提高調(diào)度效率具有重要意義。本文提出了一種基于神經(jīng)網(wǎng)絡和遺傳算法混合的云負載的預測方法，根據(jù)歷史數(shù)據(jù)預測未來短期CPU資源的需求，提高數(shù)據(jù)中心CPU的使用率，提局能效。

本文第1部分介紹相關(guān)工作的研究情況。第2部分提出基于神經(jīng)網(wǎng)絡與遺傳算法混合的預測方法，第3部分實驗及其結(jié)果分析，最后總結(jié)與展望。

1 相關(guān)工作

在服務器領(lǐng)域，一臺完全空閑的服務器的能耗能達到其峰值的70%左右。處理器高能耗隨之帶來的問題是配套冷卻設施的開銷。據(jù)統(tǒng)計，計算資源消耗的每1瓦電能就需要額外的0.5?1瓦特進行冷卻。Bohra等人采用“主成分分析”方法對監(jiān)控事件的相互關(guān)聯(lián)關(guān)系進行分析發(fā)現(xiàn){CPU，Cache}對和{Disk，DRAM}

對有很高的相關(guān)性，由此把系統(tǒng)負載分成CPU密集負載和IO密集負載。Kaushik提出的綠色HDFS概念，將hadoop集群邏輯分為熱區(qū)和冷區(qū)，采用數(shù)據(jù)分類與節(jié)能的策略確保在冷區(qū)存儲的數(shù)據(jù)長期不被訪問，從而關(guān)閉冷區(qū)的數(shù)據(jù)節(jié)點，但當冷區(qū)節(jié)點被喚醒的頻率較高時，反而消耗更多能源。從軟件層面上看，文獻提出的一種綠色云架構(gòu)實現(xiàn)虛機的重新配置，分配與再分配，以OPU的能耗為模型測量云平臺的能源消耗。Biirge等人在異構(gòu)的數(shù)據(jù)中心處理請求的調(diào)度上，關(guān)注用戶任務布署的時間與節(jié)點，得出甚至只要運用很簡單的啟發(fā)信息都可以提高能效。在網(wǎng)絡方面，文獻中提出了一種域內(nèi)流量工程機制GreenTE，能夠在保證用戶需求的前提下最大限度讓數(shù)據(jù)鏈路進入休眠狀態(tài)，Cianfrani等人提出一種能耗每女感的OSPF路由協(xié)議，通過優(yōu)化Dijkstra算法與共享效率低的路由器最短路徑樹的方式，提供最少路徑數(shù)的路由服務。

在預測資源請求方面，文獻中通過分析主機狀態(tài)間轉(zhuǎn)換花費的時鐘頻率與電功率，提出綠色調(diào)度算法，用神經(jīng)網(wǎng)絡作為云資源的預測原型。但實驗僅對NASA、Clark Netweb服務器url請求數(shù)作預測，粒度不夠精細。John J.Prevost等人同樣是預測url請求數(shù)，他們通過不同時間間隔模擬神經(jīng)網(wǎng)絡與線性自回歸模型，從實驗數(shù)據(jù)來看，二者都有較理想的近似曲線，但神經(jīng)網(wǎng)絡在90s間隔的案例中均方差值較大，預測效果不理想，分析得出神經(jīng)網(wǎng)絡存在收斂速度慢，易陷于局部最優(yōu)解等不足。

2011年google對外公布了其29天的云平臺實際數(shù)據(jù)，為進一步研究云平臺信息提供了重要的實踐依據(jù)?；谠摂?shù)據(jù)，已經(jīng)取得了相關(guān)的研究成果。其中，ZitaoLiu等人對此進行多方面的統(tǒng)計分析得出，在云計算中心任務的調(diào)度呈現(xiàn)周期性，其中被殺死（loll）和完成（finish）的任務（task）的數(shù)量相對穩(wěn)定，而被殺死的任務占用CPU60%的時鐘周期，可成功完成的任務僅占10%?15%，結(jié)論表明合理運用啟發(fā)信息可提高完成任務所占用CPU時鐘周期的比例。文獻中提出一種預測失敗任務的普適框架。作者分析云任務屬性，以任務結(jié)束狀態(tài)作為結(jié)構(gòu)體數(shù)據(jù)，選擇中長型任務，以上述的結(jié)構(gòu)體作為輸入，用周期神經(jīng)網(wǎng)絡訓練預測器，訓練完成后用該預測器對任務結(jié)束狀態(tài)作預測。但資源消耗的范化丟失了數(shù)據(jù)的一些原始特性，無法辨別任務失敗的具體原因，預測器無法在短時間內(nèi)規(guī)避相同錯誤的作業(yè)。

綜上所述，國內(nèi)外研究從多個方面尋求云節(jié)能方案。對于請求資源預測這一方面，資源粒度未能具體到物理或虛擬的靜態(tài)資源，而云能耗的度量大多都是以此構(gòu)建模型的。算法單一，神經(jīng)網(wǎng)絡雖具有良好的非線性映射能力，但同時它也存在收斂慢等不足；多元線性回歸可以準確地計量各個因素之間的相關(guān)程度與回歸擬合程度的高低，提高預測方程式的效果，但可能忽略了交互效應和非線性的因果關(guān)系。本文將主機的CPU作為能效的研究對象，在系統(tǒng)使用率層面，通過準確預測CPU的需求量來對服務平臺進行休眠，關(guān)閉等操作將極大降低云平臺的能耗水平。本文提出一種基于神經(jīng)網(wǎng)絡和遺傳算法混合的用戶資源請求預測模型，預測未來短期CPU請求量，以此值為參照關(guān)閉閑置主機，從而提高系統(tǒng)使用率，降低能耗。

2 算法模型

2.1 BP神經(jīng)網(wǎng)絡

BP（Back Propagation）神經(jīng)網(wǎng)絡是一種按誤差逆?zhèn)鞑ニ惴ㄓ柧毜亩鄬忧梆伨W(wǎng)絡。從信息處理角度對人腦神經(jīng)元網(wǎng)絡進行抽象，建立某種突觸聯(lián)系強

度可變的簡單模型，按不同的連接方式組成不同的網(wǎng)絡。每個節(jié)點代表一個神經(jīng)元（Neuron），接受一組輸入信號，通過激勵函數(shù)生成特定輸出。神經(jīng)網(wǎng)絡模型拓撲結(jié)構(gòu)包括輸入層（inputlayer）、隱含層（hidelayer）和輸出層（outputlayer），如圖1所示：

輸入信號依次通過輸入層、隱含層、輸出層逐級前饋，直至網(wǎng)絡輸出。之后學習系統(tǒng)計算網(wǎng)絡的實際輸出與期望輸出的誤差，根據(jù)這個誤差逐級反饋調(diào)整網(wǎng)絡權(quán)值，縮小實際輸出與期望輸出的差值，完成網(wǎng)絡的學習過程。其具體過程如下：

（1）前饋計算

在該過程中，第層神經(jīng)元的輸入為該神經(jīng)元相連的第層神經(jīng)元輸出的權(quán)重和，再將該和作為激勵函數(shù)的參數(shù)，計算出該神經(jīng)元的輸出，設在第時刻第個神經(jīng)元的輸入為，輸出為以，該神經(jīng)元的輸出可表示為：

其中，表示節(jié)點到節(jié)點的輸入信號，表示節(jié)點到節(jié)點的權(quán)重，表示節(jié)點的閾值，為激勵函數(shù)。

（2）反饋傳播

反饋傳播的含義在于，第層神經(jīng)元的誤差項是所有與該神經(jīng)元相連的第層的神經(jīng)元誤差項權(quán)重和與該神經(jīng)元激活函數(shù)/梯度的乘積。

對于/為sigmoid函數(shù)，輸出層第時刻第個神經(jīng)元，其誤差計算公式可表示為：

其中，表示期望輸出值，為實際輸出值。

而對于隱含層第《時刻第個神經(jīng)元，其誤差計算公式可表示為：

第時刻第層第個神經(jīng)元根據(jù)誤差項，調(diào)整與該神經(jīng)元連接的第層所有神經(jīng)元的權(quán)重值，其調(diào)整計算公式可表示為：

其中，表示學習率，為節(jié)點的輸出。

2.2 遺傳算法

遺傳算法（Genetic Algorithm）是模擬物競天擇的生物進化與自然選擇的計算模型，通過維護一個潛在解的群體執(zhí)行多方向的搜索，以問題潛在解集作為初始化種群，以直接或間接的方式為該種群的每個個體進行基因編碼，實現(xiàn)從表現(xiàn)型到基因型的映射。在下一代中，根據(jù)問題域個體的適應性函數(shù)（fitness）選擇個體，并借助遺傳學的遺傳算子（geneticoperators）對染色體進行組合交叉（crossover），變異（mutation），繁衍出代表新解集的種群。這個過程將導致后代種群像生物進化一樣更加適應于環(huán)境，逐漸逼近問題的全局最優(yōu)解。

2.3 混合遺傳算法

2.3.1 算法描述

通過2.1，2.2的描述可以發(fā)現(xiàn)，神經(jīng)網(wǎng)絡與遺傳算法都具有自適應，自組織的特點，神經(jīng)網(wǎng)絡雖具有良好的非線性映射能力，但易陷于局部最優(yōu)解，而遺傳算法從問題解集開始搜索，覆蓋面大，易于尋找全局最優(yōu)解。結(jié)合上一節(jié)的神經(jīng)網(wǎng)絡，具體給出遺傳算法的關(guān)鍵步驟。

（1）基因編碼

遺傳算法的基因編碼有直接與間接編碼兩種方式。以直接的方式對神經(jīng)網(wǎng)絡相鄰層的權(quán)重矩陣進行編碼，建立這樣一個神經(jīng)網(wǎng)絡拓撲模型，3個輸入節(jié)點，4個隱含節(jié)點和一個輸出節(jié)點。如圖2所示：

其中表示節(jié)點1與節(jié)點4的連接值，表示節(jié)點2與節(jié)點4的連接值，以此類推，用權(quán)值矩陣記錄的節(jié)點間連接關(guān)系作為種群個體的遺傳信息。

（2）自然選擇

確定輸入；經(jīng)過神經(jīng)網(wǎng)絡的前饋計算，以均方誤差：

作為適應性函數(shù)（fitness），值越小表示適應性越好。其中，分別表示第n時刻輸出節(jié)點k的預測值與實際值。以輪盤賭的方式模擬自然選擇，在輪盤賭中，權(quán)重矩陣代表種群個體，用矩陣對應的適應值計算該個體在輪盤中所占據(jù)的扇形比例，以此近似該個體被自然環(huán)境所選中的概率。

（3）組合交叉

組合交叉模擬父母雙方染色體配對過程，使子類更加逼近問題的最優(yōu)解。組合的方式多種多樣，這里介紹種群內(nèi)部與種群間的基因重組，如圖3，圖4所示。

種群內(nèi)部的重組體現(xiàn)在保留當前最優(yōu)解的種群權(quán)值矩陣，種群間則使用的是單點組合交叉的方式組合交叉重組父母雙方權(quán)值矩陣，以產(chǎn)生新的解集空間。種群內(nèi)部的重組體現(xiàn)在保留當前最優(yōu)解的種群權(quán)值矩陣，種群間則使用的是單點組合交叉的方式組合交叉重組父母雙方權(quán)值矩陣，以產(chǎn)生新的解集空間。（4）基因變異

變異算子定義為以小概率事件修改基因重組后子類的權(quán)重矩陣，使得對問題的求解有機會從當前空間跳躍到另一個搜索空間，逼近問題的全局最優(yōu)解。

（5）過渡條件

如此重復以上步驟，當達到預期的適應值或種群的適應值趨于穩(wěn)定時，將適應性最好的基因作為神經(jīng)網(wǎng)絡的權(quán)值矩陣，進入第6步。

（6）前饋傳播

對于每一組輸入，計算其實際輸出。

（7）反饋傳播

根據(jù)公式（2）（3），調(diào)整權(quán)值矩陣，當達到公式（8）小于預期的閾值或達到最大迭代次數(shù)時，結(jié)束算法。否則回到第6步。該算法的偽代碼如表1所示。

2.3.2 實例分析

以拓撲結(jié)構(gòu)為3-4-1的神經(jīng)網(wǎng)絡為例，假定初始條件下資源統(tǒng)計如下表2所示：

任選一組輸入數(shù)據(jù)（以編號1為例），通過前饋算，三組基因的輸出值分別為0.55，0.61，0.66，其適應值為0.013，0.005，0.001。對應的在輪盤中所占的比例為0.06，0.16，0.78。在輪盤賭中選中的基因為基因B與基因C。其基因重組，變異過程如圖7所示：

產(chǎn)生下一代個體，其適應值為0.0128。重復輪盤賭步驟構(gòu)建新一代種群。假設圖9的基因適應值滿足迭代結(jié)束條件，則進入神經(jīng)網(wǎng)絡訓練過程。

任選一組輸入（以編號2為例），經(jīng)過網(wǎng)絡傳播，輸出值為0.63，根據(jù)實驗誤差與函數(shù)梯度調(diào)整矩陣，設學習率為0.25，閾值b設置為0。過程如圖8所示：

重復網(wǎng)絡訓練過程，直到達到最大迭代次數(shù)或均方差小于閾值，結(jié)束程序。

3 實驗及其數(shù)據(jù)分析

3.1 實驗環(huán)境與參數(shù)設置

本文實驗是在單機環(huán)境下完成的。華碩AllSeries臺式電腦，CPU為InterCorei5-4590

3.30GHz，8GB內(nèi)存，1TB硬盤，主板集成聲卡和網(wǎng)卡，獨立顯卡。編程平臺為java環(huán)境。文獻使用了神經(jīng)網(wǎng)絡和線性回歸模型對服務器資源的請求數(shù)做出預測，而神經(jīng)網(wǎng)絡的預測效果相比下并不理想。實驗主要目的是測試神經(jīng)網(wǎng)絡結(jié)合遺傳算法是否能突破局部最優(yōu)解，更加逼近全局最優(yōu)解的非線性曲線。因此設計了以下實驗。

實驗1GA擴大搜索范圍，尋找全局最優(yōu)解區(qū)間。對谷歌數(shù)據(jù)的分析得出，集群的資源請求數(shù)據(jù)具有周期性，且一周為一個周期，換言之，上周一與這周一在請求值上具有相似性，所以我們明確以上周一與這周一的數(shù)據(jù)作為訓練樣本，預測下周一的請求數(shù)據(jù)。以上周一的數(shù)據(jù)作為網(wǎng)絡的輸入，這周一同一時刻的數(shù)據(jù)作為輸出，這樣就可以在夜間輕量負載的時間段執(zhí)行預測程序。

初始化一個3-7-1的網(wǎng)絡拓撲結(jié)構(gòu)，分別對應于輸入層，隱藏層和輸出層。輸入層3個節(jié)點分別是時間戳，CPU請求核數(shù)，任務請求量，輸出層為CPU的預測值?；诖送負涞臋?quán)值矩陣構(gòu)建GA的編碼基因，首先隨機初始化矩陣集合，接著確定輸入值，每隔5mini己錄一次{timestamp，request Core，request Tasknum}結(jié)構(gòu)數(shù)據(jù)，以24小時為整個時間跨度，可得到容量為288的數(shù)組。通過神經(jīng)網(wǎng)絡前饋傳播輸出預測值，以均方差：

作為個體的適應性函數(shù)值，遵循優(yōu)勝劣汰的規(guī)則，將適應值最高的個體基因直接遺傳給下一代，接著用輪盤賭的方式在種群中選擇待交配的雙方，采用單點基因重組構(gòu)造新的權(quán)值矩陣。其變異率設置為0.05，變異區(qū)間[-0.5，0.5]。實驗中設置的參數(shù)如表4所示。實驗2BP神經(jīng)網(wǎng)絡再訓練，逼近全局最優(yōu)解。由實驗1訓練的適應值最大的編碼基因，作為BP神經(jīng)網(wǎng)絡的權(quán)值矩陣，進入神經(jīng)網(wǎng)絡訓練過程，得出逼近全局最優(yōu)解的權(quán)值矩陣。設定sigmmd函數(shù)為激活函數(shù)，學習率為0.5。實驗中設置的參數(shù)如表5所示。

3.2 實驗分析

統(tǒng)計下周一的CPU資源請求數(shù)據(jù)，如圖9所示。使用神經(jīng)網(wǎng)絡，以上周與本周的數(shù)據(jù)樣本作為訓練集，輸出結(jié)果如圖10所示。

混合算法，訓練集同上，測試結(jié)果如圖11所示。BP神經(jīng)網(wǎng)絡與混合算法預測值與實際值差值樣本抽樣，如表6，表7所示。

如圖10所示，除個別數(shù)據(jù)節(jié)點，其它節(jié)點預測值與實際值相差較大，曲線逼近程度不理想。出現(xiàn)這種過擬合現(xiàn)象的主要因素是BP算法本身易陷于局部最優(yōu)解。而在圖11中，除去少數(shù)節(jié)點，二者曲線波形相似，預測值曲線逼近實際值。表7中，混合算法均值為正數(shù)，說明該算法預測值平均高于集群的實際值，從而保證集群的SLA。本文提出的混合算法，在查找全局最優(yōu)解方面借鑒遺傳算法，以面的方式搜索解集空間，尋找全局最優(yōu)解區(qū)間，再用神經(jīng)網(wǎng)絡逼近該區(qū)間的最優(yōu)解，二者的混合更適用于復雜的非線性曲線問題求解。

4 總結(jié)和進一步研究

云數(shù)據(jù)中心的高能耗與低使用率的巨大反差催生了綠色節(jié)能的槪念。麵艮務器，網(wǎng)絡，軟件為提高能效的三大研究目標。針對服務器領(lǐng)域，本文提出的基于神經(jīng)網(wǎng)絡與遺傳算法混合預測模型，自身具#轍子的學習能力，搜索全局最優(yōu)解的能力較強，對云資源請求量的逼近效果較為理想，可為數(shù)據(jù)中心資源分配與任務調(diào)度提供參考。但該模型輸入?yún)?shù)類型較為局限，僅為timestamp、core、tasknum，且本文中該模型僅用于預測CPU資源，未來將考慮基于此構(gòu)建云平臺資源請求的普適框架。