Liveness and Boundedness of Synchronous Data Flow Graphs.

A.H. Ghamarian, M. Geilen, T. Basten, B. Theelen, M.R. Mousavi and S. Stuijk. Proceedings of the 6th International Conference on Formal Methods in Computer-Aided Design (FMCAD'06), San Jose, CA, USA, IEEE, November 2006.

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.

(Paper in .pdf format )

Extended version of this paper appeared as Technical Report ESR-2006-04, Electronic Systems Group, Department of Electrical Engineering, Eindhoven University of Technology.

(Technical Report in .pdf format )

@InProceedings{MousaviFMCAS06,
    author      = "Ghamarian, A.H. and Geilen, M. and  Basten, T. and Theelen, B. and Mousavi, M.R.  and Stuijk, S.", 
    title       = "Liveness and Boundedness of Synchronous Data Flow Graphs.",
    booktitle   = "Proceedings of the 6th International Conference on Formal Methods in Computer-Aided Design (FMCAD'06)",
    publisher   = "IEEE Press, USA, 2006",
    note        = "To appear".
}