
FAST ALGORITHMS FOR RETIMING LARGE VLSI CIRCUITSAbstractRetiming is the process of relocating flipflops within a circuit to achieve improved clock periods by balancing the latchtolatch delays, while maintaining the inputoutput latency of the circuit. Traditional approaches to retiming have been limited to small circuits due to large computational complexities. The work described in this talk presents research towards developing efficient methods for retiming large circuits within reasonable CPU times. Although the talk will focus on edgetriggered circuits, the techniques have a natural extension to levelclocked circuits. The retiming problem may be stated as either minimumperiod retiming, where the clock period is to be minimized without regard to the number of latches in the final circuit, or as minimumarea retiming, where the number of flipflops are to be minimized at a given clock period. We present solutions to each problem, with the solution to the former being used to set up the latter.
The approach is based on the equivalence between retiming and the
problem of clock skew optimization. In clock skew optimization,
skews are deliberately introduced into the clocking network. The
optimal skews are first computed using an efficient graphtheoretic
formulation. Next, this solution is translated into a retimed
circuit. In case of minimum period retiming, a feasible solution is
required, whereas for minimum area retiming, this procedure is used
to derive bounds on the variables in the retiming problem. Our
retiming algorithms can handle circuits with 50,000 gates in minutes.
Copies of SlidesThe slides in postscript format
Relevant PapersMinimum period retiming (edgetriggered)Minimum area retiming (edgetriggered) Minimum period retiming (levelclocked) Minimum area retiming (levelclocked)

Contact 
©20022018 U.C. Regents 