【摘要】：對于電池供電的嵌入式設(shè)備來說,低能耗是一個關(guān)鍵設(shè)計指標(biāo),嵌入式低能耗研究有著廣闊的應(yīng)用前景和重要的應(yīng)用價值,逐漸引起工業(yè)界和學(xué)術(shù)界的高度關(guān)注。本文研究了嵌入式系統(tǒng)的節(jié)能調(diào)度問題。針對嵌入式系統(tǒng)中具有嚴(yán)格執(zhí)行時限要求的周期性任務(wù),提出了四種節(jié)能調(diào)度算法。還針對無線傳感器網(wǎng)絡(luò),提出了三維空間K虛擬柵欄覆蓋節(jié)能調(diào)度算法。 對于電壓可變的處理器,已有研究考慮了理想的具有連續(xù)可變電壓的處理器模型,而真實的可變電壓處理器僅具有離散的電壓等級。動態(tài)電壓縮放(Dynamic Voltage Scaling,DVS)是一個有效的節(jié)能技術(shù),它通過降低處理器運行時的電壓來節(jié)能。但是,降低電壓的同時會導(dǎo)致任務(wù)執(zhí)行時間增加,因此需要優(yōu)化延遲和能耗這對互為矛盾的指標(biāo)。 對于具有離散電壓等級的單處理器,本文首先提出了一種最優(yōu)電壓選擇算法,使得在不違背給定應(yīng)用執(zhí)行時限的前提下系統(tǒng)能耗最少。與已有啟發(fā)式算法不同,最優(yōu)電壓選擇算法將該節(jié)能調(diào)度問題轉(zhuǎn)化為多選擇背包問題的變種,然后采用動態(tài)規(guī)劃方法求得最優(yōu)解。更進(jìn)一步,由于在處理器上調(diào)度任務(wù)時,電壓切換會引起額外的躍遷代價,影響系統(tǒng)的延遲和能耗,因此又提出了一種改進(jìn)的單處理器節(jié)能調(diào)度算法,該算法考慮了離散電壓模型、動態(tài)能耗,以及電壓躍遷代價。對于多處理器MPSoC架構(gòu)上的任務(wù),傳統(tǒng)任務(wù)調(diào)度算法關(guān)注并行化的挖掘以提高系統(tǒng)吞吐率,降低延遲�，F(xiàn)在,MPSoC架構(gòu)已被廣泛的應(yīng)用到嵌入式系統(tǒng)中,像多媒體和網(wǎng)絡(luò)處理等計算密集型的嵌入式應(yīng)用,對能耗和延遲都很關(guān)注,因而對任務(wù)調(diào)度算法提出了新的挑戰(zhàn)。針對運行在MPSoC架構(gòu)上的實時嵌入式應(yīng)用,提出了兩種兩階段的基于重定時的節(jié)能調(diào)度算法,它們將充分發(fā)掘MPSoC架構(gòu)的并行潛力,并且和減少能耗關(guān)聯(lián)起來考慮,既滿足了應(yīng)用執(zhí)行時限的要求,又達(dá)到了降低應(yīng)用能耗的目標(biāo)。在設(shè)計算法時,兩個算法第一階段都采用重定時技術(shù)進(jìn)行任務(wù)并行化,將一個迭代周期內(nèi)的迭代內(nèi)依賴關(guān)系轉(zhuǎn)化成迭代間的依賴關(guān)系,從而減少了由于迭代內(nèi)依賴關(guān)系和處理器間通信所導(dǎo)致的空閑時隙。這些贏得的空閑時隙在第二個階段所利用以進(jìn)行能量優(yōu)化。在第二個能量優(yōu)化階段,第一個算法是模擬彈簧行為的啟發(fā)式節(jié)能調(diào)度算法,它考慮了動態(tài)能耗和靜態(tài)能耗。更進(jìn)一步,由于影響系統(tǒng)能耗的因素很多,這些因素對能耗的影響又是錯綜復(fù)雜的,所以本文又提出了第二個基于遺傳算法的節(jié)能調(diào)度算法,該算法考慮了多種能耗相關(guān)的因素,如動態(tài)能耗、靜態(tài)能耗、電壓躍遷代價、處理器間通信代價等因素,設(shè)計了染色體的基因編碼方式、適度函數(shù)、交叉算子等。該算法可以充分發(fā)掘多處理器MPSoC架構(gòu)的潛力以及現(xiàn)代芯片的節(jié)能特性,實現(xiàn)對能耗和性能的多目標(biāo)優(yōu)化。 無線傳感器網(wǎng)絡(luò)是典型的分布式嵌入式系統(tǒng),以上所提出的系統(tǒng)級的節(jié)能調(diào)度算法在每一個傳感器硬件節(jié)點上同樣適用。但是對于傳感器網(wǎng)絡(luò),不僅應(yīng)該關(guān)注每一個節(jié)點的能耗,還應(yīng)該從整個網(wǎng)絡(luò)協(xié)同工作角度出發(fā)考慮節(jié)能。因此,本文還研究了無線傳感器網(wǎng)絡(luò)三維空間柵欄覆蓋中的節(jié)能問題。研究表明,單個虛擬柵欄覆蓋的節(jié)點睡眠調(diào)度算法是NP-Hard問題,本文提出了單個虛擬柵欄覆蓋調(diào)度算法求得近似解。在此基礎(chǔ)上,又提出了K-虛擬柵欄覆蓋調(diào)度算法來最優(yōu)化K-虛擬柵欄調(diào)度,使得在同一時刻,在滿足傳感檢測范圍的前提下,讓最少數(shù)量的傳感器節(jié)點交替工作,既滿足網(wǎng)絡(luò)覆蓋要求,又減少能耗,延長了傳感器網(wǎng)絡(luò)的生命周期。
【圖文】：

嵌入式系統(tǒng)節(jié)能調(diào)度算法研究 圖 4.1 本文調(diào)度策略示意圖圖4.1 通過一個例子來闡述本文所提調(diào)度策略的思想內(nèi)涵。圖4.1(a)是原始任務(wù)圖，代表一個周期性應(yīng)用。圖4.1(c)是該任務(wù)在高電壓和低電壓兩種模式下的能耗和計算時間。圖4.1(d)是采用傳統(tǒng)表調(diào)度算法，給兩個處理器核都分配高電壓的情況下完成該應(yīng)用的一個周期內(nèi)的任務(wù)所產(chǎn)生的調(diào)度情況。可以看出，此種調(diào)度需要耗時16μs，，耗能137μJ。圖4.1(e)是采用基于DAG的調(diào)度方法和動態(tài)電源管理方法相結(jié)合產(chǎn)生的一個調(diào)度，它在處理器核PE2空閑時讓PE2進(jìn)入休眠狀態(tài)來節(jié)能，此種調(diào)度耗時16μs，耗能73.4μJ。相比與圖4.1(d)所給方法有了很大的進(jìn)步。但是

圖4.2 一個電路示意圖圖4.3 圖4.2電路示意圖的變形下面解釋延遲的物理意義。如圖4.4(b)所示，假設(shè)一個延遲用邊上的一個橫線表示，則n個延遲就用n條橫線表示。對于任意節(jié)點v ∈V，節(jié)點v的重定時函數(shù)r :V→Z是經(jīng)過節(jié)點v的延遲數(shù)，記作d(e)。對于從節(jié)點u到節(jié)點v的任意一條邊e (u ,v)∈E，若其上的延遲數(shù) d ( e)>0，則表示在第j次循環(huán)中，計算節(jié)點v時需要用到在第 j d(e)次循環(huán)中節(jié)點u計算后得到的數(shù)據(jù)。(a) (b)圖 4.4 任務(wù)圖示例：(a) 原始任務(wù)圖 G (b)重定時后的任務(wù)圖 Gr在電路中
【學(xué)位授予單位】：西安電子科技大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2011
【分類號】：TP368.1

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 趙曉鶯;易江芳;佟冬;程旭;;利用遺傳算法實現(xiàn)CMOS組合電路靜態(tài)功耗優(yōu)化[J];北京大學(xué)學(xué)報(自然科學(xué)版);2007年03期

2 陳燕;董世娜;趙宏杰;;影響電解電容器漏電流的因素[J];電子產(chǎn)品可靠性與環(huán)境試驗;2007年06期

3 駱祖瑩;潘月斗;;CMOS電路晶體管級功耗優(yōu)化方法[J];計算機(jī)研究與發(fā)展;2008年04期

4 李仁發(fā);劉彥;徐成;;多處理器片上系統(tǒng)任務(wù)調(diào)度研究進(jìn)展評述[J];計算機(jī)研究與發(fā)展;2008年09期

5 蔣湘濤;胡志剛;賀建飚;;基于調(diào)用鏈分析的低功耗編譯優(yōu)化[J];吉林大學(xué)學(xué)報(工學(xué)版);2009年01期

6 夏宏,蘇林萍;Cache低功耗技術(shù)研究[J];計算機(jī)工程與應(yīng)用;2005年23期

7 張承義;張民選;;片內(nèi)二級Cache的靜態(tài)功耗優(yōu)化技術(shù)研究[J];計算機(jī)工程與科學(xué);2007年03期

8 賀小川;賈焰;;搶占閾值調(diào)度的功耗優(yōu)化[J];計算機(jī)學(xué)報;2008年11期

9 王力生;郭振軻;;基于DVS的實時多核嵌入式系統(tǒng)低功耗算法[J];計算機(jī)應(yīng)用研究;2009年01期

10 周寬久;遲宗正;西方;;嵌入式軟硬件低功耗優(yōu)化研究綜述[J];計算機(jī)應(yīng)用研究;2010年02期

相關(guān)博士學(xué)位論文 前1條

1 蔣杰;無線傳感器網(wǎng)絡(luò)覆蓋控制研究[D];國防科學(xué)技術(shù)大學(xué);2005年

本文編號：2693427