应用情景检测的安全任务内电压调度算法

陈 杰，易本顺

(武汉大学电子信息学院 武汉 430079)

随着移动电话、PDA、数码相机等移动嵌入式实时系统发展的日新月异，逐渐增多的大数据量处理与其电池供电、能量有限的矛盾也日益突出，促使研究者们探索延长电池工作时间的方法。动态电压调节技术及电压可调处理器的出现为降低处理器能耗提供了一种有效方法[1-2]，它们可针对处理器不同计算量的任务分配不同的电压等级，在满足任务处理实时性(也即安全性)的同时，减少处理器空闲时间、降低能耗，能获得很好的节能效果[3-4]。近年来，研究者们提出了任务内的电压调度策略，在任务程序中设置电压调整点(VSP)对电压进行实时调整，算法简单易行而节能效果更优。

根据剩余处理路径预测策略的不同，任务内的电压调度算法可分为基于剩余最坏情况处理路径(RWEP)[5]、基于剩余平均情况处理路径(RAEP)[6]及基于剩余最优化情况处理路径(ROEP)[7]共3类。因该3类基本算法在实际应用中存在节能效果不佳或实时性难以确保的缺陷，文献[8]提出了3种改进的基于RAEP的电压调度算法及其实时性确保方法，并提出应用任务程序的数据流和控制流信息标识VSPs，并将VSPs尽可能前移以优化调度任务处理电压。虽显著地降低了任务处理能耗，却引入了大量的预处理开销。文献[9]提出了基于RWEP的情景感知任务内电压优化调度技术(简称为SA-RWEP)，根据人为经验设置情景检测点(SDP)，对少数变量进行前摄检测、提前感知及利用空闲时隙，引入的预处理开销小、节能效果明显，性能更优。

基于文献[9]，本文提出一种改进的SD-RAEP。首先，引入基于RAEP的轮廓感知安全任务内电压调度算法(简称为PAS-RAEP)；然后，陈述在待处理的任务代码中选择参数及依其定义情景的方法；最后，提出SDP设置算法，以便在代码合理位置检测情景的发生。算法节能效果明显、具有很好的实时性。

1 能耗模型与任务模型

处理器能耗由动态能耗和漏电能耗两部分组成。降低处理器工作电压会线性地降低工作频率，导致任务处理时间延长，而其能耗和功耗分别以大于工作电压二次方和三次方的幅值降低。因此，根据任务参数，在任务处理实时性得到满足的前提下，降低处理器工作电压、减少空闲时隙，不仅可以提高处理器利用率，而且可以显著地降低能耗[2]。

2 SD-RAEP算法

2.1 PAS-RAEP算法

SD-RAEP算法将具有最大加权概率的处理路径作为参考路径，并依此预测基本块的剩余平均处理时钟周期数为：

2.2 参数选择和情景定义

在任务程序代码中，一些参数取不同值时任务工作量变化较大，这些参数一般只能取少数几个值，可以在程序中执行输入数据或加入赋值语句的方式进行设定，且在余下部分(或全部)的任务处理过程中保持不变。基于该事实，可以利用这些参数的值域划分应用情景，在任务处理时根据所发生的情景较为精确地预测任务处理的部分路径，剔除多余路径，优化调度余下基本块电压、降低任务处理能耗[9]。

根据各个参数取不同值时任务工作量的最大变化(简称为影响因子或IC)的大小，选择若干参数定义情景以在处理任务时进行检测。在该过程中，一般不必计算所有参数的IC，而只需选择在各个结构条件表达式中出现的参数进行计算即可。在计算参数v的ICv时，以从后向前的方式遍历程序抽象句法树，按式(6)～式(9)规则计算各个结构的ICv，累加得到v对任务的影响因子，该计算过程基于最坏情况处理时钟周期数(WCEC)。式(6)～式(9)中，S表示非控制型语句，v对其影响因子为0；B为条件表达式，B1及B2为语句段；nmin和nmax分别表示循环迭代的最小和最大次数，式(7)～式(9)为3种基本结构IC的计算规则。可选择IC相对较大的参数定义情景：在任务代码中，收集与每个所选参数进行比较的常数及相应比较符，利用其划分所选参数的取值区间，每个区间对应任务处理的一种情景。

2.3 SDP设置算法

根据所选定的参数和定义的情景，便可在任务程序中的适当位置设置SDP。SDP需检测任务处理过程中所发生的情景，由几行计算和判断语句完成。激活的情景应得到及时的感知，因此，在任务第一个基本块之前应设置SDP，检测程序输入数据所激活的情景，而在所选参数的值可确定时也应设置SDP。SDP设置算法的伪代码借用了文献[8]中变量前趋点及先行点的概念。设置SDP算法如下：

算法功能由函数SDP_Setup和Find_MDP实现。SDP_Setup完成SDP设置点的迭代搜索、确定及SDP设置全过程。首先调用SetSDP在任务第一个基本块之前设置SDP；然后调用Find_Conditions_Line搜索程序各个结构的条件表达式中包含先前选定参数且以vi的取值情况作为条件成立判据之一的行，函数返回其行号集将其中的元素称为基准点，针对基准点sj，应用Find_MDP函数，迭代搜索的前趋点集和先行点集最后在先行点处设置SDP。Find_MDP完成搜索参数多级前趋点集。首先搜索输入行处输入参数的前趋点集P，称此时的输入参数为中间变量，前趋点p为中间变量前趋点；然后对p中等式右边的变量进行识别，构成变量集V′(p)，如果其非空，则调用Find_MDP对V′(p)中的变量继续进行迭代搜索，函数返回最终搜索结果。

对于存在一个或多个SDP的点，判断各个SDP所涉及的参数，如果参数vi的每个相关情景发生时，任务的预测剩余处理路径与不进行情景检测时的预测路径相同，则在该点取消对vi的情景检测。完成SDP的设置后，采用PAS-RAEP算法对参考路径基本块进行电压调度并处理，任务处理偏离参考路径时则重新确定参考路径并更改处理频率。当任务处理到达SDP设置处时，利用中间变量前趋点处的表达式(由Transform函数关联)计算vi值后判断其哪一个情景被激活，并在相应基准点移除部分代码或判据，如所移除的代码中包含其他基准点，移除代码的同时也应移除这些基准点对应的SDP，之后仍需重新确定参考路径及进行频率更新。

3 仿真实验与分析

通过仿真实验对SD-RAEP算法性能进行分析，算法各步骤在SUIF2平台上实现。假定处理器最小处理频率为20 MHz，最大可达66 MHz(如采用ARM 7TDM I内核的微处理器S3C44B0X)，且在该范围内，频率可连续转换，转换开销为70 µs。分支结构任选的一条有向边的概率值由标准差为1、均值为0.5的正态分布计算得到，选择参考路径及基于RAEP的电压调度时，考虑情景检测所引入的开销，而将任务的截止期设置为最坏情况处理时间的1.5倍。通过MP3解码多媒体应用[10]，仿真实验验证了在移动嵌入式实时系统的低功耗设计中，应用SD-RAEP算法能显著地降低系统能量开销，保证任务处理的实时性，且比SA- RWEP性能更优。

表1 MP3解码器中IC值较大的参数

计算MP3解码器中参数的IC，其值大于100的参数已在表1中列出。由于第二个参数与第三个参数的IC值相差较大，因此，可以选择前两个参数定义情景。表2对SD-RAEP与SA-RWEP在平均节省能量及情景检测引入开销(以时钟周期数计)两项指标上进行了性能比较，解码器输入处理文件为随意在因特网下载的立体声歌曲，平均节省能量以基于RWEP的电压调度算法结果[5]为参考且表中所列为20次实验结果的平均值。同时，仿真实验也对只选最大IC值参数及选择两个以上参数定义情景的情况进行了比较与分析。

从表2中可知，SD-RAEP较SA-RWEP节省更多能量。基于RWEP的电压调度算法虽能较好地满足处理的实时性要求，然而，由于任务的处理很可能不会沿着最长路径且处理器频率范围有限，因此，基于该方法的电压调度可能会留有较多的空闲时隙，节能效果一般；而基于RAEP是以最大加权概率的处理路径作为参考路径的轮廓感知安全任务内电压调度算法，既考虑了剩余处理路径的概率，又考虑了该路径的时钟周期数，不会产生空闲时隙，比基于RWEP的电压调度算法的节能效果要好很多，而处理的实时性也能得到保证。另外，SA-RWEP根据人为经验设置SDP，虽然可以有效地控制SDP数量，算法相对简单，任务的预处理阶段的开销也较小，然而，缺乏依据的SDP设置方法会造成情景检测过早或不及时，使得情景发生后却无法感知或延迟感知，电压调度优化效果及节能效果有限或无效果。应用本文提出的SDP设置算法能最早地精确感知情景的发生并及时准确地做出路径预测及相应代码与CFG图简化处理，适时调整处理电压，最大程度地节省能量。通过在所有参数情景激活点设置SDP，算法也能感知参数各个情景状态的变化，而加入的较多的情景检测代码也引入了更多的额外开销，如表2所示。然而，当提前检测到的任务剩余工作量的预测值变化较大时，其对节能效果的影响较小。从表中也可以看出，增加参数mode_extension定义情景为应用SD-RAEP的最佳方案，节能性最优；而如增加参数m ixed_block_flag，反而会降低节能效果。

表2 SD-RAEP与SA-RWEP的性能比较

4 结 论

在研究了目前存在的任务内电压调度策略后，本文提出基于情景检测的安全任务内电压调度算法，以降低移动嵌入式实时系统的任务处理能耗。仿真实验证实应用该算法能在任务处理过程中及时感知发生的情景，优化地调度处理电压，明显地降低处理能耗而实时性也能得到保证，从而实现系统低功耗运行的目的。

[1] YUAN L, QU G. Analysis of energy reduction on dynam ic voltage scaling-enabled systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005, 24(12): 1827-1837.

[2] WANG A, CHANDRAKASAN A. Energy-efficient DSPs for w ireless sensor networks[J]. IEEE Signal Processing Magazine, 2002, 19(4): 68-78.

[3] YUAN T, EKICI E. Cross-layer collaborative in-network processing in multihop w ireless sensor networks[J]. IEEE Transactions on Mobile Computing, 2007, 6(3): 297-310.

[4] 桂盛霖, 雷航. 能耗限制的松弛任务实时调度算法[J]. 电子科技大学学报, 2008, 37(4): 598-601.

GUI Sheng-lin, LEI Hang. On energy-constrained real-time scheduling for elastic tasks[J]. Journal of University of Electronic Science and Technology of China, 2008, 37(4):598-601.

[5] SHIN D, KIM J, LEE S. Intra-task voltage scheduling for low-energy hard real-time applications[J]. IEEE Design &Test of Computers, 2001, 18(2): 20-30.

[6] SHIN D, KIM J. Intra-task voltage scheduling on DVS-enabled hard real-time systems[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24(10): 1530-1549.

[7] SEO J, KIM T, LEE J. Optimal intratask dynamic voltage-scaling technique and its practical extensions[J].IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25(1): 47-57.

[8] SHIN D, KIM J. Optimizing intratask voltage scheduling using profile and data-flow information[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2007, 26(2): 369-385.

[9] GHEORGHITA S V, BASTEN T, CORPORAAL H.Intra-task scenario-aware voltage scheduling[C]//Proceedings of the 2005 International Conference on Compilers, Architectures and Synthesis for Embedded Systems. New York: ACM, 2005.

[10] LAGERSTROM K. Design and implementation of an MP3 decoder[EB/OL]. [2009-07-13]. http://www.km lager.com.

编 辑 张 俊