Paper Info
Title
Single-rate approximations of cyclo-static synchronous dataflow graphs
Abstract
Exact analysis of synchronous dataflow (sdf) graphs is often considered too costly, because of the expensive transformation of the graph into a single-rate equivalent. As an alternative, several authors have proposed approximate analyses. Existing approaches to approximation are based on the operational semantics of an sdf graph. We propose an approach to approximation that is based on functional semantics. This generalises earlier work done on multi-rate sdf graphs towards cyclo-static sdf (csdf) graphs. We take, as a starting point, a mathematical characterisation, and derive two transformations of a csdf graph into hsdf graphs. These hsdf graphs have the same size as the csdf graph, and are approximations: their respective temporal behaviours are optimistic and pessimistic with respect to the temporal behaviour of the csdf graph. Analysis results computed for these single-rate approximations give bounds on the analysis results of the csdf graph. As an illustration, we show how these single-rate approximations may be used to compute bounds on the buffer sizes required to reach a given throughput.
Year
DOI
Venue
2014
10.1145/2609248.2609249
SCOPES
Keywords
Field
DocType
algorithms,models of computation,transformation,approximation,theory,synchronous dataflow
Graph,Operational semantics,Computer science,Parallel computing,Approximations of π,Theoretical computer science,Dataflow,Functional semantics,Graph product,Throughput
Conference
Citations 
PageRank 
References 
2
0.38
15
Authors
4
Name
Order
Citations
PageRank
Robert de Groote11078.67
Philip K. F. Holzenspies21037.91
kuper3347.20
Gerard J. M. Smit488889.18