Well-behaved dataflow programs for DSP computation

Abstract

Accumulation of tokens on the arcs of a dataflow program operating on potentially infinite streams in a DSP computation leads to unbounded storage requirement. Compile-time techniques to determine the storage requirement are essential for efficient scheduling. A class of program graphs called regular stream flow graphs is studied. Restricting the construction to a set of construction rules facilitates compile-time predictability of storage requirement. Compared to existing methods, the model has a stronger verifiability, which is due to the structure of the well-constructed graphs.