幾種實時嵌入式系統(tǒng)DVS策略的分類比較*

李煊鵬，張 哲，時龍興， *

(1.東南大學集成電路學院，南京 210096；2.東南大學電子工程學院， 南京210096)

隨著CMOS制造工藝技術的不斷提升以及嵌入式系統(tǒng)軟硬件構架的不斷更新，各種嵌入式設備如移動電話， MP4播放器，數碼相機等性能都獲得了大幅的增長。然而，伴隨著性能的改善，能耗問題越來越成為關注的焦點。電池技術相對落后性能增長的實際情況要求我們不得不將注意力集中到在移動嵌入式設備有限的電池電量條件下，如何最大限度地降低系統(tǒng)功耗以延長有效使用時間，并且在有實時性要求的設備中，如何滿足任務截止時間限。

在所有移動終端中，處理器是整個系統(tǒng)的核心部件，它的性能與功耗情況直接影響到嵌入式設備的運行狀況。目前，兩種主流的降低系統(tǒng)功耗的方法是：①設備關閉，也就是通常我們所說的動態(tài)電源管理(Dynamic Power Management—DPM)和②設備減速，也就是我們將要分析的動態(tài)電壓調節(jié)(Dynamic Voltage Scaling—DVS)[5]。通過處理器調度關閉閑置設備，如內存、硬盤、顯示器、I/O接口等可以有效的降低系統(tǒng)功耗，然而大部分情況下，我們很難實現對這些設備的頻繁操作，并且考慮關斷開銷更讓DPM技術只存在理論價值。然而， DVS技術則根據電壓和功耗之間的關系，運用處理器動態(tài)調節(jié)特性，既滿足任務截止時間限，又通過調節(jié)電壓和頻率實現系統(tǒng)功耗的降低。

本文中，我們將在第1部分中引入DVS策略的模型基礎，介紹DVS技術實現功耗降低的基本原理。在第2部分中，將根據第1部分中提到的策略模型，對關鍵DVS算法進行分類比較。相關算法的仿真將在第3部分中進行描述。最后，第4 部分對實時嵌入式系統(tǒng)DVS策略進行總結。

1 實時DVS策略模型

縱觀實時系統(tǒng)下DVS策略，不難發(fā)現絕大多數策略都基于兩大影響因素，其一，動態(tài)電流功耗，其二，結合漏電流功耗的總功耗。前者是早期大部分文章研究的重點，而后者則在近幾年DVS策略的研究中占有越來越重要的位置。

根據CMOS晶體管特性，動態(tài)電流產生的功耗PAC可有下式表示：

其中， CL表示負載電容， Vdd表示供電電壓， f表示系統(tǒng)頻率。

而供電電壓Vdd與電路延遲τ的關系可由下式表示：

其中， VT表示CMOS晶體管的閾值電壓， VG表示輸入門電壓。

從上述等式我們可以看出，動態(tài)電流功耗PAC與供電電壓Vdd成二次方關系，而電路延遲限制了系統(tǒng)頻率，所以供電電壓Vdd也與頻率f相關。因而，考慮動態(tài)電流作用的DVS策略將根據電壓，頻率與功耗之間的關系，以降低系統(tǒng)動態(tài)功耗為主，并且要求滿足任務截止時間限。

然而，隨著工藝技術的不斷提升，從微米工藝到深亞微米，再到如今的納米級工藝，單個芯片的集成度越來越高，單個CMOS晶體管的閾值電壓呈指數下降趨勢，以至于過去在功耗方面并不起主導作用的漏電流不斷增大。伴隨著越來越大的旁路電流，漏電流所產生的功耗PDC成為整個系統(tǒng)功耗的重要組成部分，其功耗計算由下列等式表示：

其中， Isubn表示子閾值電流， Ij表示反向偏置節(jié)點電流， Vbs表示體偏置電壓。可看出漏電流功耗PDC與供電電壓Vdd也相互關聯。

系統(tǒng)的總功耗P可以由下式表示：

其中， Pon表示系統(tǒng)工作內部電壓功耗。根據漏電流產生的功耗對總功耗的影響，采用計算關鍵點(Critical Point)的方法，尋求最小可能功耗。因而，區(qū)分動態(tài)電流功耗與漏電流功耗將成為我們分類的重要標準。

2 實時DVS策略分類比較

我們分析研究的對象主要是實時系統(tǒng)下周期性任務的動態(tài)電壓調節(jié)(DVS)策略。在本文中，我們將DVS策略分為兩大類：動態(tài)功耗DVS策略和靜態(tài)功耗DVS策略。動態(tài)功耗DVS策略將根據動態(tài)功耗模型進行分析，又可以細化成三類子策略：任務間DVS(InterDVS)策略，任務中DVS(IntraDVS)策略和混合DVS(HybridDVS)策略[8]。而靜態(tài)功耗DVS策略將根據漏電流功耗模型進行分析，更加注重漏電流在系統(tǒng)功耗中的作用，同時考慮整個系統(tǒng)部件功耗，不僅包括處理器以及外圍設備如內存和I/O等[5]。

2.1 動態(tài)功耗DVS策略

動態(tài)功耗的DVS策略利用功耗與電壓，頻率之間的關系，以及實時系統(tǒng)下任務調度策略，如單調速率調度(RM)和最早截止時間優(yōu)先調度(EDF)，來降低系統(tǒng)功耗。實時系統(tǒng)下動態(tài)功耗DVS策略的計算將通過減速因子(slowdown factor)的取值來決定運行時處理器的速度，進而達到滿足任務時限要求的同時降低功耗。減速因子(slowdown factor)則根據系統(tǒng)是否運行時更新狀態(tài)又分別對應離線(Off-Line)算法和在線(On-Line)算法[6]。

由于減速因子對任務執(zhí)行速率的影響，任務會余留一定的空閑時間(slack time)。它是任務實際執(zhí)行時間和最壞運行時間之間的差值。無論任務間DVS策略還是任務中DVS策略都是探求空閑時間進而修正處理器速度。對于任務間DVS策略而言，一般都是采用運行-計算-分配-再運行的步驟。任務間DVS策略又細分為兩部分：空閑時間評估(slack estimation)與空閑時間分配(slack distribution)，后者大多采用貪心算法，即所有的空閑時間都默認全部分配給下一個處于激活狀態(tài)的任務。本文DVS策略主要集中在空閑時間評估上，根據減速因子的特性決定分類，又可分為動態(tài)空閑評估和靜態(tài)空閑評估。動態(tài)空閑評估是一種在線算法，我們將給出三種動態(tài)空閑評估算法類別：

(1)基于優(yōu)先級的空閑時間獲取算法

該類算法基于EDF與RM的調度特性，若高優(yōu)先級任務完成時間早于最壞運行時間(WCET)，后續(xù)的低優(yōu)先級任務能夠使用已完成的高優(yōu)先級任務所余留的空閑時間[9，11]。當然，也可能出現相反的情況，只不過那樣往往需要更大的運行開銷。

(2)處理器利用率更新算法

該類算法通過已完成任務的實際執(zhí)行時間重新計算最壞處理器利用率來評估所需處理器性能。一旦處理器利用率進行了更新，時鐘速率也要進行相應地修正[1]。該類算法的優(yōu)點在于執(zhí)行簡單，僅在單個調度點根據已完成任務的處理器利用率進行更新。

(3)任務到達時間算法

該類算法使用下一任務到達時間(NTA)來評估動態(tài)空閑時間，如果調度點時間t與最壞運行時間WCET的和小于NTA，任務則按更低的速率運行以滿足當前任務完成時間是下一任務到達時間[14]。該類算法相對前一算法計算開銷較大，但考慮到任務到達的閾值時間，具有更好的實時性。

相對于動態(tài)空閑評估而言，靜態(tài)空閑評估算法較為簡單，因為算法靜態(tài)確定下一任務所能獲得的空閑時間，而動態(tài)空閑時間則是來自于任務執(zhí)行期間的運行時變量。靜態(tài)空閑評估是一種離線算法，下面我們給出一種靜態(tài)空閑評估算法：

(4)最大恒速率算法

該類算法是一種最為普遍使用的靜態(tài)空閑評估方法。最大恒速率被定義為能夠保證任務有效調度的最小時鐘頻率[10，14]。例如在EDF調度中，任務的處理器利用率U小于1時(對應于最大處理器速度fmax)，則采用f′max=U?fmax來計算新速率。

相比較任務間DVS策略，任務中DVS策略大多比較簡單，因為是根據單個任務運行狀態(tài)來決定任務的執(zhí)行速率。因而任務中DVS策略大多采用一種離線算法。下面給出兩類任務中DVS策略：

(1)基于路徑算法

該類算法基于預測參考執(zhí)行路徑來進行調度，例如最壞執(zhí)行路徑(WCEP)。當實際執(zhí)行與預測執(zhí)行路徑不同時就對系統(tǒng)時鐘頻率進行調整。如果新路徑要比預測執(zhí)行路徑花費更長的執(zhí)行時間，則調高時鐘頻率。反之，降低時鐘頻率。具體有Shin D等人[12]提出的intraShin算法。

(2)隨機算法

該類算法采用相對保守的策略，認為系統(tǒng)以低速開始運行后提速的方法在功耗節(jié)省上優(yōu)于以高速開始若出現空閑時間而降速的策略[10]。該類算法中，時鐘速度會在特定時間點提升而無論采用何種執(zhí)行路徑。因為采用了相對保守的策略，不像前一策略能夠充分利用所有空閑時間，通過最大程度功耗節(jié)省來彌補性能的損失。

混合DVS策略則根據空閑時間，可以工作在任務間和任務中兩種模式下。它不同于純的任務間或任務中DVS策略，從理論上比后兩者能夠降低更多功耗。

2.2 集成靜態(tài)功耗DVS策略

上述的DVS策略大都通過頻率調節(jié)來進行減速，然而這樣的策略雖然降低動態(tài)功耗卻導致漏電流功耗的增長。特別是近年來，隨著每一代CMOS工藝技術提升，漏電流功耗出現大幅增長，過去的130 nm工藝對應亞閾值漏電流為0.01 μA/μm，而如今的45 nm工藝相應的亞閾值電流則為3 μA/μm，僅電流就提高了30倍，因而降低漏電流功耗就變得越為重要。

基于能耗和減速因子成比例的前提，如 input vector control和power supply gating等用來降低漏電流功耗，以及通過控制體偏置電壓進而調節(jié)閾值電壓的方法和基于自適應體偏置的調度技術也是降低靜態(tài)功耗的方法。這些方法在只考慮處理器功耗時能夠獲得不錯的效果，但當涉及如內存、I/O等設備時，上述方法往往不能起到很好的降低系統(tǒng)總功耗的效果。這就產生了將減速因子(slowdown)與關斷因子(shutdown)組合考慮的新方法來降低功耗。這里，處于關斷(shutdown)狀態(tài)被認為是幾乎沒有漏電流功耗的狀態(tài)。

在早期研究中， Irani等人[15]考慮了DVS與關斷因子的組合問題，作者基于連續(xù)電壓范圍和功耗凸函數(convex power consumption function)的假設提出了一種競爭性離線算法。 Lee Y等人[16]提出了實時周期系統(tǒng)下的一種延遲調度(procrastination scheduling)策略以及Leakage Control EDF(LC-EDF)和Leakage Control Dual Priority(LC-DP)調度算法。單個設備的延遲算法將決定系統(tǒng)何時進入或離開關斷狀態(tài)。延遲算法通過延長睡眠間隔能夠有效地減少喚醒次數，能夠帶來更高效的系統(tǒng)性能同時滿足任務的截止時間限。

整合延遲算法和動態(tài)電壓調節(jié)技術是一種有效的降低系統(tǒng)功耗的方法。 Jejurikar R等人[7]評估了在EDF調度策略下的延遲算法的使用情況，并測試了固定優(yōu)先級(fixed priority)和競爭優(yōu)先級(dual priority)系統(tǒng)調度性能。他們認為Lee的LC-DP算法中延遲會導致任務不能滿足截止時間限，進而修正了該延遲算法存在的問題。在隨后的研究中，他們計算了兩種優(yōu)先級調度策略下的任務延遲間隔，指出競爭優(yōu)先級調度比固定優(yōu)先級調度在延遲間隔中能更有效地降低系統(tǒng)功耗。

集成靜態(tài)功耗的DVS策略因為需要考慮漏電流功耗對總功耗的影響，所以在結合動態(tài)功耗條件下，計算系統(tǒng)的關鍵點(Critical Point)來確定最小總功耗時系統(tǒng)的關鍵速度(Critical Speed)，繼而給出系統(tǒng)的低功耗調度策略， 于是有相應的 Critical Speed DVS(CS-DVS)和Critical Speed DVSwith Procrastination(CS-DVS-P)[4]；后者引入延遲算法，通過增加任務之間的空閑時間，進一步降低功耗。

3 實時DVS策略仿真

我們的實時DVS策略仿真是根據Pering T等人[2]和Shin D等人[13]提出的仿真與評估方法加以改進。該方法以UI、Real-Time Audio和MPEG Decompression等作為基準測試程序，硬件平臺也使用具有能夠進行連續(xù)電壓調節(jié)的如Intel PXA系列處理器，并且系統(tǒng)搭載一定的外設，如內存、I/O和硬盤等。仿真器將一組任務序列作為輸入，該序列包含每個任務的周期和運行開銷以及相應的一些系統(tǒng)參數。輸出為處理器利用率與功耗的關系模型。在仿真中我們將最壞截止時間(WCET)對應處理器速率為最大執(zhí)行速率，任務序列為隨機序列，并定義其周期和WCET的取值范圍。

在動態(tài)功耗DVS策略中具體算法可能是由一種或幾種空閑評估算法組成。我們列出主要的算法組合，如表1。

表1 動態(tài)DVS策略算法組合

針對上述DVS算法，我們通過標準化評估模型分析他們的平均功耗情況與不使用DVS策略模型的功耗比，如圖1。

圖1 動態(tài)功耗DVS策略的功耗比較

對于考慮靜態(tài)功耗的DVS算法而言，在處理器利用率較小的時候， CS-DVS-P算法能獲得最小的功耗，隨著處理器利用的上升，一般DVS以及CS-DVS算法都能與CS-DVS-P獲得大致相同的功耗，如圖2。

圖2 漏電流功耗DVS策略功耗比較

圖2中的功耗是相對于沒有采用DVS策略的功耗而得到的標準化功耗。 CS-DVS相對于普通DVS策略能夠減少5%的系統(tǒng)功耗，而CS-DVS-P通過延長睡眠間隔時間而進一步減少了關斷開銷，從而能夠獲得了比CS-DVS多達18 %的功耗節(jié)省。

4 總結

實時嵌入式系統(tǒng)的DVS策略在仿真環(huán)境下往往能達到10 %～40%的功耗節(jié)省。然而在實際應用中往往因為現實環(huán)境的復雜性和多樣性而無法達到令人滿意的功耗降低。我們看到多數理論都基于貪心算法，即從理論上滿足任務時限的條件下最大可能地降低功耗。后續(xù)研究將把重點放在DVS策略與DPM策略相結合以及針對混合DVS策略研究的拓展。

我們認為從近些年實時DVS策略發(fā)展的角度來看，漏電流功耗對整個系統(tǒng)功耗影響的研究將占更大的比重，特別是在考慮漏電流與動態(tài)電流之間相互關系的研究上有望進一步深入。同時，在實際工程領域的應用也會是未來一段時間的研究重點。此外，我們認為結合VLSI等相關芯片制造領域技術的發(fā)展，將DVS策略集成到芯片制造中也會成為未來DVS策略研究的一個重要方向。

[ 1] Pillai P， Shin K G.Real-Time Dynam ic Voltage Scaling for Low-Power Embedded Operating Systems[ J] .ACM SIGOPSOperating Systems Review.New York：ACM， 2001：89-102.

[ 2] Pering T， Burd T， Brodersen R.The Simulation and Evaluation of Dynamic Voltage Scaling Algorithms[ C] //Proceedings of the 1998 International Symposium on Low Power Electronics and Design.New York：ACM， 1998：76-81.

[ 3] Pouwelse J， Langendoen K， Skips H.Dynamic Voltage Scalingon a Low-Power Microprocessor[ C] //Proceedings of the 7th annual international conference on Mobile computing and networking，New York：ACM， 2001：251-259.

[ 4] Jejurikar R， Pereira C， GuptaR.Leakage Aware Dynamic Voltage Scaling for Real-time Embedded Systems[ C] //Proceedings of the 41st Annual Design Automation Conference.New York：ACM，2004：275-180.

[ 5]Jejurikar R， Gupta R.Dynam ic Voltage Scaling for System-wide Energy Minimization in Real-time Embedded Systems[ C] //Proceedings of the 2004 International Symposium on Low Power Electronics and Design(ISLPED'04)， 2004：78-81.

[ 6] Jejurikar R， Gupta R.Energy Aware Task Scheduling with Task Synchronization for Embedded Real-Time Systems[ J] //Computer-Aided Design of Integrated Circuits and Systems， IEEE Transactionson， June 2006：1024-1037.

[ 7] Jejurikar R， GuptaR.Procrastination Scheduling in Fixed Priority Real-time Systems[ C] //Proceedingsof the 2004ACM SIGPLAN/SIGBED Conference on Languages， Compilers， and Tools for Embedded Systems.New York：ACM， 2004：57-66.

[ 8] Kim W， Shin D， Yun H S， et al.Performance Comparison of Dynam ic Voltage Scaling Algorithms for Hard Real-time Systems[ C] //Proceedingsof the 2002 Real-Time and Embedded Technology and Applications Symposium， 2002：219-228.

[ 9]Aydin H， Melhem R， Alvarez P M.Dynamic and Aggressive Scheduling Techniques for Power-aware Real-time Systems[C] //Proceedingsof the 22nd IEEEReal-time Systems Symposium， December， 2001.

[ 10] Gruian F.Hard Real-time Scheduling Using Stochastic Data and DVSProcessors[C] //Proceedings of the International Symposium on Low Power Electronicsand Design.August， 2001：46-51.

[ 11] Kim W， Kim J， Min S L.A Dynam ic Voltage Scaling A lgorithm for Dynam ic Priority Hard Real-time Systems Using Slack Time Analysis[C] //Proceedingsof Design， Automation and Test in Europe(DATE'02).March 2002：788-794.

[ 12] Shin D， Kim J， Lee S.Intra-task Voltage Scheduling for Low-energy Hard Real-time Applications[ J].IEEE Design and Test of Computers.March 2001， 18(2)：20-30.

[ 13] Shin D， Kim W， Jeon J， Kim J， et al.SL.SimDVS：An Integrated Simulation Environment for Performance Evaluation of Dynamic Voltage Scaling Algorithms[ C] //Proceedings ofWorkshop on Power-aware Computer Systems(PACS 2002).February， 2002.

[ 14] Shin Y， Choi K， Sakurai T.Power Optimization of Real-time Embedded Systemson Variable Speed Processors[ C] //Proceedingsof the International Conference on Computer-aided Design.November， 2000：365-368.

[ 15] Irani S， Shukla S， Gupta R.Algorithms for Power Savings[ C] //Proceedingsof Symposium on Discrete Algorithms.January， 2003.

[ 16] Lee Y， Reddy K P， Krishna CM.Scheduling Techniques for Reducing Leakage Power in Hard Real-time Systems[ C] //EcuroMicro Conference on Real Time Systems， 2003.