The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks
The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks
复制标题
DOI：
10.1145/3606342
复制
发表时间：
2023-07
影响因子：
1.6
通讯作者：
Sanjoy Baruah;A. Marchetti-Spaccamela
中科院分区：
文献类型：
--
作者：
Sanjoy Baruah;A. Marchetti-Spaccamela
条件DAG（CDAG）任务模型用于对包含条件表达式的多处理器实时系统进行建模，条件表达式的结果在评估之前是未知的。多处理器平台上的CDAG任务的可行性分析是完整的复杂性类pspace，假设np pspace，这一结果排除了使用线性规划求解器有效地解决这个问题。它进一步表明，可以没有伪多项式时间算法，解决这个问题，除非p = pspace。
The Conditional DAG (CDAG) task model is used for modeling multiprocessor real-time systems containing conditional expressions for which outcomes are not known prior to their evaluation. Feasibility analysis for CDAG tasks upon multiprocessor platforms is shown to be complete for the complexity class pspace; assuming np ≠ pspace, this result rules out the use of Integer Linear Programming solvers for solving this problem efficiently. It is further shown that there can be no pseudo-polynomial time algorithm that solves this problem unless p = pspace.