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

摘要

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

主权项

1.一种基于工作流吞吐量最大化的工作流调度方法，其特征在于，考虑多个工作流在异构分布式计算资源上调度，通过执行期限约束的工作流吞吐量最大化设计，充分利用计算资源，从而提高工作流的调度效率；所述方法包括以下步骤：步骤1，用户提交具有执行期限约束的工作流；多个用户向工作流调度系统提交具有执行期限约束的的工作流，要求该工作流必须在规定的时间内完成；如果工作流不能在规定时间内完成，反馈信息给用户，用户根据反馈信息选择下一步活动；如果工作流能够在规定的时间内完成，则将工作流的各个任务映射到异构分布式计算资源上调度执行；步骤2，将工作流转换为有向无环任务模型图DAG；步骤2.1，对每一个用户提交的工作流进行预处理；（1）用G=(V，E)表示DAG任务模型图；DAG任务模型图中各个参数的含义如下：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的输出数据完整送达以后才能开始执行；有向边的权重值：任务结点之间的数据传递的时间用有向边的权重值表示；当同一个DAG任务模型图的不同任务结点n_i和n_j在同一个计算资源上执行时，任务结点ni的输出数据不经过网络传输就能被任务结点n_j接收，有向边(n_i，n_j)的权重值为0；当n_i和n_j在不同的计算资源上执行时，由于不同的计算资源之间是通过网络进行连接，因此有向边(n_i，n_j)的权重值不为0；出入口结点：在DAG任务模型图中，没有父结点的结点称为DAG入口结点，没有子结点的结点称为DAG出口结点，每个DAG任务模型图有且仅有一个入口结点和一个出口结点；（2）制作表示某个任务结点在某计算资源上的计算时间二维表W；对每个任务进行分类，对每一类固定类型的任务结点，根据以往的经验值可以得出该任务结点在某计算资源上需要多少计算时间，从而得到一个n×m的二维表W，二维表的值表示某个任务结点在某计算资源上的计算时间，n为该DAG任务模型图中任务结点的数量，m为用于执行工作流计算的异构分布式计算资源的数量；所述异构分布式计算资源对同一个任务结点的计算时间是不相同的，因此，对同一个任务结点，在不同的计算资源上有一个不同的计算时间；步骤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任务结点进行调度；步骤4，输出工作流吞吐量最大化调度方案，并将其返回给用户；步骤5，按照步骤4输出的工作流调度方案，将用户提交的工作流映射到具体的计算资源上执行，完成工作流调度。