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

Grid Workflow Scheduling Algorithm Based on Communication Cost

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

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.