云平台上基于关键路径截取的有向无环图应用调度算法

针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题,给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术,循环找出最晚完成的未分配任务,从该任务出发,在所有未分配任务构成的图中找出最大连通子图,并计算该子图的关键路径,然后将关键路径上的任务集调度到性能匹配的虚拟机上执行;同时通过任务回填技术充分利用虚拟机的空闲时间槽,提高资源使用率。实验结果表明,在云计算平台上,该算法不仅能够在截止时间内完成有向无环图科学应用,而且可以提高资源使用率,有效减少完成该应用所需整体费用。

Critical Path Cut Based DAG application Scheduling Strategy On Cloud Platform

The characteristics of cloud computing such as on-demand provisioning of virtual machines in a pay-as-you-go manner have attracted more and more scientific workflows deploying on cloud platforms. Since there are many types of virtual machines which are charged by time periods, the difficulties of resource provisioning and task scheduling hinders efficient execution of scientific workflows on cloud platforms. To address the challenge, a novel Critical Path Cut (CPC) based scientific workflow scheduling algorithm is proposed in this paper. The algorithm schedules tasks on appropriate virtual machine based on CPC strategy by analyzing the dependencies of the tasks; meanwhile, it uses the isolated tasks to fill in the idle slots of the virtual machines, such that the resource utilization can be improved without affecting the overall performance. Experimental results demonstrate that, the proposed CPC algorithm can effectively reduce the execution cost of the scientific workflows while satisfying the deadline constraint in mean time.