改进自适应学习树电源管理预测策略

李伟生，王 冬

（重庆邮电大学 计算机科学与技术研究所，重庆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.］