电子科技大学：《DSP算法实现技术与架构 VLSI Digital Signal Processing Systems Design and Implementation》课程教学资源（课件讲稿）Chapter 05 展开 Unfolding

电子科披女学 Uaiversity of Electreaie Selence and Techaolopof Chiaa Chapter 5 Unfolding Dr.Ling National Key Lab of Communication

Chapter 5 Unfolding Dr. Ling National Key Lab of Communication

5.1 Introduction /96 a x(2k) y(n) a 5D, y(2k) x(n) 9D y(2k+1)K 4D x(2k+1) y(n)=ay(n-9)+x(n) a y(2k)=ay(2k-9)+x(2k)=y(2(k-5)+1)+x(2k) y(2k+1)=ay(2k-8)+x(2k+1)=ay(2(k-4)+0)+x(2k+1) 2021年2月 2

2021年2月 2 5.1 Introduction + X x(n) y(n) a 9D + + X X a a 4D 5D x(2k+1) x(2k) y(2k+1) y(2k) y(n)  ay(n  9)  x(n) y(2k 1)  ay(2k  8)  x(2k 1)  ay(2(k  4)  0)  x(2k 1) y(2k)  ay(2k  9)  x(2k)  ay(2(k  5) 1)  x(2k)

Unfolding? 96 1. Unfolding is a transformation technique that can be applied to a DSP program to create a new program describing more than one iteration of the original program. 2. Unfolding creates a new programs that describes J consecutive iterations of the original program. 3.Unfolding can be used to reduce sample period and create parallel processing. 2021年2月 3

2021年2月 3 Unfolding? 1. Unfolding is a transformation technique that can be applied to a DSP program to create a new program describing more than one iteration of the original program. 2. Unfolding creates a new programs that describes J consecutive iterations of the original program. 3. Unfolding can be used to reduce sample period and create parallel processing

The applications of unfolding 96 Unfold the program to reveal hidden concurrencies so that the program can be scheduled to a smaller iteration period,thus increasing the throughput of the implementation. Design parallel architectures at the word level and bit level.At the word level,these architectures can be used to design word-parallel architectures from word-serial architectures to increase the throughput or decrease the power consumption.At the bit-level,unfolding can be used to design bit-parallel and digit-serial architectures from bit-serial architectures. 2021年2月 4

2021年2月 4 The applications of unfolding  Unfold the program to reveal hidden concurrencies so that the program can be scheduled to a smaller iteration period, thus increasing the throughput of the implementation.  Design parallel architectures at the word level and bit level. At the word level, these architectures can be used to design word-parallel architectures from word-serial architectures to increase the throughput or decrease the power consumption. At the bit-level, unfolding can be used to design bit-parallel and digit-serial architectures from bit-serial architectures

5.2 Unfolding algorithm 95 The J unfolded program contains J times as many nodes and edges as the original DFG. For each node U in the original DFG,draw the J nodes Uo,U,...,U-1. s For each edge U->V with w delays in the original FG,draw the edges U withdelays fori=0,1,..,J-1. 2021年2月 5

2021年2月 5 5.2 Unfolding algorithm  The J unfolded program contains J times as many nodes and edges as the original DFG.  For each node U in the original DFG, draw the J nodes U0 ,U1 ,…,UJ-1 .  For each edge UV with w delays in the original DFG, draw the J edges UiV(i+w)%J with delays for i=0,1,…,J-1.        J i w        J i w

U Unfolding Example ■J=2 B Ao Co Do 5D Bo A 9D Br 4D A D 0+9 L2→D0+92 2021年2月 6

2021年2月 6 Unfolding  Example  J=2 C 9D D B A C0 4D 5D C1 D0 D1 B1 B0 A1 A0 0 9 2 C D 0 (0 9)%2         

U Unfolding Example ■J=4 Uo 37D 10D U V 9D U 9D U2 1+37 9D U: 2021年2月 7

2021年2月 7 Unfolding  Example  J=4 U V 37D U0 V3 V2 V1 V0 U3 U2 U1 9D 10D 9D 9D 1 37 4 U V 1 (1 37)%4         

Unfolding Example ■]=3 2D D 2D U Uo 2D 5D 6D D T 2D U U: 2D D 2021年2月 8

2021年2月 8 Unfolding  Example  J=3 U V T 5D 6D D U0 U2 U1 V0 V2 V1 T0 T2 T1 2D 2D 2D 2D 2D D D 1 (1) l i,k  1 (1) l i,k  

Unfolding algorithm proof 295 The unfolding algorithm described here indeed creates an unfolded DFG with the same precedence constraints as the original DFG. The edges UV(i+w)%with delays in the unfolded DFG corresponds to the edge U>V with w delay in the original DFG. The k-th iteration of the node U:in the J-unfolded DFG executes the (Jk+i)-th iteration of the node U in the original DFG. The output of the k-th iteration of the node U is consumed by the iteration of the node V in the unfolded DFG. 2021年2月 9

2021年2月 9 Unfolding algorithm proof  The unfolding algorithm described here indeed creates an unfolded DFG with the same precedence constraints as the original DFG.  The edges UiV(i+w)%J with delays in the unfolded DFG corresponds to the edge UV with w delay in the original DFG.  The k-th iteration of the node Ui in the J-unfolded DFG executes the (Jk+i)-th iteration of the node U in the original DFG.  The output of the k-th iteration of the node Ui is consumed by the iteration of the node V(i+w)%J in the unfolded DFG.        J i w th J i w k         (  )

Unfolding algorithm proof The output of the iteration of the node Vw corresponds to the iteration of the node V in the original DFG. U: i+w V(itw)J k k+ U V Jk+i J++6+m% =Jk+i+w 2021年2月 10

2021年2月 10 Unfolding algorithm proof  The output of the iteration of the node V(i+w)%J corresponds to the iteration of the node V in the original DFG. th J i w k         (  ) i w J th J i w J k           ( (  ) ( )% ) Ui U V(i+w)%J i w J        k i w k J         ? Jk i  ( ) ( )% i w J k i w J J Jk i w              w V