Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning

Binqi Sun, Mirco Theile, Ziyuan Qin, Daniele Bernardini, Debayan Roy, Andrea Bastoni, Marco Caccamo

Research output: Contribution to journalArticlepeer-review

Abstract

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

Original languageEnglish
Pages (from-to)1034-1047
Number of pages14
JournalIEEE Transactions on Computers
Volume73
Issue number4
DOIs
StatePublished - 1 Apr 2024

Keywords

  • DAG scheduling
  • deep reinforcement learning
  • edge generation
  • real-time

Fingerprint

Dive into the research topics of 'Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning'. Together they form a unique fingerprint.

Cite this