Liveness and Boundedness of Synchronous Data Flow Graphs

A.H. Ghamarian, M.C.W. Geilen, T. Basten, B.D. Theelen, M.R. Mousavi, S. Stuijk

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

35 Citations (Scopus)
1 Downloads (Pure)


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.
Original languageEnglish
Title of host publicationProceedings of the 6th International Conference on Formal Methods in Computer-Aided Design
Place of PublicationLos Alamitos, USA
PublisherIEEE Computer Society
ISBN (Print)0-7695-2707-8
Publication statusPublished - 2006
Eventconference; FMCAD'06, San Jose, USA; 2006-11-12; 2006-11-16 -
Duration: 12 Nov 200616 Nov 2006


Conferenceconference; FMCAD'06, San Jose, USA; 2006-11-12; 2006-11-16
OtherFMCAD'06, San Jose, USA


Dive into the research topics of 'Liveness and Boundedness of Synchronous Data Flow Graphs'. Together they form a unique fingerprint.

Cite this