1. Feasibility Analysis of Conditional DAG Tasks
- Author
-
Sanjoy Baruah and Alberto Marchetti-Spaccamela, Baruah, Sanjoy, Marchetti-Spaccamela, Alberto, Sanjoy Baruah and Alberto Marchetti-Spaccamela, Baruah, Sanjoy, and Marchetti-Spaccamela, Alberto
- Abstract
Feasibility analysis for Conditional DAG tasks (C-DAGs) upon multiprocessor platforms is shown to be complete for the complexity class pspace. It is shown that as a consequence integer linear programming solvers (ILP solvers) are likely to prove inadequate for such analysis. A demarcation is identified between the feasibility-analysis problems on C-DAGs that are efficiently solvable using ILP solvers and those that are not, by characterizing a restricted class of C-DAGs for which feasibility analysis is shown to be efficiently solvable using ILP solvers.
- Published
- 2021
- Full Text
- View/download PDF