多DAG任务调度算法

刘林东，邬依林

(广东第二师范学院计算机科学系，广东 广州 510303)

相关任务一般用有向无环图(Directed Acyclic Graph,DAG)[1-2]表示，区别于独立任务的特点是只有当前任务的所有前驱任务执行完成后，才能调度当前任务。相关任务调度根据DAG的数量一般分为单DAG任务调度和多DAG任务调度两种，近年以来，单DAG任务调度在分布式异构环境中的研究取得了较多的研究成果，通常不能将这些调度策略直接应用在多DAG任务调度问题中。

分布式异构计算环境下的任务调度问题[3]以及多DAG任务调度问题是现有任务调度的热点[4-5]，任务调度模型以及任务调度算法一般从任务排序以及任务调度两方面进行了一些优化，对约束条件较多的多DAG调度，如提交的DAG时间不一致以及限定任务调度的完成时间等，以及如何动态地对多个DAG任务进行调，兼顾多个DAG之间调度的公平性以及资源利用率等问题，需要对这些问题进一步开展研究工作。

相关任务的调度算法主要包括HEFT算法[6-7]、MCP算法、ETF算法、CPOP算法[8]、LBP算法、DSC[9]算法、DCP[10]算法、DSH算法、CPFD[11]算法、Fairness[12]算法、Backfill算法、遗传算法以及模拟退火算法等。

1 问题描述

以下分别从任务描述、资源环境以及任务调度目标等几个方面对分布式异构计算环境下相关任务调度问题进行描述。

1.1 任务描述

图1 多DAG任务图Fig.1 Multi-DAG task graph

1.2 资源环境

1.3 任务调度目标

3)整个任务集在处理机上的执行时间最短，即makespan值尽可能小；

5)任务调度算法稳定性更好，计算并对比各种任务调度算法的Slack值，评估和选择Slack值更小的任务调度算法。其中Slack是一个关于任务调度算法鲁棒性的度量，反映的是一个任务调度算法产生的任务处理时间的不确定程度，Slack的定义如式(1)所示。其中M表示DAG的跨度makespan，n表示任务数量，blevel表示任务ti到出口节点最长路径的长度，tlevel表示从入口节点到任

务ti(不包含任务ti)最长路径的长度。

(1)

2 MDTS任务调度模型

提出了一种分布式异构环境下的多DAG任务调度模型，如图2所示。MDTS任务调度模型在进行任务调度和处理机选择时分三个阶段完成，分别为DAG合并、任务排序以及任务调度。

图2 多DAG任务调度模型Fig.2 Task scheduling model of multi-DAG

2.1 多DAG合并

首先对多个DAG任务图进行合并，合并的方法是增加一个虚拟的入口任务节点和出口任务节点。入口任务节点同时作为每个子DAG入口任务节点的父亲节点，出口节点同时作为每个子DAG图出口任务节点的子任务节点，然后更新虚拟入口任务节点和出口任务节点与相关任务节点的通信开销和计算代价，多DAG任务图合并后的效果如图3所示。

图3 多DAG合并后Fig.3 The combined result of multi-DAG

2.2 任务排序

用合并后的任务在各个处理机上计算代价的二次方差以及通信成本作为参数对DAG任务进行排序。任务计算代价的方差以及通信成本越大，任务在不同的处理机上的调度时间差异就越大，给任务赋予较高的优先级，相反，则赋予较小的优先级，任务ti计算代价的方差及通信成本δi计算如下：

(2)

2.3 处理机选择与任务调度

根据已排序好的任务集，按从高到低的顺序依次对任务集进行调度，按HEFT算法中的任务调度策略对处理机进行选择与调度。

3 MDTS任务调度算法

3.1 处理机选择

在处理机选择方面，在计算完每个DAG任务在各个处理机上计算代价的二次方差以及通信成本后，按HEFT算法中的任务调度策略将任务调度到相应的处理机执行，即在处理器选择阶段，先对满足任务复制条件的任务节点进行任务复制[13-14]，从而减少相关任务之间的通信开销，再按HEFT算法将任务调度到使任务完成时间最早的处理机上执行。

3.2 调度算法

多DAG任务调度MDTS算法如表1所示，算法将DAG任务模型以及任务在处理机计算资源上的计算代价作为算法的输入，算法的输出是各个DAG中的任务与处理机对应的调度关系以及任务调度跨度、任务调度平均等待时间以及平均Slack值等。

3.3 算法性能分析

MDTS任务调度算法的各个步骤的时间复杂度分别如下：

1) 增加入口任务节点和出口任务节点子程序的时间复杂度为O(p)；

表1 MDTS算法Table 1 MDTS algorithm

4 仿真实验与结果分析

4.1 实验目的

为了验证文中提出的MDTS算法，在相同的实验条件下对提出的MDTS算法与同类调度算法Sequential和Interleave算法进行性能比较，主要比较任务跨度makespan、任务平均等待时间AWT以及平均Slack值。

4.2 模拟环境

在模拟实验环境中，设定一个分布式异构计算环境下的处理机对应一个处理机，因此可以将整个分布式异构处理机模拟成SimGrid[15-17]环境下的集群环境，基于SimGrid提供的模拟器工具包，构建一个分布式异构计算的仿真环境。其中：

(i) 处理机之间通过高速网络互连；

(ii) 每个处理机可同时进行任务执行和与其它处理机通信，而不需要争用；

(iii) 任务在处理机上执行是非抢占的；

(iv) 每个处理机之间是性能异构的，即同一个任务在不同处理机上执行存在差异性。

实验中使用的计算机配置为：Intel Core i5-3210M@2.5GHz双核笔机本处理机，8 G内存。本章实验采用的处理机分别取3个和4个。

4.3 任务调度过程分析

以2个DAG任务图为例，以下详细分析MDTS相关任务调度算法实现多DAG任务图的合并以及在分布式异构计算环境下的调度过程。

4.3.1 DAG初始化 图4表示包含两个DAG图的多DAG任务图。其中DAG1中包括有7个任务，DAG2中包括有4个任务。带箭头的边表示任务之间的通信边，边上的数字表示两个任务之间的通信代价ci,j。DAG1的入口节点为a1，出口节点为和a7；DAG2的入口节点为b1，出口节点为b4。表2、表3分别表示DAG1、DAG2中的任务在不同处理机上的计算时间ET(ti,cj)，表2、表3中包括3个处理机P0～P2，其中通信代价和执行时间的单位为 s。

图4 多DAG任务图Fig.4 Task graph of multi-DAG

任务P0P1P2a112168a210157a3152010a49126a513189a67105a7162311

表3 DAG2任务集在处理机集上的调度时间Table 3 Scheduling time of DAG2 task set on processor set

4.3.2 合并DAG任务图 通过添加一个入口任务节点和出口任务节点将图4中的DAG1和DAG2合并在一起，产生一个新的DAG图，合并的步骤为：

(i) 添加一个入口任务节点entry，将入口任务节点entry分别与DAG1、DAG2的入口任务节点a1、b1相连，设通信代价为0.01；entry任务节点在处理机上的执行时间均为0.01；

(ii) 添加一个出口任务节点exit，将出口任务节点exit分别与DAG1、DAG2的出口任务节点a7、b4相连，设通信代价为0.01；节点在处理机上的执行时间都为0.01；

(iii) 保留DAG1和DAG2中的其余节点之间的关系、通信开销以及执行代价，合并后的新DAG如图5所示，合并后的任务在处理机上的计算时间ET(ti,cj)如表4所示。

4.3.3 依赖关系矩阵 根据合并后的DAG任务图，生成任务之间对应的依赖关系矩阵，如表5所示。依赖关系矩阵的定义为：

(i)若节点i为节点j的前驱节点，则矩阵元素di,j=ci,j；

图5 合并后DAG任务图Fig.5 Combined DAG task graph

任务P0P1P2entry0.010.010.01a112168b113158a210157a3152010b214179b3182312a49126a513189a67105b4152211a7162311exit0.010.010.01

(ii)若节点i和节点j之间不存在依赖关系，则矩阵元素di,j=0；

(iii)由于DAG中节点之间的依赖关系，当i≥j时，di,j=0。

4.3.4 任务排序 计算每个任务ai计算代价的方差以及通信开销δi，并降序进行排序，计算及排序的结果如表6所示。

4.3.5 任务调度 任务集经过MDTS算法调度之后，任务与处理机的对应调度关系如图6(a)所示，图6(b)、(c)分别表示同一任务集通过Sequential、Interleave算法[18]调度的对应关系。

4.4 实验结果分析

利用3种算法分别对10个DAG任务图进行调度，表7为三种算法分别在在3个处理机、4个处理机情况下Slack值的对比情况。

表5 依赖关系矩阵Table 5 Dependency matrix

表6 任务的δi值Table 6 The δi of each task

表7 MDTS、Sequential、Interleave算法的Slack值Table 7 Slack value of MDTS, Sequential and Interleave algorithms

根据δi的值按降序进行排序，产生任务集的任务调度序列如：entry,a1,b1,a3,a2,a6,a5,b3,b2,a4,a7,b4,exit。

图6 三种算法任务调度对比Fig.6 Comparison of three algorithms for task scheduling

4.4.1 3个处理机情况 分别采用3种算法对多个DAG任务集进行调度，在处理机的数量为3的情况下，针对不同数量DAG任务模型进行调度，得到所有任务的跨度(调度长度)makespan平均等待时间AWT值以及平均Slack，如图7(a)、图7(b)、图8所示。

图7 不同DAG的任务对比图Fig.7 Comparison of task for different DAGs

图8 不同DAG的任务平均Slack对比Fig.8 Task average Slack comparison of different DAGs

图7(a)的纵坐标为算法所获得的调度跨度makespan值，横坐标为DAG数量；图7(b)的纵坐标为算法所获得的调度跨度平均等待时间AWT值，横坐标为DAG数量。从实验数据得出，在任务调度的跨度和任务平均等待时间方面，随着DAG数量的增加，均会相应的增加。总体来说，MDTS算法的性能最佳，Interleave算法的性能其次，Sequential算法的性能最差。MDTS算法和Interleave算法在1个DAG时跨度相等，最高降低了27.0%；MDTS算法和Sequential算法在1个DAG时跨度相等，最高降低了21.2%；在任务平均等待时间方面，MDTS算法在几种情况下比Interleave算法的等待时间稍长，最高降低了6.6%，MDTS算法和Sequential算法在1个DAG时相等，最高降低了55.0%。

图8中纵坐标为算法所获得的平均Slack值，横坐标为DAG数量，从图8可以看出，随着DAG数量的增加，MDTS、Sequential和Interleave算法的Slack值变化不明显，但是横向比较可以看出MDTS相对Sequential和Interleave算法有更低的Slack值，MDTS算法的Slack值最高比Sequential算法要减少53.6%，比Interleave算法要减少18.8%。

4.4.2 4个处理机情况 分别采用3种算法对多个DAG任务集进行调度，在处理机的数量为4的情况下，针对不同数量DAG任务模型进行调度，得到所有任务的跨度(调度长度)makespan、平均等待时间AWT值以及平均Slack值，如图9(a)、图9(b)、图10所示。

图9 不同DAG的任务对比图Fig.9 Comparison of task for different DAGs

图10 不同DAG的任务平均Slack对比Fig.10 Task average slack comparison of different DAGs

图9(a)的纵坐标为算法所获得的调度跨度makespan值，横坐标为DAG数量；图9(b)的纵坐标为算法所获得的调度跨度平均等待时间AWT值，横坐标为DAG数量。从实验数据得出，在任务调度的跨度和任务平均等待时间方面，随着DAG数量的增加，任务调度的跨度会相应的增加；相比3个处理机情况，4个处理机的任务调用跨度和平均等待时间相对较小。总体来说，MDTS算法的性能最佳，Interleave算法的性能其次，Sequential算法的性能最差。MDTS算法和Interleave算法在1个DAG时跨度相等，最高降低了39.0%；MDTS算法和Sequential算法在1个DAG时跨度相等，最高降低了64.1%；在任务平均等待时间方面，MDTS算法在几种情况下比Interleave算法的等待时间稍长，最高降低了16.3%，MDTS算法和FCFS算法在1个DAG时相等，最高降低了61.8%。图10中纵坐标为算法所获得的平均Slack值，横坐标为DAG数量，从图10可以看出，随着DAG数量的增加，MDTS、Sequential和Interleave算法的Slack值变化不明显，但是横向比较可以看出MDTS相对Sequential和Interleave算法有更低的Slack值，MDTS算法的Slack值最高比FCFS算法要减少59.1%，比Interleave算法要减少23.1%。

通过两组实验分析得出，MDTS算法在任务调度跨度、任务调度平均等待时间以及平均Slack方面均优于Sequential、Interleave算法。总体来讲，4个处理机下的任务调度比3个处理机环境下的任务调度效果更佳，MDTS算法在4个处理机环境中的性能比3个处理机环境下的性能更好。

5 小 结

文中首先对多个DAG任务进行合并，将多个DAG任务合并为一个DAG，在此基础上，提出了一种相关任务调度模型和相关任务调度算法MDTS算法。通过实验以及案例分析过程，MDTS算法在任务调度跨度、任务调度平均等待时间以及平均Slack方面均优于Sequential、Interleave算法。