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

[2,4] [1 ,3] [3 ,8]

[4,7]

A,[1,3] B,[2,4]

C,[3,7]

Figure 4.27 Example of a CSDFG, where node A first fires and takes 1 time unit and produces 2 tokens,
and then in its second firing it takes 3 time units and generates 4 tokens. Node B in its first firing consumes
1 token in 2 time unit, and the in its second firing takes 4 time units and consumes 3 tokens; it respectively
produces 4 and 7 tokens. A similar behavior of node C can be inferred from the figure

4.5.9 Multi-dimensional Arrayed Dataflow Graphs
This graph consists of an array of nodes and edges. The graph works well for multi-dimensional
signal processing or parallel processing algorithms.

4.5.10 Control Flow Graphs

Although a synchronous dataflow graph (SDFG) is statically schedulable owing to it predictable
communications, it can also express recursion with a fixed number of iterations. However, the
representation has an expressive limitation because it cannot capture a data-dependent flow of
tokens unless it makes use of transition refinements. This limitation prevents a concise representa-
tion of conditional flows incorporating if-else-then and do-while loops and data-depen-
dent recursions.
As opposed to a DFG which is specific to a dataflow algorithm, a CFG is suitable to process a
control algorithm. These algorithms are usually encountered in implementing communication
protocols or controller designs for datapaths.
A control dataflow graph (CDFG) combines data-driven and control-specific functionality of
an algorithm. Each node of the DFG represents a mathematical operation, and each edge represents
either precedence or a data dependency between the operations. ACDFGmay change the number of
tokens produced and consumed by the nodes in different input settings. ADFGwith varying rates of
production and consumption is called a dynamic dataflow graph (DDFG).
Example: The example here converts a code consisting of decision statements to CDFG.
Figure 4.28 shows a CDFG that implements the following code:

if (a==0)
c=a+b e;
else
c=a-b;

The figure shows two conditional edges and two hierarchically built nodes for conditional firing.
This type of DFG is transformed for optimal HWmapping by exploiting the fact that only one of the
many conditional nodes will fire. The transformed DFG shares a maximum of HW resources and
moves the conditional execution on selection of operands for the shared resource.
A dataflow graph is a good representation for reconfigurable computing. Each block in the
DFG can be sequentially mapped on reconfigurable hardware. Figure 4.29 illustrates the fact that,
in a JPEG implementation, sequential firing of nodes can be mapped on the same HW. This
sharing of HW resources at run time reduces the area required, at the cost of longer execution
times.