Home » Publication » 24211

Dettaglio pubblicazione

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

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.
ISBN: 978-3959771924
Gruppo di ricerca: Algorithms and Data Science
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma