基于化學反應優(yōu)化和優(yōu)先級的異構多核低功耗調度研究.pdf

1、隨著異構多核處理器計算能力的大幅度提升，能耗問題也成為制約其發(fā)展及應用推廣的性能瓶頸。而低功耗設計技術越靠近頂層，抽象層次越高，對功耗的影響越大，因此針對異構多核處理器系統(tǒng)的實時低功耗調度算法的研究得到了國內外研究者的廣泛關注。
　　 異構多核低功耗調度問題是一個典型的NP難問題，解決該問題的現(xiàn)有算法多采用兩階段的啟發(fā)式策略:首先利用劃分策略將任務分配到各處理單元，然后利用低功耗調度策略確定任務的執(zhí)行順序和處理單元的電壓。然而，

2、這些算法多忽略了算法的時間復雜度及任務相關特性對低功耗技術節(jié)能效果的影響。因此，本文針對異構多核處理器系統(tǒng)模型的特點，基于化學反應優(yōu)化算法全局尋優(yōu)能力強的特性，結合關鍵任務對調度長度的有效控制以及任務能耗和時間屬性對低功耗技術節(jié)能效果的影響，研究一種節(jié)能效率高、收斂速度快的異構多核低功耗調度算法，主要工作如下:
　　 在算法的任務劃分階段，針對現(xiàn)有策略收斂速度慢、全局搜索能力不足等問題，本文基于全局搜索能力強的化學反應優(yōu)化算法提

3、出一種新的任務劃分策略CROTM(Chemical Reaction Optimization for Task Mapping)。CRO是一種元啟發(fā)式算法，它通過模擬化學反應中分子運動這種自然現(xiàn)象得到。算法的核心是四種基本操作:撞墻、分解、交換和合成。交換和撞墻操作可以對局部最優(yōu)值進行有效的搜索。而為了不讓搜索停滯在局部最優(yōu)值里，合成和分解操作可以有效的拓展搜索的領域，從而盡可能的獲取到全局最優(yōu)值。CROTM充分利用CRO的優(yōu)勢，有效

4、地擴展了搜索空間，從而大大提高了獲取到全局最優(yōu)解的可能性。
　　 在算法的低功耗調度階段，針對現(xiàn)有策略時間復雜度高、忽略任務相關特性對低功耗技術節(jié)能效果的影響等問題，本文在分析現(xiàn)有算法的基礎上，結合當前流行的動態(tài)電壓縮放技術，基于關鍵任務能對調度長度進行有效控制的特性，提出一種綜合考慮任務能耗和時間屬性對節(jié)能效果的影響的低功耗調度策略。首先利用任務的關鍵性為優(yōu)先級對任務進行調度，延長松弛時間，增大系統(tǒng)降低功耗的潛力;然后根據(jù)任務

5、的能耗和時間屬性，設計一種任務縮放優(yōu)先級的計算方法，在滿足截止期和依賴關系的條件下，反復選擇具有最佳節(jié)能效果的任務進行電壓調節(jié)，優(yōu)化每次迭代過程中的系統(tǒng)能耗。
　　 為了驗證上述算法，本文基于TGFF工具，利用C++程序描述語言分別實現(xiàn)了本文算法和對比算法，以運行時間和節(jié)能率作為性能指標，對算法進行對比分析，實驗結果表明本文提出的任務劃分策略有效地擴大了問題的解空間，為下一階段的低功耗調度提供了更加豐富的任務分配方案;而本文提出