New programming models have been proposed to exploit the parallelism of modern computing architectures. Also in the real-time domain more detailed task models are under evaluation to provide a tighter analysis of parallel application with precedence and timing constraints. This paper presents two schedulability tests based on Response Time Analysis for determining whether a set of sporadic DAG-tasks with arbitrary deadlines can be scheduled by G-EDF or G-DM on a platform consisting of m identical processor. The first test is a simple polynomial time test, while the second one is a pseudo-polynomial time test. Our tests exploit the combinatorial properties of the DAGs by considering the interference experienced by each vertex. We describe a set of simulations showing that our tests outperform the tests described in [7] in terms of schedulability ratio and running time. We also provide resource augmentation bounds for our polynomial time test when considering single-DAG systems.

Response time analysis for G-EDF and G-DM scheduling of sporadic DAG-tasks with arbitrary deadline

PARRI, ANDREA;BIONDI, ALESSANDRO;MARINONI, Mauro
2015-01-01

Abstract

New programming models have been proposed to exploit the parallelism of modern computing architectures. Also in the real-time domain more detailed task models are under evaluation to provide a tighter analysis of parallel application with precedence and timing constraints. This paper presents two schedulability tests based on Response Time Analysis for determining whether a set of sporadic DAG-tasks with arbitrary deadlines can be scheduled by G-EDF or G-DM on a platform consisting of m identical processor. The first test is a simple polynomial time test, while the second one is a pseudo-polynomial time test. Our tests exploit the combinatorial properties of the DAGs by considering the interference experienced by each vertex. We describe a set of simulations showing that our tests outperform the tests described in [7] in terms of schedulability ratio and running time. We also provide resource augmentation bounds for our polynomial time test when considering single-DAG systems.
File in questo prodotto:
File Dimensione Formato  
rtns15-dag.pdf

non disponibili

Tipologia: Documento in Post-print
Licenza: Licenza non conosciuta
Dimensione 1.12 MB
Formato Adobe PDF
1.12 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

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/11382/503542
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 17
social impact