基于HEFT和CPOP的相关任务表调度算法

List Scheduling Algorithm of Dependent Tasks Based on HEFT and CPOP

DAG任务调度是当前研究的热点,DAG任务模型中任务的调度顺序一方面会影响用户服务满意质量,另一方面也会影响云服务资源的利用率,高效的任务调度算法能够使多核处理器的资源分配和并行计算能力更强.表调度算法HEFT算法以及CPOP算法在相关任务调度中存在效率较低等问题.本文基于HEFT算法和CPOP算法,提出了一种相关任务调度模型和相关任务调度算法IHEFT算法,对任务排序和任务调度两个方面进行改进.任务排序阶段,以任务的方差以及平均通信代价作为排序的依据;任务调度阶段,对满足任务复制条件的结点进行任务复制.实验证明,IHEFT算法在任务调度跨度、任务调度平均等待时间以及平均Slack值方面均优于HEFT算法和CPOP算法.

DAG task scheduling is the current hot topic.In task model of DAG,the order of task scheduling affect the service satisfaction of users on one hand,and also affect utilization rate of cloud service resources on the other hand.High efficient task scheduling algorithm may strengthen the resources distribution of the multi-core and the parallel computing ability.HEFT algorithm and CPOP algorithm are of lower efficiency in related task scheduling.Based on HEFT algorithm and CPOP algorithm,a dependent task scheduling model and task scheduling algorithm IHEFT(Improvement Heterogeneous Earliest Finish Time) algorithm are proposed in this study.The IHEFT algorithm mainly optimizes two aspects:task ordering and task scheduling.The variance of task scheduling cost on every processor core and the average communication overhead are the basis of task ordering.In the stage of task scheduling,task duplication of some nodes in DAG with some conditions can make full use of heterogeneous processor resources and shorten the completion time of task set.Experiment results show that the IHEFT algorithm performs more performance than the HEFT algorithm and the CPOP algorithm in terms of the task scheduling Makespan,the average waiting time and the average value of Slack.