一种在线节能实时调度算法

张彬连,徐洪智,2

(1.吉首大学软件服务外包学院,湖南张家界427000;2.湖南大学嵌入式系统及网络实验室,长沙410082)

一种在线节能实时调度算法

张彬连1,徐洪智1,2

(1.吉首大学软件服务外包学院,湖南张家界427000;2.湖南大学嵌入式系统及网络实验室,长沙410082)

随着多处理器系统规模的不断扩大,如何节能成为一个亟待解决的重要问题。为此,基于多处理器系统提出一种针对随机任务的在线节能实时调度算法。使用统计方法,根据已有任务的到达时间和计算量估计新任务在空闲处理器上执行的电压/频率,使还未到达的任务能够满足截止期限并有效节能。在考虑单个处理器上执行的任务时,计算执行这些任务所需的平均电压/频率,使所有任务的执行速度尽量均衡,当某些任务不能满足截止期限要求时,则调高未执行任务的电压/频率。实验结果表明,与EDF,HVEA,MEG和ME-MC算法相比,该算法在满足截止期限和节能方面具有明显的优势。

多处理器系统;随机任务;动态电压/频率调整;在线;实时;节能调度

1 概述

随着电子技术和计算机硬件技术的飞速发展,多处理器计算系统在成本和体积迅速下降的同时计算能力大幅提升,已被广泛用于计算密集型和数据密集型应用[1]。同时,高性能经常会产生高能耗,大规模多处理器计算系统消耗的能量巨大。据统计,目前计算中心服务器消耗的能量大约占全球电力总消耗的0.5%,如果照此速度发展,预计到2020年,其能量消耗将翻番[2]。在全球70%的计算中心中,能耗开销已成为第二大运营开销[3],高性能计算系统生命周期内维持正常运行所需的电力成本已经超出了系统的硬件成本[4]。为了降低系统的能耗,有许多处理器能在不同电压模式下工作,系统运行时,可动态调整电压以改变执行频率从而降低能耗。一般情况下,处理器产生的能耗包括动态能耗、静态能耗和状态转换能耗,其中动态能耗和静态能耗是CMOS处理器能耗的主要来源[5]。

近年来,有许多学者研究了节能调度问题。文献[6]基于同构集群系统采用任务复制算法减少调度长度和通信能耗,利用任务依赖之间的松弛时间,调低处理器电压以节能。文献[7]讨论了开销敏感的多处理器最优节能实时调度,根据关键速度判断系统负载情况,确定具有最低能耗值的活跃处理器个数,然后根据状态切换开销来确定最优调度序列。文献[8]针对周期性任务模型提出一种最优节能调度算法。文献[9]研究了周期性实时任务的节能调度,通过调低电压或关闭很少使用的处理器以节能,证明了在任务截止期限内使耗能最小的调度属于NP-hard问题。文献[10]提出一种同构动态电压调整(Dynamic Voltage Scaling,DVS)集群中基于自适应阈值的并行任务节能调度算法,利用任务之间的空闲时间降低处理器电压以节省能耗。以上方法在一定的条件下具有很好的节能效果,但都属于静态调度,不适合处理动态到达的任务。也有一些学者研究了动态节能调度,如文献[11]针对异构计算系统中非周期、独立任务提出一种弹性节能调度策略(EEAS),根据系统负载情况在系统节能与用户期望之间进行权衡。文献[12-13]提出了一种多核系统中基于Global EDF在线节能硬实时任务调度算法,通过引入调速因子,利用任务之间的松弛时间,结合动态电压频率调整技术,降低多核系统中任务执行速度,达到满足任务约束与节能能耗的合理折衷。文献[14]基于异构系统提出了多种动态节能调度算法:ME-MC,MEG等。文献[15]提出一种在线节能调度算法,尽量将任务调度到产生能耗最少的处理器。这些算法大都事先获取了任务的到达时间、截止期限、周期等相关属性,而现实中有些应用任务是随机到达的,很难事先获取任务的相关属性,导致现有的一些算法不太适合处理这类问题,文献[12]虽然是基于随机到达的任务,但没有考虑处理器负载较重的情况。文献[15]则没有考虑如何使更多的任务满足截止期限要求。

本文基于多处理器系统,针对随机到达的任务提出一种在线节能实时调度算法(On-line Energyefficient Real-time Scheduling Algorithm,OERSA),在满足任务截止期限的条件下实现节能。

2 系统功耗模型与问题定义

2.1 处理器功耗

根据文献[7,16]可知,处理器以速度S运行的功耗函数可表示为P(S)=αS3+β,其中,α＞0,β≥0。设处理器的速度可连续调节[17],其速度范围为[Smin,Smax],令k(k≤1)为调速因子,在t时刻处理器的频率记为kSmax,若在一段时间[t1,t2]内k保持不变,则处理器在这段时间内的功耗为:

根据功耗函数P(S)=αS3+β,某处理器以速度S执行一个单位时间的能耗为P(S)/S=αS2+β/ S[13],对P(S)/S求一阶导数得2αS-β/S2,令2αS-β/S2=0,可求出该处理器耗能最小的运行速度。所以,某一处理器处在一段时间内运行的功耗函数可表示为:

2.2 问题定义

考虑相互独立且随机到达的任务集T={t1,t2,…,tn},任务ti用三元组{ai,li,di}表示,其中,ai,li,di分别表示ti的到达时间、计算长度和截止期限。当ti到达后,即能获取该三元组的信息。如果任务ti的实际完成时间fi≤di,则称ti满足截止期限要求。调度问题的定义是给出一个由m个处理器构成的计算系统和任务集T,将任务调度到这些处理器上执行,使满足截至期限的任务数最大化并使能耗最小化。

3 OERSA算法

3.1 算法设计思想

针对随机到达的实时任务集,当一个任务到达后,立即获取它的大小和截止期限,在任务满足截止期限的条件下,查找所有可用处理器,将任务分配到预计系统总能耗最小的处理器上。由于系统中处理器的数目可能比较多,当把某个任务分配到空闲的处理器时,由于后面的任务在什么时候到达,计算量有多大是未知的,这个任务如果用最大速度执行,则可能会增加不必要的能耗,如果用一个较小的速度执行则可能会占用过多处理器的时间导致后面到达的任务不能满足截止期限要求,本文采用统计的方法根据已到达任务的大小和单位时间内的到达率估计该处理器运行的电压/频率。算法在考虑单个处理器上执行的任务时,先计算执行这些任务所需的平均电压/频率,使所有任务的执行速度尽量均衡,当某些任务不能满足截止期限要求时,则调高前面未执行任务的电压/频率。

3.2 算法描述

根据3.1节所述思想,设计OERSA调度如算法1所示。

算法1OERSA调度算法

输入任务t

输出将任务t调度到系统总能耗最小的处理器

当一个新的任务t到达后,记录前面所有已到达任务的总计算长度和总可用时间,按算法2寻找一个预计系统总能耗最小的处理器分配该任务。

算法2SearchMinEnergy(machineList,Task)

输入任务t

输出在满足任务t截止期限的要求下,将t调度到预计系统总能耗最小的处理器,并设置处理器的电压/频率,返回处理器的编号,如果任务在任何一个处理器上执行都不能满足截止期限要求,则返回0

算法2搜寻预计系统总能耗最小的cpuNo,本算法中将任务t调度到某个处理器上产生的能耗见算法3。

算法3Schedule(t,tasklistOnMachine)

输入任务t以及某个处理器上的任务列表tasklistOnMachine

输出如果任务t满足截止期限,则返回调度该任务后系统预计增加的能耗,否则返回+∞

重新计算tasklistOnMachine中所有任务执行的能耗和时间,return任务t加入tasklistOnMachine后增加的能耗。

如果处理器空闲,算法3根据当前任务和先前已到达的任务以及系统处理器数确定当前处理器的执行电压/频率(见算法4),否则尽量将单个处理器上的任务按平均电压/频率执行。

算法4EstimateSpeed(t);

输入任务t

输出处理器的执行速度

3.3 算法分析

定理1在同一个处理器上以不同速度s执行不同的任务,将其速度设置为总运算量/总运算时间后能节省能耗。

证明:先证明2个任务的情况,设任务task1以速度S1执行的时间为T1,任务task2以速度S2执行的时间为T2,S1≠S2,按这种方式执行的总能耗为:

将速度设置为总运算量/总运算时间:

以此速度执行在T1+T2时间段内仍然能完成原任务的计算,此时的能耗为:

设:

则只要证明E＞0即可,因为α＞0,本文只要考虑大括号内的项:

因为S1＞0,S2＞0且S1≠S2,所以(S2-S1)2＞0且(S1-S2)2＞0,故E1-E2＞0,2个任务的情况成立。

因为这2个任务的执行速度相同,所以本文将这2个任务看成一个任务,然后再与第3个任务按平均速度执行,以此类推,能证明定理1成立。

定理2OERSA算法的时间复杂度为O(n2)。

证明:n个任务需要执行,算法1执行n次,因为除cpuNo=SearchMinEnergy(machineList,t)这行外,其他行的时间复杂度为O(1),该行的SearchMinEnergy()函数需要执行n次,即算法2需要执行n次。执行一次算法2时,Schedule()函数需要执行m次,而Schedule()函数执行时要遍历一个处理器上的任务3次(计算mTime和mTasklLength 1次,for循环调整电压1次,最后2行语句执行1次),系统中共有m个处理器,将每个处理器上的任务遍历3次,实际上就是将系统中未执行完的任务遍历3次,系统中未执行完的任务最多为n个。所以OERSA算法的时间复杂度为O(n2)。

4 实验与结果分析

为了验证本文算法的有效性,将OERSA算法与EDF(Earliest Deadline First),HVEA(Highest Voltage Energy-aware)[11],ME-MC(MinimumEnergy Minimum Completion Time)[14],MEG(Minimum Energy Greedy)[14]算法进行比较。实验时,以Intel Xscale处理器为参考,其功耗近似为P(S)= 1.52S3+0.08W[7,16]。为了体现各处理器之间的差异,算法随机生成α,β和MaxSpeed,并分别设定其范围:1.1＜α＜1.8,0.05＜β＜0.11,0.8 GHz＜MaxSpeed＜1.8 GHz。为方便计算,实验中的能耗用P(S)乘以时间单位表示。

实验1轻量负载情形。使用3个处理器,随机产生100个任务,前后2个任务到达的时间差为1～ 10之间的随机数,任务长度为1～10之间的随机数,截止期限为任务到达时间加2倍任务长度,各处理器信息及其调度结果如表1和表2所示。

表1 处理器信息

表2 100个任务的调度结果

从表1可以看出,处理器1最快,处理器2最慢,而处理器2的β相对较小,处理器1的α相对较小。从表2中的处理器上任务数和能耗可以看出,在任务满足截至期限的条件下,OERSA算法的能耗最小。MEG和ME-MC算法总是试图将当前任务的电压/频率降至最低以节省能耗,导致有些任务的执行时间过长,使后面的任务不能满足截止期限的要求。

实验2任务长度变化的情形。使用16个处理器,随机产生1000个任务,任务长度分别为1～10, 1～15,1～20,1～25,1～30,1～35之间的随机数,前后2个任务到达的时间差为1～10之间的随机数,截止期限为任务到达时间加2倍任务长度。为便于观察实验结果,各算法产生的能耗以EDF算法为参考进行归一化处理,结果如图1所示。可以看出, EDF,HVEA和OERSA 3个算法在满足任务截止期限的性能方面基本相同,当任务长度都小于30时,它们能使所有任务都满足截止期限要求,但OERSA算法的能耗最小,该算法相对于EDF平均可节省超过40%的能耗。MEG和ME-MC算法的能耗虽然小于OERSA算法,但满足任务截止期限的性能明显不如OERSA算法。

图1 任务长度变化时各算法的性能比较

实验3处理器数目变化的情形。随机产生1000个任务,任务长度为1～100之间的随机数,前后两个任务到达的时间差为1～5之间的随机数,截止期限为任务到达时间加2倍任务长度,处理器数目分别为8,12,16,20,24,28,各算法的结果如图2所示。从图2可知,当处理器数目大于20时,EDF、HVEA和OERSA 3个算法基本能使所有任务满足截止期限要求,但OERSA算法的能耗最小,且随着处理器数目的增多,OERSA算法的相对能耗越来越小。当处理器数目达到28时,MEG和ME-MC算法仍有约10%的任务不能满足截止期限要求。

图2 处理器数目变化时各算法的性能比较

实验4任务到达时间间隔变化的情形。使用16个处理器,随机产生1000个任务,任务长度为1～500之间的随机数,前后2个任务到达的时间间隔分别为1～8,9～16,17～24,25～32,33～40,41～48的随机数,截止期限为任务到达时间加2倍任务长度,各算法的结果如图3所示。从图3可知,当前后2个任务到达的时间间隔达到17～24区间时, EDF,HVEA和OERSA 3个算法完成了所有的任务,但OERSA算法的能耗最小。当时间间隔达到33～40区间时,5个算法都完成了任务,且随着任务到达时间间隔的放宽,OERSA算法的能耗趋向于MEG算法,说明OERSA算法基本上将所有任务的执行电压/频率都调至最低,这时OERSA算法实际上已退化为MEG算法。

图3 任务到达时间间隔变化时各算法的性能比较

从上述实验可以看出,OERSA算法在满足任务截止期限方面的性能和EDF,HVEA算法基本相同,明显优于MEG和ME-MC算法,而OERSA算法的能耗始终低于EDF和HVEA算法。

5 结束语

为降低多处理器系统的能耗,本文针对随机到达的任务提出一种在线节能实时调度算法,使用统计的方法估算新任务在空闲处理器上执行的电压/频率,使还未到达的任务能够满足截止期限并有效节能,同时该算法使单个处理器上任务的执行电压/频率尽量均衡以实现节能。实验对比结果表明,与传统算法相比,本文算法在满足任务截止期限和节省能耗方面具有明显的优势。下一步将研究多处理器系统中随机任务的可靠性约束与节能调度。

[1] Goller A,LeberlF.RadarImageProcessingwith Clusters of Computers[J].IEEE Aerospace and Electronics Systems Magazine,2009,24(1):18-22.

[2] 林 闯,田 源,姚 敏.绿色网络和绿色评价:节能机制、模型和评价[J].计算机学报,2011,34(4): 593-612.

[3] Li Yu,Liu Yi,Qian Depei.An Energy-aware Heuristic Scheduling Algorithm for Heterogeneous Clusters[C]// Proceedings of the15th International Conference on Parallel and Distributed Systems.[S.l.]:IEEE Press, 2009:407-413.

[4] 过敏意.绿色计算:内涵及趋势[J].计算机工程, 2010,36(10):1-7.

[5] Jejurikar R,PereiraC,GuptaR.LeakageAware Dynamic VoltageScalingforReal-timeEmbedded Systems[C]//Proceedings of the 41st Annual Design Automation Conference.San Diego,USA:ACM Press, 2004:275-280.

[6] Liu Wei,Yin Hang,Du Wei.Dynamic Threshold-based Energy Efficient SchedulingAlgorithmfor Parallel Tasks on Homogeneous DVS-enabled Clusters[C]// Proceedings of 2011International Conference on CyberenabledDistributedComputingandKnowledge Discovery.Washington D.C.,USA:IEEE Press,2011: 321-328.

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

[8] Funaoka K,Kato S,Yamasaki N.Energy-efficient Optimal Real-time Scheduling on Multiprocessors[C]//Proceedings of the11th IEEE Symposium on Object Oriented Realtime Distributed Computing.Washington D.C.,USA: IEEE Press,2008:23-30.

[9] Lee W Y.Energy-efficient Scheduling of Periodic RealtimeTasksonLightlyLoadedMulticoreProcessors[J].IEEETransactionsonParalleland Distributed Systems,2012,23(3):530-537.

[10] 刘 伟,尹 行,段玉光,等.同构DVS集群中基于自适应阈值的并行任务节能调度算法[J].计算机学报, 2013,36(2):393-407.

[11] 朱晓敏,贺 川,王建江,等.异构计算系统中弹性节能调度策略研究[J].计算机学报,2012,35(6): 1313-1326.

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

[13] 张冬松.多核多处理器系统的节能实时调度技术研究[D].长沙:国防科学技术大学,2012.

[14] Kim J K,Siegel H J,Maciejewski A A,et al.Dynamic ResourceManagementinEnergyConstrained HeterogeneousComputingSystemsUsingVoltage Scaling[J].IEEE Transactions on Parallel and Distributed Systems,2008,19(11):1445-1457.

[15] 张彬连,徐洪智.多处理器系统的在线节能调度算法[J].计算机应用,2013,33(10):2787-2791.

[16] Zhu Dakai.Reliability-aware Dynamic Energy Management inDependableEmbeddedReal-timeSystems[C]// ProceedingsofIEEEReal-timeandEmbedded Technology and Applications Symposium.San Jose, USA:IEEE Press,2006:397-407.

[17] Li Jianjun,Shu L,Chen Jianjia,et al.Energy-efficient Scheduling in Nonpreemptive Systems with Real-time Constraints[J].IEEE Transactions on Systems,2013, 43(2):332-344.

编辑 金胡考

An On-line Energy-efficient Real-time Scheduling Algorithm

ZHANG Binlian1,XU Hongzhi1,2
(1.School of Software and Service Outsourcing,Jishou University,Zhangjiajie 427000,China; 2.Laboratory of Embedded Systems&Networking,Hunan University,Changsha 410082,China)

With the continuous expansion of the scale of the multi processor system,the issue of energy consumption becomes more and more important.How to save energy becomes an important problem to be solved.Based on the multiprocessor system,On-line Energy-efficient Real-time Scheduling Algorithm(OERSA)aiming at a random task is proposed.According to the arrival time and calculated amount of the existing task,the algorithm estimates the executive voltage/frequency of the new task in the idle processor by using statistical methods,which can meet the deadline and save the energy effectively for not yet arrived tasks.At the same time,considering the task executed on a single processor,the algorithm first calculates the average voltage/frequency required to perform these tasks,thus making all the task execution speed equal as much as possible.When some tasks can not meet the deadline requirements,voltage/frequency for previous not executed tasks will be adjusted high.Experimental results show that OERSA has obvious advantages in the aspect of meeting deadlines and energy consumption saving compared with EDF,HVEA,MEG and ME-MC algorithm.

multiprocessor system;random task;dynamic voltage/frequency scaling;on-line;real-time;energy-efficient scheduling

张彬连,徐洪智.一种在线节能实时调度算法[J].计算机工程,2015,41(2):41-46.

英文引用格式:Zhang Binlian,Xu Hongzhi.An On-line Energy-efficient Real-time Scheduling Algorithm[J].Computer Engineering,2015,41(2):41-46.

1000-3428(2015)02-0041-06

:A

:TP316.4

10.3969/j.issn.1000-3428.2015.02.009

湖南省科技计划基金资助项目(2012GK2006)。

张彬连(1978-),女,讲师、硕士,主研方向:分布式系统,任务调度算法;徐洪智,副教授、博士研究生。

2014-03-07

:2014-05-06E-mail:zhangbinlian@163.com