低功耗軟硬件劃分算法研究.pdf

1、面對依靠電池供電的便攜嵌入式移動設(shè)備在能量使用方面受到的嚴格限制以及電池技術(shù)的發(fā)展速度遠遠落后于集成電路發(fā)展速度的現(xiàn)狀，低功耗嵌入式系統(tǒng)設(shè)計已經(jīng)受到學(xué)術(shù)界和工業(yè)界的普遍重視。鑒于軟硬件劃分對系統(tǒng)功耗的關(guān)鍵影響，本文立足于解決低功耗軟硬件劃分問題的算法研究。
　　低功耗軟硬件劃分問題是NP難的組合優(yōu)化問題。通過綜述以往相關(guān)工作，發(fā)現(xiàn)整數(shù)規(guī)劃和分支定界等確定性算法只能用于求解小規(guī)模問題的精確解，大部分工作使用遺傳算法、模擬退火算法等啟

2、發(fā)式算法求得問題的近似最優(yōu)解。但是缺乏能夠代表大部分實際設(shè)計情況的低功耗軟硬件劃分形式化模型，使得以往的大部分工作只能解決特定情況下的軟硬件劃分問題，算法缺乏通用性，而且不同的算法之間很難進行比較。同時當前智能優(yōu)化算法發(fā)展迅速，一方面表現(xiàn)在融合不同算法的優(yōu)勢設(shè)計混合智能優(yōu)化算法，這類混合算法經(jīng)常表現(xiàn)出更好的全局尋優(yōu)能力和更快的設(shè)計空間探索速度；另一方面研究人員通過不斷地觀察物質(zhì)的變化過程和生物體的進化過程，近些年又提出了一些新的智能優(yōu)化

3、算法，這些算法在低功耗軟硬件劃分問題方面的應(yīng)用也值得深入研究。
　　本文首先定義了以嵌入式多處理器系統(tǒng)為目標結(jié)構(gòu)的低功耗系統(tǒng)級軟硬件劃分形式化模型，以功耗作為優(yōu)化目標，以系統(tǒng)執(zhí)行時間、軟件處理器內(nèi)存和專用集成電路面積作為約束條件。該形式化模型的定義明確了低功耗軟硬件劃分問題的優(yōu)化目標和約束條件，說明了解決該問題的啟發(fā)式智能優(yōu)化算法的適應(yīng)度函數(shù)，后面各章都是根據(jù)該適應(yīng)度函數(shù)計算優(yōu)化算法得到的軟硬件劃分解的功耗值。
　　雖然以往

4、的相關(guān)工作已經(jīng)使用構(gòu)建算法、遺傳算法、模擬退火算法等智能優(yōu)化算法解決了低功耗軟硬件劃分問題，但這些算法往往存在執(zhí)行速度慢、易于陷入局部最優(yōu)解等缺陷。本文融合禁忌搜索算法優(yōu)秀的“爬山”能力和神經(jīng)網(wǎng)絡(luò)算法在解決組合優(yōu)化問題時的出色表現(xiàn)，提出了基于神經(jīng)網(wǎng)絡(luò)的禁忌搜索算法。該算法的設(shè)計思想是：真實生物神經(jīng)元在已經(jīng)激活過之后重新激活會受到抑制，抑制神經(jīng)元重復(fù)激活的阻尼特性對應(yīng)禁忌搜索算法限制重復(fù)搜索的禁忌活動，借助神經(jīng)網(wǎng)絡(luò)的迭代方程實現(xiàn)禁忌搜索算

5、法。對多個真實任務(wù)圖的低功耗軟硬件劃分的仿真實驗表明，該算法在全局搜索能力和設(shè)計空間探索速度方面都超過在軟硬件劃分領(lǐng)域被廣泛應(yīng)用的遺傳算法。在這個算法的基礎(chǔ)上，考慮到混沌優(yōu)化能夠遍歷設(shè)計空間的特性和精致的內(nèi)在規(guī)律性，本文又在神經(jīng)網(wǎng)絡(luò)中引入混沌動態(tài)，提出了基于混沌神經(jīng)網(wǎng)絡(luò)的禁忌搜索算法，混沌對設(shè)計空間的遍歷性增強了算法跳出局部最優(yōu)的能力。通過對 GSM編碼器任務(wù)圖的低功耗軟硬件劃分的仿真實驗，該算法具有優(yōu)秀的全局搜索能力和較快的執(zhí)行速度，

6、能夠很好地兼顧對設(shè)計空間地“挖掘”和“探索”，所得低功耗軟硬件劃分解的總體質(zhì)量優(yōu)于遺傳算法。雖然本文設(shè)計的融合了神經(jīng)網(wǎng)絡(luò)、混沌優(yōu)化和禁忌搜索各自優(yōu)勢的混合智能優(yōu)化算法以低功耗軟硬件劃分作為典型問題，但是這種混合智能優(yōu)化算法也可用于其他組合優(yōu)化問題的求解。
　　近年來有別于傳統(tǒng)計算方法的量子計算受到了廣泛地關(guān)注。量子計算利用量子態(tài)的疊加性和相干性，以及量子比特之間的糾纏性，把量子力學(xué)的概念和理論引入算法領(lǐng)域，它和其他經(jīng)典算法最本質(zhì)的

7、區(qū)別在于量子計算的并行性。如果利用量子計算的并行性優(yōu)勢把量子算法和遺傳算法結(jié)合，得到量子遺傳算法，就能夠以更小的種群規(guī)模、在更短的時間內(nèi)找到問題的最優(yōu)解。針對嵌入式多處理器的目標結(jié)構(gòu)，本文提出了解決低功耗軟硬件劃分問題的量子遺傳算法，用染色體表示系統(tǒng)設(shè)計任務(wù)對處理單元的匹配，用量子位編碼表示染色體，量子位編碼特有的概率幅表示使得一個量子染色體能夠同時表征多種匹配情況，并通過旋轉(zhuǎn)量子門進行進化搜索更新，保證種群多樣性。通過 MP3解碼器任

8、務(wù)圖和 GSM解碼器任務(wù)圖的低功耗軟硬件劃分測試，量子遺傳算法得到的軟硬件劃分解的功耗均值和方差都優(yōu)于遺傳算法，而且進化過程穩(wěn)定，算法能有效地跳出局部最優(yōu)解。本文的工作擴大了量子遺傳算法的應(yīng)用領(lǐng)域，是量子遺傳算法解決低功耗軟硬件劃分問題的首次嘗試。
　　上面解決的、基于嵌入式多處理器系統(tǒng)的目標結(jié)構(gòu)、以功耗作為優(yōu)化目標、以軟件處理器內(nèi)存、專用集成電路面積和系統(tǒng)執(zhí)行時間作為約束條件的低功耗軟硬件劃分問題屬于單目標優(yōu)化，能夠滿足大部分系

9、統(tǒng)的設(shè)計要求。而另外有些系統(tǒng)設(shè)計要求在軟硬件劃分過程中同時優(yōu)化功耗和其他的設(shè)計目標，例如系統(tǒng)執(zhí)行時間，對于這類多目標優(yōu)化的軟硬件劃分問題，本文提出了基于Pareto存檔種群進化和個體遷移的多目標進化算法，在硬件面積和軟件處理器內(nèi)存的約束條件下，同時優(yōu)化系統(tǒng)執(zhí)行時間和功耗。精英種群和單目標種群協(xié)同進化的機制以及將精英種群的優(yōu)秀個體遷移到單目標種群的錦標賽選取規(guī)則提高了算法的收斂速度和非控解的精度。對GSM解碼器任務(wù)圖在一個通用處理器和兩個