111RetimingRetimingR. K. R. K. BraytonBrayton, K. , K. KeutzerKeutzer, & S. Seshia , & S. Seshia UC BerkeleyUC BerkeleyN. Shenoy, SynopsysN. Shenoy, SynopsysThanks to A. Thanks to A. KuehlmannKuehlmann, UCB, UCB2RTL Design FlowRTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibraryphysicaldesignlayoutabsq01dclkabsq01dclkModuleGeneratorsManualDesign223Logic OptimizationLogic Optimization••Perform a variety of Perform a variety of transformations and transformations and optimizationsoptimizations––Combinational Combinational transformationstransformations••Technology independentTechnology independent••Technology dependentTechnology dependent––Sequential transformationsSequential transformations••FSM state assignmentFSM state assignment••RetimingRetiminglogicoptimizationnetlistnetlistpre-optimizedsmaller, fasterless powerLibraryabsq01dclkabsq01dclk4Logic Optimization ProblemLogic Optimization ProblemFlip-flopsCombinationalLogicinputsoutputs335What about the Registers?What about the Registers?••Pure combinational optimization can be suboptimal since Pure combinational optimization can be suboptimal since relations across register boundaries are disregardedrelations across register boundaries are disregarded••Optimize a sequential circuit by optimally placing registers. Optimize a sequential circuit by optimally placing registers. Move register(s) so thatMove register(s) so that––clock cycle decreases, or number of registers decreases andclock cycle decreases, or number of registers decreases and––inputinput--output behavior is preservedoutput behavior is preserved••Also, can combine retiming with combinational optimization Also, can combine retiming with combinational optimization techniquestechniques––Move latches out of the way temporarilyMove latches out of the way temporarily––optimize larger blocks of combinationaloptimize larger blocks of combinational6Lecture OutlineLecture Outline••Why is retiming important?Why is retiming important?••Basic Model and AlgorithmsBasic Model and Algorithms••Combining with Combinational Combining with Combinational OptimizationOptimization447Retiming Retiming --tradeoffstradeoffsab6454111222clock period =# registers =43248Retiming Retiming --IntroductionIntroduction••Move registers Move registers ••GoalsGoals––clock period (minclock period (min--period retiming)period retiming)––number of registers (minnumber of registers (min--area retiming)area retiming)––number of registers for a target clock period number of registers for a target clock period (constrained min(constrained min--area retiming)area retiming)ab64645454111222clock period =# registers =43432424559Importance of RetimingImportance of Retiming••Practical sequential optimizationPractical sequential optimization••Global optimality for clock period and register Global optimality for clock period and register positioningpositioning••Must for HDL synthesisMust for HDL synthesis––lowers dependency on user descriptionlowers dependency on user description••Low power strategyLow power strategy––decrease #registers with no loss in performancedecrease #registers with no loss in performance10Practical Importance of Practical Importance of RetimingRetiming051015202530354045area area-retdelaydelay-ret6611••Circuit graphCircuit graph––gategate––wirewire––environmentenvironmentRetiming Retiming --Problem DefinitionProblem Definition1122vertex21edge1h11host vertex and host edgesab1122zV = set of gatesE = set of edgesd(v) – delay of gate (vertex), d(v) ≥≥≥≥≥≥≥≥0w(e) – # of registers on edge e, w(e) ≥≥≥≥≥≥≥≥0012Circuit RepresentationCircuit RepresentationExample: Example: CorrelatorCorrelatorCircuitCircuitδδδδδδδδ(x, y) = 1 if x=y(x, y) = 1 if x=y0 otherwise0 otherwiseOperation delayOperation delayδδδδδδδδ33+ 7+ 7••Every cycle in Graph has at least one register i.e. Every cycle in Graph has at least one register i.e. no combinational loops.no combinational loops.0033330000000022GraphGraph77aabb++δδδδδδδδδδδδδδδδHostHost7713PreliminariesPreliminaries••For a path p: VFor a path p: V00→→→→→→→→••Clock cycleClock cycle∑∑−====100)()()()(kiikiiewpwvdpd endpoints) (includes )}({max0)(:pdcpwp ==For For correlatorcorrelatorc = 13c = 13Path with Path with w(p)=0w(p)=000333300000000227714••Movement of registers from input to output of a Movement of registers from input to output of a gate or vice versagate or vice versa••Does not affect gate functionalitiesDoes not affect gate functionalities••A mathematical formulation: A mathematical formulation: RetardationRetardation––r: V r: V →→→→→→→→Z, an integer vertex labelingZ, an integer vertex labeling––wwrr(e(e) =w(e) + r(v) ) =w(e) + r(v) --r(u) for edge e= (u,v)r(u) for edge e= (u,v)Basic OperationBasic OperationRetime by 1Retime by 1Retime by Retime by --118815••Thus in the example, r(u) = Thus in the example, r(u) = --1, r(v) = 1, r(v) = --1 results in1 results in••For a path p: sFor a path p: s→→→→→→→→t, t, WWrr(p(p) = w(p) + r(t) ) = w(p) + r(t) --r(s)r(s)••RetimingRetiming––r: Vr: V→→→→→→→→Z, an integer vertex labelingZ, an integer vertex labeling––wwrr(e(e) = w(e) + r(v) ) = w(e) + r(v) --r(u) for edge e= (u,v)r(u) for edge e= (u,v)––A retiming r is legal if A retiming r is legal if wwrr(e(e) ) ≥≥≥≥≥≥≥≥0, 0, ∀∀∀∀∀∀∀∀ee∈∈∈∈∈∈∈∈EEBasic OperationBasic Operationvvuu003333000000002277vvuu00333300111100117716Retiming Retiming --AssumptionsAssumptions••Each loop in circuit contains at least one registerEach loop in circuit contains at least one register••Circuit uses single clock and edgeCircuit uses single clock and edge--triggered triggered elements (identical skew)elements (identical skew)••Gate delay is constant (and nonGate delay is constant (and non--negative)negative)••Registers are ideal (setRegisters are ideal (set--up, drive independent of up, drive independent of load)load)••Any powerAny power--up state of the design can be safely up state of the design can be safely handled by the environment (initial state handled by the environment (initial state assumption)assumption)9917Retiming Retiming