摘要：针对多处理器系统中随机到达的任务，设计了可靠性约束下的节能调度算法（ESACR）。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能，在单个处理器上运用最早截止期限优先策略进行调度并尽量使各个任务的执行电压/频率均衡，当新到任务在处理器上不能满足截止期限要求时则逐个调高前面未执行任务的电压/频率。同时，为保证系统的可靠性，ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果表明，与最高电压节能调度（HVEA）、最小能耗最小完成时间调度（MEMC）、最早完成时间优先调度（EFF）相比，ESACR在保证系统可靠性的前提下节能效果最好。
关键词：多处理器系统；随机任务；可靠性约束；节能；调度
中图分类号： TP393 文献标志码：A
英文摘要
Abstract：A kind of Energyefficient Scheduling Algorithm under the Constraint of Reliability （ESACR） for the random tasks in multiprocessor system was proposed. It would choose the processor which might consume the least energy when the tasks deadline could be guaranteed. For the signal processor， Earliest Deadline First （EDF） strategy was used to schedule the tasks and all the tasks were made execute in the same voltage/frequency. When the new task could not match the deadline， the nonexecution voltage/frequency of former tasks would be raised. At the same time， the recovery time was reserved for the executing task in order to promise that the task could be rescheduled when errors happened. The simulation shows that the ESACR can provide the better energy efficiency with the guarantee of system reliability ， compared to Highest Voltage EnergyAware （HVEA）， Minimum Energy Minimum Completion time （MEMC） and Earliest Finish First （EFF）.
英文关键词
Key words：multiprocessor system； random task； reliability constraint； energyefficient； scheduling
0 引言
因为瞬时错误更加常见，所以本文只考虑瞬时错误，假设系统的瞬时错误服从泊松分布[8，11，14]，处理器以频率f（对应的电压为V）执行任务时瞬时错误率[8，11]为：
λ（f）=λ0g（f）=λ0 10d（1-f）1-fmin（3）
1.4 问题定义
给定一个随机到达的任务集T和一个具有m个处理器的计算系统，系统中的每一个处理器都DVFS可调，任务集中的每一个任务可在任何一个处理器上执行。为使系统满足可靠性，要求执行任务的错误率保持在λ0的水平并尽量节能。
2 ESACR算法设计
2.1 算法思想
考虑有m个处理器的系统，每个处理器上的任务队列都按EDF缩略语算法进行调度。为保证每个处理器上任务执行时的可靠性，当处理器以非最高电压/频率执行时，因为可能会产生瞬时错误使系统的可靠性达不到要求，需要在任务的截止期限内预留错误恢复时间，并设定任务恢复时都以最高电压/频率执行，如果无错误发生则下一个任务可紧接着执行。当处理器以最高电压/频率执行时则不预留错误恢复时间。在考虑了预留错误恢复时间之后，处理器上的松弛时间则可回收用于节能。当一个任务到达时，立即获取任务三元组（Ai， Ci， Di）信息，假设将该任务分配到某个处理器后，处理器将按一个相对均衡的电压/频率执行任务，在满足截止期限的情况下，算法选择一个预计能耗最小的处理器执行该任务。
2.2 算法描述
为保证任务执行时的可靠性，Scheduling算法为即将执行的任务构造一个错误恢复时间recoveryTime，然后试图将任务按一个统一的电压/频率执行。当任务不能满足截止期限要求时，则逐个将前面未执行任务的电压/频率调至最高并去掉recoveryTime。
通过调用Scheduling算法返回任务ti分配到处理器m增加的能耗之后，即可应用选择法找出执行ti增加能耗最小（实际上是使系统总能耗最小）的处理器。另外当一个任务执行完后，应该更新预分配的错误恢复时间recoveryTime。根据这一思想，设计顶层算法如下：
2.3 ESACR算法分析
2.3.1 错误恢复时间设定的讨论
性质 错误恢复时间的设定方法不会导致处理器上已有的任务队列变得不可调度。
2.3.2 时间复杂度分析
为验证算法的性能，在考虑系统可靠性的前提下，将ESACR算法与最高电压节能 （Highest Voltage EnergyAware，HVEA）调度[5]、最小能耗最小完成时间 （Minimum Energy Minimum Completion time，MEMC）调度[6] 和最早完成时间优先（Earliest Finish First，EFF）调度进行比较。
3.1 实验参数设定
3.2 实验分析
任务到达时间间隔不同时，不同算法的可靠性与相对能耗相对能耗指什么？需明确说明，是否是指与EFF的比值？，若是，图中纵坐标改为“相对EFF能耗”因为EFF算法的能耗相对其他算法的能耗大一些，这里的归一化是用各个算法产生的能耗都单独除以EFF算法产生的能耗，则EFF算法的能耗变为1，其他算法的能耗则变为0-1之间的数值。
从图3（a）可知，当任务的计算量C4∈[18，48]之前时，EFF、HVEA及ESACR算法的可靠性均达到100%；当计算量变大时，四个算法的可靠性均小于100%。从图3（b）可知，可靠性能达到100%的三个算法中，ESACR算法的能耗最小，约为EFF的70%左右。
从图4（a）可知，当截止期限小于到达时间加6C？6C时，四个算法的可靠性均小于100%；当截止期限为到达时间加6C时，EFF、HVEA及ESACR算法的可靠性达到100%，MEMC的可靠性则一直小于60%。从图4（b）可知，三个可靠性达到100%的算法中，ESACR算法的相对能耗最小，约为EFF的75%左右，且随着截止期限的放宽，ESACR算法的相对能耗有下降趋势。
从图5（a）可知，当处理器数小于10时，四个算法的可靠性均小于100%；当处理器数达到10时，EFF、HVEA及ESACR算法的可靠性达到100%，MEMC的可靠性则一直小于80%。从图5（b）可知，三个可靠性达到100%的算法中，ESACR算法的相对能耗最小，平均约为EFF的70%左右，且随着处理器的增加有下降趋势。
通过以上4个实验可知，EFF、HVEA及ESACR算法的可靠性基本相同，但ESACR算法的相对能耗明显低于另外两个算法，MEMC算法虽然节能效果明显，但多数时候不能满足系统可靠性要求。
4 结语
可靠性与节能在很多系统中非常重要，针对多处理器系统中随机到达的任务，设计了可靠性约束下的节能调度算法，算法通过构造错误恢复时间以保证系统的可靠性，通过均衡单个处理器上任务的执行电压/频率以节能，实验结果表明本文算法在保证系统可靠性的前提下具有较好的节能效果。后续研究可以考虑任务调度过程中的通信能耗、存储器访问能耗等。
参考文献：
[6]KIM J K， SIEGEL H J， MACIEJEWSKI A A， et al. Dynamic resource management in energy constrained heterogeneous computing systems using voltage scaling [J]. IEEE Transactions on Parallel and Distributed Systems， 2008，19（11）：1445-1457.
[9]ZHU D， MELHEM R， MOSSE D. The effects of energy management on reliability in realtime embedded systems [C]// Proceedings of IEEE/ACM International Conference on Computer Aided Design. Piscataway： IEEE， 2004： 35-40.
