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

P S C D

D,T D

S,T S

Figure 4.19 SDFG with nodes S and D

When the number of cycles each node takes to execute and the number of tokens produced and
consumed by the node are not known a priori, these design cases can be modeled as dynamic DFG
(DDFG).

4.5.4.1 Synchronous Dataflow Graph

A typical streaming application continuously processes sampled data from an A/D converter and the
processed data is sent to a D/A converter. An example of a streaming application is a multimedia
processing system consisting of processes or tasks where each task operates on a predefined number
of samples and then produces a fixed number of output values. These tasks are periodically executed
in a defined order.
A synchronous dataflow graph (SDFG) best describes these applications. Here the number of
tokens consumed by a node on each of its edges, and as a result of its firing the number of tokens it
produces on its output edges, are known a priori. This leads to efficient HW mapping and
implementation.
Nodes are labeled with their names and number of cycles or time units they take in execution, as
demonstrated in Figure 4.19. An edge is labeled at tail and head with production and consumption
rates, respectively. The black dots on the edges are the algorithm delays between two nodes.
Figure 4.19 shows source and destination nodes S and D taking execution time T S and T D units,
respectively. The data or token production rate of S is P S and the data consumption rate of node D is
C D . The edge shows two algorithmic delays between the nodes specifying that node D uses two
iterations-old data for its firing.
An example of an SDFG is shown in Figure 4.20(a). The graph consists of three nodes A, B and C
with execution times of 2, 1 and 1 time units, respectively. The production and consumption rates of
each node are also shown, with the number of required initial delays represented by filled circles on
the edges.
An SDFG can also be represented by a topology matrix, as shown in Figure 4.20(b). Each
column of the matrix represents a node and each row corresponds to an edge. The three columns
represent nodes A, B and C in the same order. The first row depicts edge e 1 connecting nodes A
and B. Similarly the second and third rows show the connections on edges e 2 and e 3 , respectively.

1 1

e 2 1

0
0

-1
2
-2

0
-2
2

e 1 2 2

A, 2 B,1 C,1

1

1

2

2

e 3

(a) (b)

Figure 4.20 (a) Example of an SDFG with three nodes A, B and C. (b) Topology matrix for the SDFG