Signal Flow Graphs and Data Flow Graphs - Signal Processing Systems - page 1265

program that describes J consecutive iterations of the original program. As a result,
in unfolded system each delay is J -slow.
Unfolding has applications in designing high-speed and low-power VLSI archi-
tectures. One application is to unfold the program to reveal hidden concurrencies so
that the program can be scheduled to a smaller iteration period, thus increasing
the throughput of the implementation. Another application is to design parallel
architectures at the word level and bit level from serial counterpart to increase the
throughput or decrease the power consumption of the implementation.

4.1.1 The DFG Based Unfolding

Two approaches can be used to derive the J -unfolded DFG. One is to write equations
for the original and the J -unfolded programs and then draw the corresponding
unfolded DFG. This method could be tedious for large value of J . The other
approach is to use a graph-based technique which directly unfolds the original DFG
to create the DFG of the J -unfolded program without explicitly writing the equations
describing the original unfolded system.
For each node U in the original DFG, there are J nodes with the same function as
U in the J -unfolded DFG. Additionally, for each edge in the original DFG, there are
J edges in the J -unfolded DFG. Consequently, the DFG of the J -unfolded program
contains J times as many nodes and edges as the DFG of the original DFG. The
following two-step algorithm could be used to construct a J -unfolded DFG:

1. For each node U in the original DFG, draw the J nodes U 0 , U 1 ,..., U J − 1.

2. For each edge U → V with w delays in the original DFG, draw the J edges

i + w

J

U i → V ( i + w ) % J with delays for i = 0 , 1 ,..., J − 1. Apparently, if an edge

has w < J delays in the original DFG, unfolding produces J − w edges with no

delays and w edges with 1 delay in the J -unfolded DFG.

To demonstrate the unfolding algorithm, the DFG in Fig. 10 b that corresponds to
the DSP algorithm in Fig. 10 a will serve as an example, where the nodes A and B
represent input and output, respectively, and the nodes C and D represent addition
and multiplication by a , respectively. To unfold this DFG in Fig. 10 b by unfolding
factor of 2 to obtain the 2-unfolded DFG as shown in Fig. 10 c , the two steps of the
unfolding algorithm are performed:

1. The 8 nodes A i , B i , C i and D i for i = 0 , 1 are first drawn according to the 1st step

of the unfolding algorithm.
2. After these nodes have been drawn, for an edge U → V such as D → C with

no delays, this step reduces to drawing the J edges U i → V i with no delays.

Additionally, for the edges C → D with w = 9 delay, there are the edges

0 + 9

C 0 → D ( 0 + 9 ) %2 = D 1 with ( ) = 4 delays and C 1 → D ( 1 + 9 ) %2 = D 0 with

2

1 + 9

( ) =

5 delays.

2