一种面向通信开销的网格工作流调度算法

朱晓虹

（福建对外经济贸易职业技术学院　信息技术系，福建　福州　350012）

一种面向通信开销的网格工作流调度算法

朱晓虹

（福建对外经济贸易职业技术学院信息技术系，福建福州350012）

摘要：采用任务—资源分配图定义了网格任务调度模型，运用动态规划的方法提出了面向通信开销的工作流任务调度算法。采用扩展的拓扑排序算法对具有依赖关系的工作流任务进行划分，根据划分的任务子集得到相应的调度阶段，在每一阶段选择满足约束条件和以计算开销、通信开销以及任务执行成功率为最优目标函数的资源节点进行任务分配，从而使工作流任务调度目标函数最优。应用GridSim工具包实现了该调度算法，并与Min-Min算法进行对比分析。仿真结果表明，基于动态规划的网格工作流调度算法具有良好的适应性，且能较好地处理不同网络环境下任务间存在大量数据传输的网格调度问题。

关键词：网格计算；工作流；动态规划；通信开销

0　引言

移动互联网的发展使得地理位置上分散的计算资源可以协同工作，从而组成一个计算网格，实现资源共享［1-2］。由多个相互之间存在数据依赖或时序关系的网格任务组成的网格作业称为网格工作流作业。对于通信密集型的应用，在网格调度时仅仅考虑计算能力是不够的，还需要考虑通信需求。在海量数据的网格计算应用中，服务站点需要处理的数据量较为庞大，此时计算开销对于服务站点来说是影响性能的关键因素，为了保证网格计算性能，必须对分布的数据资源进行合理的调度管理［3］。文献［4］针对现有的网格工作流调度算法的不足，提出了AWSA算法，该算法充分考虑了节点的负载和服务能力，通过对任务的优先级进行排序来选择具有最大截止时间约束的站点作为最优的候选，然后根据动态负载变化情况来完成从资源到服务站点的映射。文献［5-6］提出了一种混合环境下的科学工作流执行系统架构并对其核心组件进行了阐述。针对其中的工作流调度问题，利用随机服务模型建模已有网格系统中资源的动态服务能力，以任务违约风险作为是否租借外部虚拟资源的判断指标，提出了一个科学的工作流调度算法HCA_SASWD。文献［7］提出一种用于解决具有截止时间约束的工作流调度算法（Min-Min），该算法在保证任务调度实时性的同时，有效地实现了服务站点的负载均衡。然而上述算法均没有考虑具有依赖关系的任务执行，并且通信开销已经给定，没有具体考虑通信开销对任务调度的影响。针对以上问题，笔者提出了一种面向通信开销的网格工作流调度算法，这一算法采用动态规划的思想，先用扩展的拓扑排序算法对工作流任务进行划分，分为若干个任务子集，每一个任务子集构成一个阶段。在每一个阶段综合考虑任务的计算开销和通信开销以及任务的执行成功率，使得每一阶段的任务在节点上的分配最优，从而得到任务完成时间最少的任务分配策略。

1　动态规划与任务调度模型

网格调度中，很多大规模应用有严格的截止时间约束，动态规划是用空间换时间的一种方法。建立动态规划模型主要有以下几个步骤［8］：①阶段划分；②确定状态变量Sk的含义及取值范围；③明确决策变量xk的含义及取值范围；④确定各阶段的状态转移方程Sk+1=T(Sk, xk(Sk))；⑤确定阶段指标vk(Sk, xk)和最优指标函数fk(Sk)；⑥推导出递推关系式。

本文所讨论的网格工作流是由一组有约束关系（如控制依赖，数据依赖）的子任务组合而成。由于网格的动态性和不确定性，任务分配到资源以后，资源在某些情况下可能会失效，因此在任务调度时引入了资源执行的成功率。

定义11网络工作流任务图（task graph）TG = < X, D, E, C>。其模型如图1所示，X是h个子任务的集合X = { x1, x2,…, xh}；Di=d(xi)表示每个子任务的计算量，D = { di| 0

图1　网格工作流任务图模型Fig.1 Grid task graph model

定义2网格资源分配图（grid resource）GR=(M, Q, B, P)。其模型如图2所示，M是网格计算资源的集合M={mi| 0≤i≤n}，m(xi)=Mj，Mj∈M表示给任务xi分配的资源节点；qi=q (mi)表示单位时间内资源mi的计算能力，即mi的执行速度，Q= { qi| 0≤i≤n }；bij=b ( mi, mj)为n个资源之间网络连接带宽组成的矩阵B= { bij| 0≤i, j≤n }；pi=p (mi)表示资源执行任务的成功率，P ={ pi| 0≤i≤n }。

网格调度的目标就是在满足给定的QoS约束条件下，按照某种策略选择最优的节点来对其进行任务分配。

图2　网格资源分配图模型Fig.2 Task resource assignment graph

本文讨论任务调度问题的前提是：①在工作流任务的调度中，当且仅当前驱任务执行完毕，后继任务才参与调度；②各资源节点之间可以相互通信，且bij=bji。当i=j时，bij=∞；③一个子任务只能由一个资源节点执行，一个节点只能同时执行一个任务，并且在一段时间内节点的计算性能相对稳定，即qi相对稳定；④每个子任务xi分配到资源节点m(xi)=mj，mj∈M。任务的完成时间ti包括两部分：计算时间tpi和通信时间tci，即ti=tpi+tci（i=1, 2,…, h）；⑤任务完成的计算时间由子任务的计算量和任务分配到的资源节点的计算性能决定，即tpi=d(xi)/ q (m(xi))；⑥任务完成的通信时间包括两部分，即数据传输时间和传输延长时间。数据传输时间由前驱任务和后继任务之间的数据传输量和所在网格资源之间的带宽决定；传输延长时间指的是由于当前网络系统负载存在不确定性，如网格跳数可能不同致使网络使用高峰期时传输速度的下降，用td表示。故通信时间tci=c(pre(xi),xi)/ b(m(pre(xi)),m(xi))+td。

每个子任务的目标函数包括两部分：任务的完成时间和任务的执行成功率。在调度中应优先选择任务完成时间最少，任务执行成功率最高的资源，使得子任务的目标函数最小，从而使整个网格工作流应用调度的目标函数最小。

2　基于动态规划的网格工作流调度算法

基于文献［8］建立的动态规划模型和本文所定义的任务调度模型，笔者提出了基于动态规划的网格工作流调度算法（workflow scheduling alogrithm based on dynamic programming，DPW）。DPW算法的主要思想是：首先用扩展的拓扑排序算法对工作流任务进行划分得到任务子集，根据任务子集得到不同的执行阶段。然后采用动态规划方法对每一阶段的任务进行最优规划和资源分配，使得每一阶段任务的目标函数最小，从而使网格系统的效益最大。具体步骤如下：

Step 1根据扩展的拓扑排序算法对网格工作流进行任务划分。算法描述如下：

A）在任务图中选择无前驱的任务顶点，形成一个集合；

B）从任务图中删除该顶点和所有以它为尾的依赖关系，然后转步骤A继续执行；

C）重复执行步骤A和B，直至所有的任务顶点均已输出，或者任务图中不存在无前驱的顶点为止；

D）根据以上算法得到k个任务子集，每一个任务子集用Sk表示。具体过程如图3所示，根据扩展的拓扑排序算法可得到{( x1, x2, x3)，( x4, x7)，( x5, x6)，( x8, x9)}4个任务子集，如S1为( x1, x2, x3)。

Step 2建立动态规划模型。过程描述如下：

A）根据Step1得到了k个任务子集，将调度过程划分为k个阶段；

B）状态变量Sk：当前k阶段应分配的任务集Sk；

C）决策变量Uk：xi任务( xi∈Sk)分配到相应的资源节点mj的效益函数；

E）最优目标函数递推关系：fk+1(Si+1)=min{gk+1(Sk,Uk)+fk(Sk)}。表示本阶段的目标函数是根据任务所在资源节点选择本阶段任务分配目标函数最小的资源。gk+1(Sk, Uk)表示当前阶段任务的完成时间与任务执行成功率的综合函数即

F）边界条件：初始任务没有前驱任务，没有前阶段，所以为0，即f1(S1)=0。

综上所述，网格中面向通信开销的工作流任务调度算法描述如下：

{while一个工作流应用被提交do

利用的拓扑排序算法将工作流任务分成任务子集Sk；

for每一阶段的子任务Sk选择满足动态规划约束条件和最优目标函数的网格资源节点进行调度；

endwhile }

图3　一个简单的工作流应用Fig.3 A simple workflow application

3　实验及分析

为了验证算法的性能，将本文中提出的DPW算法与Min-Min算法进行比较。利用GridSim仿真实验来模拟网格中需要被调度的计算任务和拥有的资源，整个实验步骤分为两个步骤：①网格任务的提交，负责模拟泊松分布提交待处理的计算任务；②任务分配，负责依据给定的调度算法来为任务指定合适的服务站点。

图4给出了资源同构环境下DPW算法与Min-Min算法对调度时间的影响。实验结果表明，DPW算法在资源同构时使网格具有更好的容错性并减少了整体的调度时间。

图4　两种算法在同构环境下调度时间的比较Fig.4 Comparison of scheduling time between two algorithms in a homogeneous environment

图5给出了资源异构环境下DPW算法与Min-Min算法对调度时间的影响。实验结果表明，随着数据传输量的加大以及资源能力差异的变大，数据传输时间所占的比例也越来越大，因而造成的影响也越来越明显，DPW算法与Min-Min算法相比调度长度明显减少。

图5　两种算法在异构环境下调度时间的比较Fig.5 Comparison of scheduling time between two algorithms in a heterogeneous environment

上述实验结果表明笔者提出的面向通信开销的网格工作流任务调度算法具有良好的适应性，且能较好地解决计算能力及网络带宽不同时，任务间存在大量数据传输的情况下DPW算法更优。

4　结语

网格计算中的工作流调度问题是目前的研究热点，针对现有的调度算法没有考虑通信开销对任务调度的影响这一不足，笔者提出了一种面向通信开销的网格工作流调度算法，其以扩展的拓扑排序算法对工作流任务进行划分为基础，充分考虑了计算开销和通信开销对于任务调度性能的影响，从而使工作流任务调度目标函数最优。最后的仿真实验也表明了该算法的有效性。

参考文献（References）

［1］王观玉.网格计算中任务调度算法的研究和改进［J］.计算机工程与科学，2011，33（10）：186-190.

［2］IOSUP A，EPEMA D.Grid computing workloads［J］.Internet Computing，IEEE，2011，15（2）：19-26.

［3］KUMAR P，RASTOGI R，GUPTA S K，et al.Performance parameters for load balancing algorithm in grid Computing［M］.Berlin：Springer，2012：333-336.

［4］王大伟，姜参.网格计算中一种改进的工作流调度算法［J］.计算机技术与发展，2014，24（2）：71-75.

［5］阎朝坤，胡志刚，罗慧敏.混合计算环境中截止期约束下的科学工作流调度策略［J］.计算机工程与科学，2012，34 （9）：40-46.

［6］林伟伟，齐德昱，李拥军，等.树形网格计算环境下的独立任务调度［J］.软件学报，2006，17（11）：2352-2361.

［7］KOKILAVANI T，AMALARETHINAM D I G.Load balanced Min- Min algorithm for static meta- task scheduling in grid computing［J］.International Journal of Computer Applications，2011，20（2）：43-49.

［8］邵晓曙，杨艳军.动态规划在消防增援调度中的应用［J］.武警学院学报，2008，24（8）：36-38.

（责任编辑：胡燕梅）

Grid Workflow Scheduling Algorithm Based on Communication Cost

ZHU Xiaohong
（Department of Information Technology，Fujian International Business & Economic College，Fuzhou 350012，Fujian，China）

Abstract：In this text，the author uses DAG graph and task-resource allocation graph to define the grid task scheduling model，and utilizes dynamic programming method to propose workflow task scheduling algorithm based on communication cost.By using extended topological sorting algorithm，dependent tasks are divided into subsets，according to them，obtains corresponding phases.At each stage，carries out task allocation of resource nodes which meet constraint conditions and optimal objective function based on computing cost，communication cost and the success rate of implementation，so it can get the most optimal workflow task scheduling.Uses the GridSim tool package to realize the scheduling algorithm，and compares with the Min- Min algorithm.Simulation results show that the proposed algorithm has good adaptability，and can solve grid scheduling problem better under different network environment and large number of data transmission circumstances.

Keywords：grid computing；workflow；dynamic planning；communication cost

作者简介：朱晓虹（1972—），女，副教授，硕士，研究方向：网格计算和信息安全。

基金项目：福建省教育厅A类科技项目（JA12403）

收稿日期：2015 - 03 - 18

DOI：10.16389/j.cnki.cn42-1737/n.2015.03.016

中图分类号：TP301.6

文献标志码：A

文章编号：1673-0143（2015）03-0278-05