一種面向動態(tài)異構(gòu)多處理器的任務(wù)調(diào)度算法*

張海燕,劉　彥,陳曉明,趙一弘

(1. 湖南大學(xué) 電氣與信息工程學(xué)院,湖南 長沙　410082；2.湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙　410082)

?

一種面向動態(tài)異構(gòu)多處理器的任務(wù)調(diào)度算法*

張海燕1,劉彥2?,陳曉明2,趙一弘2

(1. 湖南大學(xué) 電氣與信息工程學(xué)院,湖南 長沙410082；2.湖南大學(xué) 信息科學(xué)與工程學(xué)院,湖南 長沙410082)

提出了基于遺傳算法的面向動態(tài)異構(gòu)多處理器的調(diào)度算法(Heterogeneous Scheduling Genetic Algorithm，HSGA)，該算法利用連續(xù)的多個調(diào)度時間片完成遺傳算法的迭代計算，在保證計算效率的同時獲得較好的調(diào)度結(jié)果，從而為每個應(yīng)用選擇符合其計算特性的處理器內(nèi)核.仿真實驗表明，本文算法在4核、8核和16核的平臺上相比較于經(jīng)典的匈牙利算法ED2僅分別增加了0.4%，1.1%和1.3%，新的調(diào)度算法相比于匈牙利算法和Local調(diào)度算法具有更好的調(diào)度效果及更好的動態(tài)適應(yīng)性.

遺傳算法；任務(wù)調(diào)度；功耗控制

半導(dǎo)體技術(shù)的飛速發(fā)展使得設(shè)計者可以將更多晶體管或者處理器內(nèi)核集成到一個單芯片上從而構(gòu)成片上多處理器芯片(Chip Multiprocessor,CMP).多處理器芯片已經(jīng)在服務(wù)器計算、桌面系統(tǒng)、甚至于嵌入式計算系統(tǒng)中占據(jù)了重要的地位，成為目前主流的處理器結(jié)構(gòu).多核處理器為計算系統(tǒng)帶來高性能的同時，也在芯片可靠性方面帶來了新的挑戰(zhàn)[1-2].

隨著片上多處理器芯片的規(guī)模逐漸擴大，芯片制造和使用過程中的不可控因素造成的同構(gòu)處理器性能和關(guān)鍵參數(shù)的異構(gòu)性，成為體系結(jié)構(gòu)和系統(tǒng)層面不可忽視的因素和挑戰(zhàn).就算是在單個晶圓內(nèi)，由于生產(chǎn)工藝和流程的影響也可能導(dǎo)致各個處理器內(nèi)核的功耗、最大工作頻率等關(guān)鍵參數(shù)不同.在這種情況下，原本按照同構(gòu)片上多處理器設(shè)計的CMP芯片可能具有異構(gòu)性[3-4].大規(guī)模同構(gòu)CMP芯片將面臨眾多原本應(yīng)該性能一致的計算內(nèi)核在功耗和性能方面表現(xiàn)出不一致的情況.如果芯片中某些組件或者電路出現(xiàn)了故障、性能下降與延遲，通過相關(guān)技術(shù)手段可以使出現(xiàn)性能變化的處理器內(nèi)核降級使用[5].因此，原本同構(gòu)的多核片上處理器CMP可能由于多種不可見的因素導(dǎo)致其片上多個處理器內(nèi)核的性能與原有設(shè)計不同.相比原設(shè)計指標(biāo)將存在多個降級使用的處理器內(nèi)核，此情況稱為片上多處理器的動態(tài)異構(gòu)性.

本文主要考慮由于制造過程和使用階段的不可見因素導(dǎo)致的芯片關(guān)鍵參數(shù)變化時多處理器的任務(wù)調(diào)度問題.對于按同構(gòu)處理器設(shè)計的CMP，若不考慮上述不可見因素帶來的異構(gòu)性而進行任務(wù)調(diào)度和分配顯然難以得到優(yōu)化的結(jié)果.本文提出一種基于遺傳算法的動態(tài)異構(gòu)多處理器調(diào)度算法(HSGA)，在考慮同構(gòu)CMP處理器出現(xiàn)內(nèi)核降級使用的情況下，調(diào)整任務(wù)調(diào)度策略，在保證芯片總體功耗滿足約束的條件下獲得優(yōu)化的性能.

1　相關(guān)研究

已有相關(guān)研究考慮同構(gòu)多處理器降級的問題.文獻[4]對CMP處理器的制造過程的可變性對不同處理器內(nèi)核工作頻率的影響進行了評估，他們認(rèn)為由此帶來的工作頻率的差異達20%，論文中提出了一系列電路級的方法降低不利影響.文獻[6]為了達到CMP芯片功耗控制的目標(biāo)，將功耗過高的處理器內(nèi)核關(guān)閉.上述工作與本文的目標(biāo)類似，但他們主要是從電路級考慮和解決動態(tài)異構(gòu)性帶來的問題，本文則主要從操作系統(tǒng)的任務(wù)調(diào)度層面考慮動態(tài)異構(gòu)性給CMP性能帶來的影響.

此外，很多工作針對多核處理器上的應(yīng)用程序的特征進行優(yōu)化.文獻[7-8]主要基于IPC(Instruction Per Clock)統(tǒng)計信息對應(yīng)用程序行為進行分析從而找到更為有效的任務(wù)調(diào)度策略.在同構(gòu)多處理器平臺中還使用了任務(wù)遷移的技術(shù)提高調(diào)度效率.文獻[9]提出了基于CPI(Clock Per Instruction)棧信息的調(diào)度算法.上述工作中對于應(yīng)用程序行為分析的部分可以作為本文工作的補充，但他們的工作主要基于內(nèi)核數(shù)目少的多處理器芯片，沒有考慮同構(gòu)多處理芯片由于內(nèi)核數(shù)量增加而對任務(wù)遷移和系統(tǒng)信息采集方面帶來的限制.

多核處理器功耗管理吸引了眾多研究者的關(guān)注[10-12].Ma等人[10]的工作主要從多處理器芯片全局功耗控制入手，使用自動控制理論對CMP上的處理器內(nèi)核進行分類，并確定各自的工作頻率，所提方法展現(xiàn)了良好的效果和可擴展性.文獻[11]與本文工作類似，在考慮制造過程異構(gòu)性的情況下通過為每個處理器內(nèi)核設(shè)定合理的工作頻率來最優(yōu)化芯片性能.文獻[12]考慮了異構(gòu)多處理器平臺上的動態(tài)任務(wù)調(diào)度問題，并給出了MTS啟發(fā)式方法來解決這個NP難問題.但上述工作的目標(biāo)平臺沒有考慮多處理器芯片在使用過程中的故障導(dǎo)致處理器內(nèi)核降級使用的情況.本文的工作在具備降級使用能力的動態(tài)異構(gòu)多核處理器上，提出基于遺傳算法的功耗敏感任務(wù)調(diào)度算法.

2　系統(tǒng)模型

2.1系統(tǒng)結(jié)構(gòu)與假設(shè)

本文研究的多核處理器CMP指單個芯片上集成了多個同構(gòu)處理器內(nèi)核，內(nèi)核之間通過總線及共享內(nèi)存進行通信的架構(gòu).考慮到制造和使用過程中不可預(yù)見的故障對處理器內(nèi)核性能帶來的影響，文中認(rèn)為部分受影響的內(nèi)核可以降級使用，即降低部分關(guān)鍵性能參數(shù)和指標(biāo)但仍能正常操作.

本文主要探索在操作系統(tǒng)層面應(yīng)用自調(diào)整的任務(wù)調(diào)度策略將任務(wù)調(diào)度到合適的、降級的處理器內(nèi)核上執(zhí)行，達到降低動態(tài)異構(gòu)性對多處理器芯片計算性能影響的目的.多處理器任務(wù)調(diào)度問題是NP難問題，難以在多項式時間內(nèi)找到最優(yōu)解.考慮到實際多處理器芯片上優(yōu)化目標(biāo)和體系結(jié)構(gòu)細(xì)節(jié)的復(fù)雜性，本文做了一些假設(shè).首先，假設(shè)多處理器芯片上運行的任務(wù)之間是獨立的，忽略任務(wù)間通信，并且只考慮單線程執(zhí)行的情況.這個假設(shè)可以使在對任務(wù)運行狀態(tài)采樣更為準(zhǔn)確的同時不失一般性.其次，假設(shè)平均分配外存訪問帶寬，忽略共享外存帶寬占用的情況.簡化共享外存的帶寬分配策略有助于專注于任務(wù)行為特征和調(diào)度問題的研究.

2.2問題的描述

動態(tài)異構(gòu)多核處理器任務(wù)調(diào)度的目標(biāo)是在給定芯片總功耗預(yù)算之下獲得最佳的性能，應(yīng)用程序可以是多線程或者單線程程序，一般認(rèn)為任務(wù)線程的數(shù)目與處理器數(shù)目相同.單處理器上的并發(fā)多線程程序超出了本文討論范圍.文中使用Ti,j來表示任務(wù)i在處理器j上運行時的吞吐率，即單位時間內(nèi)執(zhí)行的指令數(shù)目.使用Pi,j來表示任務(wù)i在處理器j上運行時所產(chǎn)生的功耗.這里使用ED2來表示任務(wù)i在處理器j上執(zhí)行時的開銷[2].為了對比方便對不同處理器上的ED2值進行了歸一化處理.變量Xi,j用于表示任務(wù)i是否分配到處理器j運行的狀態(tài).現(xiàn)有m個任務(wù)和n個處理器(m=n)，動態(tài)異構(gòu)多核處理器任務(wù)調(diào)度問題可以使用整數(shù)線性規(guī)劃對其進行建模，如式(1)和式(2)所示.

(1)

(2)

式(1)表示本文的優(yōu)化目標(biāo)是最大化多處理器芯片的總吞吐率.式(2)表明使用ILP建模時給出的約束條件，即功耗低于功耗預(yù)算、一個任務(wù)只能分配給一個處理器內(nèi)核以及單個處理器內(nèi)核只能執(zhí)行一個任務(wù).

3　動態(tài)異構(gòu)多處理器調(diào)度算法

基于第2節(jié)的問題描述，本文提出基于遺傳算法的在線動態(tài)異構(gòu)多處理器調(diào)度算法HSGA.考慮遺傳算法在解決組合優(yōu)化問題時求解質(zhì)量高和算法復(fù)雜度高的特點，本節(jié)從算法設(shè)計和算法執(zhí)行框架兩個部分描述所提動態(tài)異構(gòu)多處理器調(diào)度算法.

3.1算法設(shè)計

對于給定的m個片上多處理器，n個任務(wù)/線程(其中m=n)，可設(shè)計如下算法：

1)設(shè)計編碼.如果任務(wù)i分配給處理器j，則i所對應(yīng)的基因為j,而染色體編碼為n個任務(wù)的基因組合,長度為n.如：染色體(1,3,2,4,5)表示分別把任務(wù)1至任務(wù)5分配給編號分別為1，3，2，4，5的處理器.

2)適應(yīng)度函數(shù).算法的目標(biāo)是在芯片出現(xiàn)本文所關(guān)注的動態(tài)異構(gòu)性導(dǎo)致處理器內(nèi)核產(chǎn)生難以預(yù)計的功耗變化時進行調(diào)整，使總體功耗最小.適應(yīng)度函數(shù)使用ED2指標(biāo)評估處理器功耗情況，可按公式(3)進行計算，表示該代染色體代表的所有處理器總開銷越小，適應(yīng)度越高.

(3)

3)具體算法流程.本文中使用基本的遺傳算法，其流程如下：

Step1編碼，根據(jù)所求解的具體問題,本文采用實數(shù)編碼；

Step2確定個體的評價函數(shù)，使用公式(3)所示的適應(yīng)度函數(shù)；

Step3在開始調(diào)度之前的算法初始化周期中獲取和產(chǎn)生初始群體；

Step4將調(diào)度時間片平均等分成若干個周期，并將每個周期分為探索階段和穩(wěn)定階段兩個部分.前1/10的時間稱為算法執(zhí)行周期(探索階段),其余的時間稱為調(diào)度執(zhí)行周期(穩(wěn)定階段)；

Step5開始探索階段，使用適應(yīng)度函數(shù)評價群體中的個體；

Step6使用輪盤選擇法，選擇下一代群體.使用多點基因交換的方式產(chǎn)生新的個體，從上一代群體的個體中隨機地選擇進行基因交換構(gòu)成下一代群體；

Step7獲得上一代和新的一代中適應(yīng)值最小的個體.并將本輪適應(yīng)度最大的個體替換成上一代適應(yīng)度最小的個體；

Step8開始穩(wěn)定階段，使用Step7中獲得的個體來進行調(diào)度；

Step9若滿足停機條件則停機，否則轉(zhuǎn)Step5.

若a為種群大小，迭代次數(shù)為b，則算法時間復(fù)雜度為O[b(a+m×n)].當(dāng)系統(tǒng)規(guī)模足夠大時為O(bmn)，搜索空間為O(ba).進行全搜索需要的時間,即搜索空間大小為O(m2).

3.2算法執(zhí)行框架

1)實現(xiàn)片上多核處理器芯片的全局功耗管理要求芯片內(nèi)部的各個處理器內(nèi)核具有實時可調(diào)節(jié)運行頻率的能力.目前AMD公司的Opteron系列多核芯片已具備類似功能，支持芯片全局功耗管理.

2)為了執(zhí)行片上多核處理器芯片的全局功耗管理的算法，還需要芯片內(nèi)部具備對每個處理器內(nèi)核或者分區(qū)域內(nèi)核的實時功耗監(jiān)測單元.現(xiàn)有Itanium處理器已在芯片內(nèi)部設(shè)置了單獨的傳感器用于監(jiān)測各個處理器內(nèi)核的功耗情況，Itanium處理器獨立的功耗管理單元消耗0.5 W左右的功耗，僅占用5%左右的芯片面積[2]，卻給處理器的溫度和功耗管理帶來極大的便利.

3)執(zhí)行本文算法需要芯片內(nèi)部設(shè)置任務(wù)/線程調(diào)度器和功耗管理器.這既可由單獨的處理器內(nèi)核負(fù)責(zé)，也可由操作系統(tǒng)層負(fù)責(zé).調(diào)度操作與功耗管理操作均由一個較短的采樣周期和一個較長的穩(wěn)定周期組成的時間片內(nèi)進行.在采樣周期中，通過在一小段時間內(nèi)運行不同的調(diào)度方案和功率配置方案，來評估應(yīng)用程序和異構(gòu)性能的計算內(nèi)核的性能和功耗統(tǒng)計信息.上述相關(guān)調(diào)度決定會在隨后的穩(wěn)定周期中保持，直到下一個時間片.圖1為算法執(zhí)行時間圖，假設(shè)線程調(diào)度時間片為100 ms，功耗管理時間片為10 ms[1-2].

圖1　算法執(zhí)行時間圖

圖1中，本文算法在調(diào)度采樣周期獲取處理器功耗開銷數(shù)據(jù)(開銷矩陣),獲得處理器功耗參數(shù)后在功耗采樣周期執(zhí)行所提遺傳算法對開銷矩陣進行計算,并找到合適的調(diào)度方案,找到優(yōu)化的調(diào)度方案后即可在后續(xù)的時間片的調(diào)度執(zhí)行周期執(zhí)行新的調(diào)度方案.需要說明的是，本文所考慮的動態(tài)異構(gòu)性對處理器內(nèi)核性能的影響是偶發(fā)的、低頻率的事件，因此對在線調(diào)度算法的實時性要求不高.利用此特點，將遺傳算法較高的計算開銷分配到操作系統(tǒng)時間片內(nèi)多個功耗采樣周期中執(zhí)行，一方面保證了基于遺傳算法的調(diào)度方案的有效性，另一方面也使得算法的計算開銷控制在可以接受的范圍之內(nèi).

4　實驗環(huán)境與結(jié)果分析

4.1實驗環(huán)境

本文使用與文獻[2]類似的實驗方法和平臺.文中主要使用SESC模擬器[1]模擬單個處理器.SESC模擬器可以模擬不同體系結(jié)構(gòu)的CPU，并與能耗模型Wattch,Cacti和Hotspot配合進行功耗與溫度調(diào)度方面的研究.本文使用的測試集是SPEC CPU2000，并在每個處理器內(nèi)核上均只執(zhí)行一個測試程序.為了高效地對不同規(guī)模的片上多處理器結(jié)構(gòu)進行模擬，本文使用與文獻[2]類似的層次化結(jié)構(gòu)組成多處理器模擬平臺.我們構(gòu)建了一個由多個SESC模擬器構(gòu)成的多處理器模擬環(huán)境來獲取各個處理器性能和功耗方面的參數(shù).在此基礎(chǔ)之上由一個上層框架負(fù)責(zé)信息統(tǒng)計、資源管理與調(diào)度決策.通過對SESC模擬器的配置可以獲得不同性能的、單個的處理器內(nèi)核.文中假設(shè)每個處理器具備相同的、靜態(tài)分配的外存訪問帶寬.為了便于實驗和比較，選擇如表1所示參數(shù)的處理器作為基準(zhǔn)處理器內(nèi)核.

表1　基準(zhǔn)處理器主要參數(shù)

使用8個由表1所示主要參數(shù)的基準(zhǔn)處理器組成標(biāo)準(zhǔn)的8核片上多處理器平臺，每個單獨的處理器是一個單線程、超標(biāo)量、亂序執(zhí)行的兼容MIPS指令集處理器.通過對基準(zhǔn)處理器的關(guān)鍵性能進行降級處理來對片上多處理器芯片所面臨的動態(tài)異構(gòu)性進行模擬.動態(tài)異構(gòu)性產(chǎn)生的故障可能會對CPU的各個方面帶來不同的影響，文獻[1-2]對此有較為詳細(xì)的描述，這里不再詳述.本文分別采取4種CPU降級的策略如表2所示.在8核片上多處理器的模擬器中，隨機使用下面4種方法對同構(gòu)處理器內(nèi)核進行降級處理，從而模擬出具有動態(tài)異構(gòu)特性的8核片上多處理器模擬平臺.

表2　處理器降級策略

為了測試和評估本文所提算法的有效性，通過在SPEC CPU2000測試集中選取不同測試程序組合成不同的負(fù)載作為測試輸入組合.

4.2實驗結(jié)果與討論

本節(jié)對基于遺傳算法的動態(tài)異構(gòu)調(diào)度算法的實驗結(jié)果進行分析和討論.考慮到性能和功耗的平衡，在此選擇ED2指標(biāo)作為主要評價參數(shù)[13].所有的測試數(shù)據(jù)以ED2指標(biāo)相對于匈牙利算法進行歸一化后進行分析.

首先在4核異構(gòu)多核處理器的環(huán)境下對算法的有效性進行評估,為了更好地進行算法實際效果的對比，此處選擇以動態(tài)異構(gòu)條件下調(diào)度效果較好、但時間成本很高的匈牙利算法[2]作為比較的基礎(chǔ).多處理器線程調(diào)度問題可以簡化為經(jīng)典的“指派問題”，匈牙利算法解決此類問題的算法復(fù)雜度是O(n3).Local算法是文獻[2]提出的面向動態(tài)異構(gòu)多處理器的高效調(diào)度算法.通過對相鄰的處理器進行線程“交換”來評估調(diào)度效果，若效果好則保留此調(diào)度方案，若效果不好則退回原分配方案，迭代進行.

圖2為Local調(diào)度算法和本文所提遺傳調(diào)度算法HSGA在4核動態(tài)異構(gòu)多處理器條件下各個負(fù)載的ED2值相對于匈牙利算法的逼近程度，其中“誤差線”分別表示調(diào)度結(jié)果中的最好值和最壞值.由圖2可知，本文所提遺傳算法在5組隨機組成的應(yīng)用負(fù)載測試中都表現(xiàn)出比Local算法更好的性能.與匈牙利算法相比，所提遺傳算法平均只增加了約0.4%的ED2值.值得注意的是，圖2中“誤差線”表示了在該組測試集測試過程中所產(chǎn)生的調(diào)度方案實際ED2值的動態(tài)范圍.由于我們從SPEC2000 benchmark測試集中隨機選取測試程序組合成多線程測試負(fù)載，因此“誤差線”在一定程度上反映了調(diào)度算法對于不同應(yīng)用負(fù)載在整個測試周期中的動態(tài)適應(yīng)性.所提遺傳算法比Local算法表現(xiàn)出了更好的算法階段行為適應(yīng)性，也更適用于多核/眾核處理器芯片的全局功耗控制調(diào)度.

為了進一步驗證所提算法的有效性和可擴展性，論文在8核和16核環(huán)境下進行擴展實驗對比，結(jié)果分別如圖3和4所示.

圖2　 4核調(diào)度結(jié)果

圖3　8核調(diào)度結(jié)果

圖4　16核調(diào)度結(jié)果

圖3為8核多處理器上運行SPEC2000 benchmark測試集隨機選取的任務(wù)負(fù)載進行測試的結(jié)果.在面臨不可預(yù)知的動態(tài)異構(gòu)性的情況下，Local算法比匈牙利算法的ED2增加3%左右.本文HSGA遺傳算法的ED2僅僅增加了1.1%左右，并依然展現(xiàn)出了較好的動態(tài)范圍特性.圖4為16核多處理器上運行SPEC2000 benchmark測試集的測試結(jié)果.處理器數(shù)量的增長給動態(tài)異構(gòu)調(diào)度效果帶來了一定的影響，增加了算法搜索空間.但本文HSGA遺傳算法在使用16核多處理器的情況下，整個應(yīng)用負(fù)載ED2值相比較匈牙利算法僅平均增長了1.3%左右，展現(xiàn)了本文算法良好的擴展性.隨著處理器數(shù)目的增加，傳統(tǒng)匈牙利算法的復(fù)雜度將變得難以接受.本文算法考慮由于故障或者其他不可預(yù)見因素導(dǎo)致的多處理器動態(tài)異構(gòu)性是對不同處理器結(jié)構(gòu)一個偶發(fā)的影響，因此將傳統(tǒng)遺傳算法中較為復(fù)雜的算法迭代執(zhí)行階段分散到各個調(diào)度時間片執(zhí)行，在不影響應(yīng)用負(fù)載執(zhí)行效率的情況下獲得較好的線程調(diào)度效果.

5　 結(jié)　論

隨著單芯片上晶體管密度的不斷提升，未來的片上多處理器芯片的規(guī)模將會越來越大.制造和使用過程中的不確定因素導(dǎo)致的可變性和故障將使得原本按照同構(gòu)設(shè)計的處理器內(nèi)核產(chǎn)生不可預(yù)見的異構(gòu)性.與芯片設(shè)計時的靜態(tài)異構(gòu)性相比，片上多處理器不可預(yù)見性的動態(tài)異構(gòu)性對軟件系統(tǒng)的設(shè)計提出了新的挑戰(zhàn)，即使得芯片在具備降級使用的條件時仍能獲得可以接受的計算性能.

本文提出了一種基于遺傳算法的面向不可預(yù)見動態(tài)異構(gòu)性片上多處理器的調(diào)度算法HSGA.當(dāng)片上多處理器由于不可預(yù)見的因素導(dǎo)致部分處理器內(nèi)核的工作頻率或者性能出現(xiàn)變化時，本文的遺傳算法會在調(diào)度時間片內(nèi)對應(yīng)用負(fù)載特征進行采樣，并將傳統(tǒng)遺傳算法復(fù)雜的迭代過程分散到后續(xù)多個調(diào)度時間片執(zhí)行，在保證計算效率的情況下提升了調(diào)度性能.文中基于SESC模擬器構(gòu)建了多處理器環(huán)境，運行SPEC2000 benchmark進行了仿真實驗.實驗結(jié)果表明，所提遺傳算法相比Local調(diào)度算法具有更好的調(diào)度效果和動態(tài)適應(yīng)特性.下一步，我們將進一步改進算法執(zhí)行效率，增加算法的可擴展性，并能適應(yīng)更為復(fù)雜的應(yīng)用負(fù)載.

[1]TEODORESCU R,TORRELLAS J.Variation-aware application scheduling and power management for chip multiprocessors[C]//Proceedings of the International Symposium on Computer Architecture.Washington DC:IEEE Computer Society,2008:363-374.

[2]WINTER J A,ALBONESI D H.Scheduling algorithms for unpredictably heterogeneous CMP architecture[C]//Proceedings of the International Conference on Dependable System & Networks.Washington DC:IEEE Computer Society, 2008: 42-51.

[3]BORKAR S,KARNIK T,NARENDRA S,etal.Parameter variations and impact on circuits and microarchitecture[C]//Proceedings of the Design Automation Conference.Washington DC:IEEE Computer Society,2003: 338-342.

[4]HUMENAY E,TARJAN D,SKADRON K. The impact of systematic process variations on symmetrical performance in chip multiprocessors[C]//Proceedings of the Conference on Design, Automation and Test in Europe.Washington DC:IEEE Computer Society,2007:1653-1658.

[5]SHIVAKUMAR P,KECKLER S W,MOORE C R,etal.Exploiting microarchitectural redundancy for defect tolerance[C]//Proceedings of the International Conference on Computer Design.Washington DC:IEEE Computer Society, 2003:35-42.

[6]DONALD J,MARTONOSI M.Power efficiency for variation-tolerant multicore processors[C]//Proceedings of the International Symposium on Low Power Electronics and Design.New York:ACM,2006:304-309.

[7]KUMAR R,FARKAS K,JOUPPI N,etal.Single-ISA heterogeneous multi-core architectures:the potential for processor power reduction[C]//Proceedings of IEEE/ACM International Symposium on Microarchitecture.Washington DC:IEEE Computer Society,2003:81-92.

[8]BECCHI M,CROWLEY P. Dynamic thread assignment on heterogeneous multiprocessor architectures[C]//Proceedings of the 3rd Conference on Computing Frontiers.New York:ACM, 2006:29-40.

[9]KOUFATY D,REDDY D,HAHN S.Bias scheduling in heterogeneous multi-core architectures[C]//Proceedings of the 5th European Conference on Computer Systems.New York: ACM,2010:125-138.

[10]MA K,LI X,CHEN M,etal.Scalable power control for many-core architectures running multi-threaded applications[C]//Proceedings of the International Symposium on Computer Architecture.Washington DC:IEEE Computer Society,2011:449-460.

[11]WINTER J,ALBONESI D,SHOEMAKER C.Scalable thread scheduling and global power management for heterogeneous many-core architecture[C]//Proceedings of the International Conference on Parallel Architectures & Compilation Techniques.Washington DC:IEEE Computer Society,2010:29-40.

[12]LIU G,PARK J,MARCULESCU D.Dynamic thread mapping for high-performance, power-efficient heterogeneous many-core systems[C]//Proceedings of the IEEE International Conference on Computer Design.Washington DC:IEEE Computer Society,2013:54-61.

[13]MARTIN A J.Towards an energy complexity of computation[J].Information Processing Letters,2001,77(77): 181-187.

An Improved Scheduling Algorithm for Dynamic Heterogeneous Chip Multicore Processors

ZHANG Hai-yan1,LIU Yan2?,CHEN Xiao-ming2,ZHAO Yi-hong2

(1. College of Electrical and Information Engineering, Hunan Univ, Changsha, Hunan410082, China；2. College of Computer Science and Electronic Engineering, Hunan Univ, Changsha, Hunan410082, China)

This paper presented an improved scheduling algorithm for dynamic heterogeneous chip multicore processors(Heterogeneous Scheduling Genetic Algorithm,HSGA ).The proposed scheduling algorithm uses time slices of OS scheduler to complete the iterative procedure of HSGA, which can obtain efficient task scheduling results and choose the best process core for each application task. The experiments using SESC simulator show that the ED2s of the proposed algorithm are only 0.4%, 1.1% and 1.3% higher than those of a baseline classic Hungarian Algorithm with 4 cores, 8 cores and 16 cores chip multiprocessor respectively with random degradation. And the proposed algorithm can generate more stable and adaptive results for unpredictable heterogeneity, compared with Hungarian Algorithm and Local Search Algorithm.

genetic algorithms;task scheduling;power control

1674-2974(2016)08-0151-06

2015-04-03

國家自然科學(xué)基金資助項目(61300037),National Natural Science Foundation of China(61300037)

張海燕(1976-)，女，山東臨沂人，湖南大學(xué)工程師，碩士?通訊聯(lián)系人，E-mail:liuyan@hnu.edu.cn

TP316.4

A