异构多核环境下的任务调度问题属于NP-难问题^[1–4], 即任务调度问题只能得到近似最优解, 因此异构多核环境下的任务调度问题对处理器系统的性能和效率提高具有非常重要的作用. 多核处理器任务调度的目标^[5]就是按照某种策略将每个任务合理分配到各个处理器内核上并行有序地执行, 从而减少并行运行任务间的通信开销和等待时间, 使任务的执行时间最短.

异构多核处理器平台下DAG任务调度算法主要包括表调度算法^[6,7]、聚类调度算法以及基于复制的调度算法等, 具体包括DSC、DCP、CPFD、TDS、HEFT、CPOP和PEFT等算法. 为了尽可以实现任务调度的目标, 需要从任务调度的排序以及任务调度两个环节对算法进行优化和改进. 文中利用任务的方差以及平均通信开销对任务进行排序, 将关键路径^[8]、关键结点以及任务复制技术^[9,10]应用于任务调度过程中, 从而使任务调度的效率更接近任务调度的目标．在任务排序阶段, 以任务计算代价的二次方差以及平均通信开销作为任务排序的依据, 相比传统HEFT算法直接用计算开销作为排序的依据更科学、效率更高; 在任务调度阶段, 对满足任务复制条件的节点进行任务复制, 可以避免部分任务之间的通信开销, 提高资源的利用率, 降低任务集的计算时间.

1 相关任务调度及DAG任务模型 1.1 相关任务调度

根据被调度任务之间的相关性, 可以将任务调度分为独立任务调度和相关任务^[11,12](依赖任务)调度两种类型．异构多核处理器平台下的任务调度可以分为静态任务调度和动态任务调度两种^[13]．静态任务调度^[14]是指满足硬件资源的负载均衡和通信开支的前提下将任务分配给固定的处理器内核; 而动态任务调度^[15]则指根据资源利用率的情况可以将任务分配到任何处理器内核上. 相关任务在异构多核处理器平台下的调度问题, 主要任务是将子任务映射到多个处理器内核上, 达到任务完成时间最小化等调度目标, 因此在任务调度的过程中, 不仅要考虑异构处理器内核计算能力的差异, 同时还要考虑处理器内核之间的数据通信等问题, 因此, 相关任务的调度问题均属于NP完全问题^[16].

DAG任务调度算法主要有DSC^[17]、DCP^[18]、CPFD^[19]、TDS^[20]、HEFT^[21,22]、CPOP^[21,22]和PEFT^[23]等算法. 异构多核处理器平台下DAG任务调度算法主要包括三类, 分别为表调度算法、聚类调度算法以及基于复制的调度算法.

表调度算法^[24]是最经典的DAG调度算法. 表调度算法包括静态调度算法和动态调度算法两种．静态调度算法的基本思想: 根据DAG中的所有任务之间的关系, 结合某种策略决定任务之间的优先级并构造一个调度列表; 然后为具有最高优先级的任务分配能够使它最快完成的资源并开始调度执行, 循环上述步骤直到DAG中所有任务均被调度. 动态表调度算法在执行完每一个任务后根据当前处理器内核的情况以及任务之间的依赖关系重新计算任务的优先级, 静态调度算法的不重新计算优先级, 而动态调度算法需要重新计算优先级. 常见的表调度算法包括Topcuoglu等人提出的HEFT (Heterogeneous Earliest Finish Time)算法^[25,26]以及CPOP算法.

1.2 DAG任务模型

通常使用DAG (Directed Acyclic Graph)任务图来描述相关任务之间的关系. 相关任务的特点是任务的所有前驱节点执行完成后, 后续任务才能开始执行. DAG表示为G=(V, E, ET, C), 其中V表示n个任务结点t₁, t₂,…, t_n的集合, 每一个结点v_i表示DAG中的一个任务, |V|=n; E表示k条有向边e₁, e₂,…, e_k的集合, 每条有向边c_i,j∈E, 表示任务结点t_i, t_j之间存在先后执行的关系, 即任务t_j必须在任务t_i执行完成之后才能开始执行, 每一条边的权值表示任务和任务之间的通信时间; ET表示任务t_i在处理器内核c_j上的估算计算时间, 在DAG中, 通常用平均计算时间作为任务节点的权值, 任务t_i的平均执行时间为 $\left[ {\displaystyle\sum\limits_{j = 1}^m {E{T_{i, j}}} } \right]/m$ ; C是任务之间通信开销的集合, 在DAG中, 将任务的通信开销作为边的权值.

定义1. pred(t_i)表示在给定的DAG中, 任务t_i直接前驱任务组成的集合. 如果pred(t_i)=Ø, 那么称该任务为入口任务, 用t_entry表示. succ(t_i)表示在给定的DAG中, 任务t_i直接后继任务组成的集合. 如果succ(t_i)=Ø, 那么称该任务为出口任务, 表示为t_exit. 如果在一个DAG中, 有多个入口任务或出口任务, 那么增加一个通信时间和计算时间为0的虚拟入口或出口任务.

定义2. 矩阵ET, 是一个n*m的计算时间矩阵, 其中n表示任务数, m表示处理机内核数量, ET(t_i, c_j)表示在处理机内核c_j上执行任务t_i的估算时间.

定义3. 关键路径(Critical Path, CP), 在DAG中, 一条从入口节点t_entry到出口节点t_exit的最长路径称为关键路径.

定义4. 跨度(Makespan)或调度长度表示某一个确定的调度算法对任务集T调度后, 任务集T中最后一个任务的完成时间, 如式(1)所示．其中 $AFT({t_i})$ 表示任务t_i实际完成时间, Makespan是所有出口任务中实际完成时间的最大值．

$Makespan = \max \{ AFT({t_i})\} $

(1)

定义5. 最早开始时间 $EST({t_i}, {c_j})$ 是指任务t_i在处理器内核c_j上的最早开始时间, $EST({t_i}, {c_j})$ 取 $AFT({t_i})$ 和 $EFT({c_j})$ 两个值中的较大值, 如式(2)所示.

$EST({t_i}, {c_j}) = \left\{ {\begin{array}{*{20}{c}} \!\! \!\!\!\!\!\!\!\!\!\!{AT({t_i})} \\ \!\!\!\!\!{EFT(c{}_j)} \end{array}} \right.$

(2)

定义6. 最早完成时间 $EFT({t_i}, {c_j})$ 是指任务t_i在处理器内核c_j上的最早完成时间, 其值等于任务t_i在处理器内核c_j上的最早开始时间, 加上t_i在处理机内核c_j上的计算时间, 如式(3)所示.

$EFT({t_i}, {c_j}) = EST({t_i}, {c_j}) + ET({t_i}, {c_j})$

(3)

定义7. 平均等待时间AWT, 任务集T中的所有任务在调度过程中, 设任务t_i的开始执行时间为ST_i, 任务到达时间AT_i, 则 $AWT = \left[ {\displaystyle\sum\limits_{j = 1}^n {(S{T_j} - A{T_j})} } \right]/n$ .

定义8. C表示通信开销的集合. c_i,j表示任务t_i和t_j之间的通信开销, 通常用平均通信代价 ${c_{i, j}}$ 来表示任务t_i和t_j之间的通信开销, 任务t_i和t_j之间的平均通信开销如式(4)所示. 其中 $\overline L $ 表示所有处理机内核的平均延迟, $\overline B $ 表示处理机内核相连的平均带宽, data_i,j表示t_i发送给任务t_j的数据总量．当t_i和t_j被分配到同一个处理机内核时c_i,j=0, 这是因为相比处理机内核之间的通信, 处理机内核内的通信可以被忽略.

$\overline L + \frac{{dat{a_{i, j}}}}{{\overline B }}$

(4)

定义9. Slack．Slack是一个关于任务调度算法鲁棒性的量度, 其反映的是一个算法调度产生的任务处理时间的不确定程度. Slack的定义如式(5)所示. 其中M表示DAG的Makespan, n表示任务数量, ${b_{{\rm{level}}}}$ 表示任务 ${t_i}$ 到出口节点最长路径的长度, ${t_{\rm {level}}}$ 表示从入口节点到任务 ${t_i}$ (不包含任务 ${t_i}$ )最长路径的长度.

$Slack = \left[ {\sum\limits_{{t_i} \in T} {M - {b_{\rm {level}}}({t_i}) - {t_{\rm {level}}}({t_i})} } \right]/n$

(5)

2 任务调度模型及算法 2.1 DAG任务模型

针对传统的表调度算法中存在不能准确反应DAG任务图中的内在联系、任务与处理器内核之间调度效率不高以及负载不均衡等问题, 本文提出了一种的相关任务调度模型及相关任务调度算法IHEFT算法. 相关任务调度模型如图1所示, 任务集T中的任务被调度到处理器内核集C中包括分两个步骤: 任务排序和任务调度. 任务排序阶段, 主要根据任务的执行时间方差以及平均通信开销作为排序的依据; 任务调度阶段, 判断当前任务结点的前驱结点是否为关键结点, 如果为关键结点且满足任务复制条件, 则进行任务复制, 否则按HEFT调度算法对任务进行调度.

2.2 调度算法

相关任务调度IHEFT算法如算法1所示. 算法的主要思想为: 在任务排序阶段, 用任务在各个处理器内核上的执行时间方差以及通信成本作为参数对DAG任务进行排序, 任务执行时间的方差以及通信成本越大, 任务在不同的处理器内核上的执行时间差异就越大, 给任务赋予较高的优先级, 相反, 赋予较小的优先级, 任务t_i的方差及通信成本 ${\delta _i}$ 计算如式(7)所示. 在任务调度阶段, 首先获取DAG任务图的关键路径, 关键路径上的节点任务优先级最高, 非关键路径上的任务按 ${\delta _i}$ 降序排列; 然后利用任务复制技术优化任务调度过程, 若当前任务t_i的前驱节点t_j为关键节点任务, 且复制关键节点任务t_j到被调度的处理器内核c_m可以缩短当前任务的最早完成时间, $EFT{({t_i}, {c_m})'}$ 定义如式(6)所示, 则复制关键节点任务t_j到当前处理器内核c_m; 若不满足任务复制条件, 即 $EFT{({t_i}, {c_m})'} \geqslant EFT({t_i}, {c_m})$ , 则按HEFT算法将任务调度到使任务完成时间最早的处理器内核. 通过任务复制可以减少任务间通信开销、提高处理器内核利用率等目的.

$EFT{({t_i}, {c_m})'} < EFT({t_i}, {c_m})$

(6)

${\delta _i} = \sum\limits_{k = 1, n - 1 \geqslant i \geqslant 0}^{k \leqslant m} {{{(E{T_{{t_i}, {c_k}}} - \overline {ET} )}^2}/m + {c_{i, j}}} $

(7)

3 任务调度过程分析

以1个DAG任务图为例, 分析IHEFT相关任务调度算法在异构多核处理器内核上的调度过程.

---

算法1. IHEFT算法

---

1. 从DAG任务图中读取任务数到n;

2. 从DAG任务图中读取计算节点的数量到m;

3. 读取DAG任务图中任务之间的通信开销, 并保存在c[n][n]中;

4. 计算所有任务的二次方差 $\scriptstyle {\delta _i}$ 值;

5. 按降序顺序对所有任务的 $ \scriptstyle {\delta _i}$ 值进行排序;

6. 从出口任务开始, 对DAG任务进行遍历, 计算所有任务的rank_u值;

7. 入口任务开始, 对DAG任务图进行遍历, 计算所有任务的rank_d值;

8. 计算DAG中每个任务的优先级, 计算方法为priority[t_i]=rank_u[i]+rank_d[i];

9. 通过priority[t_i]找出DAG任务图的关键路径CP;

10. while 任务集非空{

11. 从DAG任务图中找出优先级最高的任务t_i;

13. if当前任务节点t_i的前驱节点t_j是关键路径节点, 即满足式(5-11)条件;

12. 找到相应的计算节点f_m调度任务;

14. 将任务t_j复制到计算节点f_m上, 并在此计算节点上执行;

15．保存ST[i], FT[i], Avail[m]的值;

16. else

17. 调度任务t_i到计算节点f_m上;

18. 保存ST[i], FT[i], Avail[m]

19. s[i][m]=1

20. 计算所有任务的跨度Makespan值;

21. }

22. 计算任务集中所有的任务的平均等待时间AWT以及Slack值

---

3.1 DAG初始化

图2表示一个DAG任务模型, 共有10个任务, 带箭头的边表示任务之间的通信边, 边上的数字表示两个任务之间的通信代价c_i,j; 节点t₁为入口节点, 节点t₁₀为出口节点. 表1表示任务在不同处理器内核上的计算时间ET(t_i, c_j), 表1中包括3个处理器内核c₀~c₂, 10个任务t₁~t₁₀.

3.2 依赖关系矩阵

根据DAG任务模型, 生成任务之间对应的依赖关系矩阵, 如表2所示. 依赖关系矩阵的定义为:

(1)若结点i为结点j的前驱节点, 则矩阵元素d_i,j=c_i,j;

(2)若结点i和结点j之间不存在依赖关系, 则矩阵元素d_i,j=0.

3.3 任务排序

计算每个任务t_i的rank_u、rank_d、rank_u+rank_d值以及计算代价的二次方差、通信开销值 ${\delta _i}$ , 并降序进行排序, 表3所示为4核环境下各参数的计算及排序情况.

3.4 任务调度

(1)计算关键路径

计算每个任务的rank_u值以及rank_d值, 在此基础上找出DAG任务模型中的关键路径, 任务集t₁~t₁₀的关键路径为: t₁, t₃, t₈, t₁₀.

(2)任务复制

根据生成的任务调度序列t₁, t₃, t₄, t₂, t₈, t₉, t₇, t₆, t₅, t₁₀, 对每个被调度的任务检查是否满足任务复制条件 $EFT{({t_i}, {c_m})'} < EFT({t_i}, {c_m})$ , 即任务被复制到另一个处理器内核上, 要满足复制前驱任务后当前任务的完成时间要小于不复制前驱任务的完成时间. 在任务t₄和t₂被调度时, 满足任务复制条件, 分别将t₄和t₂的前驱任务t₁复制到处理器内核c₁和c₀上, 如图3(a)所示.

(3)任务调度

任务集经过调度之后, 任务与处理器内核的对应调度关系如图3(a)所示, 图3(b)、图3(c)分别表示同一任务集通过HEFT算法、CPOP算法调度的对应关系, 很明显, HEFT、CPOP算法任务调度的总长度Makespan值比IHEFT算法要大.

4 仿真实验与结果分析 4.1 实验目的

为了验证本章提出的IHEFT算法, 在相同的实验条件下对本章所提出的算法IHEFT与现有的调度算法HEFT和CPOP算法进行性能比较, 主要比较任务跨度Makespan和任务平均等待时间AWT.

4.2 模拟环境

基于SimGrid提供的模拟器工具包, 构建一个异构多核处理器的仿真环境. 其中:

(1)处理器内核之间通过高速网络互连;

(2)每个处理器内核可同时进行任务执行和与其它处理器内核通信, 而不需要争用;

(3)任务在处理器内核上执行是非抢占的;

(4)处理器内核之间是异构的, 即同一个任务在不同处理器内核上执行存在差异性．

实验中使用的计算机配置为: Intel Core i5-3210M@2.5 GHz双核笔机本处理机, 8 GB内存. 本次实验采用的处理器内核分别取3、4核.

4.3 测试数据集

IHEFT算法输入的数据包括DAG任务图(包括任务集、处理器内核集、任务间通信成本)、任务调度计算时间矩阵; 算法的输出为任务调度执行时间Makespan以及任务平均等待时间AWT．IHEFT算法任务调度测试分两种情形. 第一种情况: 任务集中包括10个任务, 处理器内核集中包括3个处理器内核, DAG任务图的数量分别为1~10; 第一种情况: 任务集中包括10个任务, 处理器内核集中包括4个处理器内核, DAG任务图的数量分别为1~10, 所有任务的到达时间为0.

4.4 实验结果分析

利用三种算法分别对10个DAG任务图进行调度, 表4为三种算法在3核、4核情况下Slack值的对比情况.

(1) 3个处理器内核

分别采用3种算法对DAG任务集进行调度, 在处理器内核的数量为3的情况下, 针对不同数量DAG任务模型进行调度, 得到所有任务的跨度(调度长度)Makespan、平均等待时间AWT的值以及平均Slack值, 如图4(a)、图4(b)、图5所示.

图4(a)的纵坐标为算法所获得的调度跨度Makespan值, 横坐标为DAG数量; 图4(b)的纵坐标为算法所获得的调度跨度平均等待时间AWT值, 横坐标为DAG数量．从实验数据得出, 在任务调度的跨度方面, IHEFT算法比HEFT算法最低降低了10%, 最高降低了15.7%; IHEFT算法比CPOP最低降低了14.3%, 最高降低了21.2%; 在任务平均等待时间方面, IHEFT算法比HEFT算法最低降低了3.3%, 最高降低了17.5%, IHEFT算法比CPOP算法最低降低了14.6%, 最高降低了28.0%．图5中纵坐标为算法所获得的平均Slack值, 横坐标为DAG数量, 从图5可以看出, 随着DAG数量的的增加, IHEFT、HEFT和CPOP算法的Slack值变化不明显, 但是横向比较可以看出IHEFT相对HEFT和CPOP算法有更低的Slack值, IHEFT算法的Slack值最高比HEFT算法要减少31.2%, 比CPOP算法要减少36.1%．

(2) 4个处理器内核

分别采用3种算法对DAG任务集进行调度, 在处理器内核的数量为4的情况下, 针对不同数量DAG任务模型进行调度, 得到所有任务的跨度makespan、平均等待时间AWT的值以及平均Slack值, 如图6(a)、图6(b)、图7所示.

图6(a)的纵坐标为算法所获得的调度跨度makespan值, 横坐标为DAG数量; 图6(b)的纵坐标为算法所获得的调度跨度平均等待时间AWT值, 横坐标为DAG数量. 从实验数据得出, 在任务调度的跨度方面, IHEFT算法比HEFT算法最低降低了22.2%, 最高降低了27.1%; IHEFT算法比CPOP最低降低了29.1%, 最高降低了34.4%; 在任务平均等待时间方面, IHEFT算法比HEFT算法最低降低了19.9%, 最高降低了24.8%, IHEFT算法比CPOP算法最低降低了33.6%, 最高降低了37.0%. 图7中纵坐标为算法所获得的平均Slack值, 横坐标为DAG数量, 从图7可以看出, 随着DAG数量的的增加, IHEFT、HEFT和CPOP算法的Slack值变化不明显, 但是横向比较可以看出IHEFT相对HEFT和CPOP算法有更低的Slack值, IHEFT算法的Slack值最高比HEFT算法要减少26.6%, 比CPOP算法要减少34.3%.

通过两组实验分析得出, IHEFT算法在任务调度跨度以及任务调度平均等待时间两方面均优于HEFT算法和CPOP算法. 在任务调度跨度方面最小分别降低了10%和14.3%, 在任务调度平均等待时间方面最小分别降低了3.3%和14.6%．IHEFT的任务排序方面采用计算代价的二次方差作为排序依据更能体现任务的优先级, 而在任务调度的过程中对满足条件的任务进行任务复制可以有效地减少任务调度的跨度、任务调度平均等待时间以及平均Slack值.

5 结论与展望

文中介绍了相关任务调度及DAG任务模型的基本概念, 对相关任务调度算法HEFT算法和CPOP算法进行了介绍. 由于HEFT算法和CPOP算法在相关任务调度中存在一些缺陷, 基于HEFT算法和CPOP算法, 对相关任务调度中任务排序和任务调度两个方面进行改进, 提出了一种相关任务调度模型和相关任务调度算法IHEFT算法. 通过实验证明, IHEFT算法在任务调度跨度、任务调度平均等待时间以及平均Slack方面均优于HEFT算法和CPOP算法.