應(yīng)用情景檢測(cè)的安全任務(wù)內(nèi)電壓調(diào)度算法

陳 杰，易本順

(武漢大學(xué)電子信息學(xué)院 武漢 430079)

隨著移動(dòng)電話、PDA、數(shù)碼相機(jī)等移動(dòng)嵌入式實(shí)時(shí)系統(tǒng)發(fā)展的日新月異，逐漸增多的大數(shù)據(jù)量處理與其電池供電、能量有限的矛盾也日益突出，促使研究者們探索延長(zhǎng)電池工作時(shí)間的方法。動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)及電壓可調(diào)處理器的出現(xiàn)為降低處理器能耗提供了一種有效方法[1-2]，它們可針對(duì)處理器不同計(jì)算量的任務(wù)分配不同的電壓等級(jí)，在滿足任務(wù)處理實(shí)時(shí)性(也即安全性)的同時(shí)，減少處理器空閑時(shí)間、降低能耗，能獲得很好的節(jié)能效果[3-4]。近年來(lái)，研究者們提出了任務(wù)內(nèi)的電壓調(diào)度策略，在任務(wù)程序中設(shè)置電壓調(diào)整點(diǎn)(VSP)對(duì)電壓進(jìn)行實(shí)時(shí)調(diào)整，算法簡(jiǎn)單易行而節(jié)能效果更優(yōu)。

根據(jù)剩余處理路徑預(yù)測(cè)策略的不同，任務(wù)內(nèi)的電壓調(diào)度算法可分為基于剩余最壞情況處理路徑(RWEP)[5]、基于剩余平均情況處理路徑(RAEP)[6]及基于剩余最優(yōu)化情況處理路徑(ROEP)[7]共3類。因該3類基本算法在實(shí)際應(yīng)用中存在節(jié)能效果不佳或?qū)崟r(shí)性難以確保的缺陷，文獻(xiàn)[8]提出了3種改進(jìn)的基于RAEP的電壓調(diào)度算法及其實(shí)時(shí)性確保方法，并提出應(yīng)用任務(wù)程序的數(shù)據(jù)流和控制流信息標(biāo)識(shí)VSPs，并將VSPs盡可能前移以優(yōu)化調(diào)度任務(wù)處理電壓。雖顯著地降低了任務(wù)處理能耗，卻引入了大量的預(yù)處理開銷。文獻(xiàn)[9]提出了基于RWEP的情景感知任務(wù)內(nèi)電壓優(yōu)化調(diào)度技術(shù)(簡(jiǎn)稱為SA-RWEP)，根據(jù)人為經(jīng)驗(yàn)設(shè)置情景檢測(cè)點(diǎn)(SDP)，對(duì)少數(shù)變量進(jìn)行前攝檢測(cè)、提前感知及利用空閑時(shí)隙，引入的預(yù)處理開銷小、節(jié)能效果明顯，性能更優(yōu)。

基于文獻(xiàn)[9]，本文提出一種改進(jìn)的SD-RAEP。首先，引入基于RAEP的輪廓感知安全任務(wù)內(nèi)電壓調(diào)度算法(簡(jiǎn)稱為PAS-RAEP)；然后，陳述在待處理的任務(wù)代碼中選擇參數(shù)及依其定義情景的方法；最后，提出SDP設(shè)置算法，以便在代碼合理位置檢測(cè)情景的發(fā)生。算法節(jié)能效果明顯、具有很好的實(shí)時(shí)性。

1 能耗模型與任務(wù)模型

處理器能耗由動(dòng)態(tài)能耗和漏電能耗兩部分組成。降低處理器工作電壓會(huì)線性地降低工作頻率，導(dǎo)致任務(wù)處理時(shí)間延長(zhǎng)，而其能耗和功耗分別以大于工作電壓二次方和三次方的幅值降低。因此，根據(jù)任務(wù)參數(shù)，在任務(wù)處理實(shí)時(shí)性得到滿足的前提下，降低處理器工作電壓、減少空閑時(shí)隙，不僅可以提高處理器利用率，而且可以顯著地降低能耗[2]。

2 SD-RAEP算法

2.1 PAS-RAEP算法

SD-RAEP算法將具有最大加權(quán)概率的處理路徑作為參考路徑，并依此預(yù)測(cè)基本塊的剩余平均處理時(shí)鐘周期數(shù)為：

2.2 參數(shù)選擇和情景定義

在任務(wù)程序代碼中，一些參數(shù)取不同值時(shí)任務(wù)工作量變化較大，這些參數(shù)一般只能取少數(shù)幾個(gè)值，可以在程序中執(zhí)行輸入數(shù)據(jù)或加入賦值語(yǔ)句的方式進(jìn)行設(shè)定，且在余下部分(或全部)的任務(wù)處理過(guò)程中保持不變?；谠撌聦?shí)，可以利用這些參數(shù)的值域劃分應(yīng)用情景，在任務(wù)處理時(shí)根據(jù)所發(fā)生的情景較為精確地預(yù)測(cè)任務(wù)處理的部分路徑，剔除多余路徑，優(yōu)化調(diào)度余下基本塊電壓、降低任務(wù)處理能耗[9]。

根據(jù)各個(gè)參數(shù)取不同值時(shí)任務(wù)工作量的最大變化(簡(jiǎn)稱為影響因子或IC)的大小，選擇若干參數(shù)定義情景以在處理任務(wù)時(shí)進(jìn)行檢測(cè)。在該過(guò)程中，一般不必計(jì)算所有參數(shù)的IC，而只需選擇在各個(gè)結(jié)構(gòu)條件表達(dá)式中出現(xiàn)的參數(shù)進(jìn)行計(jì)算即可。在計(jì)算參數(shù)v的ICv時(shí)，以從后向前的方式遍歷程序抽象句法樹，按式(6)～式(9)規(guī)則計(jì)算各個(gè)結(jié)構(gòu)的ICv，累加得到v對(duì)任務(wù)的影響因子，該計(jì)算過(guò)程基于最壞情況處理時(shí)鐘周期數(shù)(WCEC)。式(6)～式(9)中，S表示非控制型語(yǔ)句，v對(duì)其影響因子為0；B為條件表達(dá)式，B1及B2為語(yǔ)句段；nmin和nmax分別表示循環(huán)迭代的最小和最大次數(shù)，式(7)～式(9)為3種基本結(jié)構(gòu)IC的計(jì)算規(guī)則。可選擇IC相對(duì)較大的參數(shù)定義情景：在任務(wù)代碼中，收集與每個(gè)所選參數(shù)進(jìn)行比較的常數(shù)及相應(yīng)比較符，利用其劃分所選參數(shù)的取值區(qū)間，每個(gè)區(qū)間對(duì)應(yīng)任務(wù)處理的一種情景。

2.3 SDP設(shè)置算法

根據(jù)所選定的參數(shù)和定義的情景，便可在任務(wù)程序中的適當(dāng)位置設(shè)置SDP。SDP需檢測(cè)任務(wù)處理過(guò)程中所發(fā)生的情景，由幾行計(jì)算和判斷語(yǔ)句完成。激活的情景應(yīng)得到及時(shí)的感知，因此，在任務(wù)第一個(gè)基本塊之前應(yīng)設(shè)置SDP，檢測(cè)程序輸入數(shù)據(jù)所激活的情景，而在所選參數(shù)的值可確定時(shí)也應(yīng)設(shè)置SDP。SDP設(shè)置算法的偽代碼借用了文獻(xiàn)[8]中變量前趨點(diǎn)及先行點(diǎn)的概念。設(shè)置SDP算法如下：

算法功能由函數(shù)SDP_Setup和Find_MDP實(shí)現(xiàn)。SDP_Setup完成SDP設(shè)置點(diǎn)的迭代搜索、確定及SDP設(shè)置全過(guò)程。首先調(diào)用SetSDP在任務(wù)第一個(gè)基本塊之前設(shè)置SDP；然后調(diào)用Find_Conditions_Line搜索程序各個(gè)結(jié)構(gòu)的條件表達(dá)式中包含先前選定參數(shù)且以vi的取值情況作為條件成立判據(jù)之一的行，函數(shù)返回其行號(hào)集將其中的元素稱為基準(zhǔn)點(diǎn)，針對(duì)基準(zhǔn)點(diǎn)sj，應(yīng)用Find_MDP函數(shù)，迭代搜索的前趨點(diǎn)集和先行點(diǎn)集最后在先行點(diǎn)處設(shè)置SDP。Find_MDP完成搜索參數(shù)多級(jí)前趨點(diǎn)集。首先搜索輸入行處輸入?yún)?shù)的前趨點(diǎn)集P，稱此時(shí)的輸入?yún)?shù)為中間變量，前趨點(diǎn)p為中間變量前趨點(diǎn)；然后對(duì)p中等式右邊的變量進(jìn)行識(shí)別，構(gòu)成變量集V′(p)，如果其非空，則調(diào)用Find_MDP對(duì)V′(p)中的變量繼續(xù)進(jìn)行迭代搜索，函數(shù)返回最終搜索結(jié)果。

對(duì)于存在一個(gè)或多個(gè)SDP的點(diǎn)，判斷各個(gè)SDP所涉及的參數(shù)，如果參數(shù)vi的每個(gè)相關(guān)情景發(fā)生時(shí)，任務(wù)的預(yù)測(cè)剩余處理路徑與不進(jìn)行情景檢測(cè)時(shí)的預(yù)測(cè)路徑相同，則在該點(diǎn)取消對(duì)vi的情景檢測(cè)。完成SDP的設(shè)置后，采用PAS-RAEP算法對(duì)參考路徑基本塊進(jìn)行電壓調(diào)度并處理，任務(wù)處理偏離參考路徑時(shí)則重新確定參考路徑并更改處理頻率。當(dāng)任務(wù)處理到達(dá)SDP設(shè)置處時(shí)，利用中間變量前趨點(diǎn)處的表達(dá)式(由Transform函數(shù)關(guān)聯(lián))計(jì)算vi值后判斷其哪一個(gè)情景被激活，并在相應(yīng)基準(zhǔn)點(diǎn)移除部分代碼或判據(jù)，如所移除的代碼中包含其他基準(zhǔn)點(diǎn)，移除代碼的同時(shí)也應(yīng)移除這些基準(zhǔn)點(diǎn)對(duì)應(yīng)的SDP，之后仍需重新確定參考路徑及進(jìn)行頻率更新。

3 仿真實(shí)驗(yàn)與分析

通過(guò)仿真實(shí)驗(yàn)對(duì)SD-RAEP算法性能進(jìn)行分析，算法各步驟在SUIF2平臺(tái)上實(shí)現(xiàn)。假定處理器最小處理頻率為20 MHz，最大可達(dá)66 MHz(如采用ARM 7TDM I內(nèi)核的微處理器S3C44B0X)，且在該范圍內(nèi)，頻率可連續(xù)轉(zhuǎn)換，轉(zhuǎn)換開銷為70 μs。分支結(jié)構(gòu)任選的一條有向邊的概率值由標(biāo)準(zhǔn)差為1、均值為0.5的正態(tài)分布計(jì)算得到，選擇參考路徑及基于RAEP的電壓調(diào)度時(shí)，考慮情景檢測(cè)所引入的開銷，而將任務(wù)的截止期設(shè)置為最壞情況處理時(shí)間的1.5倍。通過(guò)MP3解碼多媒體應(yīng)用[10]，仿真實(shí)驗(yàn)驗(yàn)證了在移動(dòng)嵌入式實(shí)時(shí)系統(tǒng)的低功耗設(shè)計(jì)中，應(yīng)用SD-RAEP算法能顯著地降低系統(tǒng)能量開銷，保證任務(wù)處理的實(shí)時(shí)性，且比SA- RWEP性能更優(yōu)。

表1 MP3解碼器中IC值較大的參數(shù)

計(jì)算MP3解碼器中參數(shù)的IC，其值大于100的參數(shù)已在表1中列出。由于第二個(gè)參數(shù)與第三個(gè)參數(shù)的IC值相差較大，因此，可以選擇前兩個(gè)參數(shù)定義情景。表2對(duì)SD-RAEP與SA-RWEP在平均節(jié)省能量及情景檢測(cè)引入開銷(以時(shí)鐘周期數(shù)計(jì))兩項(xiàng)指標(biāo)上進(jìn)行了性能比較，解碼器輸入處理文件為隨意在因特網(wǎng)下載的立體聲歌曲，平均節(jié)省能量以基于RWEP的電壓調(diào)度算法結(jié)果[5]為參考且表中所列為20次實(shí)驗(yàn)結(jié)果的平均值。同時(shí)，仿真實(shí)驗(yàn)也對(duì)只選最大IC值參數(shù)及選擇兩個(gè)以上參數(shù)定義情景的情況進(jìn)行了比較與分析。

從表2中可知，SD-RAEP較SA-RWEP節(jié)省更多能量?；赗WEP的電壓調(diào)度算法雖能較好地滿足處理的實(shí)時(shí)性要求，然而，由于任務(wù)的處理很可能不會(huì)沿著最長(zhǎng)路徑且處理器頻率范圍有限，因此，基于該方法的電壓調(diào)度可能會(huì)留有較多的空閑時(shí)隙，節(jié)能效果一般；而基于RAEP是以最大加權(quán)概率的處理路徑作為參考路徑的輪廓感知安全任務(wù)內(nèi)電壓調(diào)度算法，既考慮了剩余處理路徑的概率，又考慮了該路徑的時(shí)鐘周期數(shù)，不會(huì)產(chǎn)生空閑時(shí)隙，比基于RWEP的電壓調(diào)度算法的節(jié)能效果要好很多，而處理的實(shí)時(shí)性也能得到保證。另外，SA-RWEP根據(jù)人為經(jīng)驗(yàn)設(shè)置SDP，雖然可以有效地控制SDP數(shù)量，算法相對(duì)簡(jiǎn)單，任務(wù)的預(yù)處理階段的開銷也較小，然而，缺乏依據(jù)的SDP設(shè)置方法會(huì)造成情景檢測(cè)過(guò)早或不及時(shí)，使得情景發(fā)生后卻無(wú)法感知或延遲感知，電壓調(diào)度優(yōu)化效果及節(jié)能效果有限或無(wú)效果。應(yīng)用本文提出的SDP設(shè)置算法能最早地精確感知情景的發(fā)生并及時(shí)準(zhǔn)確地做出路徑預(yù)測(cè)及相應(yīng)代碼與CFG圖簡(jiǎn)化處理，適時(shí)調(diào)整處理電壓，最大程度地節(jié)省能量。通過(guò)在所有參數(shù)情景激活點(diǎn)設(shè)置SDP，算法也能感知參數(shù)各個(gè)情景狀態(tài)的變化，而加入的較多的情景檢測(cè)代碼也引入了更多的額外開銷，如表2所示。然而，當(dāng)提前檢測(cè)到的任務(wù)剩余工作量的預(yù)測(cè)值變化較大時(shí)，其對(duì)節(jié)能效果的影響較小。從表中也可以看出，增加參數(shù)mode_extension定義情景為應(yīng)用SD-RAEP的最佳方案，節(jié)能性最優(yōu)；而如增加參數(shù)m ixed_block_flag，反而會(huì)降低節(jié)能效果。

表2 SD-RAEP與SA-RWEP的性能比較

4 結(jié) 論

在研究了目前存在的任務(wù)內(nèi)電壓調(diào)度策略后，本文提出基于情景檢測(cè)的安全任務(wù)內(nèi)電壓調(diào)度算法，以降低移動(dòng)嵌入式實(shí)時(shí)系統(tǒng)的任務(wù)處理能耗。仿真實(shí)驗(yàn)證實(shí)應(yīng)用該算法能在任務(wù)處理過(guò)程中及時(shí)感知發(fā)生的情景，優(yōu)化地調(diào)度處理電壓，明顯地降低處理能耗而實(shí)時(shí)性也能得到保證，從而實(shí)現(xiàn)系統(tǒng)低功耗運(yùn)行的目的。

[1] YUAN L, QU G. Analysis of energy reduction on dynam ic voltage scaling-enabled systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005, 24(12): 1827-1837.

[2] WANG A, CHANDRAKASAN A. Energy-efficient DSPs for w ireless sensor networks[J]. IEEE Signal Processing Magazine, 2002, 19(4): 68-78.

[3] YUAN T, EKICI E. Cross-layer collaborative in-network processing in multihop w ireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(3): 297-310.

[4] 桂盛霖, 雷航. 能耗限制的松弛任務(wù)實(shí)時(shí)調(diào)度算法[J]. 電子科技大學(xué)學(xué)報(bào), 2008, 37(4): 598-601.

GUI Sheng-lin, LEI Hang. On energy-constrained real-time scheduling for elastic tasks[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(4):598-601.

[5] SHIN D, KIM J, LEE S. Intra-task voltage scheduling for low-energy hard real-time applications[J]. IEEE Design &Test of Computers, 2001, 18(2): 20-30.

[6] SHIN D, KIM J. Intra-task voltage scheduling on DVS-enabled hard real-time systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(10): 1530-1549.

[7] SEO J, KIM T, LEE J. Optimal intratask dynamic voltage-scaling technique and its practical extensions[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(1): 47-57.

[8] SHIN D, KIM J. Optimizing intratask voltage scheduling using profile and data-flow information[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(2): 369-385.

[9] GHEORGHITA S V, BASTEN T, CORPORAAL H.Intra-task scenario-aware voltage scheduling[C]//Proceedings of the 2005 International Conference on Compilers, Architectures and Synthesis for Embedded Systems. New York: ACM, 2005.

[10] LAGERSTROM K. Design and implementation of an MP3 decoder[EB/OL]. [2009-07-13]. http://www.km lager.com.

編 輯 張 俊