Lune

RTSS2022Top-tier venue

Response Time Analysis for Prioritized DAG Task with Mutually Exclusive Vertices

Ran Bi, Qingqiang He, Jinghao Sun, Zhenyu Sun, Zhishan Guo, Nan Guan, Guozhen Tan

Abstract

Directed acyclic graph (DAG) becomes a popular model for modern real-time embedded software. It is really a challenge to bound the worst-case response time (WCRT) of DAG task. Parallelism, dependencies and mutual exclusion become three of the most critical properties of real-time parallel tasks. Recent work applied prioritizing techniques to reduce DAG task's WCRT bound, which has well studied the first two properties, i.e., parallelism and dependencies, but leaves the mutually exclusive property as an open problem. This paper focuses on all the three properties of real-time parallel software, and investigates how to estimate the WCRT of the DAG task model with mutually exclusive vertices and under prioritized list scheduling algorithms. We derive a reasonable WCRT bound for such a complicated DAG task, and prove that the corresponding WCRT bound computation problem is strongly NP-hard. It means that there are no pseudo-polynomial time algorithms to compute the WCRT bound. For the prioritized DAG with a constant number of mutual exclusive vertices, we develop a dynamic programming algorithm that is able to estimate the WCRT bound within pseudo-polynomial time. Experiments are conducted to evaluate the performance of our analysis method implemented with different priority assignment policies against the state-of-the-art.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

1 top-tier paper has cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers1

  1. RED: A Systematic Real-Time Scheduling Approach for Robotic Environmental DynamicsZexin Li, Tao Ren, Xiaoxi He, Cong LiuRTSS 2023 · 8 citations

Builds on3

  1. DAG Scheduling and Analysis on Multiprocessor Systems: Exploitation of Parallelism and DependencyShuai Zhao, Xiaotian Dai, Iain Bate, Alan Burns et al.RTSS 2020 · 73 citations
  2. Calculating Worst-Case Response Time Bounds for OpenMP Programs with Loop StructuresJinghao Sun, Nan Guan, Zhishan Guo, Yekai Xue et al.RTSS 2021 · 11 citations
  3. A Finer-Grained Blocking Analysis for Parallel Real-Time Tasks with Spin-LocksZe-Wei Chen, Hang Lei, Maolin Yang, Yong Liao et al.DAC 2021 · 5 citations

Related papers

  1. Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive ExecutionHaochun Liang, Xu Jiang, Nan Guan, Qingqiang He et al.DAC 2023 · 6 citations
  2. On Computing Exact WCRT for DAG Tasks†Jinghao Sun, Feng Li, Nan Guan, Wentao Zhu et al.DAC 2020 · 12 citations
  3. Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG TasksNiklas Ueter, Mario Günzel, Jian-Jia ChenRTSS 2021 · 13 citations
  4. Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDFYoungeun Cho, Dongmin Shin, JaeSeung Park, Chang-Gun LeeRTSS 2021 · 12 citations
  5. A Multi-Level DPM Approach for Real-Time DAG Tasks in Heterogeneous ProcessorsFederico Reghenzani, Ashikahmed Bhuiyan, William Fornaciari, Zhishan GuoRTSS 2021 · 12 citations
Dusk over the sea between two cliffs drawn in fine vertical lines