基于系统信息的动态功耗管理策略

李 波，董 岚，任 玲

（吉林省六六一台，长春 130119）

基于系统信息的动态功耗管理策略

李 波，董 岚，任 玲

（吉林省六六一台，长春 130119）

传统的嵌入式系统动态功耗管理策略仅从设备的角度考察工作负载状况，忽略了工作负载的应用特征，针对这一问题，本文从系统状态的角度分析负载，提出非平稳系统下功耗策略改进方法SMBSP。

动态功耗管理；Markov决策过程；策略优化；嵌入式系统

1 引言

动态电源管理（DPM）根据系统工作负载的变化情况来有选择地将系统资源设置为低功耗模式，以最少的元件或元件最小工作量的低耗能状态来完成系统任务，从而达到降低系统能耗的目的。性能限制条件下的功耗最小化（或者功耗限制条件下的性能最大化）策略模型是一个受限的最优化问题。

DPM功耗管理策略大体上可分为三类：超时策略、预测策略和随机策略。其中，超时策略（Timeout）是一种原理最为简单，但同时也是应用最为广泛的技术，它分为两种情况：具有固定超时时限的策略（Fixed Timeout）和自适应超时策略（Adaptive Timeout），前者在设备经过一段固定的空闲时间段后会关闭目标设备，而后者会根据设备的历史记录来动态调整超时时限值。预测策略在开始时就对本次空闲时间长度进行预测，一旦预测值足够大，在一开始就将PMC（Power Manageable Component）切换到相应休眠模式。随机策略则通过设备操作请求和设备服务的Markov模型描述系统的随机行为，从而能够更准确地选择设备将要进入的低功耗状态。

近年来，关于随机DPM策略的研究非常活跃。对于非平稳系统，Chung等提出了基于滑动窗口的DPM算法；Li等应用基于强化学习的Q学习方法对参数未知系统进行优化，能够有效地优化确定型策略，但不能很好地满足带约束优化问题的需要；S.Irany提出的是基于概率统计的超时策略，用窗口内的样本直方图近似计算分布从而确定最佳超时门限[18]。以上算法都假设空闲时间长度服从一定的概率分布，如几何分布、负指数分布、重尾分布等，不适用于一般分布的情况，本文通过对设备负载的进一步分析，提出了SMBSP算法。

2 系统信息的获取

参考基于程序计数器的访问预测（PCAP）策略方法，线程的执行可以根据设备的API函数被调用地址进行划分，栈（stack）反映了线程的调用过程，如图1所示，采用栈深（stack depth）和返回地址（return address）来联合区分调用路径。其中，栈深是当前栈指针（stack pointer，即当前sp寄存器的内容）与初始栈指针的差值，返回地址是当前链接寄存器的内容，这些可以从线程保存的上下文中获取，这样可以根据函数调用的栈深和返回地址来预测设备操作的间隔时间。

基于系统信息建立统计查找表，其中保存了间隔时间的设备操作所对应的Ra和Sd以及间隔时间的分布（Ra，Sd分别表示返回地址和栈深），每次操作请求到来时根据Ra和Sd匹配查找表，并根据实际的间隔时间更新分布。属于相同进程和线程组分类的操作序列具有相似性，因此可以共享同一张查找表。查找表中保存的分布信息即为所需的各进程设备操作时间间隔的分布。

3 SMBSP算法

3.1 Markov随机模型

设PMC具有K种低功耗休眠模式，按功率由高到低排列分别由m1，m2，…，mk+1表示。PMC空闲并保持就绪模式记为m0，就绪模式是指PMC空闲并保持就绪。PMC工作状态记为mk+1=mw。有w(m0)≥w(m1)≥…≥w(mk)≥w(mk+1)。

PMC状态集合包括可长时间驻留状态，用M=｛mi|i=0，1，…，K+1}表示。可将一次空闲时段内PMC状态变化过程抽象为受控马尔科夫链，由以下五元组描述：

式中，状态空间S={(tk，mk)|n=0，1…，NMAX}，(t0，m0)开始状态和（tMAX，mK+1）为终止状态，当PMC转变为mK+1模式，则保持mK+1模式，直到tMAX，时间t可以上节中建立的查找表获得；A(s)是状态为s∈S时功耗管理器可用命令集合；Pst(a)是转换概率，指当前状态为s采取动作a∈A(s)时，下一状态为t的概率；c(s，a)是代价函数，指状态为s采取动作a时，在随后间隔时间内的功耗；v为目标优化函数，指空闲时间总功耗的数学期望，若设备处于模式i时的平均功耗为ai，从模式i进入正常工作状态的转换能耗为bi，设备操作的间隔时间服从概率密度函数为FD(t)的分布，设置从模式i转换到状态i+1的超时门限为k，则空闲时间总功耗的数学期望为

3.2 Markov策略优化

定义功耗和性能损失向量

策略优化实质上是性能约束下的功耗优化问题，本文采用折扣模型进行分析。

对策略π和固定的折扣因子β（0＜β＜1），系统在第n个决策周期的d和c的折扣期望可用式（5）表示

式中，p(1)表示系统在初始时刻t1的状态概率分布；表示在策略π下，从决策周期0到周期n-1的转移矩阵。因此，性能约束下的功耗优化问题可用式（6）描述。

折扣准则下式（6）转化为式（7）的线性规划问题（LP）。

4 实验结果

为了评估策略的节能效果和对性能的影响，本文用VC6.0仿真环境来验证随机最优算法的效果，并将其与timeout，predictive算法进行比较。采用某型诸元计算器作为实验对象，图2给出了某型诸元计算器的PSM（Power State Machine）模型。各个状态均标有相应的功耗，边线上标出了状态转换所需要的时间及切换功耗。

在本文的仿真环境中，为验证效果产生了六个不同的任务列，基于系统信息的时间序列概率统计查找表如表1所示，决策时刻即为表中的各时间点。

每个任务列分别应用以下电源管理策略（其中平衡时间Tbe=80，时间点数N=12）：

（1）Timeout1：超时阈值=80（等于Tbe）的固定时限超时策略。

（2）Timeout2：超时阈值=120（等于1.5倍Tbe）的固定时限超时策略。

（3）Predict：Hwang的指数平均法[11]（预测策略），取a=0.5，使最近的历史和先前的历史有相等的权衡值。

（4）Adaptive1：超时阈值=80的自适应DPM策略。

（5）Adaptive2：超时阈值=120的自适应DPM策略。

（6）This paper：本文策略。

采用竞争率作为功耗评估指标，延迟率作为性能指标，命中率作为策略的预测效率指标，分别定义如下：

延迟率（TA为当前策略下的总时间，Tno为无策略时的总时间）。

命中率η=预测正确次数/预测总次数。

竞争率反映了当前策略相对于最优策略降低功耗的效率，值越高表示节能效果越接近最优策略，各策略的竞争率比较如图3所示，Timeout策略的超时阈值大小决定了竞争率结果，如果选择不准确则节能效果十分不理想。Predict策略波动很大，而Adaptive策略则相对比较稳定，这是因为Predict策略预测值有比较大的延迟性，而Adaptive策略则加入了一定的自适应机制。本文策略的竞争率达到了0.57。在不考虑性能损失的条件下，选择超时阈值准确的超时策略和本文策略的节能效果都是趋近于最优的。

各策略的延迟率和命中率比较分别如图4和图5所示，Adaptive策略拥有较低的延迟率和较高的命中率，Predict策略虽然有最高的命中率但同时有最高的延迟率，这也导致了它的竞争率有较大的波动性。超时策略只有准确选择超时阈值时，节能效果才趋近于最优，否则效果十分不理想，但对同一系统进行统计时，其估计值是可能不同的，所以准确的超时阈值是很难得到的。从整体上看，除本文策略延迟率小于0.1外，其他策略都超过了0.15，主要原因是其他策略均没有引入决策时刻机制。从图中可以看出对同一系统进行系统信息的时间序列概率统计时，其估计值是可能不同的，策略可能不是最优的，但通过本文算法得到的最终策略都是趋近于最优的。

在考虑性能损失的条件下，假定初始时刻SP处于S1模式，无请求且队列为空，则初始概率分布为b=(1,0,0,0,0,…,0)T。设折扣因子β=0.8，时间点数N=12，则根据公式（7）求解该线性规划得到各时刻点最优策略如下

5 结束语

针对嵌入式系统的多任务环境，本文提出了一种基于系统信息的随机策略（SMBSP），通过任务的调用和堆栈信息分析任务对设备的访问模式，采用基于概率统计的随机模型进行决策。本文给出的随机最优算法可以在节能和系统性能之间找到恰当的折衷切入点，在二者之间取得较好的平衡，算法计算量小，适合在嵌入式系统中应用。需要指出的是，实验最后部分通过该算法得到的策略适当地简化了系统模型，其结果仅具有参考性；其次，基于系统信息的马尔可夫模型只是对一个相当复杂的随机过程的大致估计，对于同一系统其估计值是可能不同的，但通过本文算法得到的最终策略都是趋近于最优的。

System Message based Dynamic Power Management Policy

Li Bo, Dong Lan, Ren Ling
(The 661th Station Jilin province, Changchun, 130119)

Traditional dynamic power management policies of embedded system only focus on equipment workload situation from the perspective of device, and ignore the application features of the workload. An improved method called SMBSP (System message based stochastic policy) is proposed on the basis of analyzing workload according to system state.

Dynamic power management; Markov decision processes; Policy optimization; Embedded system

10.3969/J.ISSN.1672-7274.2015.06.009

TK01+8

B

1672-7274（2015）06-0054-04