Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard
Feasibility Analysis of Conditional DAG Tasks is co-NPNP-Hard
复制标题
条件 DAG 任务的可行性分析是 co-NPNP-Hard
DOI：
10.1145/3453417.3453422
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Baruah, Sanjoy
中科院分区：
文献类型：
--
作者：
Baruah, Sanjoy
传统上，可行性分析算法要求其输入的运行时间不低于伪多项式，才能被认为是高效的。但这种情况正在发生变化：受整数线性规划 (ILP) 求解器性能大幅提高的推动，最近的一些工作已开始考虑将有限使用 ILP 求解器视为可行性分析的可接受的效率。在本文中，提出了对一类可行性分析问题的表征，这些问题可以在这种更广泛的效率解释下有效地解决。此表征应用于条件有向无环图 (DAG) 工作负载模型，并确定可使用 ILP 求解器有效求解的 DAG 可行性分析问题与不可使用 ILP 求解器有效求解的 DAG 可行性分析问题之间的界限。
Feasibility-analysis algorithms have traditionally been required to have running times no worse than pseudo-polynomial in their inputs, in order to be considered efficient. But this is changing: motivated by a vast improvement in the performance of Integer Linear Programming (ILP) solvers, some recent work has begun to consider the limited use of ILP solvers as acceptably efficient for the purposes of feasibility analysis. In this paper, a characterization is proposed for the class of feasibility-analysis problems that can be solved efficiently under this more expansive interpretation of efficiency. This characterization is applied to the conditional directed acyclic graph (DAG) workload model, and a demarcation is identified between the feasibility-analysis problems on DAGs that are efficiently solvable using ILP solvers and those that are not.
登录
查看更多内容
重复实时任务的通用模型
DOI：
--
发表时间：
1998
期刊：
Proceedings 19th IEEE Real-Time Systems Symposium (Cat. No.98CB36279)
影响因子：
--
作者：
Sanjoy Baruah
通讯作者：
Sanjoy Baruah
指定处理器分配时调度 DAG
DOI：
10.1145/3394810.3394813
发表时间：
2020
期刊：
RTNS 2020: Proceedings of the 28th International Conference on Real-Time Networks and Systems
影响因子：
--
作者：
Baruah, Sanjoy
通讯作者：
Baruah, Sanjoy
DOI：
10.1109/ipdps47924.2020.00112
发表时间：
2020-05
期刊：
2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
A. Marchetti-Spaccamela;Nicole Megow;Jens Schlöter;M. Skutella;L. Stougie
通讯作者：
A. Marchetti-Spaccamela;Nicole Megow;Jens Schlöter;M. Skutella;L. Stougie
完备集和多项式时间层次结构
影响因子：
1.1
作者：
C. Wrathall
通讯作者：
C. Wrathall