FAST ALGORITHMS FOR RETIMING LARGE VLSI CIRCUITS
Retiming is the process of relocating flip-flops within a circuit to achieve improved clock periods by balancing the latch-to-latch delays, while maintaining the input-output 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 edge-triggered circuits, the techniques have a natural extension to level-clocked circuits.
The retiming problem may be stated as either minimum-period retiming, where the clock period is to be minimized without regard to the number of latches in the final circuit, or as minimum-area retiming, where the number of flip-flops 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 graph-theoretic
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 (edge-triggered)
|©2002-2018 U.C. Regents|