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

Directed acyclic graph application scheduling strategy based on critical path cut on cloud platform

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

To address the problems that the resource is surplus, the resource utilization rate is low and the cost is unreasonably high for virtual machines in the scientific application of DAG（directed acyclic graph）, a novel DAG scientific workflow scheduling algorithm based on CPC（critical path cut） was proposed. In the algorithm, the CPC technology was adopted to circularly find the unallocated task which is finished at last; the biggest connected subgraph was found from the graph constructed by the whole unallocated tasks; the critical path of this subgraph was calculated and the task set on the critical path was scheduled to the performance-matched virtual machine to execute. Meanwhile, the isolated tasks were used to fill in the idle slots of the virtual machines, such that the resource utilization could be improved. 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. 