基于关键路径前瞻的工作流调度算法

Workflow Scheduling Algorithm Based on Critical Path Lookahead

为了进一步提高工作流调度的效率,对异构环境下的工作流调度算法进行研究,提出了一种基于关键路径前瞻算法(critical path lookahead algorithm,CPLA)的工作流调度算法.该算法在任务确定优先级阶段考虑了入口任务到当前任务的最长路径,以及当前任务到出口任务的最长路径;在资源选择阶段考虑了关键路径任务和非关键路径任务对调度结果的影响.使用随机生成的和真实世界的2种不同类型的有向无环图(directed acyclic graph,DAG)工作流来评估CPLA的性能,实验结果表明:CPLA能够有效地缩短调度长度,算法的效率、加速比、调度长度比等性能有所提高,并且算法的时间复杂度低于目前调度效果最好的Lookahead算法.

To further improve the efficiency of workflow scheduling, a workflow scheduling algorithm in heterogeneous environment was s tu d ied, and a workflow scheduling algorithm based on critical path lookahead algorithm （ CPLA） was proposed.In the task priority stage, the longest path of the entry task to the current task was considered, and the longest path of the current task to exit task was also taken into consideration.In the resource selection stage,the impact of tasks of the critical path and asks of the non critical path on the scheduling results were considered. Two different types of DAGs which were randomly generated and from real-world were used to evaluate the performance of CPLA. The experimental results show that the CPLA can effectively shorten the scheduling length.The performances of this algorithm, such as efficiency, sp eed u p, scheduling length ratio of algorithm are improved, and the time complexity of the algorithm is lower than that of the lookahead algorithm.