异构计算环境下基于优先队列划分的调度算法  

Scheduling Algorithm Based on Priority Queue Dividing in Heterogeneous Computing Environment

作　　者：王兰 张龙信 满君丰 周立前 李肯立 WANG Lan;ZHANG Long-xin;MAN Jun-feng;ZHOU Li-qian;LI Ken-li(School of Computer Science,Hunan University of Technology,Zhuzhou 412007,China;College of Computer Science and Electronic Engineering,Hunan University,Changsha 410082,China)

机构地区：[1]湖南工业大学计算机学院,湖南株洲412007 [2]湖南大学信息科学与工程学院,长沙410082

出　　处：《小型微型计算机系统》2020年第2期303-309,共7页Journal of Chinese Computer Systems

基　　金：国家重点研发计划“云计算和大数据”重点专项子课题项目(2018YFB1003401)资助;国家自然科学基金项目(61702178,61672224,61871432,61702177)资助;湖南省自然科学基金项目(2019JJ50123,2018JJ4063,2019JJ60008)资助;湖南省教育厅重点项目(17A052,16A059)资助;中国国家留学基金项目(201808430297)资助.

摘　　要：人工智能的飞速发展对高性能计算提出了更高的要求,异构计算环境下任务调度问题一直是高性能计算中的关键问题.本文提出一种基于优先队列划分的调度算法(PQDSA),该算法根据DAG(有向无循环图)任务集的入口节点数量确定优先队列数,通过任务的通信开销和计算开销划分任务队列,进而将关键节点任务分配给合适的队列,以产生效果较佳的任务调度队列,从而提高任务间的并行性,降低任务集的完工时间.与此同时,进一步基于插入策略将任务调度到处理器上,使任务调度更加高效地执行.PQDSA算法可以减少任务间的时间消耗,提高处理器的调度效率.通过与两个经典算法的性能对比,实验结果表明本文提出的PQDSA算法在任务完工时间和调度效率方面都要明显优于对比的算法.With rapid development of artificial intelligence,researchers pay more and more attentions to high performance computing which can improve performance of artificial intelligence.The task scheduling problem in heterogeneous computing environment has always been a key issue in high performance computing.In this paper,we propose a scheduling algorithm based on priority queue dividing(PQDSA).The algorithm determines the number of queues according to the number of entry nodes of the DAG(Directed acyclic graph),divides the priority task queue by the communication overhead and computational overhead of the task,and then assigns the critical node tasks to the appropriate queue to generate a better task scheduling queues.It thereby can improve the parallelism of parallel tasks and reduce the task set completion time.While satisfying the priority constraints,tasks are further scheduled based on the insertion strategy to appropriate processors,so that task scheduling can be executed more efficiently.The PQDSA algorithm can reduce the completion time of task set and improve the scheduling efficiency of processors.By comparing the performance with two classical algorithms,our experimental results show that our presented novel algorithm(PQDSA)obtains greater task completion time and scheduling efficiency than two classical algorithms.

关 键 词：优先队列划分 高性能计算 完工时间 调度效率 

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