TY - GEN
T1 - ML for RT
T2 - 27th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS 2021
AU - Lee, Seunghoon
AU - Baek, Hyeongboo
AU - Woo, Honguk
AU - Shin, Kang G.
AU - Lee, Jinkyu
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/5
Y1 - 2021/5
N2 - As machine learning (ML) has been proven effective in solving various problems, researchers in the real-time systems (RT) community have recently paid increasing attention to ML. While most of them focused on timing issues for ML applications (i.e., RT for ML), only a little has been done on the use of ML for solving fundamental RT problems. In this paper, we aim at utilizing ML to solve a fundamental RT problem of priority assignment for global fixed-priority preemptive (gFP) scheduling on a multiprocessor platform. This problem is known to be challenging in the case of a large number (n) of tasks in a task set because exhaustive testing of all priority assignments (as many as n!) is intractable and existing heuristics cannot find a schedulable priority assignment, even if exists, for a number of task sets. We systematically incorporate RT domain knowledge into ML and develop an ML framework tailored to the problem, called PAL. First, raising and addressing technical issues including neural architecture selection and training sample regulation, we enable PAL to infer a schedulable priority assignment of a set of n tasks, by training PAL with same-size (i.e., with n tasks) samples each of whose schedulable priority assignment has already been identified. Second, considering the exhaustive testing of all priority assignments of each task set with large n makes it intractable to provide training samples to PAL, we derive inductive properties that can generate training samples with large n from those with small n, through empirical observation of PAL and mathematical analysis of the target gFP schedulability test. Finally, utilizing the inductive properties and additional techniques, we propose how to systematically implement PAL whose training sample generation process not only yields unbiased samples but also is tractable even for large n. Our experimental results demonstrate PAL covers a number of additional task sets, each of which has never been proven schedulable by any existing approaches for gFP.
AB - As machine learning (ML) has been proven effective in solving various problems, researchers in the real-time systems (RT) community have recently paid increasing attention to ML. While most of them focused on timing issues for ML applications (i.e., RT for ML), only a little has been done on the use of ML for solving fundamental RT problems. In this paper, we aim at utilizing ML to solve a fundamental RT problem of priority assignment for global fixed-priority preemptive (gFP) scheduling on a multiprocessor platform. This problem is known to be challenging in the case of a large number (n) of tasks in a task set because exhaustive testing of all priority assignments (as many as n!) is intractable and existing heuristics cannot find a schedulable priority assignment, even if exists, for a number of task sets. We systematically incorporate RT domain knowledge into ML and develop an ML framework tailored to the problem, called PAL. First, raising and addressing technical issues including neural architecture selection and training sample regulation, we enable PAL to infer a schedulable priority assignment of a set of n tasks, by training PAL with same-size (i.e., with n tasks) samples each of whose schedulable priority assignment has already been identified. Second, considering the exhaustive testing of all priority assignments of each task set with large n makes it intractable to provide training samples to PAL, we derive inductive properties that can generate training samples with large n from those with small n, through empirical observation of PAL and mathematical analysis of the target gFP schedulability test. Finally, utilizing the inductive properties and additional techniques, we propose how to systematically implement PAL whose training sample generation process not only yields unbiased samples but also is tractable even for large n. Our experimental results demonstrate PAL covers a number of additional task sets, each of which has never been proven schedulable by any existing approaches for gFP.
KW - ML for RT
KW - Machine Learning
KW - Priority Assignment
KW - Real Time Systems
KW - Schedulability Analysis
UR - http://www.scopus.com/inward/record.url?scp=85113769349&partnerID=8YFLogxK
U2 - 10.1109/RTAS52030.2021.00018
DO - 10.1109/RTAS52030.2021.00018
M3 - Conference contribution
AN - SCOPUS:85113769349
T3 - Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS
SP - 118
EP - 130
BT - Proceedings - 2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium, RTAS 2021
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 18 May 2021 through 21 May 2021
ER -