多处理器系统可靠性约束下的节能调度算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇多处理器系统可靠性约束下的节能调度算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：针对多处理器系统中随机到达的任务，设计了可靠性约束下的节能调度算法（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 引言
随着制造工艺的不断进步，多处理器系统的性能越来越强，但其功耗也越来越大，节能已成为一个亟待解决的重要问题[1]。目前，已有许多处理器具备动态电压/频率调节（Dynamic Voltage/Frequency Scaling， DVFS）功能，应用程序执行时可动态调整电压/频率以降低能耗。近年来，有很多学者基于DVFS研究了多处理器系统或多核系统的任务调度节能问题，如：文献[2]基于DVFS提出一种启发式测试调度方法用于缩短测试时间；文献[3]提出一种基于任务图的节能调度算法；文献[4]考虑处理器的切换开销，提出一种基于帧任务模型的节能调度算法；文献[5]根据负载情况权衡系统能耗与用户期望；文献[6]讨论了能量受限的异构系统任务调度；文献[7]证明了在多处理器系统中满足任务截止期限的最优能耗调度是NP难问题。
目前大多数研究都是通过回收空闲时间、降低非关键任务的执行频率、关闭处理器等方法进行节能，在节能调度中很少分析系统的可靠性。可靠性是任务在截止期限内被正确执行的概率[8]，尤其在不通？尤其在航空、交通、医疗等许多安全关键的实时系统设计中非常重要。航空、交通、医疗等许多安全关键的实时系统设计中非常重要。系统运行时的错误一般分为瞬时错误和永久错误，而瞬时错误更加常见。已有研究表明，降低处理器的运行频率，会增加系统的瞬时错误[9]。在节能调度中，因为调低了处理器的运行频率，从而会导致系统的可靠性下降，因此对于安全关键的系统考虑可靠性是非常必要的。也有一些学者研究了系统的可靠性和节能的问题，如：文献[8]基于抢占最早截止期限优先（Earliest Deadline First， EDF）策略分别研究了实时周期性任务静态和动态可靠性感知能耗管理（ReliabilityAware Power Management， RAPM）方案，证明了静态RAPM是NP难问题；文献[10] 针对多核平台中的周期性实时任务，提出满足可靠性目标的节能调度算法；文献[11]在保证系统可靠性的同时通过调节处理器的速度和关闭处理器以节省能耗；文献[12]基于帧的实时任务集在保证系统可靠性的前提下使能耗最小化。以上这些算法都是基于周期性或帧任务分析系统可靠性与节能调度的问题，需要事先知道任务的相关属性，不太适合动态随机任务的调度。基于以上原因，本文分析多处理器系统中可靠性约束下的动态随机任务节能调度，提出可靠性约束下的节能调度 （Energyefficient Scheduling Algorithm under the Constraint of Reliability， ESACR）算法，在保证系统可靠性的同时节能。
1.3 错误模型
因为瞬时错误更加常见，所以本文只考虑瞬时错误，假设系统的瞬时错误服从泊松分布[8，11，14]，处理器以频率f（对应的电压为V）执行任务时瞬时错误率[8，11]为：
λ（f）=λ0g（f）=λ0 10d（1-f）1-fmin（3）
其中：d是一个大于0的常数；λ0是处理器以最大频率执行时的平均瞬时错误率。因此当f1。当执行频率调到最低的时候，系统的最大错误率λ（fmin）=λ010d（1-fmin）1-fmin=λ010d，如果d=2[8，11]，则系统以最低频率运行时发生瞬时错误的概率是λ0的100倍。
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。根据这一思想，设计顶层算法如下：
当一个新任务到达时，顶层算法在保证可靠性的前提下选择一个增加能耗最小的处理器执行该任务，如果有任务执行完毕，则更新预留的错误恢复时间recoveryTime。在某个处理器上只有当任务出现瞬时错误才考虑恢复，当处理器的电压/频率被调低时，始终在任务的截止期限内保留一个错误恢复时间。如图1（a）所示，假设某个处理器上分配了任务t1，t2，…，tk，任务t1从time0时刻开始执行到time1结束，为了保证系统的可靠性，预留一个从time1至time2的时间段用于恢复任务t1。如果t1没有发生瞬时错误，则可t2从time1时刻开始运行，如图1（b）所示，这时需要在任务t2的后面预留一个错误恢复时间；如果图1（a）中t1发生了错误，time1至time2时间段用于恢复t1，t2从time2处开始执行，如图1（c）所示，这时仍然需要给t2预留错误恢复时间。
2.3 ESACR算法分析
2.3.1 错误恢复时间设定的讨论
性质 错误恢复时间的设定方法不会导致处理器上已有的任务队列变得不可调度。
前面是定理或性质吗，若不是，后面的证明有些奇怪，要么删除证明证明 设某个处理器的任务队列为t1， t2，…，tk，
算法在设定t1的错误恢复时间为time1至time2时，如图1（a）所示，任务队列是可调度的，否则t1将以最大电压/频率执行，不需给t1设定错误恢复时间。如果给t1设定了错误恢复时间，当t1执行完后，任务队列变为图1（b）或图1（c）的形式。这时，不管t1是否发生瞬时错误，t2至tk原来都是可以调度的，只需考虑给t2设定错误恢复时间后，t3至tk是否可以调度即可，如果给t2设定错误恢复时间，后面的任务仍可调度，则设定；否则t2以最高电压/频率执行，这时不需设定错误恢复时间，后面的任务显然可以被调度。所以，错误恢复时间的设定方法不会导致处理器上已有的任务队列变得不可调度。
2.3.2 时间复杂度分析
根据2.2节算法描述，当一个新任务到达时，需要执行Scheduling算法选择预计能耗最小的处理器。在执行Scheduling算法时，最坏的情况是新任务到达时前面到达的任务都没有执行完，设第i个任务到达的时候，处理器j上有kj个任务没有执行完，这时Scheduling算法中第指的行编号的1）、9），还是指实际上的行，第一行没有编号，请作者核实？2.3.1节 中提到的行号和Scheduling算法中标出的行号是对应的。建议用原文中的描述方式。1）、9）、10）、12）、22）行计算次数为kj，第17）行为kj2，其余各行计算次数为1，所以Scheduling算法在第j个处理器上的执行时间为5kj+kj2+C，其中C为常数。考虑到系统有m个处理器，所以某个新任务到达后的计算时间为∑mj=1核实是否加括号。这三个位置的括号都需要，原文没有错误。（5kj + k2j + C），第i个任务到达时所有处理器上的任务总数为i-1个，可知∑mj=1kj=i-1。而∑mj=1核实是否加括号（5kj + k2j + C）=5（i-1） + mC + ∑mj=1k2j ≤5（i-1）+mC+（i-1）2。因为任务总数为n，计算总时间应小于∑ni=1核实是否加括号[5（i-1）+mC+（i-1）2]，时间复杂度可写成O（n3）的形式。根据前面的分析方法同样可得出顶层算法中指的程序编号还是实际中的行，建议用程序编号表示第6）行，计算时间最坏情况为n2。所以ESACR算法的最坏时间复杂度为O（n3）；一般情况下，当后面的任务到达时，前面的一些任务可能已执行完毕，所以ESACR算法时间复杂度在实际中会远小于O（n3）。
3 实验比较与分析
为验证算法的性能，在考虑系统可靠性的前提下，将ESACR算法与最高电压节能 （Highest Voltage EnergyAware，HVEA）调度[5]、最小能耗最小完成时间 （Minimum Energy Minimum Completion time，MEMC）调度[6] 和最早完成时间优先（Earliest Finish First，EFF）调度进行比较。
3.1 实验参数设定
根据文献[4]中的近似功耗函数p（f）=1.52f3+0.08w，为体现处理器异构，本文随机生成α、β以及处理器的最大频率fmax，其范围分别为：1.4≤α≤1.6，0.07≤β≤0.09，1.0≤fmax≤1.6，fmin由能耗模型中的公式计算得出。为方便计算，各算法产生的能耗用p（f）乘以时间单位表示，什么含义？并以EFF算法为参考进行归一化处理，将EFF算法产生的能耗归整为1。系统运行时的错误率由式（3）计算，并设d=2[8，11]，当处理器以最高频率执行时设错误率λ0=0.01%（因为瞬时错误率λ0满足系统可靠性要求，在实验中将其忽略）。为比较各种算法的可靠性和能耗，将不能在截止期限内完成的任务也视为发生错误，将系统的可靠性表示为R=截止期限内正确完成的任务数/任务总数。
3.2 实验分析
实验1 使用8个处理器，随机生成1000个任务，任务的到达时间间隔a分别为a1∈[1，4]，a2∈[1，6]，a3∈[1，8]，a4∈[1，10]，a5∈[1，12]的随机数，任务的计算量为C∈[5，50]的随机数，截止期限D为到达时间加3C是否可用3C描述？3倍C可直接用3C表示。各算法的可靠性与能耗如图2所示。
从图2（a）可知，当任务的到达时间间隔a1∈[1，4]时，四个算法的可靠性都小于100%；当时间间隔达到或超过a2∈[1，6]时，EFF、HVEA及ESACR算法的可靠性为100%；直到时间间隔为a5∈[1，12]时，MEMC的可靠性仍小于100%。从图2（b）可知，当可靠性达到100%的时候，ESACR的能耗最小，约为EFF的50%左右，且随着任务到达时间间隔变长，ESACR的相对能耗越小。
实验2 使用8个处理器，随机生成1000个任务，任务的到达时间间隔为a∈[1，5]的随机数，任务的计算量C分别为C1∈[9，39]，C2∈[12，42]，C3∈[15，45]，C4∈[18，48]，C5∈[21，51]的随机数，截止期限D为到达时间加4C。各算法的可靠性与能耗如图3所示。
任务到达时间间隔不同时，不同算法的可靠性与相对能耗相对能耗指什么？需明确说明，是否是指与EFF的比值？，若是，图中纵坐标改为“相对EFF能耗”因为EFF算法的能耗相对其他算法的能耗大一些，这里的归一化是用各个算法产生的能耗都单独除以EFF算法产生的能耗，则EFF算法的能耗变为1，其他算法的能耗则变为0-1之间的数值。
从图3（a）可知，当任务的计算量C4∈[18，48]之前时，EFF、HVEA及ESACR算法的可靠性均达到100%；当计算量变大时，四个算法的可靠性均小于100%。从图3（b）可知，可靠性能达到100%的三个算法中，ESACR算法的能耗最小，约为EFF的70%左右。
实验3 使用16个处理器，随机生成1000个任务，任务的到达时间间隔为a∈[1，5]的随机数，任务的计算量为C∈[5，100]的随机数，截止期限D分别为到达时间加2C4、6C、8C和10C2C、4C、6C、8C、10C。各算法的可靠性与能耗如图4所示。
从图4（a）可知，当截止期限小于到达时间加6C？6C时，四个算法的可靠性均小于100%；当截止期限为到达时间加6C时，EFF、HVEA及ESACR算法的可靠性达到100%，MEMC的可靠性则一直小于60%。从图4（b）可知，三个可靠性达到100%的算法中，ESACR算法的相对能耗最小，约为EFF的75%左右，且随着截止期限的放宽，ESACR算法的相对能耗有下降趋势。
实验4 分别使用6、8、10、12、14个处理器，随机生成1000个任务，任务的到达时间间隔为a∈[1，5]的随机数，任务的计算量为C∈[5，50]的随机数，截止期限D为到达时间加4C。各算法的可靠性与能耗如图5所示。
从图5（a）可知，当处理器数小于10时，四个算法的可靠性均小于100%；当处理器数达到10时，EFF、HVEA及ESACR算法的可靠性达到100%，MEMC的可靠性则一直小于80%。从图5（b）可知，三个可靠性达到100%的算法中，ESACR算法的相对能耗最小，平均约为EFF的70%左右，且随着处理器的增加有下降趋势。
通过以上4个实验可知，EFF、HVEA及ESACR算法的可靠性基本相同，但ESACR算法的相对能耗明显低于另外两个算法，MEMC算法虽然节能效果明显，但多数时候不能满足系统可靠性要求。
4 结语
可靠性与节能在很多系统中非常重要，针对多处理器系统中随机到达的任务，设计了可靠性约束下的节能调度算法，算法通过构造错误恢复时间以保证系统的可靠性，通过均衡单个处理器上任务的执行电压/频率以节能，实验结果表明本文算法在保证系统可靠性的前提下具有较好的节能效果。后续研究可以考虑任务调度过程中的通信能耗、存储器访问能耗等。
参考文献：
[1]WU X， HAN J， WANG T. Energyaware scheduling of hard realtime tasks in VFDbased multicore systems [J].Journal of Computer Research and Development， 2012， 49（5）：1018-1027.（吴小东，韩建军，王天江.一种基于VFD多核系统的硬实时任务节能调度算法[J].计算机研究与发展，2012，49（5）：1018-1027.）
[2]KAVOUSIANOS X， CHAKRABARTY K， JAIN A， et al. Test scheduling for multicore SoCs with dynamic voltage scaling and multiple voltage islands [C]// Proceedings of 2011 20th Asian Test Symposium. Piscataway： IEEE， 2011： 33-39.
[3]TOKARNIA A M， PEPE P C F， PAGOTTO L D. Pathbased dynamic voltage and frequency scaling algorithms for multiprocessor embedded applications with soft delay deadlines [C]// Proceedings of 2011 14th Euromicro Conference on Digital System Design. Piscataway： IEEE， 2011：109-116.
[4]ZHANG D， WU F， CHEN F，et al. An overheadaware optimal energyefficient realtime scheduling algorithm on multiprocessors [J]. Chinese Journal of Computers， 2012， 35（6）：1297-1312.（张冬松，吴飞，陈芳园，等.开销敏感的多处理器最优节能实时调度算法[J].计算机学报，2012，35（6）：1297-1312.）
[5]ZHU X， HE C， WANG J，et al. An elastic energyaware scheduling strategy for heterogeneous computing systems [J]. Chinese Journal of Computers， 2012， 35（6）：1313-1326.（朱晓敏，贺川，王建江，等.异构计算系统中弹性节能调度策略研究[J].计算机学报，2012，35（6）：1313-1326.）
[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.
[7]LEE W Y. Energyefficient scheduling of periodic realtime tasks on lightly loaded multicore processors [J]. IEEE Transactions on Parallel and Distribute Systems， 2012， 23（3）： 530-537.
[8]ZHU D， AYDIN H. Reliabilityaware energy management for periodic realtime tasks [J]. IEEE Transactions on Computers， 2009， 58（10）：1382-1397.
[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.
[10]HAQUE M A， AYDIN H， ZHU D. Energyaware task replication to manage reliability for periodic realtime applications on multicore platforms [C]// Proceedings of the 2013 International Green Computing Conference. Piscataway： IEEE， 2013： 1-11.
[11]LIN M， PAN Y，YANG L T， et al. Scheduling codesign for reliability and energy in cyberphysical systems [J]. IEEE Transactions on Emerging Topics in Computing， 2013，1（2）： 353-365.
[12]LI Z， WANG L， LI S， et al. Reliability guaranteed energyaware framebased task set execution strategy for hard realtime systems [J]. The Journal of Systems and Software， 2013， 86（12）： 3060-3070.
[13]LI J， SHU L C， CHEN J， et al. Energyefficient scheduling in nonpreemptive systems with realtime constraints [J]. IEEE Transactions on Systems， 2013， 43（2）： 332-344.
[14]ZHANG Y， CHAKRABARTY K. Energyaware adaptive checkpointing in embedded realtime systems [C] // DATE’03： Proceedings of the Design， Automation and Test in Europe Conference and Exhibition. Piscataway： IEEE， 2003： 918-923.