Kỹ thuật viễn thông - Chapter 5: Unfolding

Chapter 5: Unfolding Keshab K. Parhi Chap. 5 2 • Unfolding º Parallel Processing A B 2D (1) (1) A0àB0=> A2àB2=> A4àB4=>.. A1àB1=> A3àB3=> A5àB5=>.. 2 nodes & 2 edges T¥= (1+1)/2 = 1ut 2-unfolded A0 B0 D (1) (1) A1 B1 D (1) (1) 0,2,4,. 1,3,5,. 4 nodes & 4 edges T¥= 2/2 = 1ut T’¥= 2ut T’¥= 2ut • 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 3 • 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 V37D U0 U3 U2 U1 V3 V2 V1 V09D 9D 9D 10D Ø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. w = 37 Þë(i+w)/4û = 9, i = 0,1,2 =10, i = 3 Chap. 5 4 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 J- unfolded DFG with iteration bound JT¥ . U T V D 5D 6D U0 U1 U2 V0 V1 V2 T0 T1 T2 2D 2D 2D D D 2D 2D 3-unfolded DFG Chap. 5 5 • 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 6 Case 1 : ØThe original DFG cannot have sample period equal to the iteration bound because a node computation time is more than iteration bound Ø If the computation time of a node ‘U’, tu, is greater than the iteration bound T¥, then étu/T ¥ù - unfolding should be used. Ø In the example, tu = 4, and T¥ = 3, so é4/3ù - unfolding i.e., 2- unfolding is used. Chap. 5 7 • Case 2 : ØThe original DFG cannot have sample period equal to the iteration bound because the iteration bound is not an integer. ØIf a critical loop bound is of the form tl/wl where tl and wl are mutually co-prime, then wl-unfolding should be used. ØIn the example tl = 60 and wl = 45, then tl/wl should be written as 4/3 and 3-unfolding should be used. •Case 3 : In this case the minimum unfolding factor that allows the iteration period to equal the iteration bound is the min value of J such that JT¥ is an integer and is greater than the longest node computation time. Chap. 5 8 • Parallel Processing : Ø Word- Level Parallel Processing Ø Bit Level Parallel processing vBit-serial processing vBit-parallel processing vDigit-serial processing Chap. 5 9 • Bit-Level Parallel Processing Bit-parallel a0 a1 a2 a3 b0 b1 b2 b3 Bit-seriala3 a2 a1 a0 b3 b2 b1 b0 Digit-Serial (Digit-size = 2) a2 a0 a3 a1 b2 b0 b3 b1 Bit-serial adder D a3 a2 a1 a0 b3 b2 b1 b0 s3 s2 s1 s0 4l+1,2,34l+0 0 Chap. 5 10 • The following assumptions are made when unfolding an edge U®V : Ø The wordlength W is a multiple of the unfolding factor J, i.e. W = W’J. Ø All edges into and out of the switch have no delays. • With the above two assumptions an edge U®V can be unfolded as follows : Ø Write the switching instance as Wl + u = J( W’l + ëu/Jû ) + (u%J) Ø Draw an edge with no delays in the unfolded graph from the node Uu%J to the node Vu%J, which is switched at time instance ( W’l + ëu/Jû ) . Chap. 5 11 Example : U V 12l + 1, 7, 9, 11 U0 V0 U1 V1 U2 V2 4l + 3 4l + 0,2 4l + 3 Unfolding by 3 To unfold the DFG by J=3, the switching instances are as follows 12l + 1 = 3(4l + 0) + 1 12l + 7 = 3(4l + 2) + 1 12l + 9 = 3(4l + 3) + 0 12l + 11 = 3(4l + 3) + 2 Chap. 5 12 • Unfolding a DFG containing an edge having a switch and a positive number of delays is done by introducing a dummy node. A B C 2D 6l + 1, 5 6l + 0, 2, 3, 4 A B C D2D 6l + 1, 5 6l + 0, 2, 3, 4 Inserting Dummy node A0 A1 A2 D1 D0 D2 B2 B1 B0 C2 C1 C0 2l + 0 2l + 1 2l + 0 2l + 1 2l + 1 2l + 0 D D B0 A2 B1 B2 A0 C0 C1 C2 D 2l + 0 2l + 1 2l + 0 2l + 1 Chap. 5 13 • If the word-length, W, is not a multiple of the unfolding factor, J, then expand the switching instances with periodicity lcm(W,J) • Example: Consider W=4, J=3. Then lcm(4,3) = 12. For this case, 4l = 12l + {0,4,8), 4l+1 = 12l + {1,5,9}, 4l+2 = 12l + {2,6,10}, 4l+3 = 12l + {3,7,11}. All new switching instances are now multiples of J=3.