摘要
为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无环图(DAG)分割的工作流调度算法PBWS。以工作流调度效率与代价同步优化为目标,算法将调度求解过程划分为三个阶段进行:工作流DAG结构分割、分割结构调整及资源分配。工作流DAG结构分割阶段在确保任务间执行顺序依赖的同时求解初始的任务分割图;分割结构调整阶段以降低执行跨度为目标,在不同分割间对任务进行重分配;资源分配阶段旨在选择代价最高效的任务与资源映射关系,确保资源的总空闲时间最小。利用五种科学工作流DAG模型对算法进行了仿真实验。结果表明,PBWS算法仅以较小的执行跨度为开销,极大降低了工作流执行代价,实现了调度效率与调度代价的同步优化,其综合性能是优于同类型算法的。
For optimizing the economical cost and scheduling efficiency of cloud workflow scheduling,this paper proposed a workflow scheduling algorithm PBWS based on DAG( directed acyclic graph) partition. With the goal of optimizing synchronously the workflow scheduling efficiency and cost,this algorithm divided the scheduling solution into three stages: In the process of workflow DAG structure partition,partition structure adjustment and resource allocation. In the process of workflow DAG structure partition,it got the initial tasks partition graph when guaranteeing the execution order-dependency between tasks.In the process of partition structure adjustment,it re-allocated tasks in different partitions with a goal of reducing execution makespan. In the process of resource allocation,it determine the most cost-efficient matches between tasks and resources to ensure the minimization of the total idle time of resource. This paper constructed some simulation experiments for algorithms by the five types of scientific workflow DAG model. The experimental results show that PBWS algorithm can greatly reduce the execution cost of workflow in terms of cost by a little of overhead on execution makespan and realize the synchronous optimization of the scheduling efficiency and the scheduling cost,whose overall performance performs better than the same type of algorithms.
作者
薛凡
Xue Fan(College of Innovation&Entrepreneurship,Huanghuai University,Zhumadian Henan 463000,China)
出处
《计算机应用研究》
CSCD
北大核心
2019年第12期3725-3728,3734,共5页
Application Research of Computers
关键词
云计算
科学工作流
调度优化
DAG分割
执行跨度
cloud computing
scientific workflow
scheduling optimization
DAG partition
execution makespan
