TY - GEN
T1 - Feasibility analysis of conditional DAG tasks
AU - Baruah, Sanjoy
AU - Marchetti-Spaccamela, Alberto
N1 - Publisher Copyright:
© Sanjoy Baruah and Alberto Marchetti-Spaccamela; licensed under Creative Commons License CC-BY 4.0
PY - 2021/7/1
Y1 - 2021/7/1
N2 - 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.
AB - 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.
KW - Conditional directed acyclic graphs
KW - Multiprocessor feasibility analysis
KW - PSPACE-complete
UR - https://www.scopus.com/pages/publications/85114961794
U2 - 10.4230/LIPIcs.ECRTS.2021.12
DO - 10.4230/LIPIcs.ECRTS.2021.12
M3 - Conference contribution
AN - SCOPUS:85114961794
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021
A2 - Brandenburg, Bjorn B.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021
Y2 - 5 July 2021 through 9 July 2021
ER -