FAST ALGORITHMS FOR RETIMING LARGE VLSI CIRCUITS


Abstract

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 Slides

The slides in postscript format


Relevant Papers

Minimum period retiming (edge-triggered)

Minimum area retiming (edge-triggered)

Minimum period retiming (level-clocked)

Minimum area retiming (level-clocked)


Contact 
©2002-2018 U.C. Regents