李偉生，王 冬

（重慶郵電大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)研究所，重慶400065）

0 引 言

為了延長功能日益多元化的嵌入式設(shè)備的使用時(shí)間，動(dòng)態(tài)電源管理 （dynamic power management，DPM）技術(shù)獲得了越來越多的研究?？傮w上來講，DPM策略分為3類：超時(shí)策略［1］、預(yù)測策略［2］以及隨機(jī)策略［3］。目前提出的DPM預(yù)測策略中，有的基于歷史空閑時(shí)間統(tǒng)計(jì)［4］，有的基于機(jī)器學(xué)習(xí)的智能方法［5］，還有的基于編譯器的架構(gòu)［6］進(jìn)行預(yù)測策略的實(shí)現(xiàn)。自適應(yīng)學(xué)習(xí)樹 （adaptive learning tree，ALT）是較早提出的一種根據(jù)工作負(fù)載的歷史空閑時(shí)間統(tǒng)計(jì)序列建立的樹形結(jié)構(gòu)，文獻(xiàn) ［7］中提出一種基于概率自適應(yīng)學(xué)習(xí)樹的預(yù)測策略，克服了ALT中的 “死鎖”問題，但是存在高功耗缺陷，文獻(xiàn) ［8］采用基于空閑時(shí)間期望值的策略進(jìn)行預(yù)測，但是忽略了歷史狀態(tài)序列預(yù)測結(jié)果之間的關(guān)聯(lián)性也存在功耗高問題。為了進(jìn)一步降低設(shè)備功耗，本文在基于概率自適應(yīng)學(xué)習(xí)樹的基礎(chǔ)上，增加空閑時(shí)間期望值節(jié)點(diǎn)來預(yù)測下一次空閑時(shí)設(shè)備應(yīng)該進(jìn)入的低功耗狀態(tài)，并采用樹形結(jié)構(gòu)中狀態(tài)預(yù)測節(jié)點(diǎn)的概率統(tǒng)計(jì)對預(yù)測空閑時(shí)間期望值進(jìn)行加權(quán)更新，仿真實(shí)驗(yàn)表明了策略的有效性。

1 基于概率的自適應(yīng)學(xué)習(xí)樹

基于概率的自適應(yīng)學(xué)習(xí)樹假設(shè)設(shè)備在空閑狀態(tài)下?lián)碛衝種低功耗狀態(tài) （狀態(tài)數(shù)量為n＋1，包含一種正常工作狀態(tài)），然后基于IPC （Idle period clustering）原理［9］將設(shè)備的每一段空閑狀態(tài)時(shí)間長度對應(yīng)于一個(gè)整型數(shù)值IG（tidle）來表示，對于n＋1種狀態(tài)，可以用狀態(tài)集合U ＝ ｛0，1，...，N｝來表示所有狀態(tài)，這樣對于長度為m的一串歷史統(tǒng)計(jì)空閑時(shí)間序列，就可以用Sm＝s0s1...sm－1來表示，其中si∈U（i＝0...m－1），s0代表最近的一次空閑時(shí)間的IG（tidle）值，然后根據(jù)該歷史序列sm來預(yù)測下一個(gè)空閑時(shí)間設(shè)備應(yīng)進(jìn)入的功耗狀態(tài)。

基于概率的自適應(yīng)學(xué)習(xí)樹模型如圖2所示，在初始狀態(tài)下，該策略假設(shè)IG（tidle）的歷史序列sm＝00...0，且每一個(gè)歷史路徑中IG（tidle）的預(yù)測初始概率都設(shè)為相等的，顯然，在任何條件下，同一給定序列上的所有IG（tidle）的預(yù)測概率滿足相加總和為1，從而很好的解決了ALT策略中存在的 “死鎖”問題并且因而建立了與其他可能預(yù)測狀態(tài)之間的聯(lián)系。除了上述與ALT的區(qū)別以外，基于概率的自適應(yīng)學(xué)習(xí)樹在初始階段就已經(jīng)是全部建立完成的，層與層之間不存在預(yù)測分支，而ALT在初始階段只能配置到F0層，無疑增加了搜索預(yù)測過程的復(fù)雜性。

圖1 具有兩種低功耗狀態(tài)的概率自適應(yīng)學(xué)習(xí)樹

在概率更新過程中 （自學(xué)習(xí)過程），基于概率的自適應(yīng)學(xué)習(xí)樹策略采用了滑動(dòng)窗口的技術(shù)，更新過程如下：窗口的每一格保存了歷史中實(shí)際的IG（tidle），當(dāng)窗口當(dāng)前長度小于窗口設(shè)定長度時(shí)，窗口中的每一個(gè)狀態(tài)依次后移一位，新得到的IG（tidle）加入窗口的最新位置 （第0位置），并且窗口長度加1；如果歷史IG（tidle）數(shù)量等于窗口長度，則拋棄最老的歷史IG（tidle），再進(jìn)行與上面相同的操作，但保持窗口長度不變。顯然，對于一定的歷史路徑，下一次預(yù)測結(jié)果為各個(gè)預(yù)測狀態(tài)概率中的最大者。

基于概率的自適應(yīng)學(xué)習(xí)樹對歷史實(shí)際空閑狀態(tài)有很好的統(tǒng)計(jì)，所以在以預(yù)測正確率為評估標(biāo)準(zhǔn)的條件下是比較好的。但是文獻(xiàn) ［8］中通過對能耗與空閑時(shí)間關(guān)系的分析，說明了如果以空閑時(shí)間期望值作為預(yù)測依據(jù)，可以使設(shè)備整體功耗在統(tǒng)計(jì)意義上達(dá)到最小。

2 基于空閑時(shí)間期望值策略

式中：ai——設(shè)備處于狀態(tài)i時(shí)的功耗，bi——設(shè)備從狀態(tài)i切換到正常工作狀態(tài)的功耗損失，E（t）——空閑時(shí)間期望，進(jìn)而使用相鄰狀態(tài)之間的平衡時(shí)間［10］建立量化判決門限序列，并建立E（t）到該門限序列的對應(yīng)關(guān)系，從而摒棄了原有學(xué)習(xí)樹中的歷史統(tǒng)計(jì)記錄葉子節(jié)點(diǎn)，以E（t）值所對應(yīng)的量化值作為下一段空閑時(shí)間設(shè)備應(yīng)該進(jìn)入的狀態(tài)預(yù)測值。更新過程中，該策略采取指數(shù)平均方法［11］對E（t）值進(jìn)行加權(quán)更新，以進(jìn)行下一次的預(yù)測。指數(shù)平均預(yù)測更新算法的計(jì)算公式如下

其中a是0到1之間的一個(gè)常數(shù)，表示與上次真實(shí)值的接近程度，a越大，表示預(yù)測值越接近上次的真實(shí)值。

通過上面的分析我們知道該策略在統(tǒng)計(jì)意義上可以獲得比較低的功耗損失，但是由于其采用的指數(shù)加權(quán)方法忽略了歷史狀態(tài)序列預(yù)測結(jié)果之間的關(guān)聯(lián)性，導(dǎo)致空閑時(shí)間長度的預(yù)測準(zhǔn)確性不是很高，此外，參數(shù)a的設(shè)置也會(huì)對空閑時(shí)間預(yù)測的準(zhǔn)確性及其更新的反應(yīng)速度有著較大的影響。鑒于此，本文提出基于概率統(tǒng)計(jì)加權(quán)空閑時(shí)間的自適應(yīng)學(xué)習(xí)樹電源管理預(yù)測策略。

3 概率統(tǒng)計(jì)加權(quán)空閑時(shí)間的自適應(yīng)學(xué)習(xí)樹

該策略延續(xù)采用了類似基于概率的自適應(yīng)學(xué)習(xí)策略中的樹形結(jié)構(gòu)。與其它方法不同的是，在每一個(gè)與預(yù)測分支相連的決策節(jié)點(diǎn)中除了保留基于概率的自適應(yīng)學(xué)習(xí)策略中各個(gè)IG（tidle）值概率的字段外，另外引入了一個(gè)字段Tave來代表下次預(yù)測的空閑時(shí)間長度。預(yù)測方法也不再是基于窗口中IG（tidle）值出現(xiàn)的概率來預(yù)測下一次可能的低功耗狀態(tài)，而是通過該保存的空閑時(shí)間長度與平衡時(shí)間的比較來預(yù)測下一次可能的空閑時(shí)間長度，以控制下次空閑時(shí)間到來時(shí)設(shè)備應(yīng)該進(jìn)入的狀態(tài)，其狀態(tài)模型如圖2所示，左邊的葉子節(jié)點(diǎn)部分代表策略執(zhí)行中間過程中的某個(gè)狀態(tài)，右邊的葉子節(jié)點(diǎn)表示初始狀態(tài)。

圖2 具有兩種低功耗狀態(tài)的改進(jìn)自適應(yīng)學(xué)習(xí)樹

基于空閑時(shí)間期望值策略根據(jù)文獻(xiàn) ［9］中對設(shè)備每次處于低功耗狀態(tài)i時(shí)的能耗與空閑時(shí)間t的關(guān)系描述，假設(shè)空閑時(shí)間分布具有概率密度函數(shù)f（t），得到設(shè)備處于狀態(tài)i時(shí)的能耗期望如下所示［9］

在對該學(xué)習(xí)樹進(jìn)行更新的過程中，雖然在整個(gè)時(shí)間段里，用戶操作可能是沒有規(guī)律、難以預(yù)測的，但是在局部時(shí)間段里，用戶的操作往往有一定的規(guī)律，存在相關(guān)性［12］。而基于概率的自適應(yīng)學(xué)習(xí)策略采用的滑動(dòng)窗口技術(shù)較好維持了一段局部時(shí)間內(nèi)的預(yù)測情況，所以我們采用基于該統(tǒng)計(jì)的歷史概率來對預(yù)測時(shí)間均值進(jìn)行加權(quán)更新的方法。具體更新方法如下：首先，采取與基于概率的自適應(yīng)學(xué)習(xí)策略同樣的方法對每一個(gè)狀態(tài)的預(yù)測概率值進(jìn)行更新；接下來，無論是否預(yù)測正確，都用實(shí)際的空閑時(shí)間長度乘以其對應(yīng)保存狀態(tài)的概率再加上預(yù)測空閑時(shí)間長度乘以1減去實(shí)際狀態(tài)對應(yīng)狀態(tài)的概率。公式表示為

式中：Pactual——實(shí)際的空閑時(shí)間長度對應(yīng)的IG（tidle）值在歷史中的概率。例如在圖2中，假設(shè)給定歷史序列為s2＝00，則路徑選擇為a→b→e，預(yù)測狀態(tài)0、1和2對應(yīng)的概率分別為1／5、1／5和3／5，假設(shè)實(shí)際空閑時(shí)間長度值應(yīng)該對應(yīng)的狀態(tài)為2，則該歷史序列下預(yù)測的新的空閑時(shí)間長度均值更新為。通過采取這樣的更新方法，在預(yù)測正確的時(shí)候，給定歷史序列下預(yù)測的空閑時(shí)間長度均值將保持在一個(gè)小范圍內(nèi)；而當(dāng)預(yù)測錯(cuò)誤的時(shí)候，由于我們根據(jù)其實(shí)際空閑時(shí)間長度對應(yīng)的概率值進(jìn)行更新，從而保證了不會(huì)出現(xiàn)時(shí)間預(yù)測的陡增或者陡降現(xiàn)象，較好地維持了一段時(shí)間內(nèi)預(yù)測空閑時(shí)間長度的期望值。

此外，在具體實(shí)現(xiàn)時(shí)，我們摒棄了以前預(yù)測過程中對歷史序列復(fù)雜的搜索匹配過程，而是根據(jù)設(shè)備的低耗電狀態(tài)數(shù)量類似于二進(jìn)制采用了一個(gè)n＋1進(jìn)制的數(shù)位方法，每一個(gè)歷史序列都對應(yīng)于該n＋1進(jìn)制中的一個(gè)具體數(shù)值 （如具有2種低功耗狀態(tài)的歷史序列210可以轉(zhuǎn)換為 “三進(jìn)制”數(shù) （210）3＝2＊3＊3＋1＊3＝21），而預(yù)測的狀態(tài)概率或者預(yù)測時(shí)間長度都保存在相應(yīng)數(shù)值索引下的結(jié)構(gòu)體中。從而在下次進(jìn)行預(yù)測時(shí)，只需根據(jù)乘法和加法運(yùn)算得到預(yù)測點(diǎn)的索引值然后直接獲取即可，在一定程度上簡化了算法的復(fù)雜性。

具體算法步驟描述如下：

（1）初始化樹形結(jié)構(gòu)。包括建立歷史路徑序列索引表，初始化預(yù)測狀態(tài)概率和預(yù)測空閑時(shí)間長度信息等結(jié)構(gòu)體變量；

（2）根據(jù)歷史路徑序列進(jìn)行空閑時(shí)間長度預(yù)測 （初始?xì)v史路徑序列選擇為s3＝000）；

（3）當(dāng)有空閑時(shí)間出現(xiàn)時(shí)，根據(jù)當(dāng)前歷史路徑序列索引值中的預(yù)測空閑時(shí)間長度控制設(shè)備進(jìn)入相應(yīng)的低功耗狀態(tài)；

（4）設(shè)備實(shí)際空閑時(shí)間結(jié)束，首先計(jì)算歷史路徑序列的索引值，然后更新該索引值中的預(yù)測狀態(tài)概率，再根據(jù)得到的新的預(yù)測狀態(tài)概率值更新該歷史路徑序列下一次的預(yù)測時(shí)間長度，最后根據(jù)實(shí)際空閑時(shí)間長度更新歷史路徑序列；

（5）控制設(shè)備進(jìn)入工作模式；

（6）重復(fù)第 （2）至第 （6）步驟直到設(shè)備進(jìn)入關(guān)斷狀態(tài)。

通過以上的算法實(shí)現(xiàn)，理論上可以得到比基于時(shí)間期望策略更低的整體功耗花費(fèi)和較高的預(yù)測準(zhǔn)確率，本文在下一小節(jié)給出仿真實(shí)驗(yàn)結(jié)果。

4 實(shí)驗(yàn)與結(jié)果

4.1 仿真環(huán)境

仿真環(huán)境設(shè)置如下：

（1）系統(tǒng)具有兩種低功耗狀態(tài)，各個(gè)狀態(tài)的功耗分別為pon＝1 W ，pstandby＝0.3 W ，psleep＝0.1 W ，切換功耗分別為pontosleep＝10 W ，pontostandby＝6 W ，pstandbytosleep＝2 W ；

（2）歷史序列長度設(shè)置為3，滑動(dòng)窗口長度設(shè)置為10；（3）基于期望值策略中的指數(shù)平均系數(shù)a取值為0.5；（4）在空閑時(shí)間長度服從平均分布概率條件下分別進(jìn)行五次實(shí)驗(yàn)。

4.2 仿真結(jié)果

通過以上參數(shù)設(shè)定，在Matlab中對兩種算法進(jìn)行仿真實(shí)驗(yàn)，我們通過以下兩種指標(biāo)來進(jìn)行比較：

（1）誤預(yù)測率PER：誤預(yù)測率PER＝×100%，PER值越低，說明預(yù)測越準(zhǔn)確。

（2）競爭率CR：競爭率CR＝，CR值越低，表明功耗節(jié)省的效果越顯著。

1）兩種策略的誤預(yù)測率比較

從圖3中兩種方法的誤預(yù)測率對比可以看出，在進(jìn)行的5次實(shí)驗(yàn)中，本文采用的方法普遍比基于時(shí)間期望值策略的方法低9個(gè)百分點(diǎn)左右，也即預(yù)測正確率與基于時(shí)間期望值策略相比有比較大的提高。這是由于本文方法利用歷史概率統(tǒng)計(jì)對空閑時(shí)間長度值進(jìn)行預(yù)測及更新，使得預(yù)測值與實(shí)際空閑時(shí)間長度值更為接近，從而量化后的IG（tidle）預(yù)測值與實(shí)際空閑時(shí)間應(yīng)該進(jìn)入的低功耗狀態(tài)更加符合。

2）兩種策略的競爭率比較

圖3 兩種算法誤預(yù)測率對比

從表1中兩種方法所對應(yīng)的競爭率 （CR）可以看出，對沒有采取其他任何動(dòng)態(tài)電源管理策略的系統(tǒng)來說，兩中算法的功耗分別高于離線理想功耗20.9%和23.69%。當(dāng)空閑時(shí)間長度值服從均勻分布的概率條件時(shí)，本文采用的方法功耗節(jié)省的效果低于基于期望值策略2.79個(gè)百分點(diǎn)，更好的達(dá)到了功耗的節(jié)省。兩種方法的競爭率仿真實(shí)驗(yàn)效果圖如圖4所示。

圖4 兩種算法競爭率對比

5 結(jié)束語

對于嵌入式移動(dòng)終端來說，通過采用DPM策略降低設(shè)備功耗是一個(gè)重要的問題，同時(shí)為了不影響用戶的使用體驗(yàn)，所采用DPM策略的預(yù)測正確率也是一個(gè)重要衡量因素。本文提出一種基于概率統(tǒng)計(jì)加權(quán)空閑時(shí)間的改進(jìn)自適應(yīng)學(xué)習(xí)樹電源管理預(yù)測策略，通過在學(xué)習(xí)樹中增加空閑時(shí)間期望結(jié)點(diǎn)作為下一次預(yù)測的依據(jù)，并采用在學(xué)習(xí)樹中所存儲的各種狀態(tài)的實(shí)際歷史概率統(tǒng)計(jì)更新空閑時(shí)間長度預(yù)測值，從而克服了基于空閑時(shí)間期望值策略忽略歷史狀態(tài)序列預(yù)測結(jié)果之間的關(guān)聯(lián)性問題，使得預(yù)測的空閑時(shí)間長度值更加接近實(shí)際空閑時(shí)間期望，從而可以得到更小的功耗損失。仿真結(jié)果表明，與基于空閑時(shí)間期望值策略相比，本方法可以獲得更低的功耗損失，同時(shí)提高了預(yù)測的準(zhǔn)確率。

：

［1］LU Xuanbei.An approach to system－level advanced dynamic power management ［J］.Computer Applications and Software，2008，25 （11）：89－91 （in Chinese）. ［陸玄蓓.高級動(dòng)態(tài)電源管理在系統(tǒng)軟件層的設(shè)計(jì)與實(shí)現(xiàn) ［J］.計(jì)算機(jī)應(yīng)用與軟件，2008，25 （11）：89－91.］

［2］ZHAO Tan，CHEN Yu.Predictive shutdown method of dynamic power management based on active period ［J］.Application Research of Computers，2007，24 （7）：58－60 （in Chinese）.［趙坦，陳渝.一種基于活躍態(tài)的動(dòng)態(tài)電源管理預(yù)測算法 ［J］.計(jì)算機(jī)應(yīng)用研究，2007，24 （7）：58－60.］

［3］JIANG Qi，XI Hongsheng，YIN Baoqun.Stochastic switching model and policy optimization online for dynamic power management ［J］.ACTA Automatica Sinica，2007，33 （1）：66－71 （in Chinese）.［江琦，奚宏生，殷保群.動(dòng)態(tài)電源管理的隨機(jī)切換模型與在線優(yōu)化［J］.自動(dòng)化學(xué)報(bào)，2007，33 （1）：66－71.］

［4］BU Aiguo，LIU Hao，LI Jie.PBALT dynamic power management policy ［J］.Journal of Circuits and Systems，2005，10（4）：56－60 （in Chinese）.［卜愛國，劉昊，李杰.PBALT動(dòng)態(tài)電源管理策略 ［J］.電路與系統(tǒng)學(xué)報(bào)，2005，10 （4）：56－60.］

［5］Gaurav Dhiman，Tajana Simunic Rosing.Dynamic power management using machine learning ［C］／／IEEE／ACM International Conference on Computer－Aided Design，2006：747－754.

［6］Magesh Kumar C，Sindhwani M，Srikanthan T.Profile－based techniques for dynamic power management in embedded systems［C］／／International Conference on Electronic Design，2008：1－6.

［7］HE Kejia.Probability－based adaptive learning prediction strategy ［J］.Computer Engineering，2010，36 （10）：215－220（in Chinese）. ［何可佳.基于概率的自適應(yīng)學(xué)習(xí)預(yù)測策略［J］.計(jì)算機(jī)工程，2010，36 （10）：215－220.］

［8］QI Longning，HU Chen，ZHANG Zhe，et al.Idle expectation table based prediction policy of dynamic power management ［J］.Journal of Circuits and Systems，2007，12 （2）：89－93 （in Chinese）.［戚隆寧，胡晨，張哲，等.基于時(shí)間期望表的DPM預(yù)測策略 ［J］.電路與系統(tǒng)學(xué)報(bào)，2007，12 （2）：89－93.］

［9］Sandy Irani，Gaurav Singh，Sandeep K Shukla，et al.An overview of the competitive and adversarial approaches to designing dynamic power management strategies ［C］／／Evanston，USA：IEEE Transactions on Very Large Scale Integration Systems，2005：1349－1361.

［10］Kimiyoshi Usami，Daisuke Ikebuchi，Hiroshi Nakamura，et al.On－chip detection methodology for break－even time of power gated function units ［C］／／New Jersey，USA：International Symposium on Low Power Electronics and Design，2011：241－246.

［11］LI Jian－chuan.An adaptive dynamic power management prediction strategy of DSP ［C］／／Quebec，Canada：International Congress on Image and Signal Processing，2010：4179－4183.

［12］ZHONG Weijun，LIU Mingye，PENG Gang.Research on predictive algorithm of dynamic power management in embedded system ［J］.Microelectronics and Computer，2005，22（11）：56－58 （in Chinese）.［鐘偉軍，劉明業(yè)，彭剛.嵌入式系統(tǒng)動(dòng)態(tài)電源管理預(yù)測算法研究 ［J］.微電子學(xué)與計(jì)算機(jī)，2005，22 （11）：56－58.］