多处理器系统的在线节能调度算法

摘 要：随着多处理器系统计算性能的提高，能耗管理已变得越来越重要，如何满足实时约束并有效降低能耗成为实时调度中的一个重要问题。基于多处理器计算系统，针对随机到达的任务，提出一种在线节能调度算法（OLEAS）。该算法在满足任务截止期限的前提下，尽量将任务调度到产生能耗最少的处理器，当某个任务在所有处理器上都不能满足截止期限要求时，则调整处理器之间的部分任务，使之尽量满足截止期限要求。同时，OLEAS尽量使单个处理器上的任务按平均电压/频率执行，以降低能耗，只有当新到任务不满足截止期限要求时，才逐个调高前面任务的电压/频率。模拟实验比较了OLEAS、最早完成时间优先（EFF）、最高电压节能（HVEA）、最低电压节能（LVEA）、贪心最小能耗（MEG）和最小能耗最小完成时间（MEMC）的性能，结果表明OLEAS在满足任务截止期限和节省能耗方面具有明显的综合优势。

关键词：多处理器系统；在线调度；动态电压调整；节能

0 引言

随着计算机硬件技术的快速发展，多处理器计算系统的成本变得越来越低，同时其计算能力变得越来越强。但是，处理器的高性能也会带来高能耗，能耗管理已成为多处理器系统中的一个重要问题，对于电池供电的嵌入式系统尤其如此。目前，已有许多处理器可在不同的电压模式下工作，如Intel公司的Core2 Duo processor[1]，AMD公司的mobile Athlon[2]，ARM公司的ARM11 MPCore[3]等。在系统运行时，通过动态调整电压以改变执行频率从而降低系统能耗，即为动态电压频率调整（Dynamic Voltages Frequency Scaling，DVFS）技术。一般情况下，处理器产生的能耗包括动态能耗、静态能耗和状态转换能耗。动态能耗通常是速度（频率）的凸函数和递增函数，速度越高动态能耗越多；静态能耗是由于泄露电流而产生的，状态转换能耗则是处理器关闭和唤醒时产生的。以上三种能耗中，动态能耗和静态能耗是CMOS处理器能耗的主要来源[4]。

近年来，有许多学者研究了多处理器或多核系统的节能调度问题并已取得很多成果。多数情况下，多机节能调度问题是NP难问题[5]，在实际中多采用启发式调度方法求近似最优解。通常将调度算法分为两大类，即静态（离线）调度和动态（在线）调度。在静态调度中，任务具有周期性特征，且到达时间已知[6]；对于非周期到达的任务，通常采用动态调度算法。Zhu等[7]引入了多处理器系统中空闲时间共享的概念来减少能量消耗，同时提出了两种基于空闲时间共享的节能调度算法。Aydin等[8]提出一种周期性任务静态调度算法，根据系统平均负载情况调节CPU运行速度并保证任务在截止期限内完成。吴小东等[9]基于全局异步局域同步及电压频率域技术的多核处理器计算平台，在静态策略的基础上提出空闲时间重分配策略。张冬松等[10]提出一种基于帧任务模型的最优节能实时调度算法。Funaoka等[11]针对周期性任务模型提出一种最优节能调度算法。文献[12]利用依赖任务之间的松弛时间，调低处理器电压以节能。文献[13]对周期性的实时任务采用调低电压或关闭处理器的方法节能并证明在任务截止期限内使耗能最小的调度属于NP难问题。以上研究在一定的条件下能起到很好的节能效果，但都属于静态调度算法，不适合处理动态到达的任务。

目前，已有很多学者对动态节能调度进行了研究，Zong 等[14]提出了两种节能复制调度算法，即节能复制算法和性能能量折中复制算法，用于提高系统性能并节约能量。文献[15]提出一种弹性节能调度策略用于动态调度异构计算系统中非周期、独立任务；文献[16]提出了几种基于异构系统的动态调度算法，如随机负载平衡（Opportunistic Load Balancing， OLB）、贪心最小能耗（Minimum Energy Greedy， MEG）、最小能耗最小完成时间（Minimum Energy Minimum Completion time， MEMC）等；文献[17]提出了一种多核系统中基于Global EDF在线节能硬实时任务调度算法。这些算法大都是将任务尽量调度到较低频率的处理器或采用降频的方法减少动态功耗实现节能，通过关闭处理器的方法减少静态能耗，但一般事先知道任务的到达时间、周期和时限等属性，在已知先验知识情况下考虑节能调度问题。而在很多应用中无法事先获得任务属性，已有的一些算法不太合适处理这类问题。文献[17]虽然也是针对动态到达的任务，但需要假设任务集在可抢占的Global EDF调度算法中是可调度的，对于负载较重的情况没有做过多的考虑；文献[15]则没有将能耗降至更低。基于以上分析，本文提出一种在线节能调度（OnLine EnergyAware Scheduling，OLEAS）算法，针对随机到达的任务，在满足任务截止期限的前提下，将任务调度到耗能最少的处理器实现有效节能，如果任务不能满足截止期限要求，则对各处理器上的预分配的任务进行调整，使之尽量满足截止期限要求。

1 系统模型

1.1 处理器模型

本文主要考虑具有独立DVFS的多处理器系统，假设多处理器系统拥有m个处理器{cpu1，cpu2，cpu3，…，cpum}。按文献[10，18]所述，cpui以速度S运行的功耗函数表示为

1.2 任务模型

1.4 调度器模型

设计算系统拥有m个处理器和1个调度器，调度器模型如图1所示。用户随机提交任务后，调度器先获取任务的大小和用户期望的截止期限，然后将该任务放入全局任务队列，通过调度计算后再为该任务分配处理器。在调度器上建立一张处理器状态及处理器上的任务信息表用于模拟和预测处理器状态。在每个处理器上建立一个缓冲区，用于存放即将要执行的部分任务。

1.5 问题定义

给定一般的实时任务集T，包含n个任务，且随机到达。给定一个由m个处理器组成的异构系统，任何一个任务可以在任何一个处理器上执行。要求在最大限度满足用户期望的前提下使系统消耗的能量最小化，即

2 OLEAS算法

2.1 算法思想

针对一般非周期实时任务集，当任务到达后，立即获取任务的大小和截止期限，将任务放入全局任务缓冲区。遍历处理器状态信息表，取任务在截止期限内执行的能耗最小的处理器进行任务及处理器电压/频率的预分配。在计算某个处理器上的能耗时，先计算处理器上还未执行任务的总计算量和总可用时间，得到这些任务的平均电压/频率，然后逐个考察任务，在截止期限内尽量按平均电压/频率执行，如果某个任务不能满足截止期限的要求才逐个调高前面未执行任务的电压/频率。如果将所有处理器的电压/频率调至最高，新到任务还不能在截止期限内完成，这时考虑在处理器之间调整一些未执行的任务，使新任务尽量满足截止期限要求。

2.2 算法描述

根据2.1节所述算法思想，设计OLEAS调度策略如下。

算法4通过模拟删除任务队列i中的一个比newtask小的任务j，这时j有可能在其他处理器上满足截止期限要求，同时newtask也可能在处理器i上满足截止期限要求。

2.3 算法分析

定理1 OLEAS算法的最坏时间复杂度为O（n3）。

证明 当一个任务到达后，OLEAS算法执行SimulateSchedule（）函数m次，设K为所有处理器上未完成的任务数，ki为某个处理器上未完成的任务数，则SimulateSchedule（）函数第1）行执行ki次，第2）～3）行执行ki次，第9）行执行ki次，虽然第12）行为while循环且该循环嵌套在for之内，但最多只执行ki次，第19）行执行ki次，所以SimulateSchedule（）函数共执行5ki次。因为共有m个处理器，有k1+k2+…+km=K，所以一个任务到达后需执行5K次，最坏的情况下，当最后一个任务到达时，所有任务都没有执行完，所需计算次数为5×（1+2+3+…+n），复杂度为O（n2）。如果调度不成功，需执行AdjustTaskForMinConsumption（）函数，该函数第1）～2）行遍历所有任务执行K次，第4）行最多执行ki次， 第5）行执行5ki次，6）～7）行执行m×5kj次，所以执行次数为K （ki+5ki+m×5kj）=K（6 ki+5K）

在实际情况中，由于任务随机到达，当后面的任务到达时，前面有些任务已经执行完了，所以一般情况下算法的复杂度小于O（n3），如果任务不需要在处理器之间调整，则算法复杂度小于O（n2）。

3 实验与分析

本章通过一些实验来验证OLEAS算法的性能，将其与非节能最早完成时间优先（Earliest Finish First， EFF）算法、最高电压节能（Highest Voltage EnergyAware， HVEA）算法[15]、最低电压节能（Lowest Voltage EnergyAware， LVEA）算法[15]、贪心最小能耗（MEG）算法[16]和最小能耗最小完成时间（MEMC）算法[16]进行比较。

3.1 实验参数

以Intel Xscale处理器为参考，处理器的功耗近似为P（S）=1.52S3+0.08W[10，18]。本文中为了体现各节点计算能力的异构性，用处理器编号作为随机数种子，随机产生α、β和Smax，并将其范围分别设定为1.2≤α≤1.7，0.06≤β≤0.1，0.8≤Smax≤1.6，Smin通过公式Smin=3β/2α计算得到。一段时间内任务到达的数量近似地服从泊松分布，任务的到达时间、计算长度、截止时限随机产生，并对计算长度和截止期限作如下约束，即如果所有处理器都空闲时，任何一个新到任务都可以在截止期限内完成。另外为了方便计算，实验中的时间取时间单位，能耗则用P（S）乘以时间单位表示。

3.2 实验及结果分析

为了从各个角度考察算法满足任务截至期限的能力和节能效果，本文分别模拟了不同任务长度、不同处理器数目、不同任务到达时间间隔、不同任务截至期限等情况下算法的执行情况。

实验一 任务长度不同的情况。使用4个处理器，产生1000个任务，设置前后两个任务到达时间差为1～20的随机数，任务长度分别为5～10，5～20，5～40，5～60，5～80，5～100的随机数，任务截止时限设为到达时间加2倍任务长度。为便于观察各种算法的差异，考察能耗时以EFF算法产生的能耗为参考作归一化处理，各算法产生的能耗及完成的任务数如图2所示。

图片

图2 任务长度不同时各算法的性能

从图2可以看出，OLEAS的能耗明显少于EFF和HVEA，但完成的任务数却和EFF及HVEA相差不大；MEG和MEMC产生的能耗和完成的任务数相差不大，但完成的任务数明显少于前三者。从图2（a）中看出LVEA完成任务的能力明显弱于其他五种算法，当任务长度取值为5～60后，其余五种算法所完成的任务数都开始急剧减少，说明任务的计算长度和截止期限的要求已经超过了系统所能承受的限度。在5～60之前OLEAS、EFF、HVEA能完成差不多的任务数，但OLEAS的平均能耗小于EFF的50%，同时也小于HVEA的60%。MEG和MEMC的能耗虽低一些，但所完成的任务数显著少于前面三种算法。

实验二 处理器数目不同的情况。分别使用4、8、12、16、20、24、28个处理器，产生1000个任务，设置前后两个任务到达时间差为1～5的随机数，任务长度为5～100的随机数，任务截止时限设为到达时间加2倍任务长度。各算法产生的能耗及完成的任务数如图3所示。

图片

图3 处理器数目不同时各算法的性能

从图3（a）可以看出， EFF、HVEA和OLEAS三种算法完成的任务数基本相同；MEMC和MEG完成的任务数也基本相同，但明显少于EFF、HVEA和OLEAS；LVEA完成的任务数则显著少于前面五个算法；当处理器数达到20时，EFF、HVEA和OLEAS基本上能完成所有任务，而其他三种算法完成的任务数最多都不到80%；处理器数少于20时，所有算法都不能完成全部任务，说明负载过重处理器资源不足，但OLEAS和EFF及HVEA完成了几乎相同的任务，说明OLEAS提高了大多数任务的执行电压/频率，另外三个算法则不会因为负载过重而升高尚未执行的任务的电压，所以这三个算法的线型走势较平坦。再看图3（b），LVEA的能耗最低，但其完成的任务数相当少； OLEAS和HVEA的走势类似，OLEAS的能耗约为EFF的60%左右，且始终低于HVEA。当处理器数达到20以后， OLEAS和HVEA相对于EFF都有很好的节能效果，但OLEAS比HVEA节能，因为这时OLEAS能降低更多任务的电压以节能。

实验三 任务到达时间间隔不同的情况。产生1000个任务，使用8个处理器，任务长度为20～200的随机数，分别设置前后两个任务到达时间间隔为1～5，6～10，11～15，16～20，21～25，25～30的随机数，任务截止时限设为到达时间加2倍任务长度。各算法产生的能耗及完成的任务数如图4所示。

从图4可以看出，和图3类似，EFF、HVEA及OLEAS完成的任务数大致相同，但OLEAS最为节能，另外三个算法在相同的情况下完成的任务数则明显少一些。

实验四 任务长度不同，截止期限不同的情况。产生1000个任务，使用16个处理器，设置前后两个任务到达时间差为1，任务长度为5～100的随机数，任务截止时限设为到达时间分别加任务长度的18、20、22、24、26、28、30、32倍。各算法产生的能耗及完成的任务数如图5所示。

图片

图4 任务到达时间间隔不同时各算法的性能

图片

图5 任务长度不同，截止期限不同时各算法的性能

本组实验是在一段很短的时间内就知道了所有任务的属性，在某种程度上具有静态调度的一些特征。从图5可以看出，在任务完成数方面，OLEAS和HVEA的结果几乎相同，且明显优于其他几个算法；在能耗方面，LVEA、MEG、MEMC因有大量任务没有完成，所以能耗很少；EFF、HVEA、OLEAS三个算法中，OLEAS能耗最少，特别在截止期限大于26倍任务长度时， OLEAS的能耗相对于另外两个算法有快速下降的趋势。

从以上四个实验可以看出，OLEAS在满足任务截止期限方面的性能和EFF、HVEA相当，且远优于LVEA、MEG和MEMC。在能耗方面，OLEAS则始终低于EFF和HVEA，特别当所有任务在OLEAS下都能满足截止期限要求时，随着截止期限的放宽，OLEAS相对于EFF、HVEA可节能40%以上。

4 结语

本文针对具有独立DVFS的异构多处理器系统，提出一种在线节能调度算法，在满足任务截止期限的前提下尽量将任务调度到产生能耗最少的处理器上执行。该算法在考虑单个处理器时则尽量均衡该处理器上各任务的执行电压/频率以节能，当某个任务按此电压/频率不能在截止期限完成时，则会逐个调高前面未开始执行的任务的电压/频率。如果某个任务在所有处理器上都不能满足截止期限要求，算法还会将部分任务在处理器之间进行调整，使更多的任务在截止期限内完成。最后进行了大量实验，结果表明本文算法具有明显的综合优势。

参考文献：

[1] Intel. Technology brief： Balancing performance and power consumption[EB/OL].[20121120]. http：///embedded/322286.pdf#iid=2399.

[2] AMD Corporation. Mobile AMD Athlon 4 processor model 6 CPGA data sheet[EB/OL].[20121120]. http：//shirase.tk/pc/24319.pdf.

[3] ARM Corporation. The architecture for the digital world ARM11MPCore[EB/OL].[20121120]. http：///zh/products/processors/classic/arm11/arm11mpcore.php.

[4] JEJURIKAR R， PEREIRA C， GUPTA R. Leakage aware dynamic voltage scaling for realtime embedded systems[C]// Proceedings of the 41st Annual Design Automation Conference. New York： ACM， 2004：275-280.

[5] YANG C Y， CHERT J J， KUO T W. An approximation algorithm for energyefficient scheduling on a chip multipmcessor[C]// Proceedings of the Design， Automation and Test in Europe Conference and Exhibition. Piscataway： IEEE， 2005：468-473.

[6] KWOK Y K， AHMAD I. Static scheduling algorithms for allocating directed task graphs to multiprocessors[J]. ACM Computing Surveys，1999，31（4）：406-471.

[7] ZHU D， MELHEM R， CHILDERS B R. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor realtime systems[J]. IEEE Transactions on Parallel and Distributed Systems，2003，14（7）：686-700.

[8] AYDIN H， MELHEM R， MOSSE D， et al. Poweraware scheduling for periodic realtime tasks[J]. IEEE Transactions on Computers，2004，53（5）：584-600.

[9] 吴小东，韩建军，王天江.一种基于VFD多核系统的硬实时任务节能调度算法[J].计算机研究与发展，2012，49（5）：1018-1027.

[10] 张冬松，吴飞，陈芳园，等.开销敏感的多处理器最优节能实时调度算法[J].计算机学报，2012，35（6）：1297-1312.

[11] FUNAOKA K， KATO S， YAMASAKI N. Energyefficient optimal realtime scheduling on multiprocessors[C]// Proceedings of the 11th IEEE Symposium on Object Oriented Realtime Distributed Computing. Washington， DC： IEEE Computer Society， 2008：23-30.

[12] LIU W， YIN H， DU W. Dynamic thresholdbased energy efficient scheduling algorithm for parallel tasks on homogeneous DVSenabled clusters[C]// Proceedings of the 2011 International Conference on CyberEnabled Distributed Computing and Knowledge Discovery. Washington， DC： IEEE Computer Society， 2011：321-328.

[13] LEE W Y. Energyefficient scheduling of periodic realtime tasks on lightly loaded multicore processors[J]. IEEE Transactions on Parallel and Distributed Systems， 2012，23（3）：530-537.

[14] ZONG Z L， MANZANARES A， RUAN X J，et al. EAD and PEBD：Two energyaware duplication scheduling algorithms for parallel tasks on homogeneous clusters[J]. IEEE Transactions on Computers，2011，60（3）：360-374.

[15] 朱晓敏，贺川，王建江，等.异构计算系统中弹性节能调度策略研究[J].计算机学报，2012，35（6）：1313-1326.

[16] 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.

[17] 张冬松，吴彤，陈芳园，等.多核系统中基于Global EDF的在线节能实时调度算法[J].软件学报，2012，23（4）：996-1009.

[18] ZHU D. Reliabilityaware dynamic energy management in dependable embedded realtime systems[C]// Proceedings of the 12th IEEE Realtime and Embedded Technology and Applications Symposium. Piscataway： IEEE， 2006：397-407.