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

电子种越女学 University of Electroale Science and Technelery of China 986 Chapter 6 Folding Dr.Ling National Key Lab of Science and Technology on Communications

Chapter 6 Folding Dr. Ling National Key Lab of Science and Technology on Communications

Folding /96 The folding transformation is used to systematically determine the control circuits in DSP architectures where multiple algorithm operations are time- multiplexed to a single function unit. ■ By executing multiple algorithm operations on a signal functional unit,the number of functional units in the implementation is reduced,resulting in an integrated circuits with low silicon area. It is important to minimize the silicon area of the IC, which is achieved by reducing the number of functional units,registers,multiplex and interconnection wires. 2021年2月 2

2021年2月 2 Folding  The folding transformation is used to systematically determine the control circuits in DSP architectures where multiple algorithm operations are time￾multiplexed to a single function unit.  By executing multiple algorithm operations on a signal functional unit, the number of functional units in the implementation is reduced, resulting in an integrated circuits with low silicon area.  It is important to minimize the silicon area of the IC, which is achieved by reducing the number of functional units, registers, multiplex and interconnection wires

6.1 introduction 956 y(n)=a(n)+b(n)+c(n) 21+0 b(n)· 21+1 (n) b(n) c(n) a(n) <21+0 21+0/ y(n) a(n) →y(n) (1) (1) T2+1 Cycle Adder input Adder input Output (left) (top) 0 a(0) b(0) 1 a(0)+b(0) c(0) 2 a(1) b(1) a(0)+b(0)+c(0) 3 a(1)+b(1) c(1) 4 a(2) b(2) a(1)+b(1)+c(1) 5 a(2)+b(2) c(2) 2021年2月 3

2021年2月 3 6.1 introduction a(n) + + y(n) b(n) c(n) (1) (1) + D a(n) b(n) c(n) y(n) 2l+0 2l+1 2l+0 2l+0 2l+1 y(n)  a(n) b(n) c(n) Cycle Adder input (left) Adder input (top) Output 0 a(0) b(0) 1 a(0)+b(0) c(0) 2 a(1) b(1) a(0)+b(0)+c(0) 3 a(1)+b(1) c(1) 4 a(2) b(2) a(1)+b(1)+c(1) 5 a(2)+b(2) c(2)

/96 In general,the data on the input of the folded realization is assumed to be valid for N cycles before changing,where N is the number of algorithm operations executed on a single functional unit in hardware. Folding provides a means for trading area for time in a DSP architecture. Folding can be used to reduce the number of hardware functional units by a factor of N at the expense of increasing the computation frequency by a factor of N. 2021年2月 4

2021年2月 4  In general, the data on the input of the folded realization is assumed to be valid for N cycles before changing, where N is the number of algorithm operations executed on a single functional unit in hardware.  Folding provides a means for trading area for time in a DSP architecture.  Folding can be used to reduce the number of hardware functional units by a factor of N at the expense of increasing the computation frequency by a factor of N

/96 While the folding transformation reduces the number of functional units in the architecture,it may also lead to an architecture that uses a large amount of registers. To avoid architectures using excessive amounts of registers,techniques can be used to compute the minimum number of registers and to allocation data to these register. 2021年2月 5

2021年2月 5  While the folding transformation reduces the number of functional units in the architecture, it may also lead to an architecture that uses a large amount of registers.  To avoid architectures using excessive amounts of registers, techniques can be used to compute the minimum number of registers and to allocation data to these register

6.2 Folding Transformation /986 The folding transformation provides a systematic technique for designing control circuits for hardware where several algorithm operations are time-multiplexed on a single functional unit. Folding equation is the basis for this technique. 2021年2月 6

2021年2月 6 6.2 Folding Transformation  The folding transformation provides a systematic technique for designing control circuits for hardware where several algorithm operations are time-multiplexed on a single functional unit.  Folding equation is the basis for this technique

43 Folding equation 966 (Pu) Nl+v U W(e)D Ho PuD DU→V) Hv w(e) H H(v) NI u Pu Nw(e) D(U->V)=[N(I+w(e))+v]-[NI+u+P)=Nw(e)-P+v-u 2021年2月 7

2021年2月 7 Folding equation U W(e)D V (Pu) HU PuD DF(UàV) HV Nl+v ( ) [ ( ( )) ] [ } ( ) e D U V N l w e v Nl u P Nw e P v u F U U            l w(e) U V H(u) H(v) Nl Nw(e) u Pu v

Folding set /96 A folding set is an ordered set of operations executed by the same functional unit. The operation in the j-th position within the folding set is executed by the functional unit during the time partition j. a example ■S1={A1Φ，A2}forN=3; 2021年2月 8

2021年2月 8 Folding set  A folding set is an ordered set of operations executed by the same functional unit.  The operation in the j-th position within the folding set is executed by the functional unit during the time partition j.  example  S1={A1 ,Φ,A2 } for N=3;

Steps 96 1.Pre-assign the folding sets. 2.Retiming to get a feasible solution that D(U→V)≥0. Once valid folding sets have been assigned, retiming can be used to ether satisfy this property or determine that the folding set are not feasible. 3.Fold the retimed DFG using folding sets and DU→V). 2021年2月 9

2021年2月 9 Steps 1. Pre-assign the folding sets. 2. Retiming to get a feasible solution that DF (UàV)≥0.  Once valid folding sets have been assigned, retiming can be used to ether satisfy this property or determine that the folding set are not feasible. 3. Fold the retimed DFG using folding sets and DF (UàV)

Retiming for Folding /96 Goal:For a folded system to be realizable,D'(U->V)20 must hold for all the edges in the folded graph. ■ If W-(e)is the folded delays in the edge U>V for the retimed graph.W(e)=w(e)+r(V)-r(U) D'(U→V)≥0 →Nw-(e)-Pu+v-u≥0 →N(w(e)+r(V)-r(U)-Pu+v-u≥0 r(U-rW)sD(U→ W retime fold r-rs2” G G G w(e) w-(e) DE DE' 2021年2月 10

2021年2月 10 Retiming for Folding  Goal: For a folded system to be realizable, D’F (UàV)≥0 must hold for all the edges in the folded graph.  If Wr (e) is the folded delays in the edge UàV for the retimed graph. Wr (e)=w(e)+r(V)-r(U) D’ F (UàV)≥0  Nwr (e)–PU+v–u≥0  N(w(e)+r(V)–r(U))-PU+v–u≥0  ( ) ( ) ( ) ( ) ( ) ( ) F F D U V r U r V N D U V r U r V N             G Gr GF retime fold w(e) wr(e) DF DF’