一种基于DAG图划分的网格关联任务调度算法

A Scheduling Algorithm of Related Tasks Based on DAG Graph in Grid

网格计算中的大型应用程序往往被分解为多个关联任务.对于这类应用,任务间的依赖是一个不可忽略的因素.传统算法只能将其视为元任务来考虑,限制了对任务粒度的进一步划分,从而大大降低了任务调度的性能.本文提出一种基于DAG图划分的关联任务调度算法.它优先调度关键路径上的任务,同时利用任务复制的方法充分利用资源上的时间碎片,保证依赖关系及时得到满足.仿真结果表明,对于网格环境下的大规模关联任务,该算法有效地提高了作业执行速度和资源使用效率.

Large scale applications are usually divided into multiple tasks in grid computing environment.For such applications,the interdependence of these tasks is an essential factor.Traditional algorithms these tasks can only be regarded as meta-task,thus it limits the further division of these tasks and greatly reduces the performance of task scheduling.This paper presents a related task scheduling algorithm based on DAG.It preferentially schedules the tasks which are on the critical path and takes advantage of pieces of time by using task duplication to ensure that dependencies are met in a timely manner.The Experimental results show that this algorithm can improve the speed of operating and the utilization efficiency of resources for the large scale related tasks in grid environment.