Skip to Main content Skip to Navigation
New interface
Conference papers

Feasibility Analysis of Conditional DAG Tasks

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03395589
Contributor : Marie-France Sagot Connect in order to contact the contributor
Submitted on : Friday, October 22, 2021 - 2:26:03 PM
Last modification on : Friday, November 25, 2022 - 7:04:09 PM

File

LIPIcs-ECRTS-2021-12.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Sanjoy Baruah, Alberto Marchetti-Spaccamela. Feasibility Analysis of Conditional DAG Tasks. ECRTS 2021 - 33rd Euromicro Conference on Real-Time Systems, Jul 2021, Modena, Italy. pp.1-17, ⟨10.4230/LIPIcs.ECRTS.2021.12⟩. ⟨hal-03395589⟩

Share

Metrics

Record views

31

Files downloads

68