多云环境下基于代价驱动的科学工作流调度策略

摘要

Aiming at the deadline-constrained scientific workflow scheduling problem under multi-cloud environment, the concept of partial critical paths algorithm is introduced. A cost-driven scheduling strategy for scientific workflow is proposed to reduce the execution cost of workflow as much as possible and satisfy its deadline constraint. The characteristics of multi-cloud environment and scientific workflows are taken into account in this strategy. Firstly, the adjacent two tasks with a common directed cut-edge are merged into a single task based on the workflow structure. Then, the partial critical paths with subdeadline constraints are searched based on the critical parent iterative mechanism. Finally, the most suitable instances are allocated to the partial critical path and all the tasks in the path are scheduled to their corresponding instance. Various workflows are used for evaluating the proposed strategy and experimental results show that the proposed strategy has a better execution efficiency and a lower workflow execution cost.%针对多云环境下带截止日期约束的科学工作流调度问题，引入局部关键路径算法思想，提出基于代价驱动的科学工作流调度策略，目的是在满足科学工作流截止日期约束的同时，尽可能降低执行代价。该策略充分考虑多云环境和科学工作流的独有特性，首先根据工作流自身结构合并存在有向割边的相邻任务；再基于关键父任务迭代机制寻找带局部截止日期的局部关键路径；最后为局部关键路径分配最适合实例，并执行所有任务。实验表明，文中策略有效提高现有真实科学工作流的执行效率，并大幅减少执行代价。