Efficient Response Time Bound for Typed DAG Tasks
- Resource Type
- Conference
- Authors
- He, Qingqiang; Sun, Yongzheng; Lv, Mingsong; Liu, Weichen
- Source
- 2023 IEEE 29th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA) RTCSA Embedded and Real-Time Computing Systems and Applications (RTCSA), 2023 IEEE 29th International Conference on. :226-231 Aug, 2023
- Subject
- Communication, Networking and Broadcast Technologies
Components, Circuits, Devices and Systems
Computing and Processing
Directed acyclic graph
Interference
Real-time systems
Computational efficiency
Complexity theory
Time factors
Task analysis
response time bound
typed DAG task
heterogeneous multi-core
- Language
- ISSN
- 2325-1301
Heterogeneous multi-core platforms have been used in many fields to meet the increasing requirement of computation. In this paper, we study the response time bound of typed DAG (directed acyclic graph) tasks on heterogeneous multi-core platforms. The existing bound has exponential time complexity. In this paper, we propose a new bound that can be computed with complexity $O(\vert V\vert +\vert E\vert)$ and is only slightly larger than the state-of-the-art. Experiments demonstrate that the computation of our bound is significantly more efficient than the existing bound and our bound has almost the same tightness as the existing bound.