On the Volume Calculation for Conditional DAG Tasks: Hardness and Algorithms

Jinghao Sun, Yaoyao Chi, Tianfei Xu, Lei Cao, Nan Guan, Zhishan Guo, Wang Yi

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020
EditorsGiorgio Di Natale, Cristiana Bolchini, Elena-Ioana Vatajelu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages204-209
Number of pages6
ISBN (Electronic)9783981926347
DOIs
Publication statusPublished - Mar 2020
Event2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020 - Grenoble, France
Duration: 9 Mar 202013 Mar 2020

Publication series

NameProceedings of the 2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020

Conference

Conference2020 Design, Automation and Test in Europe Conference and Exhibition, DATE 2020
Country/TerritoryFrance
CityGrenoble
Period9/03/2013/03/20

Keywords

  • Conditional branches
  • DAG
  • NP-hard
  • Volume

ASJC Scopus subject areas

  • Hardware and Architecture
  • Safety, Risk, Reliability and Quality
  • Modelling and Simulation
  • Electrical and Electronic Engineering

Cite this