嵌入式多核多任务实时DVFS调度方法仿真

王晓莹,张仲雯,何海生

(桂林电子科技大学计算机工程学院,广西 北海 536000)

1 引言

近年来,嵌入式设备在其它技术的扶持下取得了突飞猛进的发展,多核处理器系统也因低成本、高速率等优势在嵌入式设备中被广泛应用。在对多核处理器研究过程中,任务调度是一个十分重要的内容,一个优秀的任务调度方法可以最大限度的发挥嵌入式设备性能,同时保证最低的能耗。人们对多媒体应用程序的需求越来越高,传统单核单任务调度的方式已经很难满足复杂的编解码处理程序。因此,多核多任务调度方式应时而生,将数字信号处理器引入到传统微处理器中协同操作,在提高调度效率的同时有效降低计算量。但是,由于处理器数量的增多,系统的能耗也随之增大,对于嵌入式设备来说,在调度过程中要格外关注能耗变化情况。

针对该问题,梁秋玲等人[1]利用并行感知调度算法实现对多核系统的任务调度。计算任务点到终点的最大路径,并按递减的顺序排序,从而决定任务的调度顺序;在多核系统中,充分考虑了任务的相关性和最早可执行时间,凭借构造的优化匹配评估函数,完成多核任务的调度。陈莹等人[2]提出基于可靠性的多核系统任务调度方法。对所有应用程序任务有向无环图建模分析,获得了任务执行效率、任务依赖性和任务通信量。采用聚类多数投票的方法,研究投票并行性和纯再执行序列化之间的关系。采用硬实时应用任务映射方法,以最小化通信代价和任务图副本实例最小化为目标,获得可靠度阈值,实现对多核系统的任务调度。由于上述两种方法实现过程较为繁杂,导致最终的调度效率低。

基于此,引入实时DVFS算法,通过分析处理器的实时负载情况,动态调节电压、频率,达到降低能耗、提高嵌入式设备工作效率的目的。结果验证所提方法可在花费最少时间的前提下完成高效率地调度。

2 DVFS算法描述

DVFS[3]是一种动态的、先进的设备能耗分析管理算法,通过分析处理器当前负载是否处于理想范围内,来调整电压和频率,达到降低设备功耗的目的。一般情况下,互补金属氧化物半导体(CMOS)具有相当大规模的数据群体,分布在集成电路中。计算集成电路上的总能耗为:

E=CeffV2fclkT

(1)

式中,Ceff表示有效切换电容,V表示设备当前电压,fclk表示时钟频率,T表示总的运行时间。

(2)

(3)

通过上述分析可以看出,在理想状态下CPU的功耗可以节省75%左右,并且对执行任务效率不产生任何影响。

3 嵌入式多核多任务能耗模型

嵌入式多核多任务能耗模型主要通过以下定义分析:

定义1:假设嵌入式设备的处理器只存在运行和休眠两种状态,当片上多核处理器存在n个同构核[5],计算处理器核corei在频率为p时的运行功耗Ei(p)为:

Ei(p)=Es+λ(Eind+Ed)=Es+λ(Eind+Cefpm)

(4)

式中,Es表示休眠状态处理器所产生的能耗值;Eind、Ed分别表示频率无关功率、频率相关功率;Cef表示开关电容处于有效状态下;m表示处理器功率指数,是一个常数项,且m≥2;λ表示多核处理器当前状态。当λ=0时,处理器为休眠状态;当λ=1时,处理器处于运行状态。

(5)

定义2:基于实时DVFS算法的嵌入式设备多核处理器,可以通过调节每个核的运行频率达到降低功率的目的,运行频率的调节要遵循设备相关标准,保证在[pmin,pmax]区间内,将θi定义为corei在t时刻下的频率调节系数,pi=θipmax。那么,具有n个核的多核处理器的运行总功耗为:

(6)

定义3:在单位时钟频率下,将n个核的多核处理器的功耗定义为En,最小功耗为Enmin。

(7)

(8)

定义4:当T=t2-t1时,具有n个核的多核处理器功耗为E(T),该值与时间和频率调节系数有着直接关系,且满足式(9)条件:

λCef(θipmax)m-1]}dt

(9)

4 嵌入式多核多任务调度实现

4.1 多核多任务调度数学模型

在嵌入式多核处理器中,每个计算节点都是同构的,给出了数学模型构建条件为:

条件1:将一个调度任务分割成k个子任务G={g1,g2,…,gk},任务与任务之间存在一定的约束条件。

条件3:预估执行子任务所需的时间用一维向量RG={RG1,RG2,…,RGk}来表示,其中,RGk表示执行子任务Gk的预估时间。

条件4:处理器核、通信延迟[8-9]、多任务调度时延以及调度任务量Comuab之间成正比,所有子任务之间的调度任务量可构成一个二维数组Comum×n。

条件5:给出一个二维数组Sche={σabd∈{1,0}|d∈[1,n]},σabd=1表示调度任务Gk在处理器核Lab上的执行集合,PreGk集合表示任务Gk的所有前驱任务[10-12]。

条件6:任务Gk的初始时间设定为begin[k],完成时间为finish[k],那么可得:

(1-σabd)Comuab}finish[k]=RGk+begin[k]

(10)

多核CPU多任务调度的目的就是在策略集合SI中找到合适的调度策略SI′,使T的值始终保持在最小值。综上所述,嵌入式多核多任务调度数据模型为:

(11)

4.2 多核多任务调度实现

嵌入式多核CPU的利用率,会随着CPU负载的变化而发生改变。CPU一般情况下不会满负载运行,所以需要计算其实际负载情况,为了降低能耗,把任务分配到一个低负荷的处理器中,让其它相对高负荷的处理器处于睡眠状态。为了更加具体地描述算法,给出以下几点假设:

假设1:由上文分析可知,能耗是嵌入式设备在一段时间内产生的能耗,主要影响因素为时间和功耗。

假设2:功耗代表了一段时间内的能量消耗情况,描述的是CPU的能量消耗速率。在时间段Δt内,平均功耗为:

Eavg=ΔE/Δt

(12)

瞬时功耗表示Δt接近0时的平均功耗,计算公式为:

(13)

假设3:E集合了处理器各部分能耗之和,计算公式整理后为:

E=Ecpu+Ememory+Eio+Eother

(14)

其中各部分能耗计算公式为:

Ecpu=∂1Etotal,0.46∂10.50

Ememory=∂2Etotal,0.08∂20.10

Eio=∂3Etotal,0.32∂30.41

Eother=∂4Etotal,0.08∂40.10

(15)

其中,∂1、∂2、∂3、∂4分别表示处理器各部分的能耗系数。

假设4:处理核负载(Loadsystem)指的是在一段时间内,处理核执行调度任务时工作流指令数[13]与嵌入式设备执行指令数之间的比率,计算公式为:

(16)

式中,Instructionsload表示执行调度任务时的指令数,Instructionsidle表示运行空闲指令数。

假设5:处理核潜在处理能力(Loadpotential)在正常状态下为1,在休眠状态下为0。

假设6:嵌入式设备预期负载[14]Loadexp ect指的是在参考了处理核平均负载Loadavg和单位时间内运行负载Loadcurrent情况,对未来一段时间内可能产生的负载预估的结果:

Loadexp ect=π×Loadavg+ϑ×Loadcurrent

(17)

式中,π、ϑ分别表示Loadavg和Loadcurrent对Loadexp ect的影响权值[15],π+ϑ=1。

嵌入式设备会根据式(16)计算每个处理核的潜在负载处理能力,并且利用式(17)预测将来一段时间内可能产生的负载。在新的调度工作准备好后,设备确定是否有处于睡眠状态下的处理核,若有,则遍历所有的处理核;若无,则表示目前的设备负荷很大,应该根据公平调度的原则合理安排。根据各处理器的潜在负载处理能力,寻找最接近于期望负荷的处理器核,并将其分配给处理核。当没有一个处理核具备适当的负载处理能力时,它就会唤醒睡眠中的处理器,并把任务分配到处理器上。当调度任务完成后,如果该处理核没有其它任务,则直接进入休眠状态;如果有,找到与其负载情况接近的处理核,并将任务调度到该处理核中,从而完成嵌入式设备多核多任务调度。

5 实验分析

5.1 实验环境

所提算法的主要目的是在嵌入式多核处理器中,保证最低能耗的前提下实现多任务调度。为了凸显实验结果的真实性,将所提方法与并行感知调度算法、可靠性任务调度算法对比验证。

为了模拟不同多核处理器下算法的有效性,选择三种不同的多核CPU,分别是双核4物理线程的Inter core i5 3230M2.6GH、4核8物理线程的Inter core i7 Q740 1.73GH以及6核物理线程的Inter Xeon E5-2620 2.00GH。由于每个CPU功耗与频率不同,能耗与离散频率之间的对应关系也有所不同,具体如表1所示。将θi的值分别设定为0.2、0.4、0.6、0.8、1.0,引入θi可降低CPU即时理论功率计算难度。

表1 三种多核处理器功耗与离散频率对应关系

5.2 实验结果及分析

在不同类型的嵌入式多核处理器下,对比三种算法执行多任务调度时的功耗情况,实验结果如图1所示。

图1 三种算法不同多核CPU下功耗对比

通过观察图1可以看出,在不同类型的多核处理器下,所提方法执行多任务调度消耗的功率始终低于3.5mW,可靠性任务调度算法与并行感知调度算法均高于所提方法。这是由于所提方法通过构建嵌入式多核多任务能耗模型,综合分析算法在执行多核多任务调度时的能耗,并结合实时DVFS技术降低各项能耗。

在不同的调度任务数量下,对比三种算法完成任务调度所需的最大完成时间,实验结果如图2所示。

图2 三种算法多核多任务调度时间对比结果

从图2中可以很清楚地看出,随着调度任务数量的不断增加,三种算法的最大完成时间也出现了不同幅度的上升趋势。其中,所提方法的时间增长幅度最小,所需的最大完成时间为10ms,而其它两种方法所需要的时间均高于所提方法。这是由于所提方法凭借实时DVFS技术,在降低嵌入式多核处理器能耗的同时,不会影响调度任务的效率,从而可实现花费最少的时间完成高效率的多任务调度。

6 结论

针对当前多核多任务调度算法存在的诸多缺点,在综合考虑多核多任务调度的特点后,将实时DVFS技术引入其中,提出一种全新的调度方法。分析执行多核多任务调度所消耗的能量,构建多核多任务调度模型;计算嵌入式设备中每个处理核的潜在负载处理能力,以及将来可能产生的负载,选取合适的处理核完成调度。实验结果表明,在处理相同的调度任务时,所提方法产生的能耗最低,所花费的时间最短。