Research On Intelligent Scheduling Algorithms For DAG Tasks Based On Deep Reinforcement Learning

DAG(Directed Acyclic Graph)task scheduling in distributed heterogeneous computing systems is one of the hot issues in the field of computer architecture research,and scheduling models and scheduling algorithms are the two most important aspects of DAG task scheduling.How to assign reasonably tasks to different processors to get the shortest completion time is a problem that needs to be solved by task scheduling.In addition,DAG tasks with new applications have many kinds of computing tasks and complex parallel dependencies,traditional heuristic-based task scheduling algorithms cannot easily adapt to both software and hardware environment changes,which results in the decreased system efficiency.Using machine learning method to solve the challenges faced by the heuristic-based method is the future trend in system research field.To solve the problem of adaptive scheduling of DAG tasks in heterogeneous computing systems,this paper proposes to design and implement a self-learning smart scheduling algorithm using deep learning and reinforcement learning methods in various application scenarios.The main contributions of this paper include:(1)Design of DAG task smart scheduling model in distributed heterogeneous computing system.In the distributed heterogeneous computing system,the smart scheduling model of DAG tasks mainly involves the representation of DAG task scheduling model,scheduling target,scheduling state,scheduling action and scheduling reward function based on reinforcement learning.(2)A scheduling algorithm based on a combination of deep learning and reinforcement learning.In this paper,we propose an adaptive DAG task scheduling(ADTS)algorithm using deep reinforcement learning.The scheduling problem is properly defined in the reinforcement learning process.An efficient scheduling state space,action space and reward function are designed to train the REINFORCE agent based on the policy gradient.Using this algorithm to explore the ability of long-term rewards,the ADTS algorithm can achieve a good scheduling strategy.The experimental results show that the proposed ADTS algorithm has certain effectiveness compared with the classical HEFT and CPOP algorithms.(3)Smart DAG task scheduling algorithm based on Monte Carlo tree search.In this paper,we propose a smart DAG task scheduling algorithm based on single-player Monte Carlo tree search(MCTS).The MCTS method is used to determine the actual scheduling strategy.In the process of task scheduling,the algorithm balances the relationship between exploration and exploitation.The experimental results show that the proposed single-player MCTS algorithm is more effective than the classical HEFT,CPOP and PEFT algorithms.