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

Retiming for folding 966 Example ■Original graph (S1/3) (S1/1) N (1) OUT X a b (S1/2) (S/0) (S2/0) (S2/2) (S2/3) (S2/1) Folding sets:S1={4,2,3,1}S2={5,8,6,7} 2021年2月 11

2021年2月 11 Retiming for folding  Example  Original graph + + X X X + D X D + (S1/3) (S1/1) (S1/0) (S1/2) (S2/0) (S2/3) (S2/2) (S2/1) a b c d 1 2 3 5 6 4 7 8 IN OUT (1) (2) Folding sets: S1={4, 2, 3, 1} S2={5, 8, 6, 7}

Retiming for folding 986 4*0-1+1-3,unfeasible without retiming Dp(U-→)=Nw(e)-P+v-u Folding equation Retiming constraint DE(1→2)=-3 r(1)-r(2)≤-1 D=(1→5)=0 r(1)-r(5)≤0 DF(1-→6)=2 r(1)-r(6)≤0 D=(1→7)=7 r()-r(7)≤1 By constraint graph and D=(1→8)=5 r(1)-r(8)≤1 shortest path algorithm, Ds(3→1)=0 r(3)-r(1)≤0 a solution can be D=(4→2)=0 r(4)-r(2)≤0 obtained. D=(5→3)=0 r(5)-r(3)≤0 r(1)=-1,r(2)=0 DF(6→4)=-4 r(6)-r(4)≤-1 r(3)=-1,r(4)=0 D(7→3)=-3 r(7)-r(3)≤-1 r(5)=-1,r(6)=-1 D=(8→4)=-3 r(8)-r(4)≤-1 r(7)=-2,r(8)=-1 2021年2月 12

2021年2月 12 Retiming for folding By constraint graph and shortest path algorithm, a solution can be obtained. (8 4) 3 (7 3) 3 (6 4) 4 (5 3) 0 (4 2) 0 (3 1) 0 (1 8) 5 (1 7) 7 (1 6) 2 (1 5) 0 (1 2) 3                           F F F F F F F F F F F D D D D D D D D D D D (1) (2) 1 (1) (5) 0 (1) (6) 0 (1) (7) 1 (1) (8) 1 (3) (1) 0 (4) (2) 0 (5) (3) 0 (6) (4) 1 (7) (3) 1 (8) (4) 1 r r r r r r r r r r r r r r r r r r r r r r                           ( ) ( ) ( ) e D U V F r U r V N              (1) 1, (2) 0 (3) 1, (4) 0 (5) 1, (6) 1 (7) 2, (8) 1 r r r r r r r r               Folding equation Retiming constraint ( ) ( ) e D U V Nw e P v u F U      4*0-1+1-3, unfeasible without retiming

/966 Retimed graph (S/3) (S/1) IN OUT D a (S/2) 3 6 (S1/0) (S2/0) (S2/2) d X. D (S2/3) (S271) 2021年2月 13

2021年2月 13  Retimed graph + D + X X X D + D D X D + (S1/3) (S1/1) (S1/0) (S1/2) (S2/0) (S2/3) (S2/2) (S2/1) a b c d 1 2 3 5 6 4 7 8 IN OUT D

folding transformation /96 D-(1→2)=4×1-1+1-3=1 Delay in D(1→5)=4×1-1+0-3=0 folded graph D=(1→6)=4×1-1+2-3=2 D(1→7)=4×1-1+3-3=3 D(1-→8)=4×2-1+1-3=5 D(3→1)=4×0-1+3-2=0 D(4→2)=4×0-1+1-0=0 D(5→3)=4×0-2+2-0=0 D-(6→4)=4×1-2+0-2=0 D(7→3)=4×1-2+2-3=1 D(8→4)=4×1-2+0-1=1 Thus,D'F(U→V)≥0 is guaranteed. 2021年2月 14

2021年2月 14 folding transformation (1 2) 4 1 1 1 3 1 (1 5) 4 1 1 0 3 0 (1 6) 4 1 1 2 3 2 (1 7) 4 1 1 3 3 3 (1 8) 4 2 1 1 3 5 (3 1) 4 0 1 3 2 0 (4 2) 4 0 1 1 0 0 (5 3) 4 0 2 2 0 0 (6 4) 4 1 2 0 2 0 (7 3) 4 1 2 2 3 1 (8 4) 4 F F F F F F F F F F F D D D D D D D D D D D                                                                         1 2 0 1 1     Delay in folded graph Thus, D’F (UàV)≥0 is guaranteed