Precise Response Time Analysis for Multiple DAG Tasks with Intra-task Priority Assignment

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In many real-time application domains, there are execution dependencies, such tasks may be formulated as multiple Directed Acyclic Graphs (DAGs) and scheduled with intra-task (i.e., intra-DAG) priority assignment.
The worst-case completion time of a DAG must be bounded and schedulability analysis must be conducted during the design phase to estimate the required hardware resources. Typical examples include automotive systems and Ultra-Reliable Low Latency Communications (URLLC), which is the ``to-business'' protocol in 5G technologies, deployed in industrial automation for instance.
To bound the execution time of multiple DAGs, there are two key factors to analyze: the intra-task interference for a single DAG and the inter-task interference between DAGs.
While extensive efforts have been invested, the existing methods either still contain a large degree of pessimism or are even erroneous due to errors in the derived analysis.
In this paper, we first provide an in-depth analysis of the limitation and defects of the existing methods.
Inspired by these observations, we construct novel response time analysis for multiple DAG tasks with arbitrary intra-task priority assignment.
Our analysis precisely accounts for both the intra- and inter-task interference by fully exploring the node parallelism in each DAG as well as between DAGs.
Extensive experimental results show that the proposed analysis obtains tighter bounds and improves the system scheduability by at least 300\% compared to state-of-the-art approaches. This improvement is even larger when the scheduling pressure is relatively high, up to 100\% versus 0\% in many cases.
This work notably advances the use of response time analysis in the industry. Practitioners have to resort to either potentially unsafe measurement results or significant resource over-provisioning when precise analysis is unavailable.
Original languageEnglish
Title of host publicationProc. 29th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)
Number of pages11
ISBN (Electronic)979-8-3503-2176-0
ISBN (Print)979-8-3503-2177-7
Publication statusPublished - 23 Jun 2023

Bibliographical note

©2023 IEEE. This is an author-produced version of the published paper. Uploaded in accordance with the University’s Research Publications and Open Access policy.

Cite this