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
N1 - Funding Information:
†This work is supported by NSFC (61972076, 61772123, 61532007, 61602104), GRF (15213818, 15204917) and NSF(CNS-1850851). * Corresponding author: Nan Guan, [email protected]
Publisher Copyright:
© 2020 IEEE.
PY - 2020/7
Y1 - 2020/7
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 - http://www.scopus.com/inward/record.url?scp=85093985954&partnerID=8YFLogxK
U2 - 10.1109/DAC18072.2020.9218744
DO - 10.1109/DAC18072.2020.9218744
M3 - Conference article published in proceeding or book
AN - SCOPUS:85093985954
T3 - Proceedings - Design Automation Conference
SP - 1
EP - 6
BT - 2020 57th ACM/IEEE Design Automation Conference, DAC 2020
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 57th ACM/IEEE Design Automation Conference, DAC 2020
Y2 - 20 July 2020 through 24 July 2020
ER -