王靜蓮，龔 斌

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

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

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

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

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

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

1 引言

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

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

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

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

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

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

2 數(shù)學建模

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

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

本文前期研究［17］為彌補當前調(diào)度技術的局限和空白，解決不同約束與性能指標的沖突性等問題，并兼顧不同運行環(huán)境的差異性、不同應用的計算或者數(shù)據(jù)密集特性，有效量化了動態(tài)電壓頻率調(diào)整和動態(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)度目標就是在滿足任務間依賴關系同時，尋找任務需求模型與資源拓撲結(jié)構(gòu)之間的映射調(diào)度方案｛（αi，φj）｝，i∈［1，m］，j∈［1，n］，使異構(gòu)計算任務的調(diào)度長度和系統(tǒng)節(jié)點能效收益達到最優(yōu)，求盡可能多的（甚是是全部）的非劣解，可以描述為：

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

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

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

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

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

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

IM-CP算法

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

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

表1　實驗的相關參數(shù)設置

4 仿真實驗及結(jié)果

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

4.1整體性能比較

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

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

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

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

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

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

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

5 結(jié)論

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

［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］馬艷，龔斌，鄒立達.基于平衡定價和成本梯度的科學工作流調(diào)度策略［J］.電子學報，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)為山東大學博士研究生.主要從事并行與高性能計算、綠色計算和多目標全局優(yōu)化算法等方向的研究.

E-mail：wjljing@163.com

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

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

電子學報URL：http：//www.ejournal.org.cn 10.3969/j.issn.0372-2112.2016.04.020

2014-10-23；

2014-12-18；責任編輯：覃懷銀

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