Symbolic Computation of the Minimum Buffer Sizes for Dataflow Graphs (Extended Version)
Résumé
Synchronous dataflow graphs are widely used to design digital signal processing and
real-time streaming applications. A benefit of that model is to allow static analyses to predict
and guarantee the performances (e.g., throughput, memory 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 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. 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 this investigation, 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.
Domaines
Systèmes embarqués
Origine : Fichiers produits par l'(les) auteur(s)