TY - JOUR
T1 - Efficient Feasibility Analysis for Graph-Based Real-Time Task Systems
AU - Sun, Jinghao
AU - Shi, Rongxiao
AU - Wang, Kexuan
AU - Guan, Nan
AU - Guo, Zhishan
N1 - Funding Information:
Manuscript received April 17, 2020; revised June 17, 2020; accepted July 6, 2020. Date of publication October 2, 2020; date of current version October 27, 2020. This work was supported in part by the National Foundation of Science of China under Grant 61972076, Grant U1808206, and Grant 61672140; in part by the Research Grants Council of Hong Kong under Grant GRF 15204917 and Grant 15213818; and in part by the National Science Foundation under Grant CNS-1850851. This article was presented in the International Conference on Embedded Software 2020 and appears as part of the ESWEEK-TCAD special issue. (Corresponding author: Nan Guan.) Jinghao Sun is with the School Of Computer Science and Technology, Dalian University of Technology, Dalian 116024, China.
Funding Information:
This work was supported in part by the National Foundation of Science of China under Grant 61972076, Grant U1808206, and Grant 61672140; in part by the Research Grants Council of Hong Kong under Grant GRF 15204917 and Grant 15213818; and in part by the National Science Foundation under Grant CNS-1850851.
Publisher Copyright:
© 1982-2012 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - The demand bound function (DBF) is a powerful abstraction to analyze the feasibility/schedulability of real-time tasks. Computing the DBF for expressive system models, such as graph-based tasks, is typically very expensive. In this article, we develop new techniques to drastically improve the DBF computation efficiency for a representative graph-based task model, digraph real-time tasks (DRT). First, we apply the well-known quick processor-demand analysis (QPA) technique, which was originally designed for simple sporadic tasks, to the analysis of DRT. The challenge is that existing analysis techniques of DRT have to compute the demand for each possible interval size, which is contradictory to the idea of QPA that aims to aggressively skip the computation for most interval sizes. To solve this problem, we develop a novel integer linear programming (ILP)-based analysis technique for DRT, to which we can apply QPA to significantly improve the analysis efficiency. Second, we improve the task utilization computation (a major step in DBF computation for DRT) efficiency from pseudo-polynomial complexity to polynomial complexity. Experiments show that our approach can improve the analysis efficiency by dozens of times.
AB - The demand bound function (DBF) is a powerful abstraction to analyze the feasibility/schedulability of real-time tasks. Computing the DBF for expressive system models, such as graph-based tasks, is typically very expensive. In this article, we develop new techniques to drastically improve the DBF computation efficiency for a representative graph-based task model, digraph real-time tasks (DRT). First, we apply the well-known quick processor-demand analysis (QPA) technique, which was originally designed for simple sporadic tasks, to the analysis of DRT. The challenge is that existing analysis techniques of DRT have to compute the demand for each possible interval size, which is contradictory to the idea of QPA that aims to aggressively skip the computation for most interval sizes. To solve this problem, we develop a novel integer linear programming (ILP)-based analysis technique for DRT, to which we can apply QPA to significantly improve the analysis efficiency. Second, we improve the task utilization computation (a major step in DBF computation for DRT) efficiency from pseudo-polynomial complexity to polynomial complexity. Experiments show that our approach can improve the analysis efficiency by dozens of times.
KW - Demand bound function (DBF)
KW - digraph real-time tasks (DRT)
KW - feasibility
KW - linear program (LP)
UR - http://www.scopus.com/inward/record.url?scp=85096035288&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2020.3012174
DO - 10.1109/TCAD.2020.3012174
M3 - Journal article
AN - SCOPUS:85096035288
VL - 39
SP - 3385
EP - 3397
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
SN - 0278-0070
IS - 11
M1 - 9211560
ER -