###
:2019,28(3):118-125
本文二维码信息
码上扫一扫!
基于HEFT和CPOP的相关任务表调度算法
(1.广东第二师范学院 计算机科学系, 广州 510303;2.华南理工大学 计算机系统研究所, 广州 510006)
List Scheduling Algorithm of Dependent Tasks Based on HEFT and CPOP
(1.Department of Computer Science, Guangdong University of Education, Guangzhou 510303, China;2.Research Institute of Computer Systems, South China University of Technology, Guangzhou 510006, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 178次   下载 121
投稿时间:2018-09-12    修订日期:2018-10-08
中文摘要: DAG任务调度是当前研究的热点,DAG任务模型中任务的调度顺序一方面会影响用户服务满意质量,另一方面也会影响云服务资源的利用率,高效的任务调度算法能够使多核处理器的资源分配和并行计算能力更强.表调度算法HEFT算法以及CPOP算法在相关任务调度中存在效率较低等问题.本文基于HEFT算法和CPOP算法,提出了一种相关任务调度模型和相关任务调度算法IHEFT算法,对任务排序和任务调度两个方面进行改进.任务排序阶段,以任务的方差以及平均通信代价作为排序的依据;任务调度阶段,对满足任务复制条件的结点进行任务复制.实验证明,IHEFT算法在任务调度跨度、任务调度平均等待时间以及平均Slack值方面均优于HEFT算法和CPOP算法.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61772205);广东省科技计划项目(2014B010110004,2016A010106007,2016B090927010);广东第二师范学院网络工程重点学科(ZD2017004);广东第二师范学院计算机实验教学示范中心(SY2016014)
引用文本:
刘林东,邬依林.基于HEFT和CPOP的相关任务表调度算法.计算机系统应用,2019,28(3):118-125
LIU Lin-Dong,WU Yi-Lin.List Scheduling Algorithm of Dependent Tasks Based on HEFT and CPOP.COMPUTER SYSTEMS APPLICATIONS,2019,28(3):118-125

用微信扫一扫

用微信扫一扫