基于多核处理器的节能任务调度方法

叶常华，左朝树

(保密通信重点实验室，成都 610041)

0 引言

近年来，随着无线和移动设备的广泛应用，功耗问题日益突出。功耗问题不是一个单一的问题，其关系到系统安全性及散热代价等方面。因此，低功耗作为实时嵌入式系统的一个关键的设计需求，正在受到越来越多的关注。

对于多核的节能任务调度，张冬松等［1］做了深入讨论，指出多核系统中的实时节能调度问题可以归纳为分配问题、优先级问题和速度调节问题三个方面。彭蔓蔓等［2］提出了一种基于异构多核处理器的节能任务分配方法。该方法通过将任务进行两轮分配，降低了系统总能耗。桑楠等［3］提出了一种针对周期任务的多处理器节能调度算法。该算法通过静态分析确定了最低处理器调度要求，在满足可调度性的条件下动态缩放各个处理器电压，从而降低了整个系统的能耗。Liu等［4］提出了一种针对流媒体应用的多核节能任务调度方法。该方法将依赖性任务集转化为独立任务后，在硬实时条件约束下以能耗最小为原则确定任务映射。王颖锋等［5，6］提出了一种面向同构多核处理器的节能任务调度算法。该算法将任务独立化后，按照调度长度最短的原则安排任务映射，然后在各个核进行频率/电压调整以降低系统功耗。

这些研究一般都没有考虑各处理器的任务在不同频率/电压模式下的电压转换能量，而且一些算法求得的解是近似最优解，还有优化的空间。因此，基于目前的研究现状，通过深入研究，基于遗传算法进行节能任务调度的方法被设计出来。该方法首先利用RDAG算法将任务独立化，然后以能耗最低为原则，采用遗传算法确定任务映射。基于 Intel PXA270功耗模型，采用几个随机任务集进行仿真实验，结果表明该方法比现有的方法节省了20%～30%的能耗。

1 任务和功耗

1.1 任务模型

任务集可以抽象为有向无环图，表示为G={V，E，p，ET，CT，D}。其中 V 是结点集，E 是有向边的集合，p是节点间所差的迭代次数的集合，ET表示任务的执行周期数集合，CT表示任务间的通信周期数集合，D表示任务集的截止时间。例如，vi∈V、vj∈V分别表示任务集的两个任务。eij表示两个任务的依赖关系，即任务vj在vi之后执行。p(eij)=k(k为常数)表示任务vj在任务vi后的第k轮执行。Eti∈ET表示任务vi执行的周期数，Ctij∈CT表示任务vi和任务vj间的核间通信周期数。

1.2 功耗模型

对于具有多个核的同构处理器，假设每个处理器核都支持m个离散的频率/电压模式。将每个核的频率/电压模式表示为Core(F，V)，F代表频率的集合，V代表电压的集合。其中，Corei=(fi，Vi)，表示一个频率/电压模式。

总能耗为

式中，Etask代表所有任务消耗的总能量;Ecommunication代表核间通信消耗的总能量;Etransition代表各核状态变换消耗的总能量;Eidle代表各核空闲时小号的的总能量。

任务vi所消耗的动态能量为

式中，PAC是处理器每周期动态功耗;Eti是任务vi所需执行周期数;Ceff是每周期平均开关电容;Vdd是电源电压;f是处理器时钟频率。电压从Vddi转换到Vddj所产生的转换能量为

式中，Cr是电源导轨电容。

2 多核节能任务调度算法

2.1 算法思想

存在包含依赖关系的周期性硬实时任务集G={V，E，p，ET，CT，D}及具有 n 个核的同构处理器，其中每个核的频率/电压模式为Core(F，V)。算法是把该任务集的任务以特定处理器频率分配到各个核上进行处理，使得总能耗最小。算法思想如图1所示，首先使用Liu等［4］提出的RDAG算法将任务独立化，然后使用基于多核节能任务调度的遗传算法确定最佳的任务映射。

图1 算法思想

其中，基于多核节能任务调度的遗传算法思想如下。

(1)任务调度种群的初始化

遗传算法的一个优点是它能够隐式并行地搜索解空间的多个解，当然这需要随机地生成一个包含多个解的初始种群。设任务集共有m个任务，种群中的个体 i表示为 Ui={vi1，vi2，…，vim，fi1，fi2，…，fim}。vij代表为任务集中的任务vj分配的处理器核，fij代表该任务在核vij上运行时对应的处理器频率。种群初始化步骤如下:(a)随机产生一个个体;(b)将该个体中各核上的任务按fi由大到小的序列执行;(c)若某处理器核上的任务执行总时间长于限定时间，则淘汰该个体;(d)回到步骤(a)，直到产生给定数目的个体，形成一个种群。

(2)调度序列的选择

选择的目的是使得较优的个体能够以较大的概率遗传到下一代。设个体i适应度函数为

Egi是个体i消耗的总能量。假设任务集有m个任务，处理器核共有n个，核i上的任务共S(i)个，按执行频率降序排列。ET表示任务的执行周期数集合，CT表示任务间的通信周期数集合。任务vi和任务vj间的核间通信周期数

由式(1)(2)(3)(4)(6)可得

式中，Pk代表执行任务k时处理器功率;Pc代表核间通信功率;Vddk代表执行核上第k个任务时的处理器电压;Pidle为空闲时处理器功率;tidle(k)表示第k个处理器的空闲时间。

采用轮盘赌方式进行选择，使得较优的个体被选中的概率较高。方式如下:(a)计算当前种群中所有个体适应度函数的总和Sum;(b)计算适应度函数的一个累加值序列:Seq={s1，s2，…，sk}，k代表个体数随机生成一个数 x，0≤x ＜Sum;令s0=0，如果，si－1≤x ＜si，则个体 i被选择。

(3)调度序列的交叉和变异

交叉和变异的目的是为了增加种群的多样性，其操作如图2所示。采用的单点交叉方法如下:(a)通过选择得到两个个体;(b)随机选择一个交叉点;(c)将两个个体交叉点以后的部分进行交叉。如图2(a)所示，Ui={vi1，vi2，…，vim，fi1，fi2，…，fim}和 Uj={vj1，vj2，…，vjm，fj1，fj2，…，fjm}为两个个体。假设交叉点为k，则将k以后的序列互换。

图2 交叉和变异操作

从个体中随机选择某一个元素进行变异，分两种情况:若选择的元素表示处理器核，则变异后的元素同样表示处理器核;若该元素表示处理器频率，变异后的元素同样表示处理器频率。如图2(b)所示，个体Ui的第k个元素表示一个处理器核，该元素发生了变异，将会变为表示另一个处理器核的元素。

2.2 算法描述

基于多核节能任务调度的遗传算法输入为独立化后的任务集G、处理器核数n、任务集截止时间D、各核的频率/电压模式 Core(F，V)、各核在不同频率下的功率、核间的通信功率、算法每代的个体数N、遗传的最大代数Gn、截止条件q、交叉概率P1及变异概率P2，输出为最终调度序列S。S=［L0，L1，…，Ln－1］，其中Li表示核 i的调度序列。算法伪代码如下。

图3 算法伪代码

3 实验结果与分析

为了验证算法的有效性，将上述算法与文献［6］中的方法进行比较。实验中各任务执行周期数在10至50间随机产生，而任务间通信周期数在1至5之间随机产生。输入任务个数和边数，随机产生一个用有向无环图表示的任务集。

处理器采用Intel PXA270［7］的功耗模型，该模型的模式转换时间可以忽略，其频率/电压模式及对应的功耗见表1。设定系统总线频率固定为208 MHz，电源导轨电容Cr为5 pF。在该模型下，随机产生6个任务集，其特征见表2。设置遗传算法交叉概率和变异概率分别为0.9和0.03。在两核和四核下分别进行比较，得出功耗比较图，如图4所示。可以看出，文章的方法节能效果优于文献［6］的方法。主要原因在于文献［6］的方式在进行任务到核的分配时运用的是一种近似算法，得到的解还有优化的空间。

表1 Intel PXA270功耗模型频率及对应电压和功耗

表2 任务集特征

4 结语

随着多核嵌入式系统的发展，能耗问题已成为研究的热点。在当前研究的基础上，针对多核节能任务调度算法的不足，设计了一种节能任务调度方法。该方法分两个阶段:第一阶段采用RDAG算法将依赖性任务独立化，第二阶段运用遗传算法将任务集分配到各处理器核上进行处理。实验表明，该方法达到了较为良好的节能效果。

［1］张冬松，陈芳园，等.多核系统中基于动态电压频率调节的实时节能调度研究［J］.计算机工程与科学，2010，32(9):157-162.

［2］彭蔓蔓，徐立超，等.异构多核处理器的任务分配及能好研究［J］.计算机应用研究，2010，27(5):1 729-1 731.

［3］桑楠，李保宇，等.多处理器的节能调度算法［J］.电子科技大学学报，2008，37(1):116-119.

［4］LIU H，SHAO Z L，et al.Overhead-Aware System-Level Joint Energy and Performance Optimization for Streaming Applications one Multiprocessor Systems-on-Chip［C］//Proceedings of the 2008 Euromicro Conference on Real-Time Systems，Washington DC，2008:92-101.

［5］王颖锋，刘志镜.一种变电压多核处理器上的有效节能方法［J］.计算机科学，2010，37(9):294-296.

［6］王颖锋，刘志镜.面向同构多核处理器的节能任务调度方法［J］.计算机科学，2011，38(9):294-297.

［7］YANG C C，WANG K C，et al.Energy Efficient Intra-Task Dynamic Voltage Scaling for Realistic Cpus of Mobile Devices［J］.Journal of Information Science and Engineering，2009，25(1):251-272.