ELEC 7770 Advanced VLSI Design Spring 2012 Constraint Graph and Retiming SolutionRetiming TheoremRetiming Theorem ExplainedExamine Condition 2Timing OptimizationRepresenting a ConstraintConstraint GraphFeasibility ConditionExample: Infeasible ConstraintsSolving a Constraint SetThe General Path ProblemDijkstra’s Shortest Path AlgorithmDijkstra’s Shortest Path Algorithm Example 1Dijkstra’s Shortest Path Algorithm Example 2Dijkstra’s Algorithm, G(V, E, W)Try Dijkstra’s Algorithm for Your GraphDijkstra’s Longest Path AlgorithmDijkstra’s Alg. Does Not Work for Cycles, Mixed WeightsBellman’s Equations – Shortest PathBellman-Ford Algorithm, G(V, E, W)Bellman-Ford Shortest PathBellman-Ford Longest PathBellman’s Equations – Longest PathBellman-Ford for Cycles, Neg. WeightsBellman-Ford for Negative CycleRetiming ExampleRetiming GraphFeasibility Constraints (Condition 1)Slide 29Max Delay for Min Weight PathsTiming Optimization, T = 7.5?Slide 32Timing Optimization, T = 11.25?Slide 34Retimed CircuitReferenceSpring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)11ELEC 7770ELEC 7770Advanced VLSI DesignAdvanced VLSI DesignSpring 2012Spring 2012Constraint Graph and Retiming SolutionConstraint Graph and Retiming SolutionVishwani D. AgrawalVishwani D. AgrawalJames J. Danaher ProfessorJames J. Danaher ProfessorECE Department, Auburn UniversityECE Department, Auburn UniversityAuburn, AL 36849Auburn, AL [email protected]@eng.auburn.eduhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr10/course.htmlhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr10/course.htmlSpring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)22Retiming TheoremRetiming TheoremGiven a network G(V, E, W) and a cycle time T, Given a network G(V, E, W) and a cycle time T, (r1, . . . ) is a feasible retiming if and only if:(r1, . . . ) is a feasible retiming if and only if:ri – rj ri – rj ≤ wij≤ wijfor all edges (vi,vj) for all edges (vi,vj) εε E Eri – rj ≤ W(vi,vj) – 1 ri – rj ≤ W(vi,vj) – 1 for all node-pairs vi, vj such thatfor all node-pairs vi, vj such thatD(vi,vj) > TD(vi,vj) > TWhere,Where,W(vi,vj) is the minimum weight path between vi and vjW(vi,vj) is the minimum weight path between vi and vjD(vi,vj) is the maximum delay among all minimum D(vi,vj) is the maximum delay among all minimum weight paths between vi and vjweight paths between vi and vjRetiming Theorem ExplainedRetiming Theorem ExplainedCondition 1, ri – rj Condition 1, ri – rj ≤ wij is related to edge weight:≤ wij is related to edge weight:Original circuit is feasible => original weight wij is positiveOriginal circuit is feasible => original weight wij is positiveOriginally, ri = rj = 0Originally, ri = rj = 0Retiming, rj flip-flops added to eij, ri flip-flops removed Retiming, rj flip-flops added to eij, ri flip-flops removed from eij, net reduction ri – rj must be less than wij to leave from eij, net reduction ri – rj must be less than wij to leave the retimed weight of eij positive.the retimed weight of eij positive.Condition 2, ri – rj ≤ W(vi,vj) – 1 is related to path Condition 2, ri – rj ≤ W(vi,vj) – 1 is related to path delays between node pairs being less than clock delays between node pairs being less than clock period T whenever path weight is 0.period T whenever path weight is 0.Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)33Examine Condition 2Examine Condition 2Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)44vivjrirjW1, D1W2, D2W3, D3W1 = W2 < W3, W(vi, vj) = W1 = W2, minimum weight among pathsD1 > D2, therefore D(vi, vj) = D1, maximum delay of a minimum weigh pathIf D1 ≤ T, there is no requirement on ri, rjIf D1 > T, Retimed weight W1’ = W1 – ri + rj ≥ 1 (at least 1 FF on path)or ri – rj ≤ W1 – 1Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)55Timing OptimizationTiming OptimizationFind the clock period (T) by path analysis.Find the clock period (T) by path analysis.Set clock period to T/2 and find a feasible Set clock period to T/2 and find a feasible retiming.retiming.If feasible, further reduce the clock period to If feasible, further reduce the clock period to half.half.If not feasible, increase clock period.If not feasible, increase clock period.Do a binary search for optimum clock period.Do a binary search for optimum clock period.Retime the circuit.Retime the circuit.Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)66Representing a ConstraintRepresenting a Constraint ri – rj ≤ wij or rj ≥ ri – wij rj ri– wijSpring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)77Constraint GraphConstraint Graph r1 ≥ r0 + 3 r1 ≥ r2 + 1 r2 ≥ r0 + 1 r2 ≥ r1 – 1 r3 ≥ r1 + 1 r3 ≥ r2 + 4 r0 ≥ r3 – 6 r0r1r2r3-1 1311 4-6Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)88Feasibility ConditionFeasibility ConditionA set of values for variables can be found if and A set of values for variables can be found if and only if the constraint graph has no positive only if the constraint graph has no positive cycles.cycles.This is also the condition for the solvability of the This is also the condition for the solvability of the longest path problem, which provides a solution longest path problem, which provides a solution to the set of constraints.to the set of constraints.Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)99Example: Infeasible ConstraintsExample: Infeasible Constraints x1 ≥ x2 + 6 x2 ≥ x1 – 3 x1 x26-3x1x260x1 ≥ x2 + 6x2 ≥ x1 – 3 33Positive cycle mean no longest path can be found.Spring 2015, Feb 15 . . .Spring 2015, Feb 15 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1010Solving a Constraint SetSolving a