軟硬件節(jié)能原理深度融合之綠色異構(gòu)調(diào)度算法*

王靜蓮,龔 斌,劉 弘,李少輝

1(魯東大學(xué) 信息與電氣工程學(xué)院,山東 煙臺(tái) 264025)

2(山東大學(xué) 軟件學(xué)院,山東 濟(jì)南 250101)

3(山東省高性能計(jì)算中心,山東 濟(jì)南 250101)

4(山東師范大學(xué) 信息科學(xué)與工程學(xué)院,山東 濟(jì)南 250014)

近年來(lái),虛擬云聚合廣域分布的各類硬件資源(同構(gòu)或異構(gòu)集群、存儲(chǔ)設(shè)備及高級(jí)儀器等),形成對(duì)用戶相對(duì)透明、虛擬的高性能環(huán)境,深受世界青睞.然而,自 2010 年開(kāi)始,信息通信技術(shù)(information communication technology,簡(jiǎn)稱ICT)領(lǐng)域因其全球25%能耗之巨,及當(dāng)年跟全世界航空運(yùn)輸業(yè)相當(dāng)?shù)腃O2排放量,成為第五大耗能產(chǎn)業(yè)[1];另有數(shù)據(jù)顯示,ICT 產(chǎn)業(yè)存在很大能源浪費(fèi):中國(guó)數(shù)據(jù)中心PUE(power usage effectiveness)普遍大于2.2(同期資料顯示:美國(guó)數(shù)據(jù)中心的PUE 也基本保持在1.9).隨著全球能源短缺、極端天氣頻現(xiàn)以及低碳經(jīng)濟(jì)或人類可持續(xù)發(fā)展的迫切需要,虛擬云高性能向高效能計(jì)算的演進(jìn),已引起國(guó)內(nèi)外各界廣泛關(guān)注[2].

目前,相關(guān)研究大致集中在硬件和軟件兩個(gè)層面.

通常,云物理層可采用嵌入低功耗組件改變系統(tǒng)架構(gòu)方法,實(shí)現(xiàn)操作過(guò)程中能耗監(jiān)管和優(yōu)化調(diào)節(jié).這種方法一定程度有效,但設(shè)計(jì)和更換費(fèi)用過(guò)于昂貴[3,4].

事實(shí)上,云效能的高低很大程度上由調(diào)度中間件決定,即基于服務(wù)質(zhì)量(quality of service,簡(jiǎn)稱QoS)指標(biāo),在一組具有任意特性的云處理器中進(jìn)行資源分配和任務(wù)排序.元啟發(fā)式(meta-heuristics)優(yōu)化算法(如遺傳算法、人工免疫算法等)是調(diào)度引擎核心,其基于QoS 指標(biāo)定義的個(gè)體適應(yīng)度或免疫親和度函數(shù),是仿生群體迭代進(jìn)化、更新模擬的內(nèi)驅(qū)力[5,6].

這里,將硬件云不影響計(jì)算性能而實(shí)現(xiàn)能耗值極小化作為評(píng)價(jià)目標(biāo)之一,是軟件節(jié)能的主要途徑[7].

具體講,靜態(tài)功耗由CMOS(complementary-symmetry metal oxide semiconductor)電路泄漏電流產(chǎn)生,具有穩(wěn)態(tài)性.動(dòng)態(tài)能耗則源于硬件的物理反饋原理,例如,DVFS(dynamic voltage frequency scaling)或DPM(dynamic power management)可依據(jù)工作負(fù)載啟用情況更細(xì)粒度地進(jìn)行處理器核內(nèi)“頻率”調(diào)節(jié)[8];但值得注意的是,眾核處理器囿于微結(jié)構(gòu)級(jí)DVFS 或DPM 配置等區(qū)別,會(huì)產(chǎn)生不同的頻率-電壓等級(jí),即“異構(gòu)性”;表現(xiàn)為即使具有同樣的工作負(fù)載,異構(gòu)處理器動(dòng)態(tài)功耗開(kāi)銷也差異極大.因而,存在相當(dāng)大節(jié)能空間是微體系結(jié)構(gòu)級(jí)所無(wú)法涉足而亟待調(diào)度中間件宏觀調(diào)控的.

與此同時(shí),動(dòng)態(tài)能效指標(biāo)量化,國(guó)內(nèi)外目前大多沿用模糊估算方法:基于性能計(jì)數(shù)器,實(shí)時(shí)統(tǒng)計(jì)與耗能關(guān)聯(lián)度大的硬件事件,進(jìn)而借助經(jīng)驗(yàn)得到粗略值.由于硬件應(yīng)用事件總以螺旋式上升發(fā)展,這種動(dòng)態(tài)功耗的模糊估算模式大多僅適于同構(gòu)集群.

換言之,以元啟發(fā)式算法為基礎(chǔ)的調(diào)度中間件面對(duì)異構(gòu)高維優(yōu)化難題大多存在進(jìn)化動(dòng)力不足、個(gè)體多樣性不夠或收斂速度過(guò)慢等不足[9,10].

著眼于多角度、全方位提升算法之協(xié)同進(jìn)化模擬內(nèi)驅(qū)力,本文提出一種新的綠色異構(gòu)調(diào)度算法(GHSA_ di/II).本研究屬于異構(gòu)集群體系、云調(diào)度中間件和分布式人工智能等多學(xué)科交叉方向,是文獻(xiàn)[11]后續(xù)3 年的最新成果.

1 相關(guān)工作

目前,通用多核微處理器(central processing unit,簡(jiǎn)稱CPU)與定制加速協(xié)處理器(graphic processing unit,簡(jiǎn)稱GPU)混合體系已成為千萬(wàn)億次高性能計(jì)算機(jī)一種發(fā)展趨勢(shì).由于存在DVFS 配置及CMOS 制造工藝等方面的差異,實(shí)時(shí)處理器可調(diào)電壓邊界、對(duì)應(yīng)不同負(fù)載啟用粒度的電壓和頻率級(jí)別構(gòu)成以及工作頻率與動(dòng)態(tài)能耗相互之間影響規(guī)律非常復(fù)雜[3,4,8],因此,面對(duì)計(jì)算資源異構(gòu)性,僅靠調(diào)頻核心技術(shù)之“負(fù)載→頻率”應(yīng)答機(jī)制,還存在諸多節(jié)能約束;而對(duì)異構(gòu)集群主要耗能部件的實(shí)時(shí)動(dòng)態(tài)功耗,從測(cè)量方法到預(yù)估模型現(xiàn)在都面臨一系列挑戰(zhàn).

大規(guī)模實(shí)時(shí)調(diào)度一般要求在性能不降低的情況下減少能耗值.現(xiàn)有的實(shí)時(shí)調(diào)度研究大多關(guān)注同構(gòu)系統(tǒng)的兩類簡(jiǎn)單任務(wù)對(duì)象:周期任務(wù)和靜態(tài)任務(wù).在這兩種類型中,假定“任務(wù)”是不能被搶占的最小單位,作業(yè)都被假設(shè)為無(wú)限調(diào)用任務(wù)序列;且模型中不存在作業(yè)內(nèi)并行性,即在任意時(shí)刻,每個(gè)作業(yè)實(shí)例最多在一個(gè)處理器上執(zhí)行[7].

異構(gòu)實(shí)時(shí)調(diào)度,重點(diǎn)介紹4 個(gè)代表性新成果.文獻(xiàn)[12]提出的EEVS 引擎在調(diào)度目標(biāo)中引入通信成本參數(shù)K:設(shè)定好K值后,把當(dāng)前任務(wù)映射到某處理單元,如果增加的通信量邊大于平均通信量與K值的積,則更改映射;K的最優(yōu)取值與具體任務(wù)圖相關(guān),可通過(guò)實(shí)驗(yàn)確定.文獻(xiàn)[13]提出了求解最佳處理單元數(shù)目算法,實(shí)現(xiàn)了處理機(jī)數(shù)目和時(shí)鐘頻率的有效平衡,但由于處理機(jī)數(shù)目的上下界范圍過(guò)寬,使用二分查找和線性查找確定處理機(jī)數(shù)目的方式增加了算法執(zhí)行時(shí)間和復(fù)雜度.GOA(greedy online algorithm)及TOAA(2-approximation online algorithm)是文獻(xiàn)[14]分別面向同構(gòu)、異構(gòu)系統(tǒng)提出的實(shí)時(shí)動(dòng)態(tài)任務(wù)引擎的最新研究.TOAA[14]面對(duì)計(jì)算資源的異構(gòu)性,對(duì)每個(gè)任務(wù)組反復(fù)查找最小化能耗的最佳匹配,但任務(wù)分配完全基于靜態(tài)分組和復(fù)制結(jié)果.文獻(xiàn)[15]提出了異構(gòu)系統(tǒng)下并行應(yīng)用引擎p-BFF(power-aware backfilling-first-fit):p-BFF[15]忽略調(diào)頻處理器動(dòng)態(tài)能耗量化,僅優(yōu)化靜態(tài)功耗,不適合數(shù)據(jù)密集應(yīng)用.

另外,上述調(diào)度算法大多為基于啟發(fā)式算法(heuristic algorithm).對(duì)QoS 高維指標(biāo)需求,啟發(fā)式調(diào)度會(huì)將多目標(biāo)歸一聚合至單目標(biāo)函數(shù),得到?jīng)Q策空間的一個(gè)可行解:降低了最終解的質(zhì)量,缺乏靈活性和擴(kuò)展性[16-18].

近年來(lái),模擬達(dá)爾文“適者生存”自然進(jìn)化論或生物免疫等機(jī)制的一類仿生智能算法(如遺傳算法、人工免疫算法等),被廣泛應(yīng)用于云調(diào)度優(yōu)化問(wèn)題[5,6].這類方法基于仿生個(gè)體(候選解)特征編/解碼,元啟發(fā)式(meta- heuristics)搜索解空間,具體包括遺傳算法(genetic algorithms,簡(jiǎn)稱 GA)、人工免疫算法(artificial immune algorithms)、粒子群算法(particle swarm optimization,簡(jiǎn)稱PSO)、模因算法(memetic algorithms,簡(jiǎn)稱MA)和細(xì)胞模因算法(cellular MA,簡(jiǎn)稱 cMA)等,以及元啟發(fā)式算法與其他一些技術(shù)的融合,比如神經(jīng)網(wǎng)絡(luò)(neural networks)、變鄰域搜索(variable neighborhood search)和列表調(diào)度技術(shù)(list scheduling techniques)[19,20].

元啟發(fā)式算法的并行與分布式設(shè)計(jì)具體可劃為主從模型(master-slave model)、細(xì)粒度模型(fine-grained model)和粗粒度模型(coarse-grained model),其中,粗粒度模型也稱為孤島模型(island model),被廣泛應(yīng)用在眾核CPU+GPU 混合結(jié)構(gòu)的超計(jì)算機(jī)調(diào)度服務(wù)器上,孤島模型相關(guān)研究主要集中在選擇函數(shù)、替代函數(shù)、遷移率或拓?fù)浣Y(jié)構(gòu)的設(shè)計(jì)上[21-23].

前期成果[11]為解決異構(gòu)資源管理存在問(wèn)題以適應(yīng)新環(huán)境、新應(yīng)用、新需求及新特征,圍繞節(jié)能減排及調(diào)度協(xié)同等熱點(diǎn),嘗試將一些硬件特性結(jié)合到異構(gòu)調(diào)度中間件的目標(biāo)評(píng)測(cè)中.對(duì)比實(shí)驗(yàn)結(jié)果顯示:調(diào)度引擎在節(jié)能等方面優(yōu)勢(shì)明顯,但由于技術(shù)、時(shí)間及資金等方面限制,調(diào)度模型中的能耗參數(shù)僅是憑借先驗(yàn)大體預(yù)估.

2 軟硬件節(jié)能原理深度融合的綠色異構(gòu)調(diào)度算法

通常,云體系包含用戶層、中間件層、虛擬資源層和基礎(chǔ)設(shè)施層(如圖1 所示).用戶作業(yè)可解析產(chǎn)生若干并行依賴任務(wù)集,一般建模為DAG(directed acyclic graph)集合;中間件負(fù)責(zé)作業(yè)調(diào)度、執(zhí)行,也是壓力最集中組件.鑒于CPU 和GPU 都是并行計(jì)算資源,本文在稱謂上不作區(qū)分,采用統(tǒng)一標(biāo)識(shí)并進(jìn)行異構(gòu)屬性說(shuō)明.

調(diào)度QoS 評(píng)價(jià)指標(biāo)體系與相應(yīng)元啟發(fā)式(meta-heuristics)算法(如遺傳算法、人工免疫算法等)是調(diào)度引擎核心;受達(dá)爾文“適者生存”進(jìn)化論啟發(fā)的遺傳算法,通常直接用QoS 多目標(biāo)多約束函數(shù)評(píng)價(jià)個(gè)體適應(yīng)度;類似地,在模擬生物免疫系統(tǒng)的人工免疫算法(artificial immune algorithms)中,導(dǎo)致系統(tǒng)產(chǎn)生抗體的抗原也被定義為調(diào)度QoS 評(píng)價(jià)函數(shù).

2.1 一種重視并兼發(fā)硬件節(jié)能正反饋優(yōu)勢(shì)的調(diào)度尋優(yōu)動(dòng)力方程

計(jì)算云異構(gòu)眾核處理器雖然品牌眾多,但按微結(jié)構(gòu)級(jí)DVFS 配置或動(dòng)態(tài)能耗型區(qū)分,大致可劃分為3 類:片外獨(dú)立DVFS 支持、片上全局DVFS 支持和片上每個(gè)核的DVFS 支持.

異構(gòu)系統(tǒng)實(shí)時(shí)調(diào)度QoS 評(píng)價(jià)通常包括性能、經(jīng)濟(jì)或技術(shù)等指標(biāo).借助數(shù)字傳感及物聯(lián)網(wǎng)等實(shí)驗(yàn)技術(shù),歷經(jīng)異構(gòu)眾核體系電路(非線性)特征信號(hào)實(shí)時(shí)采集、節(jié)能機(jī)理模擬大數(shù)據(jù)的回歸集成,參數(shù)間顯、隱性關(guān)系深度挖掘以及代表性參數(shù)篩選等核心步驟,本文突破異構(gòu)眾核體系動(dòng)態(tài)能耗的多元非線性回歸量化,并數(shù)學(xué)定義一系列可預(yù)知(擬匹配)硬件資源物理反饋的調(diào)度QoS 評(píng)價(jià)指標(biāo),亦即調(diào)度算法中的進(jìn)化尋優(yōu)動(dòng)力方程構(gòu)建的重要組成部分.其中,表1 顯示了本文進(jìn)化動(dòng)力方程中的定義變量及代表意義.

定義1(動(dòng)態(tài)能耗).計(jì)算云處理器按微結(jié)構(gòu)級(jí)DVFS 配置或動(dòng)態(tài)能耗型區(qū)分,大致可劃分為 3 類,即v∈{1,2,3}.本質(zhì)上,動(dòng)態(tài)能耗(單位:Wh)等于動(dòng)態(tài)功耗(單位:W)與執(zhí)行時(shí)間(用ΔTi表示)的乘積.

這里,即使具有同樣的工作負(fù)載,而由于對(duì)應(yīng)不同的“頻率-電壓等級(jí)”,能耗異構(gòu)型處理器的動(dòng)態(tài)實(shí)時(shí)功耗開(kāi)銷差別極大.歷經(jīng)參數(shù)間顯、隱性關(guān)系深度挖掘、代表性參數(shù)篩選以及實(shí)驗(yàn)數(shù)據(jù)的多元非線性回歸量化等核心步驟,異構(gòu)眾核處理器體系的動(dòng)態(tài)能耗(用D_energy(φ)表示)可定義為公式(1):

定義2(響應(yīng)時(shí)間).作為重要的異構(gòu)實(shí)時(shí)調(diào)度QoS 度量指標(biāo)之一,預(yù)估響應(yīng)時(shí)間主要考量虛擬機(jī)的執(zhí)行時(shí)間,具體涉及兩方面因素:所有虛擬機(jī)必須要執(zhí)行的指令數(shù)目以及每個(gè)虛擬機(jī)的指令處理能力(比如每秒可處理的指令數(shù)目).因而,響應(yīng)時(shí)間(用R_time(φ)表示)可定義為公式(2):

公式(2)中,虛擬機(jī)θ可映射到能耗型v(v∈{1,2,3})的計(jì)算節(jié)點(diǎn)kh上,而且其工作頻率是.

Table 1 Related variables of evolutionary dynamic equation and their representative meanings表1 進(jìn)化動(dòng)力方程相關(guān)變量及代表意義

定義3(可擴(kuò)展性).對(duì)可具動(dòng)態(tài)電壓頻率縮放的異構(gòu)眾核處理器體系,擴(kuò)展性(用Scal(φ))表示)代表現(xiàn)運(yùn)行的所有計(jì)算節(jié)點(diǎn)的最大計(jì)算潛力,亦即暫不新增計(jì)算節(jié)點(diǎn)情況下的平均計(jì)算力.

具體講,擴(kuò)展性取決于計(jì)算機(jī)點(diǎn)kh∈R+的最大計(jì)算力以及當(dāng)前計(jì)算力:

定義4(系統(tǒng)魯棒性).為預(yù)防網(wǎng)絡(luò)故障和黑客攻擊,系統(tǒng)魯棒性(用Robust(φ))表示)是異構(gòu)實(shí)時(shí)調(diào)度QoS 評(píng)價(jià)的又一重要指標(biāo).

具體可解釋為每個(gè)計(jì)算節(jié)點(diǎn)的虛擬機(jī)平均映射數(shù)目,或者計(jì)算節(jié)點(diǎn)kh∈R+失聯(lián),需要遷移或移植的虛擬機(jī)數(shù)目:

定義5(安全增益).異構(gòu)實(shí)時(shí)調(diào)度QoS 又一重要指標(biāo)是最大化保證所有可調(diào)度任務(wù)的安全性.鑒于云服務(wù)安全需求的差異化,某一任務(wù)(用αi(i∈{1,…,m})表示)的安全增益可定義為公式(5):

進(jìn)而,所有任務(wù)的安全增益(用Security(φ)表示)可定義為公式(6):

公式(6)中,針對(duì)實(shí)時(shí)任務(wù)要求存在不能滿足的情況(比如服務(wù)延遲或負(fù)載約束等),ρi(i∈{1,…,m})表示任務(wù)αi(i∈{1,…,m})是否被調(diào)度:ρi=1(i∈{1,…,m})表示任務(wù)αi(i∈{1,…,m})被調(diào)度;反之,ρi=0(i∈{1,…,m})表示任務(wù)αi(i∈{1,…,m})沒(méi)被調(diào)度.

自適應(yīng)綠色調(diào)度的目標(biāo)就是在滿足QoS 強(qiáng)約束的同時(shí),尋求調(diào)度方案(φ∈Φ),使時(shí)效、能效收益最優(yōu),系統(tǒng)魯棒性最小,以及可擴(kuò)展性、安全性最強(qiáng)等.綜合上述各類指標(biāo)量化定義,本文進(jìn)化動(dòng)力方程如公式(7)所示(Λi表示QoS 指標(biāo)的權(quán)重因子):

2.2 異構(gòu)調(diào)度候選解的三維編/解碼設(shè)計(jì)

仿照生物遺傳或人工免疫理論,一個(gè)智能調(diào)度(候選)方案看作是基因組合的進(jìn)化個(gè)體;本算法中,候選解(仿 生個(gè)體)Chr(i∈{r∈R+)的基因特征擬表示為三維編碼,代表隨機(jī)任務(wù)被分配到計(jì)算節(jié)點(diǎn)的虛擬機(jī)上.

如圖2 所示,每個(gè)立方體代表候選解不同維度的取值范圍,而其中彩色填充部分則表示一個(gè)候選解(仿生個(gè)體),即所有任務(wù)與計(jì)算節(jié)點(diǎn)及虛擬機(jī)編號(hào)的某種配置映射.因而,候選解個(gè)體Chr(i∈{r∈R+)可編碼為三維矩陣(如公式(8)):

Fig.2 Three-dimensional coding of the candidate solution (bionic individual)圖2 候選解(仿生個(gè)體)的三維編碼表示

本算法解碼細(xì)則考慮不同任務(wù)分配到同一虛擬機(jī)兩種情形.

(1) 邏輯深度不同:遵循深度值排序原則,以避免任務(wù)之間長(zhǎng)時(shí)間等待甚至發(fā)生死鎖;

(2) 邏輯深度相同:遵循關(guān)聯(lián)耦合強(qiáng)度排序原則,以縮短關(guān)鍵路徑長(zhǎng)度達(dá)到最優(yōu)效果.

2.3 基于三維編碼的協(xié)同進(jìn)化算子定義

基于三維編碼的基因組進(jìn)化模擬包括個(gè)體選擇、交叉、變異以及克隆等智能算子定義.

克隆算子在GHSA_di/II 算法中對(duì)綠色異構(gòu)調(diào)度候選解之多樣性和逼近性起著重要作用,通常,其對(duì)仿生種群Ch ={Ch1,Ch2,...,Ch?,...,Chθ}的克隆操作ΓC可以定義為公式(9):

在GHSA_di/II 算法中,對(duì)每個(gè)仿生個(gè)體采用一致的克隆概率з,使得優(yōu)化過(guò)程中的可行非支配解集規(guī)模幾乎成倍上升,保持個(gè)體多樣性同時(shí),還可加速群體收斂.具體如公式(10)所示:

與克隆相反,選擇操作將種群個(gè)體劃分為非劣解或劣解,且只有非劣解可進(jìn)入下一代.對(duì)于任何仿生個(gè)體Ch#(ι)∈Ch**(ι),如果Ch#(ι)滿足公式(11)稱為非劣解,否則是劣解:

而對(duì)仿生種群的選擇操作ΓS,可定義為公式(12):

而GHSA_di/II 算法可依據(jù)第2.1 節(jié)定義的進(jìn)化動(dòng)力信息直接在種群中選取非劣仿生個(gè)體,算法的效率極大提升.

與此同時(shí),采用不同的基因交叉、變異策略,可有助于種群多樣性保持及仿生個(gè)體間協(xié)同或信息交換.GHSA_di/II 算法對(duì)仿生個(gè)體種群的基因操作ΓG可定義為公式(13);

通常,協(xié)同進(jìn)化系統(tǒng)模擬二進(jìn)交叉(SBX cross-over)算子或多項(xiàng)式變異(polynomial mutation)算子.在GHSA_ di/II 算法中,交叉點(diǎn)或變異點(diǎn)的選取同樣可依據(jù)第2.1 節(jié)定義的進(jìn)化動(dòng)力信息.

2.4 融合非傳統(tǒng)主從式和粗粒度的多層次并行化設(shè)計(jì)及算法描述

目前,通用多核微處理器與定制加速協(xié)處理器混合體系已成為千萬(wàn)億次高性能計(jì)算機(jī)一種發(fā)展趨勢(shì),因而,為適于調(diào)度服務(wù)器的眾核處理器超混合硬件體系,GHSA_di/II 算法采用非傳統(tǒng)主從式和粗粒度相融合的多層次并行與分布式設(shè)計(jì).

一方面,依照粗粒度模型,算法將整個(gè)進(jìn)化群體劃分成若干子群(第3 步),子群被分配到不同節(jié)點(diǎn)上進(jìn)行相關(guān)的協(xié)同進(jìn)化模擬計(jì)算,并適時(shí)采取有效的遷移策略(第12 步~第19 步);另一方面,在每一個(gè)節(jié)點(diǎn)上,大量的進(jìn)化動(dòng)力方程(如遺傳算法的適應(yīng)度函數(shù)或人工免疫算法的抗原)計(jì)算采用CPU-GPU 非傳統(tǒng)的主從式模型(第5 步~第11 步).這里,主服務(wù)器是CPU,而在GPU 眾核上大量執(zhí)行的并行線程可看作客戶端.

GHSA_di/II algorithm.

2.5 算法時(shí)間復(fù)雜度分析

設(shè)在每一代進(jìn)化中,種群FeaNonPop和ModNonPop的規(guī)模都為θ,克隆倍數(shù)為з,變量的維數(shù)為￡,約束維數(shù)為?,目標(biāo)函數(shù)維數(shù)為m,則:

? 在每次克隆種群ModNonPop所用的復(fù)雜度為O(зθ);

? 交叉操作所需復(fù)雜度為O(￡зθ/2);

? 變異操作所需復(fù)雜度為O(￡зθ);

? 計(jì)算種群Pop基因親和度值的時(shí)間復(fù)雜度為O(￡зθ);

? 合并種群ModNonPop所需復(fù)雜度為O(￡θ+?θ+mθ);

? 修正種群Pop中個(gè)體模因值所需復(fù)雜度為O(3m(з+1)θ+2?(з+1)θ);

? 選取并更新可行非支配解集所需復(fù)雜度為O((2з+6+mз+2m)θ+m(з+2)2θ2+(з+2)(m+1)θlog2((з+2)θ));

? 選取并更新非支配解集所需復(fù)雜度為O((m+1)(з+1)θ+θ+m(з+1)2θ2+(m+1)(з+1)θlog2((з+1)θ)).

因此,算法GHSA_di/II 的復(fù)雜度為多項(xiàng)式時(shí)間(polynomial time).

3 仿真實(shí)驗(yàn)及結(jié)果

實(shí)驗(yàn)在山東省高性能計(jì)算中心進(jìn)行,中心擁有先進(jìn)異構(gòu)集群、存儲(chǔ)和網(wǎng)絡(luò)資源,可滿足日益增長(zhǎng)的云研究及應(yīng)用服務(wù)需求.同時(shí),中心長(zhǎng)期為各種數(shù)據(jù)密集應(yīng)用提供服務(wù),可就多種輸入實(shí)例展開(kāi)綠色驅(qū)動(dòng)調(diào)度研究,以保證其實(shí)際通用性.具體包括如下配置.

? 曙光天潮高性能計(jì)算集群;

? 浪潮TS10000 計(jì)算集群(100 個(gè)節(jié)點(diǎn),200 顆2.8Ghz Intel?Xeon?CPU);

? 浪潮TS20000 計(jì)算集群(6 個(gè)節(jié)點(diǎn),24 顆1.3GHz Intel?ItaniumII CPU);

? HP DL580 高性能服務(wù)器;

? Dell r720 服務(wù)器、Dell 交換機(jī)等大數(shù)據(jù)處理平臺(tái);

? IBM p690(32 顆1.7GHz Power4+CPU,128G 內(nèi)存,6TB 硬盤(pán));

? IBM NAS300G 存儲(chǔ)系統(tǒng)(6.6TB 容量);

? 網(wǎng)絡(luò)系統(tǒng)(InfiniBand QDR,鏈路速率40Gbps,聚合帶寬69.6TB/s);

? 操作系統(tǒng)(Windows Server 2008);

? 編程語(yǔ)言及環(huán)境(C-CUDA,Fortran,Java,MPI);

? 互聯(lián)網(wǎng)出口(教育網(wǎng)和聯(lián)通運(yùn)營(yíng)商專線).

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)分為兩部分:第1 部分探討GHSA_di/II 算法求解異構(gòu)調(diào)度優(yōu)化問(wèn)題的整體性能,對(duì)比算法是新發(fā)表的3 個(gè)實(shí)時(shí)調(diào)度算法代表——PPADE 算法[21]、MOCTS-AI 算法[22]和MaOEA/C 算法[23];第2 部分則比較分析軟硬件節(jié)能原理深度融合給異構(gòu)調(diào)度優(yōu)化解集帶來(lái)的綠色感知影響,此部分采用的任務(wù)實(shí)例包括計(jì)算密集型和數(shù)據(jù)密集型兩類.

(1) 調(diào)度實(shí)驗(yàn)采用200 個(gè)計(jì)算集群,包括常見(jiàn)的3 種能耗異構(gòu)類型(v∈{1,2,3}),而且基本各占1/3;

(2) 集群編號(hào)按能耗類型依次設(shè)置,即能耗類型v=1 集群的編號(hào)集中排在前面,然后依次是能耗類型v=2,v=3 集群的編號(hào);

(3) 集群節(jié)點(diǎn)處理器和硬盤(pán)各自的初始利用率大致范圍在[10%,40%];

(4) 在后續(xù)小節(jié)中,“processor-optim”和“disk-optim”分別表示集群節(jié)點(diǎn)能效最高時(shí),處理器和硬盤(pán)各自的理論最優(yōu)利用率.具體講,{disk-optim:[0.75,0.8],processor-optim:[0.8,0.9],v:1}表示對(duì)于能耗型v=1 的計(jì)算節(jié)點(diǎn),其處理器和硬盤(pán)各自的利用率范圍分別為[80%,90%]和[75%,80%],能效最高;同理,對(duì)于v=2 和v=3 的計(jì)算節(jié)點(diǎn),存在理論最優(yōu)值:{disk-optim:[0.6,0.65],processor-optim:[0.6,0.7],v:2}和{disk- optim:[0.45,0.5],processor-optim:[0.4,0.5],v:3}.

3.2 整體性能比較

首先,實(shí)驗(yàn)探討GHSA_di/II 算法求解異構(gòu)調(diào)度優(yōu)化問(wèn)題的整體性能,對(duì)比算法是新發(fā)表的3 個(gè)元啟發(fā)式實(shí)時(shí)調(diào)度算法代表:PPADE 算法[21]、MOCTS-AI 算法[22]和MaOEA/C 算法[23].

評(píng)價(jià)指標(biāo)包括能耗值(公式(1))以及系統(tǒng)總體性能(overall system performance,簡(jiǎn)稱 OSP).這里,保證率(guarantee ratio)是針對(duì)實(shí)時(shí)任務(wù)要求存在不能滿足的情況(比如服務(wù)延遲或負(fù)載約束等),統(tǒng)計(jì)的可調(diào)度任務(wù)數(shù)所占比例;系統(tǒng)總體性能是標(biāo)準(zhǔn)化的安全值與保證率乘積.

可調(diào)度計(jì)算節(jié)點(diǎn)從8 個(gè)增加至256 個(gè)實(shí)驗(yàn)過(guò)程中,圖3 顯示了4 種算法各自的4 項(xiàng)性能評(píng)價(jià)值.

具體講,從節(jié)能、安全性以及系統(tǒng)總體性能這3 項(xiàng)評(píng)價(jià)指標(biāo)看,GHSA_di/II 算法的解質(zhì)量明顯優(yōu)于PPADE算法[21]、MOCTS-AI 算法[22]和MaOEA/C 算法[23];這里,僅從保證率指標(biāo)看,GHSA_di/II 算法與MaOEA/C 算 法[23]接近.

更重要的是:對(duì)比3 種算法——PPADE 算法[21]、MOCTS-AI 算法[22]和MaOEA/C 算法[23],GHSA_di/II 算法不僅具備顯著的高能效優(yōu)化性能,而且隨著可調(diào)度計(jì)算節(jié)點(diǎn)從8 到256 的增加,這種優(yōu)勢(shì)迅速提升.

Fig.3 Performance comparison between four meta-heuristics heterogeneous scheduling algorithms圖3 4 種元啟發(fā)式異構(gòu)調(diào)度算法的整體性能對(duì)比

3.3 軟硬件節(jié)能原理深度融合的綠色感知優(yōu)化影響

本節(jié)實(shí)驗(yàn)重點(diǎn)探討軟硬件節(jié)能原理深度融合給以元啟發(fā)式算法(如遺傳算法、人工免疫算法等)為基礎(chǔ)異構(gòu)調(diào)度算法帶來(lái)的綠色感知優(yōu)化影響,對(duì)比算法是在上節(jié)實(shí)驗(yàn)中顯現(xiàn)與GHSA_di/II 算法之調(diào)度保證率性能指標(biāo)值接近的MaOEA/C 算法[23].

實(shí)驗(yàn)按實(shí)時(shí)任務(wù)類型分成兩部分:計(jì)算密集型和數(shù)據(jù)密集型.

3.3.1 計(jì)算密集型實(shí)時(shí)任務(wù)集的異構(gòu)調(diào)度實(shí)驗(yàn)結(jié)果及分析

對(duì)于計(jì)算密集型任務(wù),每個(gè)應(yīng)用實(shí)例被劃分成20 000 個(gè)子任務(wù),即m=20000,并將虛擬機(jī)數(shù)量設(shè)置為5 000.

? 如圖4(a)所示:200 個(gè)計(jì)算集群盡管具有3 種動(dòng)態(tài)能耗異構(gòu)類型的處理器,但經(jīng)MaOEA/C 算法[23]調(diào)度后,異構(gòu)處理器利用率之間沒(méi)有明顯差異;

? 反之,從圖4(b)分析,GHSA_di/II 算法得到的調(diào)度優(yōu)化解顯示,200 個(gè)計(jì)算集群3 種異構(gòu)處理器的資源利用率可分別接近0.9,0.7 和0.5,在相應(yīng)的理論最優(yōu)值范圍內(nèi).

Fig.4 Comparison of CPU utilization after scheduling computing tasks by MaOEA/C[23] and GHSA_di/II圖4 MaOEA/C 算法[23]和GHSA_di/II 算法調(diào)度計(jì)算密集型任務(wù)后的處理器利用率對(duì)比

類似情形也出現(xiàn)在兩種算法調(diào)度解產(chǎn)生的硬盤(pán)利用率差異上(如圖5 所示).

Fig.5 Comparison of disk utilization after scheduling computing tasks by MaOEA/C[23] and GHSA_di/II圖5 MaOEA/C 算法[23]和GHSA_di/II 算法調(diào)度計(jì)算密集型任務(wù)后的硬盤(pán)利用率對(duì)比

3.3.2 數(shù)據(jù)密集型實(shí)時(shí)任務(wù)集的異構(gòu)調(diào)度實(shí)驗(yàn)結(jié)果及分析

對(duì)于數(shù)據(jù)密集型任務(wù),每個(gè)應(yīng)用實(shí)例同樣被劃分成20 000 個(gè)子任務(wù),并將虛擬機(jī)數(shù)量設(shè)置為5 000.

? 如圖6(a)、圖7(a)所示:與計(jì)算密集型實(shí)時(shí)調(diào)度情形類似,經(jīng)MaOEA/C 算法[23]調(diào)度后,異構(gòu)處理器和硬盤(pán)利用率之間沒(méi)有明顯差異;

? 反之,從圖6(b)、圖7(b)分析,GHSA_di/II 算法得到的調(diào)度優(yōu)化解顯示:200 個(gè)計(jì)算集群3 種異構(gòu)處理器的資源利用率可分別接近0.8,0.6 和0.4,相應(yīng)硬盤(pán)的資源利用率可分別接近0.75,0.6 和0.45,皆在相應(yīng)的理論最優(yōu)值范圍內(nèi).

兩組對(duì)比數(shù)據(jù)說(shuō)明,GHSA_di/II 算法具有考量?jī)深惷芗腿蝿?wù)對(duì)硬盤(pán)存儲(chǔ)硬件不同偏好的性能優(yōu)勢(shì).這進(jìn)一步顯示,軟硬件節(jié)能原理深度融合可給實(shí)時(shí)異構(gòu)調(diào)度算法帶來(lái)有效的綠色感知優(yōu)化效果.

Fig.6 Comparison of CPU utilization after scheduling data intensive tasks by MaOEA/C[23] and GHSA_di/II圖6 MaOEA/C 算法[23]和GHSA_di/II 算法調(diào)度數(shù)據(jù)密集型任務(wù)后的處理器利用率對(duì)比

Fig.7 Comparison of disk utilization after scheduling data intensive tasks by MaOEA/C[23] and GHSA_di/II圖7 MaOEA/C 算法[23]和GHSA_di/II 算法調(diào)度數(shù)據(jù)密集型任務(wù)后的硬盤(pán)利用率對(duì)比

4 結(jié) 論

計(jì)算云高性能向高效能演進(jìn),是人類可持續(xù)發(fā)展迫切需求;同時(shí),減少?gòu)V域計(jì)算成本、降低密集應(yīng)用開(kāi)銷、兼顧云服務(wù)買賣雙方利益并保證雙層負(fù)載均衡性,也是基礎(chǔ)設(shè)施運(yùn)維商增強(qiáng)競(jìng)爭(zhēng)優(yōu)勢(shì)所在.隨著新常態(tài)(云計(jì)算、異構(gòu)計(jì)算)、新應(yīng)用(計(jì)算密集型應(yīng)用、數(shù)據(jù)密集型應(yīng)用)和QoS 新指標(biāo)(能效)的出現(xiàn),綠色感知的異構(gòu)實(shí)時(shí)調(diào)度研究具有重大的理論和應(yīng)用價(jià)值.

針對(duì)現(xiàn)有元啟發(fā)式算法為基礎(chǔ)的實(shí)時(shí)調(diào)度算法大多存在的進(jìn)化動(dòng)力不足、個(gè)體多樣性不夠或收斂速度過(guò)慢等缺陷,本文著眼于軟硬件節(jié)能原理的深度融合,提出一種新的綠色異構(gòu)調(diào)度算法.

大量仿真實(shí)驗(yàn)結(jié)果顯示:無(wú)論對(duì)于數(shù)據(jù)密集型還是計(jì)算密集型實(shí)例,GHSA_di/II 算法較其他3 種元啟發(fā)式異構(gòu)調(diào)度算法,在整體性能、節(jié)能降耗以及可擴(kuò)展性等方面,都具明顯優(yōu)勢(shì).

概言之,本研究是文獻(xiàn)[11]的后續(xù)工作,而無(wú)論輻射廣度、攻關(guān)難度、理論深度還是創(chuàng)新高度,本文的GHSA_ di/II 算法都是其進(jìn)一步的拓展和延伸,并可為推進(jìn)云模式中軟、硬件節(jié)能聯(lián)動(dòng)以提高其銜接實(shí)效探索新的道路,或奠定一定的理論和技術(shù)基礎(chǔ).