Lecture VLSI Digital signal processing systems: Chapter 5 - Keshab K. Parhi

Chapter 5: Unfolding Keshab K. Parhi • Unfolding º Parallel Processing (1) (1) A B 2D A àB => A àB => A àB =>….. A1àB1=> A3àB3=> A5àB5=>….. 2 nodes & 2 edges T¥= (1+1)/2 = 1ut 2-unfolded (1) (1) 0,2,4,…. A0 B0 T’¥= 2ut D (1) (1) 1,3,5,…. A1 B1 T’ = 2ut 4 nodes & 4 edges T¥= 2/2 = 1ut • In a ‘J’ unfolded system each delay is J-slow => if input to a delay element is the signal x(kJ + m), the output is x((k-1)J + m) = x(kJ + m – J). Chap. 5 2 • Algorithm for unfolding: ⮚For each node U in the original DFG, draw J node U , U , U2 ,…, UJ-1 . ⮚For each edge U ® V with w delays in the original DFG, draw the J edges U ® V with ë(i+w)/Jû delays for i = 0, 1, …, J-1. U 37D V w = 37 Þë(i+w)/4û = 9, i = 0,1,2 =10, i = 3 U0 9D V0 U1 9D V1 U2 9D V2 U3 10D V3 ⮚Unfolding of an edge with w delays in the original DFG produces J-w edges with no delays and w edges with 1delay in J unfolded DFG for w < J. ⮚Unfolding preserves precedence constraints of a DSP program. Chap. 5 3 D 5D 6D 3-unfolded T DFG Properties of unfolding : U0 U1 U2 2D D D V0 2D T0 V1 2D T1 V2 2D T2 2D ⮚Unfolding preserves the number of delays in a DFG. This can be stated as follows: ëw/Jû + ë(w+1)/Jû + … + ë(w + J - 1)/Jû = w ⮚J-unfolding of a loop l with w delays in the original DFG leads to gcd(w , J) loops in the unfolded DFG, and each of these gcd(w , J) loops contains w/ gcd(w , J) delays and J/ gcd(wl , J) copies of each node that appears in l. ⮚Unfolding a DFG with iteration bound T results in a J-unfolded DFG with iteration bound JT¥ . Chap. 5 4 • Applications of Unfolding ⮚Sample Period Reduction ⮚Parallel Processing • Sample Period Reduction ⮚Case 1 : A node in the DFG having computation time greater than T¥. ⮚Case 2 : Iteration bound is not an integer. ⮚Case 3 : Longest node computation is larger than the iteration bound T , and T is not an integer. Chap. 5 5 ... - tailieumienphi.vn