改進自適應學習樹電源管理預測策略

李偉生，王 冬

（重慶郵電大學 計算機科學與技術研究所，重慶400065）

0 引 言

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

1 基于概率的自適應學習樹

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

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

圖1 具有兩種低功耗狀態的概率自適應學習樹

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

基于概率的自適應學習樹對歷史實際空閑狀態有很好的統計，所以在以預測正確率為評估標準的條件下是比較好的。但是文獻 ［8］中通過對能耗與空閑時間關系的分析，說明了如果以空閑時間期望值作為預測依據，可以使設備整體功耗在統計意義上達到最小。

2 基于空閑時間期望值策略

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

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

通過上面的分析我們知道該策略在統計意義上可以獲得比較低的功耗損失，但是由于其采用的指數加權方法忽略了歷史狀態序列預測結果之間的關聯性，導致空閑時間長度的預測準確性不是很高，此外，參數a的設置也會對空閑時間預測的準確性及其更新的反應速度有著較大的影響。鑒于此，本文提出基于概率統計加權空閑時間的自適應學習樹電源管理預測策略。

3 概率統計加權空閑時間的自適應學習樹

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

圖2 具有兩種低功耗狀態的改進自適應學習樹

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

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

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

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

具體算法步驟描述如下：

（1）初始化樹形結構。包括建立歷史路徑序列索引表，初始化預測狀態概率和預測空閑時間長度信息等結構體變量；

（2）根據歷史路徑序列進行空閑時間長度預測 （初始歷史路徑序列選擇為s3＝000）；

（3）當有空閑時間出現時，根據當前歷史路徑序列索引值中的預測空閑時間長度控制設備進入相應的低功耗狀態；

（4）設備實際空閑時間結束，首先計算歷史路徑序列的索引值，然后更新該索引值中的預測狀態概率，再根據得到的新的預測狀態概率值更新該歷史路徑序列下一次的預測時間長度，最后根據實際空閑時間長度更新歷史路徑序列；

（5）控制設備進入工作模式；

（6）重復第 （2）至第 （6）步驟直到設備進入關斷狀態。

通過以上的算法實現，理論上可以得到比基于時間期望策略更低的整體功耗花費和較高的預測準確率，本文在下一小節給出仿真實驗結果。

4 實驗與結果

4.1 仿真環境

仿真環境設置如下：

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

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

4.2 仿真結果

通過以上參數設定，在Matlab中對兩種算法進行仿真實驗，我們通過以下兩種指標來進行比較：

（1）誤預測率PER：誤預測率PER＝×100%，PER值越低，說明預測越準確。

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

1）兩種策略的誤預測率比較

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

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

圖3 兩種算法誤預測率對比

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

圖4 兩種算法競爭率對比

5 結束語

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

：

［1］LU Xuanbei.An approach to system－level advanced dynamic power management ［J］.Computer Applications and Software，2008，25 （11）：89－91 （in Chinese）. ［陸玄蓓.高級動態電源管理在系統軟件層的設計與實現 ［J］.計算機應用與軟件，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）.［趙坦，陳渝.一種基于活躍態的動態電源管理預測算法 ［J］.計算機應用研究，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）.［江琦，奚宏生，殷保群.動態電源管理的隨機切換模型與在線優化［J］.自動化學報，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動態電源管理策略 ［J］.電路與系統學報，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）. ［何可佳.基于概率的自適應學習預測策略［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）.［戚隆寧，胡晨，張哲，等.基于時間期望表的DPM預測策略 ［J］.電路與系統學報，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）.［鐘偉軍，劉明業，彭剛.嵌入式系統動態電源管理預測算法研究 ［J］.微電子學與計算機，2005，22 （11）：56－58.］