Paper Info
Title
Liveness and Boundedness of Synchronous Data Flow Graphs
Abstract
Synchronous Data Flow Graphs (SDFGs) have proven to be suitable for specifying and analyzing streaming applications that run on single- or multi-processor platforms. Streaming applications essentially continue their execution indefinitely. Therefore, one of the key properties of an SDFG is liveness, i.e., whether all parts of the SDFG can run infinitely often. Another elementary requirement is whether an implementation of an SDFG is feasible using a limited amount of memory. In this paper, we study two interpretations of this property, called boundedness and strict boundedness, that were either already introduced in the SDFG literature or studied for other models. A third and new definition is introduced, namely self-timed boundedness, which is very important to SDFGs, because self-timed execution results in the maximal throughput of an SDFG. Necessary and sufficient conditions for liveness in combination with all variants of boundedness are given, as well as algorithms for checking those conditions. As a by-product, we obtain an algorithm to compute the maximal achievable throughput of an SDFG that relaxes the requirement of strong connectedness in earlier work on throughput analysis.
Year
DOI
Venue
2006
10.1109/FMCAD.2006.20
FMCAD
Keywords
Field
DocType
maximal throughput,self-timed execution result,elementary requirement,synchronous data flow graphs,earlier work,strict boundedness,maximal achievable throughput,self-timed boundedness,sdfg literature,throughput analysis
Graph,Social connectedness,Computer science,Theoretical computer science,Real-time computing,Throughput,Synchronous Data Flow,Liveness
Conference
ISBN
Citations 
PageRank 
0-7695-2707-8
29
1.52
References 
Authors
10
6
Name
Order
Citations
PageRank
A. H. Ghamarian11807.07
M. C. W. Geilen224511.49
T. Basten355134.98
B. D. Theelen425412.80
M. R. Mousavi522011.42
S. Stuijk62069.18