New Method for Real-Time Task Placement and Scheduling Using Reinforcement Learning
Explore a novel approach for real-time task placement and scheduling utilizing reinforcement learning algorithms in the context of designing a Real-Time Embedded Distributed System (RTEDS). The paper introduces the system formalization, deployment models, and the application of Q-learning for task optimization.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
SEKE 2023 JULY 2023 PSRL: A New Method for Real-Time Task Placement and Scheduling Using Reinforcement Learning Paper ID : #178 Bakhta Haouari1,3*, Rania Mzid1,2* and Olfa Mosbahi3,4* 1*ISI, University Tunis-El Manar, 2 Rue Abourraihan Al Bayrouni, Ariana, 2080, Tunisia. 2*CES Lab ENIS, University of Sfax, B.P:w.3, Sfax, 3038, Tunisia. 3*LISI Lab INSAT, University of Carthage, INSAT Centre Urbain Nord BP 676, Tunis, 1080, Tunisia. 4*National Institute of Applied Sciences and Technology (INSAT), University of Carthage, INSAT Centre Urbain Nord BP 676, Tunis, 1080, Tunisia.
Plan : Introduction System formalization Reinforcement Learning Proposed approach Evaluation Conclusion and extension 2
Introduction: Subject : The Design model of a Real-Time Embedded Distributed System (RTEDS): the best order of a set of tasks on a set of distributed processors Objectives : Definition of an appropriate deployment model Exaustive generation of feasible placements of the application tasks on distributed processors Respect of timing constraints Generation of the optimal scheduling model Minimization of the sum tasks response times 3
System formalization: The tasks scheduling involves three models: The task model : n synchronous, periodic, and independent tasks { Ti = (Ci, Pi,Di) }: o Ci is an estimation of its worst case execution time, o Pi is the activation period of the task Ti o Di is the deadline that represents the time limit in which the task Ti must complete its execution The execution model (platform) : m homogeneous processors (i.e., P = {P1, P2, . . . , Pm}). o Each processor has its own memory and runs a Real-Time Operating System (RTOS). The deployment model : a set of tuples D = {(P1, 1), (P2, 2), . . . (Pk, k)} o k : The number of processors such as k m o j : An ordered subset of tasks allocated to the processor Pj The best deployment model guarantee an order of tasks execution with the minimum sum tasks response times 4
Reinforcement Learning : RL algorithms solve problems that can be modeled as a Markov Decision Problem (MDP) A MDP can be represented by the following four tuples: S: The environmental state space A: The space of all actions that the agent can take in a given state P(St+1/St,a) : The probability distribution of that action a translates state St to state St+1 Rt+1: The reward received from the environment by performing action at on state St We propose to use the Q-learning algorithm : To solve the task placement problem To find the best task execution order 5
State : the collection of tasks already placed on the processors with respect to their deadlines, and the list of tasks that have not yet been placed Agent : decides a processor for a given task Decision epoch : Matches the placement of all the tasks on the different processors State: the set of tasks already ordered and the ones waiting for a priority assignment Agent: chooses the action to be scheduled Decision epoch: Matches the ordering of all the tasks on a given processor 7 7
Evaluation: We consider two case studies: CCS which is a subsystem of Continental AG s Cruise Control System used on AUTOSAR-compliant architectures and allows a car s speed to be maintained regardless of the surface form (flat or sloping) on which it is driving UAV : the Unmanned Air Vehicle, which is an autonomous plane with a camera dedicated to dynamically defined waypoints that was constructed as part of the AMADO project UAV Tasks model description CCS Tasks model description 8
UAV Placement models CCS Placement models 9
Conclusion and Extension : The optimal scheduling of tasks in a distributed architecture: Resolution of the placement problem based on RL techniques Resolution of the scheduling problem based on RL techniques Generation of the optimal task scheduling model Extension: applications to more complex problems to consider multi-objective ones 12
Thank you for your attention bakhta.haouari@isi.utm.tn 13
