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

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

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

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

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

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

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

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

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