Decidable Dataflow Models for Signal Processing: Synchronous Dataflow and Its Extensions - Signal Processing Systems - page 1063

Decidable Dataflow Models for Signal
Processing: Synchronous Dataflow
and Its Extensions

Soonhoi Ha and Hyunok Oh

Abstract Digital signal processing algorithms can be naturally represented by a
dataflow graph where nodes represent function blocks and arcs represent the data
dependency between nodes. Among various dataflow models, decidable dataflow
models have restricted semantics so that we can determine the execution order
of nodes at compile-time and decide if the program has the possibility of buffer
overflow or deadlock. In this chapter, we explain the synchronous dataflow (SDF)
model as the pioneering and representative decidable dataflow model and its
decidability focusing on how the static scheduling decision can be made. In addition
the cyclo-static dataflow model and a few other extended models are briefly
introduced to show how they overcome the limitations of the SDF model.

1 Introduction

Digital signal processing (DSP) algorithms are often informally, but intuitively,
described by block diagrams in which a block represents a function block and an arc
or edge represents a dependency between function blocks. While a block diagram
is not a programming model, it resembles a formal dataflow graph in appearance.
Figure 1 shows a block-diagram representation of a simple DSP algorithm, which
can also be regarded as a dataflow graph of the algorithm.
A dataflow graph is a graphical representation of a dataflow model of computa-
tion in which a node, or an actor , represents a function block that can be executed,

S. Ha ( )
Seoul National University, Seoul, Korea
e-mail: [e-mail]
H. Oh
Hanyang University, Seoul, Korea
e-mail: [e-mail]