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.
2021, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021), Pages 1-17 (volume: 196)
Feasibility analysis of conditional DAG tasks (04b Atto di convegno in volume)
Baruah Sanjoy, Marchetti Spaccamela Alberto
Gruppo di ricerca: Algorithms and Data Science