Back to Search
Start Over
Feasibility analysis of conditional DAG tasks
- Source :
- ECRTS 2021-33rd Euromicro Conference on Real-Time Systems, ECRTS 2021-33rd Euromicro Conference on Real-Time Systems, Jul 2021, Modena, Italy. pp.1-17, ⟨10.4230/LIPIcs.ECRTS.2021.12⟩
- Publication Year :
- 2021
- Publisher :
- Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2021.
-
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.<br />LIPIcs, Vol. 196, 33rd Euromicro Conference on Real-Time Systems (ECRTS 2021), pages 12:1-12:17
- Subjects :
- TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES
Software and its engineering → Real-time schedulability
[INFO]Computer Science [cs]
Conditional directed acyclic graphs
Multiprocessor feasibility analysis
PSPACE-complete
Computer systems organization → Embedded and cyber-physical systems
MathematicsofComputing_DISCRETEMATHEMATICS
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- ECRTS 2021-33rd Euromicro Conference on Real-Time Systems, ECRTS 2021-33rd Euromicro Conference on Real-Time Systems, Jul 2021, Modena, Italy. pp.1-17, ⟨10.4230/LIPIcs.ECRTS.2021.12⟩
- Accession number :
- edsair.doi.dedup.....960e868c4ce6e2c3265d262c78e69257
- Full Text :
- https://doi.org/10.4230/LIPIcs.ECRTS.2021.12⟩