TY - GEN
T1 - On the Volume Calculation for Conditional DAG Tasks: Hardness and Algorithms
AU - Sun, Jinghao
AU - Chi, Yaoyao
AU - Xu, Tianfei
AU - Cao, Lei
AU - Guan, Nan
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] 1The volume of DAG is a very important parameter for the DAG task’s response time analysis. Generally speaking, computing volume is the first step for analyzing DAG task’s response time.
Publisher Copyright:
© 2020 EDAA.
PY - 2020/3
Y1 - 2020/3
N2 - The hardness of analyzing conditional directed acyclic graph (DAG) tasks remains unknown so far. For example, previous researches asserted that the conditional DAG's volume can be solved in polynomial time. However, these researches all assume well-nested structures that are recursively composed by single-source-single-sink parallel and conditional components. For conditional DAGs in general that do not comply with this assumption, the hardness and algorithms of volume computation are still open. In this paper, we construct counterexamples to show that previous work cannot provide a safe upper bound of the conditional DAG's volume in general. Moreover, we prove that the volume computation problem for conditional DAGs is strongly \mathcal{N}\mathcal{P}-hard. Finally, we propose an exact algorithm for computing the conditional DAG's volume. Experiments show that our method can significantly improve the accuracy of the conditional DAG's volume estimation.
AB - The hardness of analyzing conditional directed acyclic graph (DAG) tasks remains unknown so far. For example, previous researches asserted that the conditional DAG's volume can be solved in polynomial time. However, these researches all assume well-nested structures that are recursively composed by single-source-single-sink parallel and conditional components. For conditional DAGs in general that do not comply with this assumption, the hardness and algorithms of volume computation are still open. In this paper, we construct counterexamples to show that previous work cannot provide a safe upper bound of the conditional DAG's volume in general. Moreover, we prove that the volume computation problem for conditional DAGs is strongly \mathcal{N}\mathcal{P}-hard. Finally, we propose an exact algorithm for computing the conditional DAG's volume. Experiments show that our method can significantly improve the accuracy of the conditional DAG's volume estimation.
KW - Conditional branches
KW - DAG
KW - NP-hard
KW - Volume
UR - http://www.scopus.com/inward/record.url?scp=85087394060&partnerID=8YFLogxK
U2 - 10.23919/DATE48585.2020.9116559
DO - 10.23919/DATE48585.2020.9116559
M3 - Conference article published in proceeding or book
AN - SCOPUS:85087394060
T3 - Proceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020
SP - 204
EP - 209
BT - Proceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020
A2 - Di Natale, Giorgio
A2 - Bolchini, Cristiana
A2 - Vatajelu, Elena-Ioana
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020
Y2 - 9 March 2020 through 13 March 2020
ER -