Lecture VLSI Digital signal processing systems - Chapter 4 introduce the retiming. The main contents of this chapter include: Retiming formulation, properties of retiming, cutset retiming,.and another content. | Chapter 4: Retiming Keshab K. Parhi Retiming : Moving around existing delays • Does not alter the latency of the system • Reduces the critical path of the system • Node Retiming D 5D 3D 3D 2D •Cutset Retiming D B A C Chap. 4 D 2D D D F D D E 2 Retiming • Generalization of Pipelining • Pipelining is Equivalent to Introducing Many delays at the Input followed by Retiming Chap. 4 3 • Retiming Formulation r(U) ω U Source node Retiming r(V) V Destination node U ω’ V ω’ = ω + r(V) - r(U) •Properties of retiming –The weight of the retimed path p = V 0 --> V1 --> Vk is given by ωr(p)= ω(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 4 • Retiming for clock period minimization – Feasibility constraint ω’(U,V) ≥ 0 ⇒ causality of the system ⇒ ω(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) (1) G D (1) (1) 2D A B C D E (1) (1) (1) D W(A,E) = 1 & D(A,E) = 5 F (2) Chap. .