一類異構(gòu)多處理器片上系統(tǒng)任務(wù)調(diào)度算法研究與應(yīng)用.pdf

1、由于芯片制造工藝的限制，處理器頻率的繼續(xù)提升遇到了物理瓶頸，多處理器技術(shù)被認為是維持片上系統(tǒng)性能增長的有效方法。異構(gòu)多處理器片上系統(tǒng)(Multi-Processor System-on-Chip，MPSoC)兼顧了系統(tǒng)的通用性與靈活性，受到了工業(yè)界和學(xué)術(shù)界的青睞，已經(jīng)被廣泛應(yīng)用于移動通信、嵌入式多媒體等領(lǐng)域。對于異構(gòu)MPSoC來說，其性能的充分發(fā)揮依賴于所采用的任務(wù)調(diào)度算法。高效的調(diào)度算法可以緩解處理器數(shù)目增加所帶來的高能耗、高溫度、高

2、成本等問題，能夠進一步擴大MPSoC的應(yīng)用范圍。在滿足各種約束的前提下對異構(gòu)MPSoC進行優(yōu)化調(diào)度已經(jīng)證明是NP難問題。因而，針對異構(gòu)MPSoC的各種應(yīng)用需求，尋求不同優(yōu)化目標下的最佳調(diào)度方案，已經(jīng)成為當今多處理器技術(shù)的研究熱點和重點。
　　隨著可重構(gòu)技術(shù)和MPSoC的發(fā)展，出現(xiàn)了包含可重構(gòu)資源的異構(gòu)MPSoC，它兼具可重構(gòu)資源的高效性和MPSoC的靈活性，為系統(tǒng)設(shè)計和應(yīng)用提供了更多的選擇。對含有可重構(gòu)資源的異構(gòu)MPSoC而言，任

3、務(wù)調(diào)度時還需要完成軟硬件劃分，因而進一步增加了問題的復(fù)雜度。針對具有可重構(gòu)功能的異構(gòu)MPSoC，以充分發(fā)揮可重構(gòu)資源的性能、解決異構(gòu)MPSoC所面臨的能耗和溫度問題為出發(fā)點，分別開展軟硬件優(yōu)化劃分算法、節(jié)能調(diào)度算法和溫度感知調(diào)度算法研究。論文的具體工作如下：
　　(1)針對雙路軟硬件劃分的特點，借鑒0/1背包問題的相關(guān)算法思想，基于模擬退火算法的全局尋優(yōu)特性，提出了一種融合貪心算法與模擬退火算法的軟硬件劃分方法。該方法在研究雙路軟

4、硬件劃分系統(tǒng)結(jié)構(gòu)基礎(chǔ)上，首先將軟硬件劃分問題規(guī)約為0/1背包問題，采用貪心算法進行快速初始劃分；然后設(shè)計一種新的接收準則，根據(jù)新解在擾動模型中的位置來計算其接收概率，基于貪心算法的預(yù)劃分結(jié)果，采用改進的模擬退火算法進行全局尋優(yōu)。由于該算法兼具貪心算法的高效性和模擬退火算法的全局尋優(yōu)能力，從而避免了模擬退火算法初始劃分難以設(shè)定的問題，在任務(wù)劃分質(zhì)量和算法運行時間方面均取得了較好的效果。仿真實驗證明了本文所提算法的有效性。
　　(2)

5、針對異構(gòu)MPSoC中處理器數(shù)目增長所引起的高能耗問題，考慮遺傳算法的高效搜索能力，采用動態(tài)電壓縮放技術(shù)，提出了一種新的節(jié)能調(diào)度算法。該算法首先對遺傳算法的選擇算子和群體更新機制進行改進，增強了群體的多樣性，然后基于改進的遺傳算法來確定任務(wù)優(yōu)先級，采用鏈表調(diào)度方法確定任務(wù)執(zhí)行順序；最后根據(jù)任務(wù)能量和時間關(guān)系，設(shè)計了一種新的任務(wù)縮放優(yōu)先級計算方法，基于該優(yōu)先級進行節(jié)能調(diào)度。該算法在具備遺傳算法的高效搜索能力的同時，彌補了其容易陷入局部最優(yōu)解

6、的缺陷，并且通過對高能耗任務(wù)進行有針對性的縮放，很好地實現(xiàn)系統(tǒng)節(jié)能。
　　(3)針對能量密度增長給異構(gòu)MPSoC所帶來的溫度提升，考慮漏極功率、供電電壓和溫度之間的關(guān)系，以系統(tǒng)峰值溫度最小化為優(yōu)化目標，提出了一種新的溫度感知調(diào)度算法。溫度升高將直接縮短處理器的生命周期，同時影響系統(tǒng)性能和使用舒適度。本文首先針對異構(gòu)MPSoC應(yīng)用推廣所面臨的溫度問題，在溫度與供電電壓關(guān)系的基礎(chǔ)上，考慮處理器的漏極功率，建立溫度模型；然后根據(jù)任務(wù)關(guān)鍵

7、路徑進行初始調(diào)度，在溫度模型基礎(chǔ)上計算任務(wù)的運行溫度，運用動態(tài)電壓縮放技術(shù)，通過迭代操作優(yōu)化系統(tǒng)峰值溫度。該算法中所考慮的溫度模型更為實際，并且直接對具有峰值溫度的任務(wù)進行優(yōu)化，從而能夠顯著降低系統(tǒng)峰值溫度和平均溫度。
　　(4)針對本文提出的任務(wù)調(diào)度算法，在相關(guān)嵌入式系統(tǒng)中進行了應(yīng)用研究。針對湖南省科研條件創(chuàng)新專項“三維熒光光譜儀高性能數(shù)學(xué)分離關(guān)鍵部件研制”，進行了軟硬件劃分算法應(yīng)用研究。該部件的核心是“數(shù)學(xué)分離”算法，涉及到大

8、量的高維矩陣運算，在嵌入式應(yīng)用中需要解決復(fù)雜計算問題。本文通過分析問題的計算特性，采用通用處理器和可重構(gòu)資源相結(jié)合的方式，進行系統(tǒng)結(jié)構(gòu)設(shè)計；然后運用本文提出的軟硬件劃分方法，對任務(wù)進行劃分，獲得了較好的系統(tǒng)性能。針對國家發(fā)改委項目“中國網(wǎng)上教育平臺”子項--“移動學(xué)習(xí)平臺”，進行了節(jié)能調(diào)度算法應(yīng)用研究。嵌入式移動平臺特別關(guān)注能耗問題，本文采用具有較好電源管理功能的PXA255芯片進行系統(tǒng)設(shè)計，并進行動態(tài)電壓縮放技術(shù)的具體實現(xiàn)。在此基礎(chǔ)上