一种基于工作流吞吐量最大化的工作流调度方法

摘要

本发明涉及一种基于工作流吞吐量最大化的工作流调度方法，包括：用户提交具有执行期限约束的工作流；将工作流转换为有向无环任务模型图DAG；进行DAG任务结点调度；输出工作流吞吐量最大化调度方案，并将其返回给用户；将用户提交的工作流映射到具体的计算资源上执行，完成工作流调度。本发明所述方法考虑多个工作流在异构分布式计算资源上调度，并使工作流完成的数目尽可能多，计算资源利用尽可能充分，克服了现有EDF方法不能根据DAG的不同特征确定调度顺序的缺点，大大提高工作流调度系统的效率，减少了由于没有在规定时间内完成计算而带来的损失，提高系统的用户体验。

说明书

技术领域

本发明涉及工作流调度技术领域，尤其涉及一种具有执行期限约束的使工作流吞吐量最 大化的工作流调度方法。

背景技术

工作流可以看作由多个基本任务组成的集合，某些任务之间具有先后顺序和数据传递依 赖关系。工作流调度技术是异构分布式计算领域中的关键技术，它直接影响到异构分布式计 算环境下工作流调度系统的运行效率和异构分布式计算资源的利用率。

目前有关异构分布式计算环境下的多DAG混合调度的研究文献分别在执行时间最小化、 公平性最大化、吞吐量最大化或资源分配优化等方面已经取得了一些进展。但在很多情况下， 用户根据应用需要可以进一步对DAG执行的有关属性和限制条件等进行描述及定义，而期 限约束是其中重要的限制条件之一。因此当一个DAG应用有了用户定义的期限约束，其调 度执行就不再以执行时间最小化为目标，而只需要在用户指定的期限之前完成即可。解决具 有期限约束的多DAG共享资源调度的吞吐量最大化问题，将会对提高多DAG应用调度的吞 吐率、提高资源利用率和节省DAG应用执行的费用等方面有重要意义。

著名学者Theodore P.Baker发表在IEEE上的文章An analysis of EDF schedulability on a  multiprocessor提出的解决具有期限约束的多个工作流调度问题的EDF（Earliest Deadline First） 方法，其基本思想是任务的期限约束越早，其任务将会越早被调度，又如学者GEORGIOS L 和STAVRINIDES HELEN D，在2010年发表于Journal of Systems and Software上的Scheduling  multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise  computations就是借鉴了EDF的思想，将每个DAG的期限约束作为优先级值来确定多个DAG 之间任务调度的优先级关系，虽然采取这种方法在多个DAG的结构和任务量大小相近的情 况下会有较好的效果，但是在很多情况下，DAG期限约束的绝对值不足以反应多个结构不同 DAG之间的紧急程度关系。例如，A和B两个DAG共享一定数量的一组资源同时进行混合 调度，其中A的期限约束（设为DA）较为紧急，接近其Makespan（在某个时间最小化算法 下的对DAG单独进行调度的时间长度，称为Makespan），而B的期限约束（设为DB）大约 为其Makespan的2倍。但如果B的任务量较小，很有可能会出现DB<DA的情况，按照EDF 方法，A的任务只有在B中所有任务优先被调度完毕后才能被调度，那么A将不能在DA之 前完成。

发明内容

针对现有技术中存在的上述问题，本发明提出一种在工作流调度系统中使用的具有执行 期限约束的工作流吞吐量最大化的方法，即考虑多个工作流在异构分布式计算资源上调度， 并使工作流完成的数目尽可能多，计算资源利用尽可能充分，这样就能够大大提高工作流调 度系统的效率，减少由于没有在规定时间内完成计算而带来的损失，提高系统的用户体验。

为了达到目的，本发明采用以下技术方案。

一种基于工作流吞吐量最大化的工作流调度方法，包括以下步骤：

步骤1，用户提交具有执行期限约束的工作流。

多个用户向工作流调度系统提交具有执行期限约束的的工作流，要求该工作流必须在规 定的时间内完成。如果工作流不能在规定时间内完成，反馈信息给用户，用户可以根据反馈 信息选择下一步活动；如果工作流能够在规定的时间内完成，则将工作流的各个任务映射到 异构分布式计算资源上调度执行。

步骤2，将工作流转换为有向无环任务模型图DAG（Directed Acyclic Graph）。

当多个工作流同时进入到调度系统时，如果要对工作流进行调度，就必须对工作流进行 预处理，将工作流转换为能够被识别和处理的DAG任务模型图。具体方法如下。

步骤2.1，对每一个用户提交的工作流进行预处理。

（1）用G=(V，E)表示DAG任务模型图。

DAG任务模型图如图2所示，各个参数的含义如下：

G=(V，E)中的V和E：V表示v个任务结点的集合，每个结点代表工作流的一个任务，称为 任务结点；E表示e条有向边的集合，每条边代表任务结点之间的先后顺序和数据传递依赖关 系。DAG任务模型图由v个任务结点和e条有向边构成。

有向边：DAG任务模型图的任意一条有向边记为(n_i，n_j)，n_i是有向边的尾任务结点，n_j是有向边的头任务结点，i和j分别表示任务结点n_i和n_j在DAG任务模型图中的编号，且满足i<j。 有向边(n_i，n_j)表示任务结点n_i和n_j之间的先后顺序和数据传递依赖关系，即任务结点n_j必须在 任务结点n_i的输出数据完整送达以后才能开始执行。具体结构参见图2。

有向边的权重值：任务结点之间的数据传递的时间用有向边的权重值表示。当同一个 DAG任务模型图的不同任务结点n_i和n_j在同一个计算资源上执行时，任务结点n_i的输出数据不 经过网络传输就能被任务结点n_j接收，有向边(n_i，n_j)的权重值为0；当n_i和n_j在不同的计算资源 上执行时，由于不同的计算资源之间是通过网络进行连接，因此有向边(n_i，n_j)的权重值不为0， 如图2中(n₃，n₇)的权重值为23，即它们之间的数据传输时间是23。

出入口结点：在DAG任务模型图中，没有父结点的结点称为DAG入口结点，没有子结点 的结点称为DAG出口结点，每个DAG任务模型图有且仅有一个入口结点和一个出口结点。

（2）制作表示某个任务结点在某计算资源上的计算时间二维表W。

对每个任务进行分类，对每一类固定类型的任务结点，根据以往的经验值可以得出该任 务结点在某计算资源上需要多少计算时间，从而得到一个n×m的二维表W，二维表的值表示 某个任务结点在某计算资源上的计算时间，n为该DAG任务模型图中任务结点的数量，m为用 于执行工作流计算的异构分布式计算资源的数量。

所述异构分布式计算资源对同一个任务结点的计算时间是不相同的，因此，对同一个任 务结点，在不同的计算资源上有一个不同的计算时间。

具体的二维表W可以参见表1，表W中的w_1,1=14，表示任务结点n₁在计算资源M₁上计算 需要14个单位的时间，这里的时间单位可由系统设定为小时，分钟，或秒，但必须统一。

表1任务结点在计算资源上的计算时间表

步骤2.2，计算DAG任务模型图中每个任务结点的向上rank值，公式如下：

${\mathrm{rank}}_u\left(n_i\right)=\overline{w_i}+\underset{n_j\in \mathrm{succ}\left(n_i\right)}{\max }(\overline{c_{i,j}}+{\mathrm{rank}}_u\left(n_j\right))$

式中，为任务n_i在m个计算资源上的平均计算时间，w_i,k表示任务结点n_i在 计算资源M_k上的计算时间；succ(n_i)为任务结点n_i的子任务结点集合；c_i,j＝L_m+data_i,j/B_m,n为 任务结点n_i和n_j在分配的两个计算资源M_m和M_n上的数据传输时间，L_m表示计算资源M_m的数据 传输启动时间，data_i,j表示从任务结点n_i到任务结点n_j传输的数据量，任意两个结点之间的数 据传递量可以表示为矩阵Data_v×v，B_m,n表示从计算资源M_m到计算资源M_n的数据传输速率，L_m和B_m,n都是异构分布式计算环境的已知参数，如果n_i和n_j被分配在了同一个计算资源上，即 m=n，则忽略计算资源内部的数据传递时间，即c_i,j=0；是任务结点n_i和n_j之间的数据传递的平均时间，表示计算资源数据传输启动时间的均值，为数据在计算资 源间的平均传输速率，和都是异构分布式计算环境的已知参数。

出口任务结点n_exit的向上rank值因为任务结点n_exit没有子结点， 表示出口结点n_exit的任务在m个计算资源上的平均计算时间，当n_i=n_exit时， rank_u(n_i)＝rank_u(n_exit)。

在计算DAG任务模型图的每一个任务结点的向上rank值时，将作为计算 的初始值，从出口任务结点n_exit的向上rank值开始向前推导，即可计算出余下任务结点的向上 rank值。

rank值可用作任务结点进行调度的优先级，任务结点的向上rank值越大，优先级越高。 优先选择优先级高的任务结点进行调度。

步骤3，进行DAG任务结点调度。

步骤3.1，输入一组步骤2得到的待调度的DAG，每一个待调度有向无环任务模型图G_i具有相应的执行期限约束将该G_i的任务结点按照由步骤2计算得到的向上rank值 的大小排序形成一个待调度的任务队列。

步骤3.2，对DAG任务结点进行调度，具体方法如下：

（1）如果所有的DAG调度完毕，则结束本次调度；否则，转步骤3.2（2）。

（2）计算G_i的相对严格程度值r，公式如下：

$r=m_{\mathrm{un}\left(G_i\right)-S_{\mathrm{HEFT}}}/m_{\mathrm{avail}-\mathrm{un}\left(G_i\right)}$

$m_{\mathrm{un}\left(G_i\right)-S_{\mathrm{HEFT}}}={\mathrm{tf}}_{\mathrm{un}\left(G_i\right)-S_{\mathrm{HEFT}}}-{\mathrm{ts}}_{\mathrm{un}\left(G_i\right)-S_{\mathrm{HEFT}}}$

$m_{\mathrm{avail}-\mathrm{un}\left(G_i\right)}=t_{\mathrm{Deadline}-G_i}-{\mathrm{ts}}_{\mathrm{un}\left(G_i\right)-S_{\mathrm{HEFT}}}$

式中，un(G_i)表示在调度过程的某个时间点上，Gi未被调度的任务结点的集合；下标 un(G_i)-S_HEFT表示使用HEFT（Heterogeneous Earliest Finish Time，异构环境最早完成时间） 算法调度un(G_i)的任务结点；表示un(G_i)的执行时间，和分别 表示un(G_i)中在计算资源上最早的开始和结束时间；表示un(G_i)的可用时间。

（3）如果所有的r值都满足0<r<1，则选择r值最大的DAG任务模型图进行调度，具 体过程是在该DAG中选择一个向上rank值最高的任务结点，即待调度队列队首的任务结点， 进行调度，将任务结点压入预先设置的任务结点栈内中，并从该DAG待调度任务结点队列 中删除该任务结点，然后转步骤3.2（1）；否则，转步骤3.2（4）。

（4）如果存在一个DAG任务模型图的r值等于1，且其它DAG任务模型图的r值满足 0<r<1，选择r=1且执行时间最长的DAG任务模型图进行调度，具体过程是将该DAG任务 模型图的所有剩余的任务结点都进行调度，将它们压入预先设置的任务结点栈内，并在未调 度完成的DAG任务模型图集合中删除该DAG任务模型图，然后转步骤3.2（1）；否则，转 步骤3.2（5）。

（5）如果存在DAG任务模型图的r值满足r>1或者r<0的情况，则表示在上一次任务 调度之后，出现了某些DAG任务模型图的任务结点不能在执行期限内完成的情况，即“过 饱和”情况，如果这种情况不是连续第二次出现，则可以采用“堆栈”与“调度回溯”相结 合的机制来处理，具体过程是取消上一次调度的压入任务栈的所有任务结点，将其返回到所 属的DAG任务模型图待调度队列，如果该DAG任务模型图已经从待调度DAG集合中删除， 则将该DAG再次加入到待调度的DAG集合，然后从r>1或者r<0的DAG任务模型图中选 择一个执行时间最长的DAG任务模型图进行调度，具体过程是将该DAG任务模型图的所有 剩余任务结点都进行调度并压入任务结点栈内，并且在未调度完成的DAG集合中删除该 DAG任务模型图，然后转步骤3.2（1）；否则，转步骤3.2（6）。

（6）如果存在DAG的r值满足r>1或者r<0的情况且这种情况是连续第二次出现，则 删除r值满足r>1或者r<0的DAG任务模型图中任务调度完成比例最低的一个DAG，并从 任务结点栈内弹出该被删除DAG任务模型图的所有任务结点，然后转步骤3.2（1）。

步骤4，输出工作流吞吐量最大化调度方案，并将其返回给用户。

步骤5，按照步骤4输出的工作流调度方案，将用户提交的工作流映射到具体的计算资 源上执行，完成工作流调度。

与现有技术相比，本发明具有以下明显优势：

（1）本发明通过计算输入到工作流调度系统的DAG的调度紧急程度，对紧急程度高的 DAG给予优先调度权限，当调度完DAG的一个任务之后，重新计算DAG的调度紧急程度， 调整调度优先权，克服了现有EDF方法不能根据DAG的不同特征确定调度顺序的缺点，大 大提高了调度的灵活性。

（2）本发明根据调度紧急程度确定DAG的调度顺序，相较于EDF的多DAG混合调度， 真正实现了细粒度的混合调度；本发明基于工作流的吞吐量最大化对工作流进行调度，大大 提高了资源利用率和工作流调度效率，减少了由于没有在规定时间内完成计算而带来的损失， 提升了用户的系统体验。

附图说明

图1为本发明所涉及方法的流程图；

图2为DAG任务模型图；

图3为实施例工作流调度系统结构示意图；

图4为需要调度的3个不同工作流的DAG任务模型图。

具体实施方式

下面将结合附图和实施例对本发明做进一步说明。

本发明实施例实现了一种工作流调度系统，按照图3所示的系统结构图进行构建，系统 至少包括用户提交工作流，工作流转换为DAG任务模型图，使用DAG调度器按照调度方法 进行DAG调度，输出工作流调度方案和工作流映射到计算资源上等五个过程，流程图如图1 所示，包括以下步骤：

1.用户提交工作流。

对于一个的工作流调度系统，用户首先向其提交工作流，用户可以对工作流设置一定的 服务质量要求，如规定该工作流必须在某个时刻之前完成，如果工作流调度系统在用户的服 务质量要求下能够完成工作流调度执行，那么就可以在最后将工作流调度方案反馈给用户， 将工作流映射到计算资源上。

2.将工作流转换为DAG任务模型图。

对于用户提交的工作流，如果需要在系统实现工作流调度，那么就需要将工作流转换为 系统可以识别的DAG任务模型图，其中工作流中的每个任务对应着DAG任务模型图的一个 结点，而工作流任务的相互依赖和数据传递关系则可以通过DAG任务模型图的有向边给出。

3.进行DAG任务模型图的任务结点调度。

将工作流转换为工作流调度系统可以识别的DAG任务模型图后，工作流调度系统的 DAG调度器将使用本发明提出的调度方法对DAG进行调度；

假设有3个不同工作流需要通过调度器（Scheduler）同时在3个处理机器M1、M2和 M3资源上调度执行，模型图分别为DAG-A、DAG-B和DAG-C，如图4所示。图4给出了 这3个DAG中任务结点间先后执行的约束关系和数据传递的平均时间各DAG中的任 务n_i在3个处理机器上的执行时间w_i,1、w_i,2、w_i,3和任务n_i的向上权值rank_u(n_i)，如表2所示。

表2各个DAG中任务的执行时间及其rank_u(n_i)值

n_iA1 A2 A3 A4 A5 B1 B2 B3 B4 C1 C2 C3 C4 w_i,113 11 26 21 7 15 12 13 10 11 13 9 12 w_i,211 10 22 19 6 13 10 12 8 7 11 7 10 w_i,310 9 19 15 5 11 8 11 6 5 9 5 8 rank_u(n_i) 53.7 20.0 36.3 34.3 6.0 49.0 20.0 27.0 8.0 36.7 24.0 21.0 10.0

根据图4和表2的数据，利用算法HEFT很容易得出3个DAG这在这3个机器上单独 调度Makespan：t_Makespan-A=43，t_Makespan-B=36，t_Makespan-C=27。根据任何一个DAG的期限约束 都大于其Makespan的假设，这里随机假设A、B和C的期限约束分别为t_Deadline-A=52、t_Deadline-B =73和t_Deadline-C=33。然而，要将上述具有期限约束的3个DAG在这3个机器上同时调度， 情况将变得较为复杂。如果选用EDF方法，总是选用期限约束最小的DAG优先调度，那么 C的t_Deadline-C=33最小，用HEFT优先调度C中所有任务，然后再用HEFT调度A，最后调 度B，很可能会造成A或B不能在期限内完成。在本发明方案中，根据公式计算A，B和C 的调度紧急程度得到A的调度紧急程度最高，那么选择A中rank值最高的任务进行调度。 当任务调度完毕之后，在任务已占用了资源的情况下，重新计算DAG的调度紧急程度，发 现DAG的调度紧急程度发生了变化，此时C的紧急程度已变为最高，所以选择C中的任务 进行调度。重复上述步骤，直到所有DAG任务调度完毕。本发明中的调度方法可以根据DAG 的调度紧急程度的动态变化而灵活做出调度调整，既可以充分利用计算资源又不会出现DAG 不能在期限约束内不能完成的现象。

4.输出工作流调度方案。

经过上面的DAG任务调度，即实现了对工作流中任务的调度，如果DAG调度成功，输 出工作流调度方案，否则将调度失败的信息反馈给用户。

5.将工作流映射到计算资源。

将工作流调度系统的结果反馈给用户，如果DAG调度成功，反馈工作流调度方案，并 在得到用户确认以后，将工作流映射到计算资源上调度执行，即可完成工作流的调度；如果 DAG调度失败，用户根据反馈信息进行下一步活动选择。