The Conditional DAG (CDAG) task model is used for modeling multiprocessor real-time systems containing conditional expressions for which outcomes are not known prior to their evaluation. Feasibility analysis for CDAG tasks upon multiprocessor platforms is shown to be complete for the complexity class pspace; assuming np not equal pspace, this result rules out the use of Integer Linear Programming solvers for solving this problem efficiently. It is further shown that there can be no pseudo-polynomial time algorithm that solves this problem unless P = PSPACE.
The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks / Baruah, Sanjoy; Marchetti-Spaccamela, Alberto. - In: ACM TRANSACTIONS ON PARALLEL COMPUTING. - ISSN 2329-4949. - 10:3(2023), pp. 1-22. [10.1145/3606342]
The Computational Complexity of Feasibility Analysis for Conditional DAG Tasks
Marchetti-Spaccamela, Alberto
2023
Abstract
The Conditional DAG (CDAG) task model is used for modeling multiprocessor real-time systems containing conditional expressions for which outcomes are not known prior to their evaluation. Feasibility analysis for CDAG tasks upon multiprocessor platforms is shown to be complete for the complexity class pspace; assuming np not equal pspace, this result rules out the use of Integer Linear Programming solvers for solving this problem efficiently. It is further shown that there can be no pseudo-polynomial time algorithm that solves this problem unless P = PSPACE.| File | Dimensione | Formato | |
|---|---|---|---|
|
Barouah_Computational_2023.pdf
accesso aperto
Note: https://doi.org/10.1145/3606342
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
1.94 MB
Formato
Adobe PDF
|
1.94 MB | Adobe PDF |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
