Symbolic Analyses of Dataflow Graphs

Adnan Bouakaz 1 Pascal Fradet 1 Alain Girault 1
1 SPADES - Sound Programming of Adaptive Dependable Embedded Systems
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : The synchronous dataflow model of computation is widely used to design embedded stream-processing applications under strict quality-of-service requirements (e.g., buffering size, throughput, input-output latency). The required analyses can either be performed at compile time (for design space exploration) or at run-time (for resource management and reconfigurable systems). However, these analyses have an exponential time complexity, which may cause a huge run-time 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. different quality-of-service requirements. We provide symbolic analyses for computing the maximal throughput of acyclic synchronous dataflow graphs, the minimum required buffers for which as soon as possible scheduling achieves this throughput, and finally the corresponding input-output latency of the graph. The paper first investigates these problems for a single parametric edge. The results are extended to general acyclic graphs using linear approximation techniques. We assess the proposed analyses experimentally on both synthetic and real benchmarks.
Type de document :
Article dans une revue
ACM Transactions on Design Automation of Electronic Systems, Association for Computing Machinery, 2017
Liste complète des métadonnées

https://hal.inria.fr/hal-01417146
Contributeur : Pascal Fradet <>
Soumis le : jeudi 15 décembre 2016 - 12:30:16
Dernière modification le : jeudi 11 octobre 2018 - 08:48:04

Identifiants

  • HAL Id : hal-01417146, version 1

Citation

Adnan Bouakaz, Pascal Fradet, Alain Girault. Symbolic Analyses of Dataflow Graphs. ACM Transactions on Design Automation of Electronic Systems, Association for Computing Machinery, 2017. 〈hal-01417146〉

Partager

Métriques

Consultations de la notice

335