Symbolic Buffer Sizing for Throughput-Optimal Scheduling of Dataflow Graphs

Abstract : The synchronous dataflow model is widely used to design real-time streaming applications which must assure a minimum quality-of-service. A benefit of that model is to allow static analyses to predict and guarantee timing (e.g., throughput) and buffering requirements of an application. Performance analyses can either be performed at compile time (for design space exploration) or at run-time (for resource management and reconfigurable systems). However, these algorithms, which often have an exponential time complexity, may cause a huge runtime overhead or make design space exploration unacceptably slow. In this paper, we argue that symbolic analyses are more appropriate since they express the system performance as a function of parameters (i.e., input and output rates, execution times). Such functions can be quickly evaluated for each different configuration or checked w.r.t. many different non-functional requirements. We first provide a symbolic expression of the maximal throughput of acyclic synchronous dataflow graphs. We then perform an analytic and exact study of the minimum buffer sizes needed to achieve this maximal throughput for a single parametric edge graph. Based on these investigations, we define symbolic analyses that approximate the minimum buffer sizes needed to achieve maximal throughput for acyclic graphs. We assess the proposed analyses experimentally on both synthetic and real benchmarks.
Type de document :
Communication dans un congrès
RTAS 2016 - 22nd IEEE Real-Time Embedded Technology & Applications Symposium, Apr 2016, Vienne, Austria. 〈10.1109/RTAS.2016.7461360〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01253168
Contributeur : Pascal Fradet <>
Soumis le : lundi 30 mai 2016 - 10:48:33
Dernière modification le : mardi 29 novembre 2016 - 13:56:08
Document(s) archivé(s) le : mercredi 31 août 2016 - 10:38:03

Fichier

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

Identifiants

Collections

Citation

Adnan Bouakaz, Pascal Fradet, Alain Girault. Symbolic Buffer Sizing for Throughput-Optimal Scheduling of Dataflow Graphs. RTAS 2016 - 22nd IEEE Real-Time Embedded Technology & Applications Symposium, Apr 2016, Vienne, Austria. 〈10.1109/RTAS.2016.7461360〉. 〈hal-01253168〉

Partager

Métriques

Consultations de la notice

288

Téléchargements de fichiers

71