TAILIEUCHUNG - Lecture VLSI Digital signal processing systems: Chapter 5 - Keshab K. Parhi
Lecture VLSI Digital signal processing systems - Chapter 5 discuss the unfolding. The main contents of this chapter include: Algorithm for unfolding, applications of unfolding, sample period reduction, parallel processing,. Inviting you refer. | Chapter 5: Unfolding Keshab K. Parhi • Unfolding ≡ Parallel Processing 2-unfolded (1) B (1) A 2D A0àB0=> A2àB2=> A4àB4=> A1àB1=> A3àB3=> A5àB5=> 2 nodes & 2 edges T∞ = (1+1)/2 = 1ut (1) 0,2,4, . B0 (1) A0 T’∞ = 2ut (1) A1 T’∞ = 2ut D (1) 1,3,5, . B1 D 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 U0 , U1 , U2 , , UJ-1 . Ø For each edge U → V with w delays in the original DFG, draw the J edges Ui → V(i + w)%J 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 V2 U3 10D 9D 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 2D D V U 3-unfolded 6D 5D T DFG U0 V0 2D U1 V1 2D T1 U2 D D T0 V2 2D T2 2D Properties of unfolding : Ø 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 wl delays in the original DFG leads to gcd(wl , J) loops in the unfolded DFG, and each of these gcd(wl , J) loops contains wl/ gcd(wl , 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 Junfolded 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. .
đang nạp các trang xem trước