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

1、一種面向動態(tài)異構(gòu)多處理器的任務(wù)調(diào)度算法摘 要：提出了基于遺傳算法的面向動態(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)性.關(guān)鍵詞：遺傳算法；任務(wù)調(diào)度；功耗控制中圖分類號：TP316.

2、4 文獻(xiàn)標(biāo)識碼：AAbstract：This paper presented an improved scheduling algorithm for dynamic heterogeneous chip multicore processorsHeterogeneous Scheduling Genetic Algorithm，HSGA .The proposed scheduling algorithm uses time slices of OS scheduler to plete the iterative procedure of HSGA， which can obtain ef

3、ficient 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 ch

4、ip multiprocessor respectively with random degradation. And the proposed algorithm can generate more stable and adaptive results for unpredictable heterogeneity， pared with Hungarian Algorithm and Local Search Algorithm.Key words：genetic algorithms；task scheduling；power control半導(dǎo)體技術(shù)的飛速開展使得設(shè)計者可以將更多晶體

5、管或者處理器內(nèi)核集成到一個單芯片上從而構(gòu)成片上多處理器芯片Chip Multiprocessor，CMP.多處理器芯片已經(jīng)在效勞器計算、桌面系統(tǒng)、甚至于嵌入式計算系統(tǒng)中占據(jù)了重要的地位，成為目前主流的處理器構(gòu)造.多核處理器為計算系統(tǒng)帶來高性能的同時，也在芯片可靠性方面帶來了新的挑戰(zhàn)1-2.隨著片上多處理器芯片的規(guī)模逐漸擴大，芯片制造和使用過程中的不可控因素造成的同構(gòu)處理器性能和關(guān)鍵參數(shù)的異構(gòu)性，成為體系構(gòu)造和系統(tǒng)層面不可無視的因素和挑戰(zhàn).就算是在單個晶圓內(nèi)，由于消費工藝和流程的影響也可能導(dǎo)致各個處理器內(nèi)核的功耗、最大工作頻率等關(guān)鍵參數(shù)不同.在這種情況下，本來按照同構(gòu)片上多處理器設(shè)計的CMP芯片

6、可能具有異構(gòu)性3-4.大規(guī)模同構(gòu)CMP芯片將面臨眾多本來應(yīng)該性能一致的計算內(nèi)核在功耗和性能方面表現(xiàn)出不一致的情況.假設(shè)芯片中某些組件或者電路出現(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，假設(shè)不考慮上述不可見因素帶來的異構(gòu)性而進(jìn)展任務(wù)調(diào)度和分配顯然難

7、以得到優(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)多處理器降級的問題.文獻(xiàn)4對CMP處理器的制造過程的可變性對不同處理器內(nèi)核工作頻率的影響進(jìn)展了評估，他們認(rèn)為由此帶來的工作頻率的差異達(dá)20%，論文中提出了一系列電路級的方法降低不利影響.文獻(xiàn)6為了到達(dá)CMP芯片功耗控制的目的，將功耗過高的處理器內(nèi)核關(guān)閉.上述工作與本文的目的類似，但他們主要是從電路級考慮和解決動態(tài)異構(gòu)性帶來的問題，本文那么主要從操作系統(tǒng)的任務(wù)調(diào)度層面考慮動

8、態(tài)異構(gòu)性給CMP性能帶來的影響.此外，很多工作針對多核處理器上的應(yīng)用程序的特征進(jìn)展優(yōu)化.文獻(xiàn)7-8主要基于IPCInstruction Per Clock統(tǒng)計信息對應(yīng)用程序行為進(jìn)展分析從而找到更為有效的任務(wù)調(diào)度策略.在同構(gòu)多處理器平臺中還使用了任務(wù)遷移的技術(shù)進(jìn)步調(diào)度效率.文獻(xiàn)9提出了基于CPIClock Per Instruction棧信息的調(diào)度算法.上述工作中對于應(yīng)用程序行為分析的部分可以作為本文工作的補充，但他們的工作主要基于內(nèi)核數(shù)目少的多處理器芯片，沒有考慮同構(gòu)多處理芯片由于內(nèi)核數(shù)量增加而對任務(wù)遷移和系統(tǒng)信息采集方面帶來的限制.多核處理器功耗管理吸引了眾多研究者的關(guān)注10-12.Ma等人

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

10、指單個芯片上集成了多個同構(gòu)處理器內(nèi)核，內(nèi)核之間通過總線及共享內(nèi)存進(jìn)展通信的架構(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í)行，到達(dá)降低動態(tài)異構(gòu)性對多處理器芯片計算性能影響的目的.多處理器任務(wù)調(diào)度問題是NP難問題，難以在多項式時間內(nèi)找到最優(yōu)解.考慮到實際多處理器芯片上優(yōu)化目的和體系構(gòu)造細(xì)節(jié)的復(fù)雜性，本文做了一些假設(shè).首先，假設(shè)多處理器芯片上運行的任務(wù)之間是獨立的，忽略任務(wù)間通信，并且只考慮單線程執(zhí)行的情況

11、.這個假設(shè)可以使在對任務(wù)運行狀態(tài)采樣更為準(zhǔn)確的同時不失一般性.其次，假設(shè)平均分配外存訪問帶寬，忽略共享外存帶寬占用的情況.簡化共享外存的帶寬分配策略有助于專注于任務(wù)行為特征和調(diào)度問題的研究.2.2 問題的描繪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)核的

12、功耗情況，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)進(jìn)展.在采樣周期中，通過在一小段時間內(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

13、ms 1-2.圖1中，本文算法在調(diào)度采樣周期獲取處理器功耗開銷數(shù)據(jù)開銷矩陣，獲得處理器功耗參數(shù)后在功耗采樣周期執(zhí)行所提遺傳算法對開銷矩陣進(jìn)展計算，并找到適宜的調(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)境本文使用與文獻(xiàn)2類似的實驗

14、方法和平臺.文中主要使用SESC模擬器1模擬單個處理器.SESC模擬器可以模擬不同體系構(gòu)造的CPU，并與能耗模型Wattch，Cacti和Hotspot配合進(jìn)展構(gòu)造進(jìn)展模擬，本文使用與文獻(xiàn)2類似的層次化構(gòu)造組成多處理器模擬平臺.我們構(gòu)建了一個由多個SESC模擬器構(gòu)成的多處理器模擬環(huán)境來獲取各個處理器性能和功耗方面的參數(shù).在此根底之上由一個上層框架負(fù)責(zé)信息統(tǒng)計、資源管理與調(diào)度決策.通過對SESC模擬器的配置可以獲得不同性能的、單個的處理器內(nèi)核.文中假設(shè)每個處理器具備一樣的、靜態(tài)分配的外存訪問帶寬.為了便于實驗和比較，選擇如表1所示參數(shù)的處理器作為基準(zhǔn)處理器內(nèi)核.使用8個由表1所示主要參數(shù)的基準(zhǔn)處

15、理器組成標(biāo)準(zhǔn)的8核片上多處理器平臺，每個單獨的處理器是一個單線程、超標(biāo)量、亂序執(zhí)行的兼容MIPS指令集處理器.通過對基準(zhǔn)處理器的關(guān)鍵性能進(jìn)展降級處理來對片上多處理器芯片所面臨的動態(tài)異構(gòu)性進(jìn)展模擬.動態(tài)異構(gòu)性產(chǎn)生的故障可能會對CPU的各個方面帶來不同的影響，文獻(xiàn)1-2對此有較為詳細(xì)的描繪，這里不再詳述.本文分別采取4種CPU降級的策略如表2所示.在8核片上多處理器的模擬器中，隨機使用下面4種方法對同構(gòu)處理器內(nèi)核進(jìn)展降級處理，從而模擬出具有動態(tài)異構(gòu)特性的8核片上多處理器模擬平臺.4.2 實驗結(jié)果與討論本節(jié)對基于遺傳算法的動態(tài)異構(gòu)調(diào)度算法的實驗結(jié)果進(jìn)展分析和討論.考慮到性能和功耗的平衡，在此選擇ED

16、2指標(biāo)作為主要評價參數(shù)13.所有的測試數(shù)據(jù)以ED2指標(biāo)相對于匈牙利算法進(jìn)展歸一化后進(jìn)展分析.首先在4核異構(gòu)多核處理器的環(huán)境下對算法的有效性進(jìn)展評估，為了更好地進(jìn)展算法實際效果的比照，此處選擇以動態(tài)異構(gòu)條件下調(diào)度效果較好、但時間本錢很高的匈牙利算法2作為比較的根底.多處理器線程調(diào)度問題可以簡化為經(jīng)典的“指派問題，匈牙利算法解決此類問題的算法復(fù)雜度是On3.Local算法是文獻(xiàn)2提出的面向動態(tài)異構(gòu)多處理器的高效調(diào)度算法.通過對相鄰的處理器進(jìn)展線程“交換來評估調(diào)度效果，假設(shè)效果好那么保存此調(diào)度方案，假設(shè)效果不好那么退回原分配方案，迭代進(jìn)展.圖2為Local調(diào)度算法和本文所提遺傳調(diào)度算法HSGA在4核

17、動態(tài)異構(gòu)多處理器條件下各個負(fù)載的ED2值相對于匈牙利算法的逼近程度，其中“誤差線分別表示調(diào)度結(jié)果中的最好值和最壞值.由圖2可知，本文所提遺傳算法在5組隨機組成的應(yīng)用負(fù)載測試中都表現(xiàn)出比Local算法更好的性能.與匈牙利算法相比，所提遺傳算法平均只增加了約0.4%的ED2值.值得注意的是，圖2中“誤差線在一定程度上反映了調(diào)度算法對于不同應(yīng)用負(fù)載在整個測試周期中的動態(tài)適應(yīng)性.所提遺傳算法比Local算法表現(xiàn)出了更好的算法階段行為適應(yīng)性，也更適用于多核/眾核處理器芯片的全局功耗控制調(diào)度. 為了進(jìn)一步驗證所提算法的有效性和可擴展性，論文在8核和16核環(huán)境下進(jìn)展擴展實驗比照，結(jié)果分別如圖3和4所示.進(jìn)展

18、測試的結(jié)果.在面臨不可預(yù)知的動態(tài)異構(gòu)性的情況下，Local算法比匈牙利算法的ED2增加3%左右.本文HSGA遺傳算法的ED2僅僅增加了1.1%左右，并仍然比較匈牙利算法僅平均增長了1.3%左右，展現(xiàn)了本文算法良好的擴展性.隨著處理器數(shù)目的增加，傳統(tǒng)匈牙利算法的復(fù)雜度將變得難以承受.本文算法考慮由于故障或者其他不可預(yù)見因素導(dǎo)致的多處理器動態(tài)異構(gòu)性是對不同處理器構(gòu)造一個偶發(fā)的影響，因此將傳統(tǒng)遺傳算法中較為復(fù)雜的算法迭代執(zhí)行階段分散到各個調(diào)度時間片執(zhí)行，在不影響應(yīng)用負(fù)載執(zhí)行效率的情況下獲得較好的線程調(diào)度效果.5 結(jié) 論隨著單芯片上晶體管密度的不斷提升，將來的片上多處理器芯片的規(guī)模將會越來越大.制造和使用過程中的不確定因素導(dǎo)致