面向異構(gòu)計(jì)算的能效感知調(diào)度研究

王靜蓮，龔 斌

（1.山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東濟(jì)南250101；2.魯東大學(xué)信息與電氣工程學(xué)院，山東煙臺264025；3.山東省高性能計(jì)算中心，山東濟(jì)南250101）

面向異構(gòu)計(jì)算的能效感知調(diào)度研究

王靜蓮1，2，龔 斌1，3

（1.山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東濟(jì)南250101；2.魯東大學(xué)信息與電氣工程學(xué)院，山東煙臺264025；3.山東省高性能計(jì)算中心，山東濟(jì)南250101）

異構(gòu)調(diào)度可使大規(guī)模計(jì)算系統(tǒng)采用并行方式聚合廣域分布的各種資源以提高性能.傳統(tǒng)調(diào)度目標(biāo)追時(shí)限約束求高性能而忽視高效能，遠(yuǎn)不能適應(yīng)綠色計(jì)算科學(xué)發(fā)展要求.因此，本文在理論上一方面建立融合能效感知的調(diào)度模型；另一方面提出適于超計(jì)算機(jī)混合體系的多學(xué)科背景的元啟發(fā)式優(yōu)化算法.從技術(shù)上解決了面向不同環(huán)境目標(biāo)的調(diào)度實(shí)施條件界定及調(diào)度指標(biāo)（時(shí)間、能耗）實(shí)時(shí)變化描述等問題.大量仿真實(shí)驗(yàn)結(jié)果表明：與三個(gè)元啟發(fā)式調(diào)度器相比，論文方法在能效及可擴(kuò)展等方面優(yōu)勢明顯；對于高維實(shí)例，整體性能改善分別達(dá)到8%，15%和17%.

異構(gòu)調(diào)度；綠色計(jì)算；協(xié)同進(jìn)化；混合并行

1 引言

目前，大規(guī)模計(jì)算系統(tǒng)采用并行技術(shù)可具高吞吐信息服務(wù)和海量數(shù)據(jù)處理能力，在科學(xué)計(jì)算和金融等領(lǐng)域需求迅猛增長［1］.隨著規(guī)模的不斷擴(kuò)大，異構(gòu)計(jì)算聚合廣域分布的各種同構(gòu)與異構(gòu)的計(jì)算機(jī)、工作站、機(jī)群、群集、數(shù)據(jù)庫、高級儀器和存儲(chǔ)設(shè)備等資源，可形成對用戶相對透明的、虛擬的高性能環(huán)境［2］.并行系統(tǒng)效能的高低很大程度上由部署在體系架構(gòu)上的資源管理系統(tǒng)決定［3］.任務(wù)調(diào)度是資源管理的核心，為了優(yōu)化某個(gè)目標(biāo)函數(shù)，其在一組具有任意特性的處理機(jī)中對任務(wù)集合進(jìn)行排序和資源分配［4］.當(dāng)前，同構(gòu)調(diào)度問題已被廣泛研究［5］；但異構(gòu)調(diào)度，鑒于其復(fù)雜性、環(huán)境的多樣性、應(yīng)用的新需求和調(diào)度目標(biāo)的折中性等，是一個(gè)亟待解決的高維多模優(yōu)化難題［6］.

與此同時(shí)，綠色計(jì)算因?yàn)榕c環(huán)境保護(hù)和人類可持續(xù)發(fā)展的密切關(guān)聯(lián)引起越來越多的社會(huì)關(guān)注［7］，而高性能領(lǐng)域的綠色計(jì)算成為數(shù)據(jù)和計(jì)算中心實(shí)際運(yùn)行的關(guān)鍵問題［8］.數(shù)據(jù)顯示，一臺不關(guān)閉的普通臺式電腦每年耗電1270度，釋放高達(dá)0.778噸二氧化碳；一次谷歌搜索消耗足以讓一只100瓦的燈泡工作1小時(shí)的能量，而兩次搜索就可釋放與燒開一壺水相當(dāng)?shù)亩趸?據(jù)調(diào)查，我國IT能源消耗約占全國每年800億元政府能源消耗的50%，而擁有大量服務(wù)器的大規(guī)模計(jì)算系統(tǒng)（如數(shù)據(jù)和計(jì)算中心）又占到IT能耗總開銷的40%.并且，信息需求量的加大催生IT投資以每年超過18%的速度增長，IT能耗也以每年 8%～10%的速度上升［9］.

另外，對高度數(shù)據(jù)密集型工作負(fù)載的支持正成為下一代計(jì)算和數(shù)據(jù)中心的關(guān)鍵技術(shù).這里，實(shí)時(shí)任務(wù)據(jù)其間的依賴性，分為獨(dú)立任務(wù)或依賴任務(wù)應(yīng)用；而數(shù)據(jù)密集型應(yīng)用是指以數(shù)據(jù)為中心，存在海量數(shù)據(jù)傳輸?shù)囊蕾嚾蝿?wù)應(yīng)用.計(jì)算資源的異構(gòu)性、調(diào)度技術(shù)的局限性和調(diào)度指標(biāo)的平衡性是面向數(shù)據(jù)密集應(yīng)用調(diào)度研究所需考慮的重要因素［10］.

再者，異構(gòu)調(diào)度算法的研究，目前主要集中在基于需求建模的啟發(fā)式算法［11］和基于進(jìn)化理論的元啟發(fā)式算法［12］.

對任務(wù)的多項(xiàng)需求，啟發(fā)式調(diào)度會(huì)將多目標(biāo)聚合成單一目標(biāo)函數(shù)處理.這種方法簡單而有效，因此被廣泛研究和采用，但其自身也存在一些固有的缺陷：由于多目標(biāo)優(yōu)化問題的解并非唯一，而是存在一個(gè)最優(yōu)解集合，稱為非劣解.而單目標(biāo)優(yōu)化算法僅能根據(jù)聚合函數(shù)得到?jīng)Q策空間的一個(gè)可行解，降低了最終解的質(zhì)量，缺乏靈活性和擴(kuò)展性.

更為合理的途徑是采用多目標(biāo)組合最優(yōu)化算法來解決這個(gè)問題，基于進(jìn)化理論的元啟發(fā)式算法是較為有效的方法.元啟發(fā)式算法應(yīng)用在異構(gòu)調(diào)度問題已有十余年［13］.但面對其復(fù)雜多樣性，目前算法大多存在兩個(gè)瓶頸：種群的收斂速度較慢或個(gè)體多樣性不能保持.并行與分布式元啟發(fā)式算法（Parallel Distributed Metaheuristics，PDM）因在較大目標(biāo)空間的搜索高效性及魯棒性，近年來被廣泛應(yīng)用；具體分為四類：主從模型，細(xì)粒度模型，粗粒度模型和混合模型.其中，粗粒度模型被廣泛應(yīng)用在超計(jì)算機(jī)體系結(jié)構(gòu)上［14～16］.但上述PDM在面向大規(guī)模實(shí)時(shí)實(shí)例時(shí)，運(yùn)行算法的超計(jì)算機(jī)雖然能達(dá)到峰值需求，但很多時(shí)候效率不高；因此面向多核CPU+GPU混合的超計(jì)算機(jī)體系結(jié)構(gòu)，元啟發(fā)式算法的并行設(shè)計(jì)也是決定問題高效求解的重要元素之一.

2 數(shù)學(xué)建模

實(shí)時(shí)應(yīng)用任務(wù)是由用戶上傳的若干子任務(wù)α= ｛αi｝（i=1，2，…，m）組成，具體可由一組屬性集合表述：αi=（bi，ωi，τi，νi，ζi，li，Si）.其中，bi、ωi及τi表子任務(wù)的到達(dá)、估計(jì)執(zhí)行和結(jié)束時(shí)間；νi表任務(wù)截止時(shí)間；ζi表計(jì)算量（周期數(shù)目）；li表需保護(hù)的數(shù)據(jù)量（單位：KB）；Si→κ（κ是一個(gè)正實(shí)數(shù)集）表示實(shí)時(shí)任務(wù)對異構(gòu)節(jié)點(diǎn)的安全需求集合；這里，通常是指保密、誠信和認(rèn)證三種.

異構(gòu)節(jié)點(diǎn)集合可表述為 φ=｛φj｝（j=1，2，…，n）.其中，每個(gè)節(jié)點(diǎn)φj有不同的屬性值，比如能耗pj、時(shí)鐘頻率ζj和轉(zhuǎn)換成本ξj等.

本文前期研究［17］為彌補(bǔ)當(dāng)前調(diào)度技術(shù)的局限和空白，解決不同約束與性能指標(biāo)的沖突性等問題，并兼顧不同運(yùn)行環(huán)境的差異性、不同應(yīng)用的計(jì)算或者數(shù)據(jù)密集特性，有效量化了動(dòng)態(tài)電壓頻率調(diào)整和動(dòng)態(tài)電源管理，提出異構(gòu)系統(tǒng)的能效優(yōu)化函數(shù)（如式（1）所示）.

式（1）中，X和E（X）分別表示調(diào)度方案集及異構(gòu)系統(tǒng)的總體能耗；對于任意i，如果存在是X中的元素，則yi=1；否則，yi=0.

融合能效感知的異構(gòu)調(diào)度目標(biāo)就是在滿足任務(wù)間依賴關(guān)系同時(shí)，尋找任務(wù)需求模型與資源拓?fù)浣Y(jié)構(gòu)之間的映射調(diào)度方案｛（αi，φj）｝，i∈［1，m］，j∈［1，n］，使異構(gòu)計(jì)算任務(wù)的調(diào)度長度和系統(tǒng)節(jié)點(diǎn)能效收益達(dá)到最優(yōu)，求盡可能多的（甚是是全部）的非劣解，可以描述為：

式（2）中，X∈Ф，Y∈Ω.X稱為決策變量，Ф是決策空間；Y為目標(biāo)函數(shù)值，Ω是目標(biāo)函數(shù)空間.fi（Xい）表示異構(gòu)計(jì)算任務(wù)的調(diào)度長度，fj（X）表示異構(gòu)系統(tǒng)能耗.

3 多學(xué)科啟發(fā)的協(xié)同進(jìn)化多目標(biāo)優(yōu)化算法

在免疫學(xué)中，抗原是導(dǎo)致免疫系統(tǒng)產(chǎn)生抗體的物質(zhì).對于多目標(biāo)優(yōu)化問題，抗原被定義為目標(biāo)函數(shù)（如式（2））.

B細(xì)胞、T細(xì)胞及一些具抗原特異性的淋巴細(xì)胞通常稱為抗體.人工免疫系統(tǒng)中抗體代表抗原的一個(gè)候選解.令X為抗體空間，抗體種群表示為N-維抗體集合（N是抗體種群規(guī)模）；且抗體由基因組成，表示為 xi= （G1，G2，…，GN）.在實(shí)際應(yīng)用中，給定優(yōu)化問題具有N-維實(shí)數(shù)的目標(biāo)搜索空間，一個(gè)候選解 xi（i∈［1，N］）由N維實(shí)數(shù)組成；而每一維代表一個(gè)問題變量并被看作基因.這里，基因的基本單位是基因座.

認(rèn)知心理學(xué)認(rèn)為模因（meme）是文化信息單位，是文化復(fù)制、傳播和發(fā)展的“基因”.模因作為一種選擇與建構(gòu)的創(chuàng)新思維和科學(xué)方法是社會(huì)進(jìn)化原動(dòng)力的一個(gè)表現(xiàn)形式.在空間X中給定一個(gè)抗體Aβ，論文將抗體基因的實(shí)時(shí)進(jìn)化信息看作模因，并形式化為 M.矩陣中每一維數(shù)據(jù)都與相應(yīng)的基因進(jìn)化信息對應(yīng)；Z、N表示模因空間的維數(shù).

論文多學(xué)科啟發(fā)的基因-模因協(xié)同進(jìn)化算法（IMCP）較人工免疫算法有三方面改進(jìn)，即除抗體個(gè)體，基因親和度值的細(xì)粒度評估及模因的數(shù)學(xué)表述，基因-模因協(xié)同進(jìn)化過程的高效模擬以及結(jié)合孤島模型和主從模型的多層次并行化設(shè)計(jì).

IM-CP算法

算法 IM-CP第7步～第 20步細(xì)粒度評估抗體基因的親和度值并有效模擬種群自組織的模因更新；而第22步～第24步定義了模因傳播并影響基因進(jìn)化的過程.

面向新近發(fā)展的混合多核CPU+GPU的高性能計(jì)算機(jī)集群體系結(jié)構(gòu)，論文提出融合粗粒度模型和主從模型的層次并行模型.即首先依據(jù)粗粒度模型，將種群劃分成若干子群，并把每個(gè)子群分配到一個(gè)節(jié)點(diǎn)上.而在每一個(gè)節(jié)點(diǎn)上，大量的個(gè)體適應(yīng)度評估計(jì)算是適于GPU加速的主從式并行應(yīng)用；這里CPU可看作主服務(wù)器，而在GPU多核上執(zhí)行的若干線程就是客戶端.第26步～第33步具體描述了多層次模型之一的粗粒度模型（也稱為孤島模型）采用的基于模因庫的并行遷移策略.

表1　實(shí)驗(yàn)的相關(guān)參數(shù)設(shè)置

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

實(shí)驗(yàn)在山東省高性能計(jì)算中心進(jìn)行，采用浪潮天梭TS10000高性能集群系統(tǒng)，英特爾至強(qiáng)5600系列處理器（2.66GHz，12MB Cache），CPU+GPU混合結(jié)構(gòu)，共有960個(gè)計(jì)算核數(shù)，計(jì)算峰值達(dá)每秒10萬億次雙精度浮點(diǎn)運(yùn)算，內(nèi)連40Gb/s帶寬1～2μs超低延遲的高速網(wǎng)絡(luò).算法的并行實(shí)現(xiàn)采用 MPICH-VMI（MPICH 1.2. 7p1版本）［18］；表1總結(jié)了實(shí)驗(yàn)集群的相關(guān)參數(shù)設(shè)置.

4.1整體性能比較

文獻(xiàn)［15］提出了一些新的模擬中型規(guī)模網(wǎng)格的任務(wù)調(diào)度實(shí)例集，并可以通過網(wǎng)站http：//www.fing.edu.uy/inco/grupos/cecal/hpc/HCSP下載應(yīng)用.這些測試集是依據(jù)文獻(xiàn)［19］所述的建模方法隨機(jī)產(chǎn)生的，其目的是模擬復(fù)雜的異構(gòu)計(jì)算環(huán)境；實(shí)例維數(shù)（任務(wù) ×機(jī)器）包括1024×32，2048×64，4096×128及8192×256，規(guī)模遠(yuǎn)大于文獻(xiàn)［11］的經(jīng)典十二個(gè)實(shí)例.

首先，針對高維異構(gòu)依賴任務(wù)調(diào)度問題，IM-CP按實(shí)例的一致性、半一致性及不一致性分類與算法Min-Min［11］和Sufferage［11］進(jìn)行性能比較.這里一致性、半一致性及不一致性的定義依從文獻(xiàn)［15］.

Min-Min和Sufferage是能在合理時(shí)間內(nèi)求解低維異構(gòu)調(diào)度問題的兩種較好啟發(fā)式算法.從圖1看，對于每維的一致性實(shí)例，算法 IM-CP相較 Min-Min和Sufferage的時(shí)間性能改善約為9%，而對半一致性實(shí)例，時(shí)間性能改善上升為12%.另外，雖然對于低維的不一致性實(shí)例，IM-CP相較Min-Min和Sufferage的時(shí)間性能改善不明顯，但面向高維的不一致性實(shí)例，其時(shí)間性能改善超過14%.

然后，針對上述同樣實(shí)例，IM-CP與目前面向計(jì)算機(jī)集群體系結(jié)構(gòu)設(shè)計(jì)的較好的三個(gè)元啟發(fā)式算法（pCHC［14］，pμ-CHC［15］和IM-dDE-CUDA［16］）進(jìn)行性能比較.如圖2總結(jié)所示，隨著異構(gòu)調(diào)度問題的規(guī)模增大，IM-CP表現(xiàn)的性能改善越大.值得注意的是，對于高維實(shí)例4096×128，IM-CP相較pμ-CHC，pCHC和IM-dDE-CUDA的性能改善分別達(dá)到8%，15%和17%.

4.2融合能效感知模型的影響

以高性能計(jì)算機(jī)集群節(jié)點(diǎn)個(gè)數(shù)為自變量，以能源效率作為函數(shù)值的四種算法的比較實(shí)驗(yàn)結(jié)果如圖3所示.圖3表明在高性能計(jì)算機(jī)集群節(jié)點(diǎn)個(gè)數(shù)從8到256遞增過程中，IM-CP較其余三種算法，能源節(jié)約優(yōu)勢明顯加強(qiáng).

模型中任務(wù)最后時(shí)間期限參數(shù)對算法解的能效影響如圖4所示.圖4清楚表明：模型中任務(wù)截止時(shí)間參數(shù)值1～100秒的遞增過程中，IM-CP求得解的能源消耗急劇下降；而在這一過程中，pCHC的能源節(jié)約能力表現(xiàn)次優(yōu).這一結(jié)果再次印證，面向高性能計(jì)算機(jī)集群算法IM-CP求解異構(gòu)調(diào)度問題的能效感知優(yōu)勢，且隨著異構(gòu)任務(wù)的截止時(shí)間參數(shù)值的不斷增大，這種優(yōu)勢更明顯.

5 結(jié)論

本文對融合能效感知的異構(gòu)調(diào)度進(jìn)行研究，有效降低數(shù)據(jù)密集應(yīng)用的通信開銷、兼顧提供者和消費(fèi)者雙方的利益并保證系統(tǒng)雙層負(fù)載均衡性.隨著新應(yīng)用（數(shù)據(jù)密集應(yīng)用、計(jì)算密集應(yīng)用）、新環(huán)境（計(jì)算網(wǎng)格、云計(jì)算、多集群環(huán)境、異構(gòu)環(huán)境）和新性能指標(biāo)（能效）的出現(xiàn)，分布式計(jì)算資源管理核心技術(shù)之調(diào)度研究具有重大的理論和應(yīng)用價(jià)值.

［1］ZHONG L，et al.A task assignment algorithm for multiple aerial vehicles to attack targets with dynamic values［J］. IEEE Transactions on Intelligent Transportation Systems，2013，14（1）：236-248.

［2］ZHENG X H，et al.A task operation model for resource allocation optimization in business process management［J］. IEEE Transactions on Systems，Man and Cybernetics，Part A：Systems and Humans，2012，42（5）：1256-1270.

［3］JING T，et al.Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems［J］.Soft Computing，2007，11（9）：873-888.

［4］SALCEDO-SANZ S，et al.Hybrid meta-heuristics algorithms for task assignment in heterogeneous computing systems［J］.Computers&Operations Research，2006，33 （3）：820-835.

［5］GONG Y J，et al.An efficient resource allocation scheme using particle swarm optimization［J］.IEEE Transactions on Evolutionary Computation，2012，16（6）：801-816.

［6］CHITRA P，et al.Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems ［J］.Applied Soft Computing，2011，11（2）：2725-2734.

［7］LI M，et al.Min-energy voltage allocation for tree structured tasks［J］.Journal of Combinatorial Optimization，2006，11（3）：305-319.

［8］LI M，et al.An efficient algorithm for computing optimal discrete voltage schedules［J］.SIAM Journal on Computing，2005，35（3）：658-671.

［9］IBM Blue Gene team.Overview of the IBM Blue Gene/P project［J］.IBM Journal of Research and Development，2008，52（1）：199-220.

［10］HAN X，et al.Deadline scheduling and power management for speed bounded processors［J］.Theoretical Computer Science，2010，411（40-42）：3587-3600.

［11］BRAUN T D，et al.A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems［J］.Journal of Parallel and Distributed Computing，2001，61（6）：810-837.

［12］GONCALVES J F，et al.A hybrid genetic algorithm for the job shop scheduling problem［J］.European Journal of Operational Research，2005，167（1）：77-95.

［13］WEBER M，et al.Distributed differential evolution with explorative-exploitative population families［J］.Genetic Programming and Evolvable Machines，2009，10（4）：343-371.

［14］NESMACHNOW S，CANCELA H，ALBA E.Heterogeneous computing scheduling with evolutionary algorithms ［J］.Soft Computing，2011，15（4）：685-701.

［15］NESMACHNOW S，et al.A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling ［J］.Applied Soft Computing，2012，12（2）：626-639.

［16］DE FALCO I，et al.Biological invasion-inspired migration in distributed evolutionary algorithms［J］.Information Sciences，2012，207（10）：50-65.

［17］馬艷，龔斌，鄒立達(dá).基于平衡定價(jià)和成本梯度的科學(xué)工作流調(diào)度策略［J］.電子學(xué)報(bào)，2010，38（10）：2416-2421. MA Y，GONG B，ZOU L D.Equilibrium pricing and cost gradient based scheduling strategy of scientific workflow ［J］.Acta Electronica Sinica，2010，38（10）：2416-2421. （in Chinese）

［18］PANT A，et al.Communicating efficiently on cluster based grids with MPICH-VMI［A］.Proceedings of IEEE International Conference on Cluster Computing［C］.San Diego，California，USA：IEEE，2004.23-33.

［19］ALI S，et al.Task execution time modeling for heterogeneous computing systems［A］.Proceedings of the 9th Heterogeneous Computing Workshop［C］.Washington，USA：IEEE，2000.185-199.

王靜蓮 女，1979年5月出生于山東省萊州市.現(xiàn)為山東大學(xué)博士研究生.主要從事并行與高性能計(jì)算、綠色計(jì)算和多目標(biāo)全局優(yōu)化算法等方向的研究.

E-mail：wjljing@163.com

龔 斌 男，1964年10月生于山東省濟(jì)南市.教授、博士生導(dǎo)師.現(xiàn)為山東大學(xué)計(jì)算中心主任、山東省高性能計(jì)算中心副主任，主要從事網(wǎng)格與高性能計(jì)算、機(jī)群計(jì)算方面的研究工作.

E-mail：gb@sdu.edu.cn

Research on Energy-Efficiency Aware Heterogeneous Scheduling

WANG Jing-lian1，2，GONG Bin1，3

（1.College of Computer Science and Technology，Shandong University，Jinan，Shandong 250101，China；2.College of Information and Electrical Engineering，Ludong University，Yantai，Shandong 264025，China；3.Shandong High Performance Computing Center，Jinan，Shandong 250101，China）

Enabled to provide pervasive access to distributed resources in parallel ways，heterogeneous scheduling is extensively applied in large-scaled computing system for high performance.Conventional real-time scheduling algorithms，however，disregard energy-efficiency in addition to stringent timing constraints.In recognition of green computing，an energyaware model is firstly presented.Secondly，inspired by multi disciplines，the meta-heuristic is addressed based on the supercomputer hybrid architecture.On the other hand，some technological breakthroughs are achieved，including boundary conditions for different heterogeneous computing and grid scheduling and descriptions of real-time variation of scheduling indexes （stringent timing constraints and energy-efficiency）.Extensive simulator and simulation experiments highlight higher efficacy and better scalability for the proposed approaches compared with the other three meta-heuristics；the overall improvements achieve 8%，15%and 17%for high-dimension instances，respectively.

heterogeneous scheduling；green computing；co-evolution；hierarchical parallelization

TP391

A

0372-2112（2016）04-0893-05

電子學(xué)報(bào)URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.020

2014-10-23；

2014-12-18；責(zé)任編輯：覃懷銀

國家自然科學(xué)基金（No.61272094）；國家863高技術(shù)研究發(fā)展計(jì)劃（No.2006AA01A113，No.2012AA01A306）