Different task models have been proposed to represent the parallel structure of real-time tasks executing on manycore platforms: fork/join, synchronous parallel, DAG-based, etc. Despite different schedulability tests and resource augmentation bounds are available for these task systems, we experience difficulties in applying such results to real application scenarios, where the execution flow of parallel tasks is characterized by multiple (and nested) conditional structures. When a conditional branch drives the number and size of sub-jobs to spawn, it is hard to decide which execution path to select for modeling the worst-case scenario. To circumvent this problem, we integrate control flow information in the task model, considering conditional parallel tasks (cp-tasks) represented by DAGs composed of both precedence and conditional edges. For this task model, we identify meaningful parameters that characterize the schedulability of the system, and derive efficient algorithms to compute them. A response time analysis based on these parameters is then presented for different scheduling policies. A set of simulations shows that the proposed approach allows efficiently checking the schedulability of the addressed systems, and that it significantly tightens the schedulability analysis of non-conditional (e.g., Classic DAG) tasks over existing approaches.

Response-Time Analysis of Conditional DAG Tasks in Multiprocessor Systems / Melani, Alessandra; Bertogna, Marko; Bonifaci, Vincenzo; Marchetti Spaccamela, Alberto; Buttazzo, Giorgio C.. - (2015), pp. 211-221. (Intervento presentato al convegno 27th Euromicro Conference on Real-Time Systems, ECRTS 2015 tenutosi a Lund, Svezia nel 7-10 luglio 2015) [10.1109/ECRTS.2015.26].

Response-Time Analysis of Conditional DAG Tasks in Multiprocessor Systems

BERTOGNA, Marko;
2015

Abstract

Different task models have been proposed to represent the parallel structure of real-time tasks executing on manycore platforms: fork/join, synchronous parallel, DAG-based, etc. Despite different schedulability tests and resource augmentation bounds are available for these task systems, we experience difficulties in applying such results to real application scenarios, where the execution flow of parallel tasks is characterized by multiple (and nested) conditional structures. When a conditional branch drives the number and size of sub-jobs to spawn, it is hard to decide which execution path to select for modeling the worst-case scenario. To circumvent this problem, we integrate control flow information in the task model, considering conditional parallel tasks (cp-tasks) represented by DAGs composed of both precedence and conditional edges. For this task model, we identify meaningful parameters that characterize the schedulability of the system, and derive efficient algorithms to compute them. A response time analysis based on these parameters is then presented for different scheduling policies. A set of simulations shows that the proposed approach allows efficiently checking the schedulability of the addressed systems, and that it significantly tightens the schedulability analysis of non-conditional (e.g., Classic DAG) tasks over existing approaches.
2015
27th Euromicro Conference on Real-Time Systems, ECRTS 2015
Lund, Svezia
7-10 luglio 2015
211
221
Melani, Alessandra; Bertogna, Marko; Bonifaci, Vincenzo; Marchetti Spaccamela, Alberto; Buttazzo, Giorgio C.
Response-Time Analysis of Conditional DAG Tasks in Multiprocessor Systems / Melani, Alessandra; Bertogna, Marko; Bonifaci, Vincenzo; Marchetti Spaccamela, Alberto; Buttazzo, Giorgio C.. - (2015), pp. 211-221. (Intervento presentato al convegno 27th Euromicro Conference on Real-Time Systems, ECRTS 2015 tenutosi a Lund, Svezia nel 7-10 luglio 2015) [10.1109/ECRTS.2015.26].
File in questo prodotto:
File Dimensione Formato  
ECRTS15_1.pdf

Open access

Tipologia: Versione dell'autore revisionata e accettata per la pubblicazione
Dimensione 505.72 kB
Formato Adobe PDF
505.72 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

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