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

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

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

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

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

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

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

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

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