《多处理器系统在线节能调度算法》由会员分享，可在线阅读，更多相关《多处理器系统在线节能调度算法（12页珍藏版）》请在金锄头文库上搜索。
1、多处理器系统在线节能调度算法摘要：随着多处理器系统计算性能的提高，能耗 管理已变得越来越重要，如何满足实时约束并有效降低能耗 成为实时调度中的一个重要问题。基于多处理器计算系统， 针对随机到达的任务，提出一种在线节能调度算法(OLEAS)o 该算法在满足任务截止期限的前提下，尽量将任务调度到产 生能耗最少的处理器，当某个任务在所有处理器上都不能满 足截止期限要求时，则调整处理器之间的部分任务，使之尽 量满足截止期限要求。同时，OLEAS尽量使单个处理器上的 任务按平均电压/频率执行，以降低能耗，只有当新到任务 不满足截止期限要求时，才逐个调高前面任务的电压/频率。 模拟实验比较了 OLEAS、
2、最早完成时间优先(EFF)、最高电 压节能(HVEA)、最低电压节能(LVEA)、贪心最小能耗(MEG) 和最小能耗最小完成时间(MEMC)的性能，结果表明OLEAS 在满足任务截止期限和节省能耗方面具有明显的综合优势。关键词：多处理器系统；在线调度；动态电压调整；节 能0引言随着计算机硬件技术的快速发展，多处理器计算系统的 成本变得越来越低，同时其计算能力变得越来越强。但是， 处理器的高性能也会带来高能耗，能耗管理已成为多处理器 系统中的一个重要问题，对于电池供电的嵌入式系统尤其如 此。目前，已有许多处理器可在不同的电压模式下工作，如 Intel 公司的 Core2 Duo processo
3、r1, AMD 公司的 mobile Athlon2, ARM公司的ARM11 MPCore3等。在系统运行时, 通过动态调整电压以改变执行频率从而降低系统能耗，即为 动态电压频率调整（Dynamic Voltages Frequency Scaling, DVFS）技术。一般情况下，处理器产生的能耗包括动态能耗、 静态能耗和状态转换能耗。动态能耗通常是速度（频率）的 凸函数和递增函数，速度越高动态能耗越多；静态能耗是由 于泄露电流而产生的，状态转换能耗则是处理器关闭和唤醒 时产生的。以上三种能耗中，动态能耗和静态能耗是CMOS 处理器能耗的主要来源4。近年来，有许多学者研究了多处理器或多核系
4、统的节能 调度问题并已取得很多成果。多数情况下，多机节能调度问 题是NP难问题5,在实际中多采用启发式调度方法求近似 最优解。通常将调度算法分为两大类，即静态（离线）调度 和动态（在线）调度。在静态调度中，任务具有周期性特征, 且到达时间已知6；对于非周期到达的任务，通常采用动 态调度算法Zhu等7引入了多处理器系统中空闲时间共享 的概念来减少能量消耗，同时提出了两种基于空闲时间共享 的节能调度算法o Aydin等8提出一种周期性任务静态调度 算法，根据系统平均负载情况调节CPU运行速度并保证任务 在截止期限内完成。吴小东等9基于全局异步局域同步及 电压频率域技术的多核处理器计算平台，在静态策
5、略的基础 上提出空闲时间重分配策略。张冬松等10提出一种基于帧 任务模型的最优节能实时调度算法。Funaoka等11针对周 期性任务模型提出一种最优节能调度算法。文献12利用依 赖任务之间的松弛时间，调低处理器电压以节能。文献13 对周期性的实时任务采用调低电压或关闭处理器的方法节 能并证明在任务截止期限内使耗能最小的调度属于NP难问 题。以上研究在一定的条件下能起到很好的节能效果，但都 属于静态调度算法，不适合处理动态到达的任务。目前，已有很多学者对动态节能调度进行了研究，Zong 等14提出了两种节能复制调度算法，即节能复制算法和性能能量折中复制算法，用于提高系统性能并节约能量。文献15提
6、出一种弹性节能调度策略用于动态调度异构计算系统中非周期、独立任务；文献16提出了几种基于异构系统 的动态调度算法，如随机负载平衡(Opportunistic Load Balancing, 0LB)、贪心最小能耗(Minimum Energy Greedy, MEG)最小能耗最小完成时间(Minimum Energy Minimum Completion time, MEMC)等；文献17提出了一种多核系 统中基于Global EDF在线节能硬实时任务调度算法。这些 算法大都是将任务尽量调度到较低频率的处理器或采用降 频的方法减少动态功耗实现节能，通过关闭处理器的方法减 少静态能耗，但一般事先
7、知道任务的到达时间、周期和时限 等属性，在已知先验知识情况下考虑节能调度问题。而在很 多应用中无法事先获得任务属性，已有的一些算法不太合适 处理这类问题。文献17虽然也是针对动态到达的任务，但 需要假设任务集在可抢占的Global EDF调度算法中是可调 度的，对于负载较重的情况没有做过多的考虑；文献15则 没有将能耗降至更低。基于以上分析，本文提出一种在线节 能调度(OnLine EnergyAware Scheduling, OLEAS)算法， 针对随机到达的任务，在满足任务截止期限的前提下，将任 务调度到耗能最少的处理器实现有效节能，如果任务不能满 足截止期限要求，则对各处理器上的预分配
8、的任务进行调 整，使之尽量满足截止期限要求。1系统模型1.1处理器模型本文主要考虑具有独立DVFS的多处理器系统，假设多 处理器系统拥有m个处理器cpul, cpu2, cpu3,，cpum。 按文献10, 18所述，cpui以速度S运行的功耗函数表示为1.2任务模型1.4调度器模型设计算系统拥有m个处理器和1个调度器，调度器模型 如图1所示。用户随机提交任务后，调度器先获取任务的大 小和用户期望的截止期限，然后将该任务放入全局任务队 列，通过调度计算后再为该任务分配处理器。在调度器上建 立一张处理器状态及处理器上的任务信息表用于模拟和预 测处理器状态。在每个处理器上建立一个缓冲区，用于存放
9、即将要执行的部分任务。1.5问题定义给定一般的实时任务集T,包含n个任务，且随机到达。 给定一个由m个处理器组成的异构系统，任何一个任务可以 在任何一个处理器上执行。要求在最大限度满足用户期望的 前提下使系统消耗的能量最小化，即 2 OLEAS算法2. 1算法思想针对一般非周期实时任务集，当任务到达后，立即获取 任务的大小和截止期限，将任务放入全局任务缓冲区。遍历 处理器状态信息表，取任务在截止期限内执行的能耗最小的 处理器进行任务及处理器电压/频率的预分配。在计算某个 处理器上的能耗时，先计算处理器上还未执行任务的总计算 量和总可用时间，得到这些任务的平均电压/频率，然后逐 个考察任务，在截
10、止期限内尽量按平均电压/频率执行，如 果某个任务不能满足截止期限的要求才逐个调高前面未执 行任务的电压/频率。如果将所有处理器的电压/频率调至最 高，新到任务还不能在截止期限内完成，这时考虑在处理器 之间调整一些未执行的任务，使新任务尽量满足截止期限要 求。2.2算法描述根据2.1节所述算法思想，设计OLEAS调度策略如下。算法4通过模拟删除任务队列i中的一个比newtask小 的任务j,这时j有可能在其他处理器上满足截止期限要求, 同时newtask也可能在处理器i上满足截止期限要求。2.3算法分析定理1 OLEAS算法的最坏时间复杂度为0 (n3)。证明当一个任务到达后，OLEAS算法执行
11、 SimulateSchedule ()函数m次，设K为所有处理器上未完 成的任务数，ki为某个处理器上未完成的任务数，则 SimulateSchedule ()函数第1)行执行ki次，第2)3) 行执行ki次，第9)行执行ki次，虽然第12)行为wh订e 循环且该循环嵌套在for之内，但最多只执行ki次，第19) 行执行ki次，所以SimulateSchedule ()函数共执行5ki 次。因为共有m个处理器，有kl+k2+km=K,所以一个任 务到达后需执行5K次，最坏的情况下，当最后一个任务到 达时，所有任务都没有执行完，所需计算次数为5X (l+2+3+-+n),复杂度为0 (n2)0
12、如果调度不成功，需执 行 AdjustTaskForMinConsumption ()函数，该函数第 1) 2)行遍历所有任务执行K次，第4)行最多执行ki次，第 5)行执行5ki次，6)7)行执行mX5kj次，所以执行次 数为 K (ki+5ki+mX5kj) =K (6 ki+5K)从图 3 (a) 可以看出，EFF、HVEA和OLEAS三种算法完成的任务数基本 相同；MEMC和MEG完成的任务数也基本相同，但明显少于 EFF、HVEA和OLEAS； LVEA完成的任务数则显著少于前面五 个算法；当处理器数达到20时，EFF、HVEA和OLEAS基本上 能完成所有任务，而其他三种算法完成的
13、任务数最多都不到 80%；处理器数少于20时，所有算法都不能完成全部任务， 说明负载过重处理器资源不足，但OLEAS和EFF及HVEA完 成了几乎相同的任务，说明OLEAS提高了大多数任务的执行 电压/频率，另外三个算法则不会因为负载过重而升高尚未 执行的任务的电压，所以这三个算法的线型走势较平坦。再 看图3 (b), LVEA的能耗最低，但其完成的任务数相当少； OLEAS和HVEA的走势类似，OLEAS的能耗约为EFF的60%左 右，且始终低于HVEAo当处理器数达到20以后，OLEAS和 HVEA相对于EFF都有很好的节能效果，但OLEAS比HVEA节 能，因为这时OLEAS能降低更多任
14、务的电压以节能。实验三任务到达时间间隔不同的情况。产生1000个任 务，使用8个处理器，任务长度为20200的随机数，分别 设置前后两个任务到达时间间隔为15, 610, 1115, 1620, 2125, 2530的随机数，任务截止时限设为到达 时间加2倍任务长度。各算法产生的能耗及完成的任务数如 图4所示。从图4可以看出，和图3类似，EFF、HVEA及OLEAS完 成的任务数大致相同，但OLEAS最为节能，另外三个算法在 相同的情况下完成的任务数则明显少一些。实验四任务长度不同，截止期限不同的情况。产生1000 个任务，使用16个处理器，设置前后两个任务到达时间差 为1,任务长度为5100
15、的随机数，任务截止时限设为到达 时间分别加任务长度的18、20、22、24、26、28、30、32 倍。各算法产生的能耗及完成的任务数如图5所示。图片图4任务到达时间间隔不同时各算法的性能图片图5任务长度不同，截止期限不同时各算法的性能本组实验是在一段很短的时间内就知道了所有任务的 属性，在某种程度上具有静态调度的一些特征。从图5可以 看出，在任务完成数方面，OLEAS和HVEA的结果几乎相同， 且明显优于其他几个算法；在能耗方面，LVEA、MEG、MEMC 因有大量任务没有完成，所以能耗很少；EFF、HVEA、OLEAS 三个算法中，OLEAS能耗最少，特别在截止期限大于26倍任 务长度时，
16、OLEAS的能耗相对于另外两个算法有快速下降的 趋势。从以上四个实验可以看出，OLEAS在满足任务截止期限 方面的性能和EFF、HVEA相当，且远优于LVEA、MEG和MEMC0 在能耗方面，OLEAS则始终低于EFF和HVEA,特别当所有任 务在OLEAS下都能满足截止期限要求时，随着截止期限的放 宽，OLEAS相对于EFF、HVEA可节能40%以上。4结语本文针对具有独立DVFS的异构多处理器系统，提出一 种在线节能调度算法，在满足任务截止期限的前提下尽量将 任务调度到产生能耗最少的处理器上执行。该算法在考虑单 个处理器时则尽量均衡该处理器上各任务的执行电压/频率 以节能，当某个任务按此电压/频率不能在截止期限完成时, 则会逐个调高前面未开始执行的任务的电压/频率。如果某 个任务在所有处理器上都不能满足截止期限要求，
