Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910293831974912 |
|---|---|
| author | Sun, Binqi Theile, Mirco Qin, Ziyuan Bernardini, Daniele Roy, Debayan Bastoni, Andrea Caccamo, Marco |
| author_facet | Sun, Binqi Theile, Mirco Qin, Ziyuan Bernardini, Daniele Roy, Debayan Bastoni, Andrea Caccamo, Marco |
| contents | 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. The code is available at https://github.com/binqi-sun/egs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_14647 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning Sun, Binqi Theile, Mirco Qin, Ziyuan Bernardini, Daniele Roy, Debayan Bastoni, Andrea Caccamo, Marco Machine Learning Distributed, Parallel, and Cluster Computing Discrete Mathematics Optimization and Control 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. The code is available at https://github.com/binqi-sun/egs. |
| title | Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning |
| topic | Machine Learning Distributed, Parallel, and Cluster Computing Discrete Mathematics Optimization and Control |
| url | https://arxiv.org/abs/2308.14647 |