Sökning: onr:"swepub:oai:DiVA.org:uu-432001" >
On Computing Exact ...
On Computing Exact WCRT for DAG Tasks
-
- Sun, Jinghao (författare)
- Dalian Univ Technol, Dalian, Peoples R China; Northeastern Univ, Shenyang, Peoples R China
-
- Li, Feng (författare)
- Northeastern Univ, Shenyang, Peoples R China
-
- Guan, Nan (författare)
- Hong Kong Polytech Univ, Hong Kong, Peoples R China
-
visa fler...
-
- Zhu, Wentao (författare)
- Dalian Univ Technol, Dalian, Peoples R China
-
- Xiang, Minjie (författare)
- Northeastern Univ, Shenyang, Peoples R China
-
- Guo, Zhishan (författare)
- Univ Cent Florida, Orlando, FL 32816 USA
-
- Wang, Yi (författare)
- Uppsala universitet,Datorteknik
-
visa färre...
-
(creator_code:org_t)
- IEEE, 2020
- 2020
- Engelska.
-
Ingår i: 57th ACM/IEEE Design Automation Conference, DAC 2020, San Francisco, CA, USA, July 20-24, 2020. - : IEEE. - 9781728110851 ; , s. 1-6
- Relaterad länk:
-
https://urn.kb.se/re...
-
visa fler...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Most current real-time parallel applications can be modeled as a directed acyclic graph (DAG) task. Existing worst-case response time (WCRT) bounds (e.g., Graham's bound) derived for DAGs may be very pessimistic. No one precisely knows the gap between the WCRT bound and the actual WCRT. In this paper, we aim to derive the exact WCRT of a DAG task under the list scheduling upon multi-core platforms. We encode the WCRT analysis problem into a satisfaction modular theoretical (SNIT) formulation based on insights into the list scheduling algorithm, and prove that our SMT program can solve the WCRT precisely, providing an accurate baseline to measure the tightness of the existing WCRT bounds. Experiments show that our method significantly improves the tightness of the WCRT bound, and is practically quite efficient, e.g., it can analyze DAGs with more than 40 vertices in a few seconds.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas