??? 摘 要： 低功耗的設計已經成為嵌入式系統設計中一個非常重要的方面，而動態電壓調度算法DVS又被認為是降低功耗的一種有效手段。分析了已有的基于電池剩余電量的DVS調度算法局限性，通過實驗對非周期性電流負載" title="電流負載">電流負載對應的電池單元行為進行建模，設計了一種新的低能耗" title="低能耗">低能耗調度算法。實驗證明該算法能很好滿足復雜的具有非周期性任務特點的嵌入式實時系統的性能與低功耗要求。
??? 關鍵詞： 電池非理想特性；自恢復效應" title="自恢復效應">自恢復效應；DVS算法；非周期性；低功耗
?
??? 能量消耗問題是近幾年在嵌入式系統設計中被廣為關注的難點與熱點，它嚴重制約著嵌入式系統的應用與發展[1]。降低能耗、延長電池壽命" title="電池壽命">電池壽命在軍用或民用嵌入式系統中(如傳感網絡節點、微小衛星、PDA等)具有重要的現實意義。動態電壓調節技術可以根據當前運行任務的需求來實時調節處理器工作電壓" title="工作電壓">工作電壓，以達到任務完成時間和系統能耗之間的平衡，因而被廣泛應用在嵌入式實時系統中。傳統DVS(Dynamic Voltage Scaling)算法（Wiser and Govil[2]）多是基于最優化的電池單元模型，而沒有試圖對電池的理化現象精確建模。實際上不同的電流負載對應的電池單元行為不同，對不同情況下電池單元行為進行精確建模能提高電池利用率，延長其壽命，故進一步研究與電池特性相關的DVS策略非常有意義。
1 基于電池特性DVS算法本質
??? DVS策略主要基于一個事實，即：處理器的確定性能量消耗與工作電壓呈平方正比的關系[3]：
??? 
?
??? C為工作電源電壓，V為每周期的平均開關電容，f 為時鐘頻率，Vbs為襯底和源極之間的電壓，Ij為節點漏電，K0、K1、K2均為常數。故在保證性能前提下，可根據系統工作狀態動態調整電壓達到降低能耗的目的。基于電池特性的DVS算法不僅根據系統工作狀態來動態調節電壓，而且還以電池特性為基礎設計調度策略，以對電池合理利用，進一步延長電池壽命。Luo[4]等人研究提出的DVS策略通過降低電池的峰值功率來優化能量消耗；Rakhmatov[5]提議利用電池自恢復效應增加電容以節省能量等，這些都是基于電池特性的研究成果并取得較好的節能效果。
2 已有的基于電池剩余能量的DVS算法局限性
??? 在Sukwon Choia[6]等人提出的一種基于電池剩余能量的可選擇DVS策略中，對周期性電流負載對應的電池單元行為建模，并根據自恢復效應影響因子的強弱將電池放電過程分為三個不同的階段，在不同階段提供不同的策略起到了降低功耗的作用。但其存在下列缺點：
??? (1)建立的電池單元行為模型有一定局限性，只符合周期性電流負載的特點；而更為普遍的具有非周期性電流負載對應的電池單元行為模型與之存在較大差異，故需要對電池單元行為重新建模。
??? (2)在rate capacity區域計算Poptimal方法：基于過去周期段處理器利用率和當前時刻預測利用率來設定最優功率，即：
?????
其中i≥1，P0=Pmax。而對非周期性和隨機任務，簡單的基于處理器以往利用率的計算模型不能提供最優的動態電壓調節方法，需要考慮采取符合隨機任務特點的新策略。
??? (3)在Alarm 區域電池進入低電壓報警區，調節功率為Poptimal=Pmin可以降低能耗。但是如果結合動態電源管理DPM策略，對系統單元采用合理的休眠/喚醒算法，則能更好地減少不必要的消耗。
3 電池的非理想特性
??? 大多數有關低能耗設計的研究，都將電池隱式認為是一個理想的電荷儲存器，即：存儲某個固定的電荷總量，而且直到電荷全部耗盡時電壓才退出標稱值。然而在實際情況中，電池沒有任何一處接近于理想電荷存儲單元。由于電池的化學特性，電池在滿電荷至臨界低電荷放電期間其放電率受到很多因素的影響。其中最主要的兩個因素是：the rate capacity effect和the recovery effect[7]。the rate capacity effect現象反映了電流負載和電池壽命的非線性反比關系，而且電池壽命變化率比電流負載變化率要快。這主要是由于電池在生命周期中所能釋放的容量總和與放電電流有關。因為從能量轉換角度看，當電流越大時，電池在將內存的化學能轉變成電能時的效率越低。電池的這種非線性特征可通過Peukert公式[8]來說明；the recovery effect現象反映了當電池空閑時電池電容有自恢復效應。因為電池在沒有放電時，電極——電解質周圍的有效物質通過擴散的方法會被重新填充，電池容量會有恢復現象。若能利用該特性，將有利于降低系統能耗，延長電池壽命。
??? 實驗在IPAQ3600 PDA上運行Linux，并修改Linux內核控制硬件來讀取電池剩余電量值。系統預設5個任務，并通過隨機策略調度其運行來模擬非周性任務的執行，在整個監測過程中，系統處于隨機的繁忙和空閑交替狀態中。實驗數據顯示（圖1）：系統工作時間與電池剩余電量值局部呈不規則曲線狀，但整體上曲線變化有一定規律，可以分為三個區域：在Recovery effect段（Lfull～LR）電容恢復現象明顯，電池部分放電被恢復效應補償，電量下降緩慢;在Rate capacity effect段(LR～Lc)恢復效應減弱補償能力下降，電量下降加快，并與放電時間趨于線性關系；最后在Alarm段(Lc～Llow)放電行為占主導，電量急速下降。
???????????????????????? 
??? 實驗結果：周期性電流負載和非周期性電流負載對應的電池電量監測曲線分別為細線條和粗線條部分。可以看到：非周期性電流負載對應的電池特性曲線仍然分為三個區域，但是其曲線波動特點很不規律。階段1：前者曲線波動均勻，后者幅度較大；階段2：前者呈線性下降，后者曲線圍繞前者上下波動；階段3：兩者電量均迅速下降，前者下降平穩，后者有平緩部分。且由于任務的隨機性，后者進入某區域的時間點相對模糊，其區域分割點與任務調度的隨機過程有關。同樣都是基于電池特性，但是在相同的特性區域，對應的電流負載特點不同，故在相同的特性區域應采用不同的策略以求低能耗最優。
4 基于電池非理想特性的DVS算法
4.1 DVS算法思想
??? 根據曲線特點分析電池動態特性，從而設計合適的策略才是關鍵：該DVS算法根據電量余值L作出策略切換。當L∈(Lfull～LR)時，以充分利用電池恢復效應為主；L∈(LR～Lc)時，因L值持續減少，故在保證系統性能前提下盡量減少放電量；L∈(Lc～Llow)時，電池電量進入低報警區，系統單元采取關閉/喚醒的PM策略，需要犧牲部分性能以盡量延長電池壽命(Lfull、LR、Lc、Llow均為電池在某時刻的電量余值）。
4.2 確定電池狀態
??? 要根據電池剩余電量進行策略切換，首先要判斷電池狀態區間分割點。非周期電流負載對應的電池行為模型不像周期性電流負載對應的電池行為那么有規律，所以判斷起來相對復雜。但共同之處在于：在相同的特性區域，同時間片能耗與補償能量的大小關系類似。所以可以將處理器工作時間劃分成若干時間段(如圖2)，task期間在單位時間段內任務的平均能耗量ΔH(式(3))和隨后相鄰的Idle期間單位時間段內平均能量補償量ΔB（式(4)），設ΔM=ΔH+ΔB，若有ΔM≤0現象出現，則電池處于recovery effect區；若在一定時間內持續ΔM>0，則認為恢復效應開始模糊，電池進入rate capacity區；若ΔM>0并且數值明顯增大，則認為電池進入alrm區。Lmax為電池最大放電量，Li為I時間片時電池剩余電量，兩個值都可通過監測獲得。B(Qk)為Qk時能耗量為：
??? 
????????????????????? 
??? 可推得Qi時能耗量：?
??? 
?
??? 在連續任務時間段內，單位時間片的平均能耗量：?
??? 
????相鄰空閑時間段內，單位時間片平均補償能量：?
??? 
4.3 DVS算法設計
??? 若電池狀態為系統所知，則系統就可以根據電池當前狀態選擇合理的DVS策略。在Recovery effect區域，應考慮充分利用電池的自恢復效應，故可以使處理器Ppower=Pmax，用以縮短任務執行時間，使處理器更多地處于空閑狀態以最大化恢復效應。在Rate capacity區，應在保證系統性能的同時，以降低任務執行時的電池負載為主。這個求解過程可以轉化為一個在相關限制條件下求目標函數最值的非線性規劃問題來解決，最優化對象是每個任務所對應的工作電壓，分析過程如下。
??? (1)時序可行性檢測（SFC）
??? 假設在時刻t，任務隊列中已經有N個被調度器接收但是還沒有執行完畢的瞬態任務，記為SQ={Ti(Si，Ei，Di)，1≤i≤N}，參數依次表示任務Ti的到達時間、在最高電壓下(即Vmax)的執行時間和截止時間。SQ中的各個任務按照Di的上升趨勢進行排序。LE(Ti，Vi，t)表示任務Ti在時刻t基于工作電壓Vi所對應的剩余執行時間。另外假設Ti(1，…，N)在進入SQ之前都經過時序可行性檢測。其主要作用是保證SQ中所有任務的deadline得到滿足。
??? (2)最優化數學模型。目標函數式(5)表示任務隊列中所有任務執行完畢時所消耗的能量，其中P（Ti，Vi）表示任務Ti在Vi下所對應的功耗。三個限制條件分別從執行時間和工作電壓上作出限制。由于Ti在進入任務隊列之前都經過了時序可行性檢測，因此該計算模型在式(6)、式(7)、式(8)限制條件下必然能夠得到一組工作電壓的最優解，記為OV={OVi，i=1，…，N}，其中OVi代表任務Ti所對應工作電壓。
??? 
?
??? 根據OV1來執行任務隊列中處于起始位置的任務; 一旦出現新的瞬態任務Tnew，且該任務已通過SFC檢驗時，系統將為SQ重新計算最優解OV；而當前任務執行完畢時，其將從任務隊列中移走并在OV中執行OVi->OVi+1的平移操作(i=1，…，N-1)。
??? 在Alarm區，為了盡可能延長電池壽命，可結合基于動態超時的DPM策略，即當電池電壓下降了ΔV(ΔV>0)后進入Alarm區域時，則在原有超時時限值t0的基礎上進一步降低，從而盡量延長電池的使用時間；反之則恢復原t0值。
??? 算法實現：
??? SelectiveDVS(Currrent task){
????? Open Dvs Mechanism；Time t0=value；
????? STATUS=Get current battery region information；
????? Switch(STATUS){
????? Case? RECOVERY_REGION：Pi=Pmax
????? Case? RATECAPACITY_REGION：
???????? If(newtask)?? Calculate OV[n]；
???????? else{ExecuteCurrentTask；RemoveCurrentTask；
???????? Vdd=OVnext；Pi=KVdd3；}
????? Case? ALARM_REGION：
???????? Close Dvs Mechanism；
??? Start DynamicTime_outPolicy(t0)；
??? //t0 is first value } }
??????Time t1=t；//Dynamic time value
????? Dynamic time_out policy(t){
?????? ?If(0<=t1<=t){
????????? If(SystemTime>=t1)? Close devices；
? ???? ???? If(tasking)? Sleep devices；
??????? If(battery coulometry down)
??????????? t1--；
??????? else? t1++；}}
5 算法性能實驗分析
??? 實驗分別采取本文設計的DVS算法、簡單DVS（Pi=Pmin）、無DVS三種策略進行對比，分別稱為算法1、算法2、算法3。如圖3可知：由于在Recovery區算法1和算法3均設定Pi=Pmax，故電池行為方式比較接近，算法2由于Pi=Pmin沒有最大化恢復效應，故曲線下降快；在Rate capacity區，算法1和算法2均考慮以降低電流負載為主，故后者曲線上升靠近前者曲線，而算法3功率仍為Pmax故電量下降較快；在Alarm區，算法1、算法2均采取了省電策略，故與算法3相比電量下降緩慢，且算法1與算法2相比，采取適當休眠策略要比持續Pmin節能效果好。表1為三種策略的效能比較。
???????????????????????? 
?????????????????????? 
??? 基于電池特性的動態電壓調節技術是降低嵌入式實時系統能耗的有效方法，也是當前研究的熱門。少量系統的任務具有周期性特點，但更多的還是具有非周期性等隨機特點的任務系統。本文通過實驗對非周期性電流負載對應的電池行為進行分析，并在此基礎上設計了適合于非周期性任務系統的策略。結果表明該算法能有效降低能耗,與無DVS策略相比，電池壽命延長17.3%，性能提高1.2%。該算法對降低非周期性電流負載的系統能耗比較合適，而對于混合型特點任務系統的低能耗策略還需要進一步研究。DVS技術在過去十幾年的時間內取得了很大的研究成果，系統低功耗設計領域的研究空間仍然非常巨大。系統層的低能耗設計以及有關能耗最優化設計和分析技術在今后幾年中還將是重要的研究主題。
參考文獻
[1] 許海燕，盧偉，楊晨輝，等.低耗能嵌入式系統的設計[J].計算機應用研究，2002，19(6)：123-124.
[2] WEISER M，WELCH B，DEMERS A，et al.Scheduling for reduced CPU energy.Proceedings of USEN/X Symposium on Operating Systems Design，Monterey，California，United?States，1994.
[3] FLAUTER K，REINHARDT S.Automatic Performance Setting for Dynamic Voltage Scaling[J].Mobile.ComPutingandNetworking，2001：26.
[4] LUO J，NIRAJ J K.Battery-aware static scheduling for distributed realtime embedded systems design.Proceedings of?ACM/IEEE Conference on Design Automation, Las Vegas，Nevada，United States，2001：444-449.
[5] MARTIN T L，BATTERIES B.Power and performance：system issues in CPU speed-setting for mobile computing，Ph.D.thesis，Department of Electrical and Computer Engineering，Carnegie Mellon University，1999.
[6] SukwonChoi，HojungCha，RhanHa.A selective DVS technique based on battery residual Microprocessors and? Microsystems 30，2006：33-42.
[7] BENINI L，CASTELLI G，MACII A.Extending lifetime of?portable systems by battery scheduling.Proceedings of the?Conference on Design，Automation and Test，Munich，Germany，2001：197-203.
[8] CaldariM，ContM，CIPPap，et al.Dynamicpower managementinanAMBA-basedbattery-poweredsystem[C].Electronics，CircuitsandSystems，2002.9thIntationalConfefence.2002，2：525-528.