TY - GEN
T1 - On computing exact WCRT for DAG Tasks
AU - Sun, Jinghao
AU - Li, Feng
AU - Guan, Nan
AU - Zhu, Wentao
AU - Xiang, Minjie
AU - Guo, Zhishan
AU - Yi, Wang
PY - 2020
Y1 - 2020
N2 - 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 (SMT) 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.
AB - 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 (SMT) 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.
UR - https://www.scopus.com/pages/publications/85093985954
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85093985954&origin=recordpage
U2 - 10.1109/DAC18072.2020.9218744
DO - 10.1109/DAC18072.2020.9218744
M3 - RGC 32 - Refereed conference paper (with host publication)
SN - 978-1-7281-5802-0
T3 - Proceedings - Design Automation Conference
BT - PROCEEDINGS OF THE 2020 57TH ACM/EDAC/IEEE DESIGN AUTOMATION CONFERENCE (DAC)
PB - IEEE
T2 - 57th ACM/IEEE Design Automation Conference (DAC 2020)
Y2 - 20 July 2020 through 24 July 2020
ER -