DAG分割模型下的云工作流调度策略  

Cloud workflow scheduling strategy in DAG partition model

作　　者：薛凡[1] Xue Fan(College of Innovation&Entrepreneurship,Huanghuai University,Zhumadian Henan 463000,China)

机构地区：[1]黄淮学院创新创业学院

出　　处：《计算机应用研究》2019年第12期3725-3728,3734,共5页Application Research of Computers

摘　　要：为了优化云工作流调度的经济代价和执行效率,提出一种基于有向无环图(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.

关 键 词：云计算 科学工作流 调度优化 DAG分割 执行跨度 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]