Response-Time Analysis of Conditional {DAG} Tasks in Multiprocessor Systems

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.
Type de document :
Communication dans un congrès
ECRTS 2015 - Euromicro Conference on Real-Time Systems, Jul 2015, Lund, Sweden. pp.211-221, 2015, 〈10.1109/ECRTS.2015.26〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01249103
Contributeur : Marie-France Sagot <>
Soumis le : mercredi 5 juillet 2017 - 15:41:18
Dernière modification le : jeudi 6 juillet 2017 - 01:13:10

Fichier

melani2015(1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Alessandra Melani, Vincenzo Bonifaci, Marko Bertogna, Alberto Marchetti-Spaccamela, Giorgio Buttazzo. Response-Time Analysis of Conditional {DAG} Tasks in Multiprocessor Systems. ECRTS 2015 - Euromicro Conference on Real-Time Systems, Jul 2015, Lund, Sweden. pp.211-221, 2015, 〈10.1109/ECRTS.2015.26〉. 〈hal-01249103〉

Partager

Métriques

Consultations de la notice

119

Téléchargements de fichiers

26