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’