Kỹ thuật viễn thông - Chapter 4: Retiming

Chapter 4: Retiming Keshab K. Parhi Chap. 4 2 Retiming : Moving around existing delays • Does not alter the latency of the system • Reduces the critical path of the system • Node Retiming 5D D 3D 3D 2D •Cutset Retiming A E DB C F 2D D D D D D Chap. 4 3 Retiming • Generalization of Pipelining • Pipelining is Equivalent to Introducing Many delays at the Input followed by Retiming Chap. 4 4 • Retiming Formulation r(U) r(V) Source node Destination node U V w Retiming U V w’ w’ = w + r(V) - r(U) •Properties of retiming –The weight of the retimed path p = V0 --> V1 --> ..Vk is given by wr(p)= w(p) + r(Vk) - r(V0) –Retiming does not change the number of delays in a cycle. –Retiming does not alter the iteration bound in a DFG as the number of delays in a cycle does not change –Adding the constant value j to the retiming value of each node does not alter the number of delays in the edges of the retimed graph. •Retiming is done to meet the following – Clock period minimization – Register minimization Chap. 4 5 • Retiming for clock period minimization – Feasibility constraint w’(U,V) ³ 0 Þ causality of the system Þ w(U,V) ³ r(U) - r(V) (one inequality per edge) – Critical Path constraint r(U) - r(V) £ W(U,V) - 1 for all vertices U and V in the graph such that D(U,V) > c where c = target clock period. The two quantities W(U,V) and D(U,V) are given as: W(U,V) = min{w(p) : U®V} D(U,V) = max{t(p) : U®V and w(p) = W(U,V) A B F C D E G (1) (1) (1) (1) (1) (1) (2) D D 2D W(A,E) = 1 & D(A,E) = 5 Chap. 4 6 • Algorithm to compute W(U,V) and D(U,V): • Let M = tmaxn, where tmax is the maximum computation time of the nodes in G and n is the # of nodes in G. • Form a new graph G’ which is the same as G except the edge weights are replaced by w’(e) = Mw(e) – t(u) for all edges UàV. • Solve for all pair shortest path problem on G’ by using Floyd Warshall algorithm. Let S’UV be the shortest path form U à V. • If U ¹ V, then W(U,V) = éS’UV/Mù and D(U,V) = MW(U,V) - S’UV + t(V). If U = V, then W(U,V) = 0 and D(U,V) = t(U). • Using W(U,V) and D(U,V) the feasibility and critical path constraints are formulated to give certain inequalities. The inequalities are solved using constraint graphs and if a feasible solution is obtained then the circuit can be clocked with a period ‘c’. Chap. 4 7 • Solving a system of inequalities : Given M inequalities in N variables where each inequality is of the form ri – rj £ k for integer values of k. Ø Draw a constraint graph ØDraw the node i for each of the N variables ri, I= 1, 2, , N. ØDraw the node N+1. ØFor each inequality ri – rj £ k , draw the edge jài of length k. ØFor each node i, i = 1, 2, , n, draw the edge N+1 ài from the node N+1 to node I with length 0. Ø Solve using a shortest path algorithm. ØThe system of inequalities have a solution iff the constraint graph contains no negative cycles. ØIf a solution exists, one solution is where ri is the minimum length path from the node N+1 to node i. Chap. 4 8 • K-slow transformation – Replace each D by kD A B D (1) (1) Clock 0 A0 ® B0 1 A1 ® B1 2 A2 ® B2 After 2-slow transformation A B 2D (1) (1) Titer= 2ut Clock 0 A0®B0 1 2 A1®B1 3 4 A2®B2 Tclk= 2ut Titer= 2´2ut=4ut *Input new samples every alternate cycles. *null operations account for odd clock cycles. *Hardware utilized only 50% time Chap. 4 9 • Retiming 2-slow graph A B D D Tclk = 1ut Titer = 2´1=2ut *Hardware Utilization = 50 % *Hardware can be fully utilized if two independent operations are available. Chap. 4 10 A 100 stage Lattice Filter with critical path 2 multiplications and 101 additions The 2-slow version 2-Slow Lattice Filter (Fig. 4.7) Chap. 4 11 A retimed version of the 2 slow circuit with critical path of 2 multiplications and 2 additions If Tm = 2 u.t. and Ta = 1 u.t., then Tclk = 6 u.t., Titer = 2X6 = 12 u.t. In Original Lattice Filter, Titer = 105 u.t. Iteration Period Bound = 7 u.t. Chap. 4 12 Other Applications of Retiming • Retiming for Register Minimization (Section 4.4.3) • Retiming for Folding (Chapter 6) • Retiming for Power Reduction (Chap. 17) • Retiming for Logic Synthesis (Beyond Scope of This Class) • Multi-Rate/Multi-Dimensional Retiming (Denk/Parhi, Trans. VLSI, Dec. 98, Jun.99)