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

1、一種面向動(dòng)態(tài)異構(gòu)多處理器的任務(wù)調(diào)度算法摘 要：提出了基于遺傳算法的面向動(dòng)態(tài)異構(gòu)多處理器的調(diào)度算法Heterogeneous Scheduling Genetic Algorithm，HSGA，該算法利用連續(xù)的多個(gè)調(diào)度時(shí)間片完成遺傳算法的迭代計(jì)算，在保證計(jì)算效率的同時(shí)獲得較好的調(diào)度結(jié)果，從而為每個(gè)應(yīng)用選擇符合其計(jì)算特性的處理器內(nèi)核.仿真實(shí)驗(yàn)說明，本文算法在4核、8核和16核的平臺(tái)上相比較于經(jīng)典的匈牙利算法ED2僅分別增加了0.4%，1.1%和1.3%，新的調(diào)度算法相比于匈牙利算法和Local調(diào)度算法具有更好的調(diào)度效果及更好的動(dòng)態(tài)適應(yīng)性.關(guān)鍵詞：遺傳算法；任務(wù)調(diào)度；功耗控制中圖分類號(hào)：TP316.

2、4 文獻(xiàn)標(biāo)識(shí)碼：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è)計(jì)者可以將更多晶體

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

6、可能具有異構(gòu)性3-4.大規(guī)模同構(gòu)CMP芯片將面臨眾多本來應(yīng)該性能一致的計(jì)算內(nèi)核在功耗和性能方面表現(xiàn)出不一致的情況.假設(shè)芯片中某些組件或者電路出現(xiàn)了故障、性能下降與延遲，通過相關(guān)技術(shù)手段可以使出現(xiàn)性能變化的處理器內(nèi)核降級(jí)使用5.因此，本來同構(gòu)的多核片上處理器CMP可能由于多種不可見的因素導(dǎo)致其片上多個(gè)處理器內(nèi)核的性能與原有設(shè)計(jì)不同.相比原設(shè)計(jì)指標(biāo)將存在多個(gè)降級(jí)使用的處理器內(nèi)核，此情況稱為片上多處理器的動(dòng)態(tài)異構(gòu)性.本文主要考慮由于制造過程和使用階段的不可見因素導(dǎo)致的芯片關(guān)鍵參數(shù)變化時(shí)多處理器的任務(wù)調(diào)度問題.對(duì)于按同構(gòu)處理器設(shè)計(jì)的CMP，假設(shè)不考慮上述不可見因素帶來的異構(gòu)性而進(jìn)展任務(wù)調(diào)度和分配顯然難

7、以得到優(yōu)化的結(jié)果.本文提出一種基于遺傳算法的動(dòng)態(tài)異構(gòu)多處理器調(diào)度算法HSGA，在考慮同構(gòu)CMP處理器出現(xiàn)內(nèi)核降級(jí)使用的情況下，調(diào)整任務(wù)調(diào)度策略，在保證芯片總體功耗滿足約束的條件下獲得優(yōu)化的性能.1 相關(guān)研究已有相關(guān)研究考慮同構(gòu)多處理器降級(jí)的問題.文獻(xiàn)4對(duì)CMP處理器的制造過程的可變性對(duì)不同處理器內(nèi)核工作頻率的影響進(jìn)展了評(píng)估，他們認(rèn)為由此帶來的工作頻率的差異達(dá)20%，論文中提出了一系列電路級(jí)的方法降低不利影響.文獻(xiàn)6為了到達(dá)CMP芯片功耗控制的目的，將功耗過高的處理器內(nèi)核關(guān)閉.上述工作與本文的目的類似，但他們主要是從電路級(jí)考慮和解決動(dòng)態(tài)異構(gòu)性帶來的問題，本文那么主要從操作系統(tǒng)的任務(wù)調(diào)度層面考慮動(dòng)

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

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

10、指單個(gè)芯片上集成了多個(gè)同構(gòu)處理器內(nèi)核，內(nèi)核之間通過總線及共享內(nèi)存進(jìn)展通信的架構(gòu).考慮到制造和使用過程中不可預(yù)見的故障對(duì)處理器內(nèi)核性能帶來的影響，文中認(rèn)為部分受影響的內(nèi)核可以降級(jí)使用，即降低部分關(guān)鍵性能參數(shù)和指標(biāo)但仍能正常操作.本文主要探究在操作系統(tǒng)層面應(yīng)用自調(diào)整的任務(wù)調(diào)度策略將任務(wù)調(diào)度到適宜的、降級(jí)的處理器內(nèi)核上執(zhí)行，到達(dá)降低動(dòng)態(tài)異構(gòu)性對(duì)多處理器芯片計(jì)算性能影響的目的.多處理器任務(wù)調(diào)度問題是NP難問題，難以在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解.考慮到實(shí)際多處理器芯片上優(yōu)化目的和體系構(gòu)造細(xì)節(jié)的復(fù)雜性，本文做了一些假設(shè).首先，假設(shè)多處理器芯片上運(yùn)行的任務(wù)之間是獨(dú)立的，忽略任務(wù)間通信，并且只考慮單線程執(zhí)行的情況

11、.這個(gè)假設(shè)可以使在對(duì)任務(wù)運(yùn)行狀態(tài)采樣更為準(zhǔn)確的同時(shí)不失一般性.其次，假設(shè)平均分配外存訪問帶寬，忽略共享外存帶寬占用的情況.簡化共享外存的帶寬分配策略有助于專注于任務(wù)行為特征和調(diào)度問題的研究.2.2 問題的描繪3.2 算法執(zhí)行框架1實(shí)現(xiàn)片上多核處理器芯片的全局功耗管理要求芯片內(nèi)部的各個(gè)處理器內(nèi)核具有實(shí)時(shí)可調(diào)節(jié)運(yùn)行頻率的才能.目前AMD公司的Opteron系列多核芯片已具備類似功能，支持芯片全局功耗管理.2為了執(zhí)行片上多核處理器芯片的全局功耗管理的算法，還需要芯片內(nèi)部具備對(duì)每個(gè)處理器內(nèi)核或者分區(qū)域內(nèi)核的實(shí)時(shí)功耗監(jiān)測單元.現(xiàn)有Itanium處理器已在芯片內(nèi)部設(shè)置了單獨(dú)的傳感器用于監(jiān)測各個(gè)處理器內(nèi)核的

12、功耗情況，Itanium處理器獨(dú)立的功耗管理單元消耗0.5 W左右的功耗，僅占用5%左右的芯片面積2，卻給處理器的溫度和功耗管理帶來極大的便利.3執(zhí)行本文算法需要芯片內(nèi)部設(shè)置任務(wù)/線程調(diào)度器和功耗管理器.這既可由單獨(dú)的處理器內(nèi)核負(fù)責(zé)，也可由操作系統(tǒng)層負(fù)責(zé).調(diào)度操作與功耗管理操作均由一個(gè)較短的采樣周期和一個(gè)較長的穩(wěn)定周期組成的時(shí)間片內(nèi)進(jìn)展.在采樣周期中，通過在一小段時(shí)間內(nèi)運(yùn)行不同的調(diào)度方案和功率配置方案，來評(píng)估應(yīng)用程序和異構(gòu)性能的計(jì)算內(nèi)核的性能和功耗統(tǒng)計(jì)信息.上述相關(guān)調(diào)度決定會(huì)在隨后的穩(wěn)定周期中保持，直到下一個(gè)時(shí)間片.圖1為算法執(zhí)行時(shí)間圖，假設(shè)線程調(diào)度時(shí)間片為100 ms，功耗管理時(shí)間片為10

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

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

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

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

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

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