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.

Feasibility analysis of conditional DAG tasks / Baruah, Sanjoy; MARCHETTI SPACCAMELA, Alberto. - 196:(2021), pp. 1-17. (Intervento presentato al convegno 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021 tenutosi a Modena, Italy (on-line)) [10.4230/LIPIcs.ECRTS.2021.12].

Feasibility analysis of conditional DAG tasks

Marchetti Spaccamela Alberto
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.
2021
33rd Euromicro Conference on Real-Time Systems, ECRTS 2021
Conditional directed acyclic graphs; Multiprocessor feasibility analysis; PSPACE-complete
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Feasibility analysis of conditional DAG tasks / Baruah, Sanjoy; MARCHETTI SPACCAMELA, Alberto. - 196:(2021), pp. 1-17. (Intervento presentato al convegno 33rd Euromicro Conference on Real-Time Systems, ECRTS 2021 tenutosi a Modena, Italy (on-line)) [10.4230/LIPIcs.ECRTS.2021.12].
File allegati a questo prodotto
File Dimensione Formato  
Baruah_Feasibility_2021.pdf

accesso aperto

Note: DOI: 10.4230/LIPIcs.ECRTS.2021.12
Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 821.09 kB
Formato Adobe PDF
821.09 kB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1571288
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact