陳 杰，易本順

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

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

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

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

1 能耗模型與任務模型

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

2 SD-RAEP算法

2.1 PAS-RAEP算法

SD-RAEP算法將具有最大加權概率的處理路徑作為參考路徑，并依此預測基本塊的剩余平均處理時鐘周期數為：

2.2 參數選擇和情景定義

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

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

2.3 SDP設置算法

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

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

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

3 仿真實驗與分析

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

表1 MP3解碼器中IC值較大的參數

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

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

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

4 結 論

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

[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] 桂盛霖, 雷航. 能耗限制的松弛任務實時調度算法[J]. 電子科技大學學報, 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.

編 輯 張 俊