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

人工智能的飞速发展对高性能计算提出了更高的要求,异构计算环境下任务调度问题一直是高性能计算中的关键问题.本文提出一种基于优先队列划分的调度算法(PQDSA),该算法根据DAG(有向无循环图)任务集的入口节点数量确定优先队列数,通过任务的通信开销和计算开销划分任务队列,进而将关键节点任务分配给合适的队列,以产生效果较佳的任务调度队列,从而提高任务间的并行性,降低任务集的完工时间.与此同时,进一步基于插入策略将任务调度到处理器上,使任务调度更加高效地执行.PQDSA算法可以减少任务间的时间消耗,提高处理器的调度效率.通过与两个经典算法的性能对比,实验结果表明本文提出的PQDSA算法在任务完工时间和调度效率方面都要明显优于对比的算法.

Scheduling Algorithm Based on Priority Queue Dividing in Heterogeneous Computing Environment

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.