Mapping on Fully Dedicated Architecture - Digital Design of Signal Processing Systems: A Practical Approach - page 154

y[n]

x[n] 1

+

1 1

1

1

1

1

x

1

1

x

Figure 4.21 SDFG implementing the difference equation (4.2)

The production and consumption rates are represented by positive and negative numbers,
respectively.

4.5.4.2 Example: IIR Filter as an SDFG

Draw an SDFG to implement the difference equation below:

y½¼x½þa 1 yn 1 ½ a 2 y½n 2 ð 4 : 2 Þ

The SDFG modeling the equation is given in Figure 4.21. The graph consists of two nodes for
multiplications and one node for addition, each taking one token as input and producing one token
at the output. The feedback paths from the output to the two multipliers each requires a delay.
These delays are shown with black dots on the respective edges.

4.5.4.3 Consistent and Inconsistent SDFG

An SDFG is described as consistent if it is correctly constructed. A consistent SDFG, once it
executes, neither starves for data nor requires any unbounded FIFOs on its edges. These graphs
represent both single- and multiple-rate systems. The consistency of an SDFG can be easily
confirmed by computing the rank of its topology matrix and checking whether that is one less than
the number of nodes in the graph [24].
An SDFG is described as inconsistent and experiences a deadlock in a streaming application if
some of its nodes starve for data at its input to fire, or on some of its edges it may need unbounded
FIFOs to store an unbounded production of tokens.

4.5.4.4 Balanced Firing Equations

A node in an SDFG fires a number of times, and in every firing produces a number of tokens on its
outgoing edges. All the nodes connected to this node on these direct edges must consume all the
tokens in their respective firing. Let nodes S and D be directly connected as shown in Figure 4.19,
where node S produces P S tokens and node D consumes C D tokens in their respective firings.
A balanced firing relationship can be expressed as:

f s P S ¼ f D C D ð 4 : 3 Þ