VLSI Digital Signal Processing Systems: Design and Implementation

5.2    AN ALGORITHM FOR UNFOLDING

In this section, an algorithm for unfolding a DFG by an unfolding factor J is described. Before this algorithm is presented, some notations are introduced and some basic properties of unfolded DFGs are described.

The operation is the floor of x, which is the largest integer less than or equal to x. For example, The operation a%b is the remainder after dividing a by b, where a and b are integers. For example, 11%4 = 3 and 25%3 = 1.

For each node U in the original DFG, there are J nodes with the same function as U in the J-unfolded DFG. For example, for the adder in Fig. 5.1(a), there are 2 adders in the 2-unfolded DFG in Fig. 5.1(b). Similarly, there are 2 multipliers in Fig. 5.1(b) corresponding to the multiplier in Fig. 5.1(a).

For each edge in the original DFG, there are J edges in the J-unfolded DFG. This can be observed in Fig. 5.1, where the edge from the adder to the multiplier in the original DFG results in 2 edges from an adder to a multiplier in the unfolded DFG.

Keeping in mind that the DFG of the J-unfolded program contains J times as many nodes and edges as the DFG of the original DFG, the following unfolding algorithm can be used to construct a J-unfolded DFG.

Unfolding Algorithm

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