基于化學(xué)反應(yīng)優(yōu)化和優(yōu)先級的異構(gòu)多核低功耗調(diào)度研究.pdf

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

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

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

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

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