多处理器系统可靠性约束下的节能调度算法

1、多处理器系统可靠性约束下的节能调度算法摘要：针对多处理器系统中随机到达的任务，设计了可靠性约束下的节能调度算法ESACR。该算法在满足任务截止期限的前提下选择一个预计产生能耗最小的处理器以节能，在单个处理器上运用最早截止期限优先策略进展调度并尽量使各个任务的执行电压/频率平衡，当新到任务在处理器上不能满足截止期限要求时那么逐个调高前面未执行任务的电压/频率。同时，为保证系统的可靠性，ESACR给正在执行的任务预留错误恢复时间以保证当发生瞬时错误时该任务能被恢复。实验结果说明，与最高电压节能调度HVEA、最小能耗最小完成时间调度MEMC、最早完成时间优先调度EFF相比，ESACR在保证系统可靠性

2、的前提下节能效果最好。关键词：多处理器系统；随机任务；可靠性约束；节能；调度中图分类号： 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 task

3、s 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

4、 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 Vo

5、ltage EnergyAware HVEA， Minimum Energy Minimum Completion time MEMC and Earliest Finish First EFF.英文关键词Key words：multiprocessor system； random task； reliability constraint； energyefficient； scheduling0 引言因为瞬时错误更加常见，所以本文只考虑瞬时错误，假设系统的瞬时错误服从泊松分布8，11，14，处理器以频率f对应的电压为V执行任务时瞬时错误率8，11为：f=0gf=0 10d1-f1-fmin

6、31.4 问题定义给定一个随机到达的任务集T和一个具有m个处理器的计算系统，系统中的每一个处理器都DVFS可调，任务集中的每一个任务可在任何一个处理器上执行。为使系统满足可靠性，要求执行任务的错误率保持在0的程度并尽量节能。2 ESACR算法设计2.1 算法思想考虑有m个处理器的系统，每个处理器上的任务队列都按EDF缩略语算法进展调度。为保证每个处理器上任务执行时的可靠性，当处理器以非最高电压/频率执行时，因为可能会产生瞬时错误使系统的可靠性达不到要求，需要在任务的截止期限内预留错误恢复时间，并设定任务恢复时都以最高电压/频率执行，假设无错误发生那么下一个任务可紧接着执行。当处理器以最高电压/

7、频率执行时那么不预留错误恢复时间。在考虑了预留错误恢复时间之后，处理器上的松弛时间那么可回收用于节能。当一个任务到达时，立即获取任务三元组Ai， Ci， Di信息，假设将该任务分配到某个处理器后，处理器将按一个相对平衡的电压/频率执行任务，在满足截止期限的情况下，算法选择一个预计能耗最小的处理器执行该任务。2.2 算法描绘为保证任务执行时的可靠性，Scheduling算法为即将执行的任务构造一个错误恢复时间recoveryTime，然后试图将任务按一个统一的电压/频率执行。当任务不能满足截止期限要求时，那么逐个将前面未执行任务的电压/频率调至最高并去掉recoveryTime。通过调用Sche

8、duling算法返回任务ti分配到处理器m增加的能耗之后，即可应用选择法找出执行ti增加能耗最小实际上是使系统总能耗最小的处理器。另外当一个任务执行完后，应该更新预分配的错误恢复时间recoveryTime。根据这一思想，设计顶层算法如下：2.3 ESACR算法分析2.3.1 错误恢复时间设定的讨论性质 错误恢复时间的设定方法不会导致处理器上已有的任务队列变得不可调度。2.3.2 时间复杂度分析为验证算法的性能，在考虑系统可靠性的前提下，将ESACR算法与最高电压节能 Highest Voltage EnergyAware，HVEA调度5、最小能耗最小完成时间 Minimum Energy M

9、inimum Completion time，MEMC调度6 和最早完成时间优先Earliest Finish First，EFF调度进展比较。3.1 实验参数设定3.2 实验分析任务到达时间间隔不同时，不同算法的可靠性与相对能耗相对能耗指什么？需明确说明，是否是指与EFF的比值？，假设是，图中纵坐标改为“相对EFF能耗因为EFF算法的能耗相对其他算法的能耗大一些，这里的归一化是用各个算法产生的能耗都单独除以EFF算法产生的能耗，那么EFF算法的能耗变为1，其他算法的能耗那么变为0-1之间的数值。从图3a可知，当任务的计算量C418，48之前时，EFF、HVEA及ESACR算法的可靠性均到达1

10、00%；当计算量变大时，四个算法的可靠性均小于100%。从图3b可知，可靠性能到达100%的三个算法中，ESACR算法的能耗最小，约为EFF的70%左右。从图4a可知，当截止期限小于到达时间加6C？6C时，四个算法的可靠性均小于100%；当截止期限为到达时间加6C时，EFF、HVEA及ESACR算法的可靠性到达100%，MEMC的可靠性那么一直小于60%。从图4b可知，三个可靠性到达100%的算法中，ESACR算法的相对能耗最小，约为EFF的75%左右，且随着截止期限的放宽，ESACR算法的相对能耗有下降趋势。从图5a可知，当处理器数小于10时，四个算法的可靠性均小于100%；当处理器数到达1

11、0时，EFF、HVEA及ESACR算法的可靠性到达100%，MEMC的可靠性那么一直小于80%。从图5b可知，三个可靠性到达100%的算法中，ESACR算法的相对能耗最小，平均约为EFF的70%左右，且随着处理器的增加有下降趋势。通过以上4个实验可知，EFF、HVEA及ESACR算法的可靠性根本一样，但ESACR算法的相对能耗明显低于另外两个算法，MEMC算法虽然节能效果明显，但多数时候不能满足系统可靠性要求。4 结语可靠性与节能在很多系统中非常重要，针对多处理器系统中随机到达的任务，设计了可靠性约束下的节能调度算法，算法通过构造错误恢复时间以保证系统的可靠性，通过平衡单个处理器上任务的执行电

12、压/频率以节能，实验结果说明本文算法在保证系统可靠性的前提下具有较好的节能效果。后续研究可以考虑任务调度过程中的通信能耗、存储器访问能耗等。参考文献：6KIM 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， 2021，1911：1445-1457.9ZHU D， MELHEM R， MOSSE D. The effects of energy management on reliab