ELEC 7770 Advanced VLSI Design Spring 2012 RetimingRetimingA Trivial Example: Reduced HardwareExample 2: Faster ClockExample 3: Reduced Flip-FlopsApplications of RetimingFundamental Operation of RetimingA Correlator CircuitGraph ModelPath Delay and Path WeightExample of Node RetimingLegal RetimingExampleExample: Illegal RetimingExample: Legal RetimingCorrelator CircuitRetimed Correlator CircuitRetiming TheoremProof of Condition 1Proof of Condition 2Retiming Optimization ProblemAlgorithm 1: Critical Path DelayAlgorithm 1 ApplicationAlgorithm 2: Retiming for Period = PAlgorithm 2 Application, P = 13Retimed Circuit for P = 13ReferencesSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)11ELEC 7770ELEC 7770Advanced VLSI DesignAdvanced VLSI DesignSpring 2012Spring 2012RetimingRetimingVishwani 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_Spr12/course.htmlhttp://www.eng.auburn.edu/~vagrawal/COURSE/E7770_Spr12/course.htmlSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)22RetimingRetimingRetiming is a function-preserving transformation Retiming is a function-preserving transformation of a synchronous sequential circuit.of a synchronous sequential circuit.Flip-flops are moved according to specific rules.Flip-flops are moved according to specific rules.Original references:Original references:C. E. Leiserson, F. Rose and J. B. Saxe, “Optimizing C. E. Leiserson, F. Rose and J. B. Saxe, “Optimizing Synchronous Circuits by Retiming,” Synchronous Circuits by Retiming,” Proc. 3Proc. 3rdrd Caltech Caltech Conf. on VLSIConf. on VLSI, 1983, pp. 87-116., 1983, pp. 87-116.C. E. Leiserson and J. B. Saxe, “Retiming C. E. Leiserson and J. B. Saxe, “Retiming Synchronous Circuitry,” Synchronous Circuitry,” AlgorithmicaAlgorithmica, vol. 6, pp. 5-35, , vol. 6, pp. 5-35, 1991.1991.Spring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)33A Trivial Example: Reduced HardwareA Trivial Example: Reduced HardwareFFFFFFSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)44Example 2: Faster ClockExample 2: Faster ClockFFFFSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)55Example 3: Reduced Flip-FlopsExample 3: Reduced Flip-FlopsFFFFFFSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)66Applications of RetimingApplications of RetimingPerformance optimizationPerformance optimizationArea optimizationArea optimizationPower optimizationPower optimizationTestability enhancementTestability enhancementFPGA optimizationFPGA optimizationSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)77Fundamental Operation of RetimingFundamental Operation of RetimingA retiming move in a circuit is caused by moving A retiming move in a circuit is caused by moving all of the memory elements at the input of a all of the memory elements at the input of a combinational block to all of its outputs, or vice-combinational block to all of its outputs, or vice-versa.versa.Combinational logicFFFFCombinational logicFF≡Spring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)88A Correlator CircuitA Correlator Circuit+ + += = = =hostAdderdelay = 7Comparatordelay = 3Flip-flopPIPOa1a2 a3a4Spring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)99Graph ModelGraph Model7 7 73 3 3 30000000011 11Vertex, vi, combinational, delay = d(vi), assumed unchanged by retiming d(host) = 0Edge, e(vi,vj) or eij, weight wij = number of flip-flops between vi and vjhab c defgSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1010Path Delay and Path WeightPath Delay and Path WeightA set of connected nodes specify a path. A set of connected nodes specify a path. A path A path does not traverse through the host node.does not traverse through the host node.Path delay = Path delay = ∑ d(vi) = combinational delay of path∑ d(vi) = combinational delay of pathPath weight = ∑ wij = clock delay of pathPath weight = ∑ wij = clock delay of pathRetiming of a node i is denoted by an integer riRetiming of a node i is denoted by an integer riIt represents the number of registers moved across, It represents the number of registers moved across, initially ri = 0initially ri = 0Register moved from output to input, ri → ri + 1Register moved from output to input, ri → ri + 1Register moved from input to output, ri → ri – 1Register moved from input to output, ri → ri – 1After retiming, edge weight wij’ = wij + rj – riAfter retiming, edge weight wij’ = wij + rj – riSpring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1111Example of Node RetimingExample of Node Retiming333333∑ ∑ d(vi) = 12, ∑ wij = 0 d(vi) = 12, ∑ wij = 0 333333∑ ∑ d(vi) = 12, ∑ wij = 2 d(vi) = 12, ∑ wij = 2 r1 = 0 r2 = 0 r3 = 0 r4 = 0 r5 = 0 r6 =0r1 = 0 r2 = -1 r3 = 0 r4 = 0 r5 = 1 r6 =0Spring 2012, Feb 10 . . .Spring 2012, Feb 10 . . .ELEC 7770: Advanced VLSI Design (Agrawal)ELEC 7770: Advanced VLSI Design (Agrawal)1212Legal RetimingLegal RetimingRetiming is legal if the retimed circuit has no Retiming is legal if the retimed circuit has no negative weights.negative weights.A legally retimed circuit is functionally equivalent A legally retimed circuit is functionally equivalent to the original circuit – proof by Leiserson and to the original circuit – proof by Leiserson and Saxe (1991)Saxe (1991)Retiming is the most general method for Retiming is the most general method for