張海燕　劉彥　陳曉明　趙一弘

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

關鍵詞：遺傳算法；任務調度；功耗控制

中圖分類號：TP316.4 文獻標識碼：A

Abstract：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.

Key words：genetic algorithms；task scheduling；power control

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

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

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

1 相關研究

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

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

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

2 系統(tǒng)模型

2.1 系統(tǒng)結構與假設

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

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

2.2 問題的描述

3.2 算法執(zhí)行框架

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

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

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

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

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

4.1 實驗環(huán)境

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

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

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

4.2 實驗結果與討論

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

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

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

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

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

5 結 論

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

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

參考文獻

[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，et al.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，et al.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，F(xiàn)ARKAS K，JOUPPI N，et al.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，et al.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.