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.
978-3959771924
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 Visualizza/Apri 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 0
  • ???jsp.display-item.citation.isi??? ND
social impact