VLSI Digital Signal Processing Systems: Design and Implementation

5.5    APPLICATIONS OF UNFOLDING

5.5.1    Sample Period Reduction

The iteration bound, T_∞, is the lower bound on the iteration period of a recursive DSP program. An implementation of the DSP program can never achieve an iteration period less than the iteration bound, even if infinite processors are available. A thorough description of the iteration bound is found in Chapter 2. In some cases, the DSP program cannot be implemented with the iteration period equal to the iteration bound without the use of unfolding. This section considers 2 such cases where unfolding allows the DSP program to be implemented with an iteration period equal to the iteration bound.

The 1st case where the iteration period cannot be made equal to the iteration bound is when there is a node in the DFG that has computation time greater than T_∞ (we assume here that the node cannot be split into 2 subnodes with smaller computation times). In this case, even retiming cannot be used to reduce the computation time of the critical path of the DFG to T_∞. For example, the DFG in Fig. 5.6(a) has iteration bound T_∞ = 3, but the nodes S and T each require computation times of 4 u.t., so the minimum sample period after retiming is 4 u.t. This DFG can be unfolded with unfolding factor 2 to get the DFG in Fig. 5.6(b). This unfolded DFG has iteration bound T_∞ = 6, and its critical path is 6 u.t. The unfolded DFG performs 2 iterations of the original DSP program in 6 u.t., so the sample period of the unfolded DFG is 6/2 = ...