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
摘要
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.
问 Lune
几分钟读透这篇 Paper,不用再花一下午。
Lune 能读完全文,也能读引用它的顶会 Paper,讲清它的结论、证据和局限,每一点都注明出自哪篇 Paper。不用硬啃,也不靠猜。
已有 1 篇顶会 Paper 引用了它。别等审稿人问起,先弄清它们发现了什么。
脉络
引用它的顶会 Paper1
它引用的 Paper3
- DAG Scheduling and Analysis on Multiprocessor Systems: Exploitation of Parallelism and DependencyShuai Zhao, Xiaotian Dai, Iain Bate, Alan Burns 等RTSS 2020 · 73 次引用
- Calculating Worst-Case Response Time Bounds for OpenMP Programs with Loop StructuresJinghao Sun, Nan Guan, Zhishan Guo, Yekai Xue 等RTSS 2021 · 11 次引用
- A Finer-Grained Blocking Analysis for Parallel Real-Time Tasks with Spin-LocksZe-Wei Chen, Hang Lei, Maolin Yang, Yong Liao 等DAC 2021 · 5 次引用
相关 Paper
- Response Time Analysis and Optimization of DAG Tasks Exploiting Mutually Exclusive ExecutionHaochun Liang, Xu Jiang, Nan Guan, Qingqiang He 等DAC 2023 · 6 次引用
- On Computing Exact WCRT for DAG Tasks†Jinghao Sun, Feng Li, Nan Guan, Wentao Zhu 等DAC 2020 · 12 次引用
- Response-Time Analysis and Optimization for Probabilistic Conditional Parallel DAG TasksNiklas Ueter, Mario Günzel, Jian-Jia ChenRTSS 2021 · 13 次引用
- Conditionally Optimal Parallelization of Real-Time DAG Tasks for Global EDFYoungeun Cho, Dongmin Shin, JaeSeung Park, Chang-Gun LeeRTSS 2021 · 12 次引用
- A Multi-Level DPM Approach for Real-Time DAG Tasks in Heterogeneous ProcessorsFederico Reghenzani, Ashikahmed Bhuiyan, William Fornaciari, Zhishan GuoRTSS 2021 · 12 次引用
