??? 摘 要： 低功耗的設(shè)計(jì)已經(jīng)成為嵌入式系統(tǒng)設(shè)計(jì)中一個(gè)非常重要的方面，而動(dòng)態(tài)電壓調(diào)度算法DVS又被認(rèn)為是降低功耗的一種有效手段。分析了已有的基于電池剩余電量的DVS調(diào)度算法局限性，通過實(shí)驗(yàn)對(duì)非周期性電流負(fù)載" title="電流負(fù)載">電流負(fù)載對(duì)應(yīng)的電池單元行為進(jìn)行建模，設(shè)計(jì)了一種新的低能耗" title="低能耗">低能耗調(diào)度算法。實(shí)驗(yàn)證明該算法能很好滿足復(fù)雜的具有非周期性任務(wù)特點(diǎn)的嵌入式實(shí)時(shí)系統(tǒng)的性能與低功耗要求。
??? 關(guān)鍵詞： 電池非理想特性；自恢復(fù)效應(yīng)" title="自恢復(fù)效應(yīng)">自恢復(fù)效應(yīng)；DVS算法；非周期性；低功耗
?
??? 能量消耗問題是近幾年在嵌入式系統(tǒng)設(shè)計(jì)中被廣為關(guān)注的難點(diǎn)與熱點(diǎn)，它嚴(yán)重制約著嵌入式系統(tǒng)的應(yīng)用與發(fā)展[1]。降低能耗、延長電池壽命" title="電池壽命">電池壽命在軍用或民用嵌入式系統(tǒng)中(如傳感網(wǎng)絡(luò)節(jié)點(diǎn)、微小衛(wèi)星、PDA等)具有重要的現(xiàn)實(shí)意義。動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)可以根據(jù)當(dāng)前運(yùn)行任務(wù)的需求來實(shí)時(shí)調(diào)節(jié)處理器工作電壓" title="工作電壓">工作電壓，以達(dá)到任務(wù)完成時(shí)間和系統(tǒng)能耗之間的平衡，因而被廣泛應(yīng)用在嵌入式實(shí)時(shí)系統(tǒng)中。傳統(tǒng)DVS(Dynamic Voltage Scaling)算法（Wiser and Govil[2]）多是基于最優(yōu)化的電池單元模型，而沒有試圖對(duì)電池的理化現(xiàn)象精確建模。實(shí)際上不同的電流負(fù)載對(duì)應(yīng)的電池單元行為不同，對(duì)不同情況下電池單元行為進(jìn)行精確建模能提高電池利用率，延長其壽命，故進(jìn)一步研究與電池特性相關(guān)的DVS策略非常有意義。
1 基于電池特性DVS算法本質(zhì)
??? DVS策略主要基于一個(gè)事實(shí)，即：處理器的確定性能量消耗與工作電壓呈平方正比的關(guān)系[3]：
??? 
?
??? C為工作電源電壓，V為每周期的平均開關(guān)電容，f 為時(shí)鐘頻率，Vbs為襯底和源極之間的電壓，Ij為節(jié)點(diǎn)漏電，K0、K1、K2均為常數(shù)。故在保證性能前提下，可根據(jù)系統(tǒng)工作狀態(tài)動(dòng)態(tài)調(diào)整電壓達(dá)到降低能耗的目的?；陔姵靥匦缘腄VS算法不僅根據(jù)系統(tǒng)工作狀態(tài)來動(dòng)態(tài)調(diào)節(jié)電壓，而且還以電池特性為基礎(chǔ)設(shè)計(jì)調(diào)度策略，以對(duì)電池合理利用，進(jìn)一步延長電池壽命。Luo[4]等人研究提出的DVS策略通過降低電池的峰值功率來優(yōu)化能量消耗；Rakhmatov[5]提議利用電池自恢復(fù)效應(yīng)增加電容以節(jié)省能量等，這些都是基于電池特性的研究成果并取得較好的節(jié)能效果。
2 已有的基于電池剩余能量的DVS算法局限性
??? 在Sukwon Choia[6]等人提出的一種基于電池剩余能量的可選擇DVS策略中，對(duì)周期性電流負(fù)載對(duì)應(yīng)的電池單元行為建模，并根據(jù)自恢復(fù)效應(yīng)影響因子的強(qiáng)弱將電池放電過程分為三個(gè)不同的階段，在不同階段提供不同的策略起到了降低功耗的作用。但其存在下列缺點(diǎn)：
??? (1)建立的電池單元行為模型有一定局限性，只符合周期性電流負(fù)載的特點(diǎn)；而更為普遍的具有非周期性電流負(fù)載對(duì)應(yīng)的電池單元行為模型與之存在較大差異，故需要對(duì)電池單元行為重新建模。
??? (2)在rate capacity區(qū)域計(jì)算Poptimal方法：基于過去周期段處理器利用率和當(dāng)前時(shí)刻預(yù)測利用率來設(shè)定最優(yōu)功率，即：
?????
其中i≥1，P0=Pmax。而對(duì)非周期性和隨機(jī)任務(wù)，簡單的基于處理器以往利用率的計(jì)算模型不能提供最優(yōu)的動(dòng)態(tài)電壓調(diào)節(jié)方法，需要考慮采取符合隨機(jī)任務(wù)特點(diǎn)的新策略。
??? (3)在Alarm 區(qū)域電池進(jìn)入低電壓報(bào)警區(qū)，調(diào)節(jié)功率為Poptimal=Pmin可以降低能耗。但是如果結(jié)合動(dòng)態(tài)電源管理DPM策略，對(duì)系統(tǒng)單元采用合理的休眠/喚醒算法，則能更好地減少不必要的消耗。
3 電池的非理想特性
??? 大多數(shù)有關(guān)低能耗設(shè)計(jì)的研究，都將電池隱式認(rèn)為是一個(gè)理想的電荷儲(chǔ)存器，即：存儲(chǔ)某個(gè)固定的電荷總量，而且直到電荷全部耗盡時(shí)電壓才退出標(biāo)稱值。然而在實(shí)際情況中，電池沒有任何一處接近于理想電荷存儲(chǔ)單元。由于電池的化學(xué)特性，電池在滿電荷至臨界低電荷放電期間其放電率受到很多因素的影響。其中最主要的兩個(gè)因素是：the rate capacity effect和the recovery effect[7]。the rate capacity effect現(xiàn)象反映了電流負(fù)載和電池壽命的非線性反比關(guān)系，而且電池壽命變化率比電流負(fù)載變化率要快。這主要是由于電池在生命周期中所能釋放的容量總和與放電電流有關(guān)。因?yàn)閺哪芰哭D(zhuǎn)換角度看，當(dāng)電流越大時(shí)，電池在將內(nèi)存的化學(xué)能轉(zhuǎn)變成電能時(shí)的效率越低。電池的這種非線性特征可通過Peukert公式[8]來說明；the recovery effect現(xiàn)象反映了當(dāng)電池空閑時(shí)電池電容有自恢復(fù)效應(yīng)。因?yàn)殡姵卦跊]有放電時(shí)，電極——電解質(zhì)周圍的有效物質(zhì)通過擴(kuò)散的方法會(huì)被重新填充，電池容量會(huì)有恢復(fù)現(xiàn)象。若能利用該特性，將有利于降低系統(tǒng)能耗，延長電池壽命。
??? 實(shí)驗(yàn)在IPAQ3600 PDA上運(yùn)行Linux，并修改Linux內(nèi)核控制硬件來讀取電池剩余電量值。系統(tǒng)預(yù)設(shè)5個(gè)任務(wù)，并通過隨機(jī)策略調(diào)度其運(yùn)行來模擬非周性任務(wù)的執(zhí)行，在整個(gè)監(jiān)測過程中，系統(tǒng)處于隨機(jī)的繁忙和空閑交替狀態(tài)中。實(shí)驗(yàn)數(shù)據(jù)顯示（圖1）：系統(tǒng)工作時(shí)間與電池剩余電量值局部呈不規(guī)則曲線狀，但整體上曲線變化有一定規(guī)律，可以分為三個(gè)區(qū)域：在Recovery effect段（Lfull～LR）電容恢復(fù)現(xiàn)象明顯，電池部分放電被恢復(fù)效應(yīng)補(bǔ)償，電量下降緩慢;在Rate capacity effect段(LR～Lc)恢復(fù)效應(yīng)減弱補(bǔ)償能力下降，電量下降加快，并與放電時(shí)間趨于線性關(guān)系；最后在Alarm段(Lc～Llow)放電行為占主導(dǎo)，電量急速下降。
???????????????????????? 
??? 實(shí)驗(yàn)結(jié)果：周期性電流負(fù)載和非周期性電流負(fù)載對(duì)應(yīng)的電池電量監(jiān)測曲線分別為細(xì)線條和粗線條部分?？梢钥吹剑悍侵芷谛噪娏髫?fù)載對(duì)應(yīng)的電池特性曲線仍然分為三個(gè)區(qū)域，但是其曲線波動(dòng)特點(diǎn)很不規(guī)律。階段1：前者曲線波動(dòng)均勻，后者幅度較大；階段2：前者呈線性下降，后者曲線圍繞前者上下波動(dòng)；階段3：兩者電量均迅速下降，前者下降平穩(wěn)，后者有平緩部分。且由于任務(wù)的隨機(jī)性，后者進(jìn)入某區(qū)域的時(shí)間點(diǎn)相對(duì)模糊，其區(qū)域分割點(diǎn)與任務(wù)調(diào)度的隨機(jī)過程有關(guān)。同樣都是基于電池特性，但是在相同的特性區(qū)域，對(duì)應(yīng)的電流負(fù)載特點(diǎn)不同，故在相同的特性區(qū)域應(yīng)采用不同的策略以求低能耗最優(yōu)。
4 基于電池非理想特性的DVS算法
4.1 DVS算法思想
??? 根據(jù)曲線特點(diǎn)分析電池動(dòng)態(tài)特性，從而設(shè)計(jì)合適的策略才是關(guān)鍵：該DVS算法根據(jù)電量余值L作出策略切換。當(dāng)L∈(Lfull～LR)時(shí)，以充分利用電池恢復(fù)效應(yīng)為主；L∈(LR～Lc)時(shí)，因L值持續(xù)減少，故在保證系統(tǒng)性能前提下盡量減少放電量；L∈(Lc～Llow)時(shí)，電池電量進(jìn)入低報(bào)警區(qū)，系統(tǒng)單元采取關(guān)閉/喚醒的PM策略，需要犧牲部分性能以盡量延長電池壽命(Lfull、LR、Lc、Llow均為電池在某時(shí)刻的電量余值）。
4.2 確定電池狀態(tài)
??? 要根據(jù)電池剩余電量進(jìn)行策略切換，首先要判斷電池狀態(tài)區(qū)間分割點(diǎn)。非周期電流負(fù)載對(duì)應(yīng)的電池行為模型不像周期性電流負(fù)載對(duì)應(yīng)的電池行為那么有規(guī)律，所以判斷起來相對(duì)復(fù)雜。但共同之處在于：在相同的特性區(qū)域，同時(shí)間片能耗與補(bǔ)償能量的大小關(guān)系類似。所以可以將處理器工作時(shí)間劃分成若干時(shí)間段(如圖2)，task期間在單位時(shí)間段內(nèi)任務(wù)的平均能耗量ΔH(式(3))和隨后相鄰的Idle期間單位時(shí)間段內(nèi)平均能量補(bǔ)償量ΔB（式(4)），設(shè)ΔM=ΔH+ΔB，若有ΔM≤0現(xiàn)象出現(xiàn)，則電池處于recovery effect區(qū)；若在一定時(shí)間內(nèi)持續(xù)ΔM>0，則認(rèn)為恢復(fù)效應(yīng)開始模糊，電池進(jìn)入rate capacity區(qū)；若ΔM>0并且數(shù)值明顯增大，則認(rèn)為電池進(jìn)入alrm區(qū)。Lmax為電池最大放電量，Li為I時(shí)間片時(shí)電池剩余電量，兩個(gè)值都可通過監(jiān)測獲得。B(Qk)為Qk時(shí)能耗量為：
??? 
????????????????????? 
??? 可推得Qi時(shí)能耗量：?
??? 
?
??? 在連續(xù)任務(wù)時(shí)間段內(nèi)，單位時(shí)間片的平均能耗量：?
??? 
????相鄰空閑時(shí)間段內(nèi)，單位時(shí)間片平均補(bǔ)償能量：?
??? 
4.3 DVS算法設(shè)計(jì)
??? 若電池狀態(tài)為系統(tǒng)所知，則系統(tǒng)就可以根據(jù)電池當(dāng)前狀態(tài)選擇合理的DVS策略。在Recovery effect區(qū)域，應(yīng)考慮充分利用電池的自恢復(fù)效應(yīng)，故可以使處理器Ppower=Pmax，用以縮短任務(wù)執(zhí)行時(shí)間，使處理器更多地處于空閑狀態(tài)以最大化恢復(fù)效應(yīng)。在Rate capacity區(qū)，應(yīng)在保證系統(tǒng)性能的同時(shí)，以降低任務(wù)執(zhí)行時(shí)的電池負(fù)載為主。這個(gè)求解過程可以轉(zhuǎn)化為一個(gè)在相關(guān)限制條件下求目標(biāo)函數(shù)最值的非線性規(guī)劃問題來解決，最優(yōu)化對(duì)象是每個(gè)任務(wù)所對(duì)應(yīng)的工作電壓，分析過程如下。
??? (1)時(shí)序可行性檢測（SFC）
??? 假設(shè)在時(shí)刻t，任務(wù)隊(duì)列中已經(jīng)有N個(gè)被調(diào)度器接收但是還沒有執(zhí)行完畢的瞬態(tài)任務(wù)，記為SQ={Ti(Si，Ei，Di)，1≤i≤N}，參數(shù)依次表示任務(wù)Ti的到達(dá)時(shí)間、在最高電壓下(即Vmax)的執(zhí)行時(shí)間和截止時(shí)間。SQ中的各個(gè)任務(wù)按照Di的上升趨勢進(jìn)行排序。LE(Ti，Vi，t)表示任務(wù)Ti在時(shí)刻t基于工作電壓Vi所對(duì)應(yīng)的剩余執(zhí)行時(shí)間。另外假設(shè)Ti(1，…，N)在進(jìn)入SQ之前都經(jīng)過時(shí)序可行性檢測。其主要作用是保證SQ中所有任務(wù)的deadline得到滿足。
??? (2)最優(yōu)化數(shù)學(xué)模型。目標(biāo)函數(shù)式(5)表示任務(wù)隊(duì)列中所有任務(wù)執(zhí)行完畢時(shí)所消耗的能量，其中P（Ti，Vi）表示任務(wù)Ti在Vi下所對(duì)應(yīng)的功耗。三個(gè)限制條件分別從執(zhí)行時(shí)間和工作電壓上作出限制。由于Ti在進(jìn)入任務(wù)隊(duì)列之前都經(jīng)過了時(shí)序可行性檢測，因此該計(jì)算模型在式(6)、式(7)、式(8)限制條件下必然能夠得到一組工作電壓的最優(yōu)解，記為OV={OVi，i=1，…，N}，其中OVi代表任務(wù)Ti所對(duì)應(yīng)工作電壓。
??? 
?
??? 根據(jù)OV1來執(zhí)行任務(wù)隊(duì)列中處于起始位置的任務(wù); 一旦出現(xiàn)新的瞬態(tài)任務(wù)Tnew，且該任務(wù)已通過SFC檢驗(yàn)時(shí)，系統(tǒng)將為SQ重新計(jì)算最優(yōu)解OV；而當(dāng)前任務(wù)執(zhí)行完畢時(shí)，其將從任務(wù)隊(duì)列中移走并在OV中執(zhí)行OVi->OVi+1的平移操作(i=1，…，N-1)。
??? 在Alarm區(qū)，為了盡可能延長電池壽命，可結(jié)合基于動(dòng)態(tài)超時(shí)的DPM策略，即當(dāng)電池電壓下降了ΔV(ΔV>0)后進(jìn)入Alarm區(qū)域時(shí)，則在原有超時(shí)時(shí)限值t0的基礎(chǔ)上進(jìn)一步降低，從而盡量延長電池的使用時(shí)間；反之則恢復(fù)原t0值。
??? 算法實(shí)現(xiàn)：
??? 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 算法性能實(shí)驗(yàn)分析
??? 實(shí)驗(yàn)分別采取本文設(shè)計(jì)的DVS算法、簡單DVS（Pi=Pmin）、無DVS三種策略進(jìn)行對(duì)比，分別稱為算法1、算法2、算法3。如圖3可知：由于在Recovery區(qū)算法1和算法3均設(shè)定Pi=Pmax，故電池行為方式比較接近，算法2由于Pi=Pmin沒有最大化恢復(fù)效應(yīng)，故曲線下降快；在Rate capacity區(qū)，算法1和算法2均考慮以降低電流負(fù)載為主，故后者曲線上升靠近前者曲線，而算法3功率仍為Pmax故電量下降較快；在Alarm區(qū)，算法1、算法2均采取了省電策略，故與算法3相比電量下降緩慢，且算法1與算法2相比，采取適當(dāng)休眠策略要比持續(xù)Pmin節(jié)能效果好。表1為三種策略的效能比較。
???????????????????????? 
?????????????????????? 
??? 基于電池特性的動(dòng)態(tài)電壓調(diào)節(jié)技術(shù)是降低嵌入式實(shí)時(shí)系統(tǒng)能耗的有效方法，也是當(dāng)前研究的熱門。少量系統(tǒng)的任務(wù)具有周期性特點(diǎn)，但更多的還是具有非周期性等隨機(jī)特點(diǎn)的任務(wù)系統(tǒng)。本文通過實(shí)驗(yàn)對(duì)非周期性電流負(fù)載對(duì)應(yīng)的電池行為進(jìn)行分析，并在此基礎(chǔ)上設(shè)計(jì)了適合于非周期性任務(wù)系統(tǒng)的策略。結(jié)果表明該算法能有效降低能耗,與無DVS策略相比，電池壽命延長17.3%，性能提高1.2%。該算法對(duì)降低非周期性電流負(fù)載的系統(tǒng)能耗比較合適，而對(duì)于混合型特點(diǎn)任務(wù)系統(tǒng)的低能耗策略還需要進(jìn)一步研究。DVS技術(shù)在過去十幾年的時(shí)間內(nèi)取得了很大的研究成果，系統(tǒng)低功耗設(shè)計(jì)領(lǐng)域的研究空間仍然非常巨大。系統(tǒng)層的低能耗設(shè)計(jì)以及有關(guān)能耗最優(yōu)化設(shè)計(jì)和分析技術(shù)在今后幾年中還將是重要的研究主題。
參考文獻(xiàn)
[1] 許海燕，盧偉，楊晨輝，等.低耗能嵌入式系統(tǒng)的設(shè)計(jì)[J].計(jì)算機(jī)應(yīng)用研究，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.