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

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

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

【參考文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：2693427