Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning
- Resource Type
- Periodical
- Authors
- Sun, B.; Theile, M.; Qin, Z.; Bernardini, D.; Roy, D.; Bastoni, A.; Caccamo, M.
- Source
- IEEE Transactions on Computers IEEE Trans. Comput. Computers, IEEE Transactions on. 73(4):1034-1047 Apr, 2024
- Subject
- Computing and Processing
Task analysis
Processor scheduling
Job shop scheduling
Program processors
Real-time systems
Dispatching
Time factors
DAG scheduling
real-time
edge generation
deep reinforcement learning
- Language
- ISSN
- 0018-9340
1557-9956
2326-3814
Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications from the automotive, avionics, and industrial domains that implement their functionalities through chains of intercommunicating tasks. This paper studies the problem of scheduling real-time DAG tasks by presenting a novel schedulability test based on the concept of trivial schedulability . Using this schedulability test, we propose a new DAG scheduling framework ( edge generation scheduling—EGS ) that attempts to minimize the DAG width by iteratively generating edges while guaranteeing the deadline constraint. We study how to efficiently solve the problem of generating edges by developing a deep reinforcement learning algorithm combined with a graph representation neural network to learn an efficient edge generation policy for EGS. We evaluate the effectiveness of the proposed algorithm by comparing it with state-of-the-art DAG scheduling heuristics and an optimal mixed-integer linear programming baseline. Experimental results show that the proposed algorithm outperforms the state-of-the-art by requiring fewer processors to schedule the same DAG tasks. https://github.com/binqi-sun/egs