Unfolding is a transformation technique of duplicating the functional blocks to increase the throughput of the DSP program in such a way that preserves its functional behavior at its outputs. Unfolding was first proposed by Keshab K. Parhi and David G. Messerschmitt in 1989. Unfolding in general program is as known as Loop unrolling. Unfolding has applications in designing high-speed and low-power ASIC architectures. One application is to unfold the program to reveal hidden concurrency so that the program can be scheduled to a smaller iteration period, thus increasing the throughput of the implementation. Another application is parallel processing in word level or bit level. Therefore these transformed circuit could increase the throughput and decrease the power consumption.
Example For a DSP program y ( n ) = a y ( n − 9 ) + x ( n ) {\displaystyle \scriptstyle y(n)=ay(n-9)+x(n)} , replacing the index n {\displaystyle \scriptstyle n} by 2 k {\displaystyle \scriptstyle 2k} could result
y ( 2 k ) = a y ( 2 k − 9 ) + x ( 2 k ) {\displaystyle \scriptstyle y(2k)=ay(2k-9)+x(2k)} . Similarly, replacing the index n {\displaystyle \scriptstyle n} by 2 k + 1 {\displaystyle \scriptstyle 2k+1} could also result as
y ( 2 k + 1 ) = a y ( 2 k − 8 ) + x ( 2 k + 1 ) {\displaystyle \scriptstyle y(2k+1)=ay(2k-8)+x(2k+1)} . Hence, we transform the program into following program that receives 2 inputs x {\displaystyle \scriptstyle x} and produce 2 outputs y {\displaystyle \scriptstyle y} at each time.
y ( 2 k ) = a y ( 2 k − 9 ) + x ( 2 k ) {\displaystyle y(2k)=ay(2k-9)+x(2k)}
y ( 2 k + 1 ) = a y ( 2 k − 8 ) + x ( 2 k + 1 ) {\displaystyle y(2k+1)=ay(2k-8)+x(2k+1)}
Algorithm for unfolding Given a DSP program in Data flow graph(DFG) format and a unfolding factor J, unfolding process transforms the DSP program into a new one by duplicating the functional blocks and reconnecting the functional blocks while maintaining its DSP functionality. We call the program performed with factor J as J-unfolded DFG. In the J-unfolded DFG, for each node U in original DFG, there are J nodes in the transformed DFG with the same function as U. For each edge in the original DFG, there are J edges in the transformed DFG but its delay is only 1/J times to the original one.
Input format DFG A data flow graph is a labeled directed graph. Each node is labeled by a type indicating its functionality, and each edge is labeled by a number indicating its delay.
Unfolding algorithm Given Unfolding factor J
For each node U in the original DFG, first, we duplicate the J functional blocks as U0, U1, ..., UJ − 1, For each edge U arrow → V with w delays in the original DFG, we create the edges on transformed graph by Ui arrow → V(i+w)%J with ⌊ i + w J ⌋ {\displaystyle \scriptstyle \lfloor {\frac {i+w}{J}}\rfloor } for i = 0, 1, ... J − 1. The following graph shows the process of the algorithm. The original DFG is composed of 2 nodes and 1 edge with 37 delays. The unfolding process uses J = 4 as its unfolding factor. The algorithm first duplicates node U and V to 4 U nodes and 4 Vnodes. Then, it perform reconnecting on the nodes with corresponding delays, like U2 connects to V with index (2 + 37)%4 = 3. Besides, the delay on edge U1 to V2 is ⌊ 37 + 1 4 ⌋ = 9 {\displaystyle \scriptstyle \lfloor {\frac {37+1}{4}}\rfloor =9} , and the delay on edge U3 to V0 is ⌊ 37 + 3 4 ⌋ = 10 {\displaystyle \scriptstyle \lfloor {\frac {37+3}{4}}\rfloor =10} .
The following graph is another example showing the unfolding algorithm. Notice that, if there is the delay smaller than unfolding factor J, the J-unfolded DFG would create the edge with 0 delay but whose corresponding edge at original DFG may be the non-zero edge. Therefore, folding process is potential to create the 0-delay edge to increase the longest path in the DFG. ((P.S. fig. of bottom right is T2 that isn't T1))
Properties Unfolding preserves the number of delay elements in a DFG. This property holds since the sum of the unfolded DFG is
… excerpt ends here. Continue reading the full article.
