Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning

• URL: http://arxiv.org/abs/2308.14647v2
• Date: Thu, 11 Jan 2024 00:20:15 GMT
• Title: Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning
• Authors: Binqi Sun, Mirco Theile, Ziyuan Qin, Daniele Bernardini, Debayan Roy, Andrea Bastoni, and Marco Caccamo
• Abstract summary: Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications. We propose a new DAG scheduling framework that attempts to minimize the DAG width by iteratively generating edges. We evaluate the effectiveness of the proposed algorithm by comparing it with state-of-the-art DAG schedulings and an optimal mixed-integer linear programming baseline.
• Score: 2.365237699556817
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. The code is available at https://github.com/binqi-sun/egs.

Related papers

• Plan-over-Graph: Towards Parallelable LLM Agent Schedule [53.834646147919436]
  Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning. This paper introduces a novel paradigm, plan-over-graph, in which the model first decomposes a real-life textual task into executable subtasks and constructs an abstract task graph. The model then understands this task graph as input and generates a plan for parallel execution.
  arXiv  Detail & Related papers  (2025-02-20T13:47:51Z)
• Chain-of-Retrieval Augmented Generation [72.06205327186069]
  This paper introduces an approach for training o1-like RAG models that retrieve and reason over relevant information step by step before generating the final answer. Our proposed method, CoRAG, allows the model to dynamically reformulate the query based on the evolving state.
  arXiv  Detail & Related papers  (2025-01-24T09:12:52Z)
• Prediction-Assisted Online Distributed Deep Learning Workload Scheduling in GPU Clusters [24.845122459974466]
  This paper proposes an adaptive shortest-remaining-processing-time-first (A-SRPT) scheduling algorithm. By modeling each job as a graph corresponding to heterogeneous Deep Neural Network (DNN) models, A-SRPT strategically assigns jobs to the available GPU. A-SRPT maps the complex scheduling problem into a single-machine instance, which is addressed optimally by a preemptive "shortest-remaining-processing-time-first" strategy.
  arXiv  Detail & Related papers  (2025-01-09T20:19:01Z)
• Instance-Aware Graph Prompt Learning [71.26108600288308]
  We introduce Instance-Aware Graph Prompt Learning (IA-GPL) in this paper. The process involves generating intermediate prompts for each instance using a lightweight architecture. Experiments conducted on multiple datasets and settings showcase the superior performance of IA-GPL compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-11-26T18:38:38Z)
• TS-EoH: An Edge Server Task Scheduling Algorithm Based on Evolution of Heuristic [0.6827423171182154]
  This paper introduces a novel task-scheduling approach based on EC theory and Evolutionary algorithms. Experimental results show that our task-scheduling algorithm outperforms existing and traditional reinforcement learning methods.
  arXiv  Detail & Related papers  (2024-09-04T10:00:32Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• GA-DRL: Graph Neural Network-Augmented Deep Reinforcement Learning for DAG Task Scheduling over Dynamic Vehicular Clouds [35.418964557667096]
  We propose a graph neural network-augmented deep reinforcement learning scheme (GA-DRL) for scheduling DAG tasks over dynamic VCs. GA-DRL outperforms existing benchmarks in terms of DAG task completion time.
  arXiv  Detail & Related papers  (2023-07-03T06:41:15Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• A Scalable Deep Reinforcement Learning Model for Online Scheduling Coflows of Multi-Stage Jobs for High Performance Computing [9.866286878494979]
  In multi-stage jobs, each job consists of multiple coflows and is represented by a Directed Acyclic Graph (DAG) In this paper, we propose a novel Pipelined-DAGNN to process the input and propose a novel coflow scheduling algorithm.
  arXiv  Detail & Related papers  (2021-12-21T09:36:55Z)
• Better than the Best: Gradient-based Improper Reinforcement Learning for Network Scheduling [60.48359567964899]
  We consider the problem of scheduling in constrained queueing networks with a view to minimizing packet delay. We use a policy gradient based reinforcement learning algorithm that produces a scheduler that performs better than the available atomic policies.
  arXiv  Detail & Related papers  (2021-05-01T10:18:34Z)
• Learning to Schedule DAG Tasks [7.577417675452624]
  We present a novel learning-based approach to scheduling directed acyclic graphs (DAGs) The algorithm employs a reinforcement learning agent to iteratively add edges directed to the DAG. Our approach can be easily applied to any existing scheduling algorithms.
  arXiv  Detail & Related papers  (2021-03-05T01:10:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.