Retiming is a powerful technique for optimizing sequential circuits. The tr
ansparent nature of level sensitive latches enables level-clocked circuits
to operate faster and require fewer memory elements than edge-triggered cir
cuits. However, this transparency makes the operation of level-clocked circ
uits very complex, and optimization of level-clocked circuits is a difficul
t task. This work presents efficient algorithms for retiming large level-cl
ocked circuits. To provide us with a simpler view of the operation of level
-clocked circuits, we present the relationship between retiming and clock s
kew optimization. We then utilize this relationship to develop efficient re
timing algorithms for period and area optimization.
For period optimization, We present an algorithm which produces near-optima
l results, but is significantly faster than the traditional algorithms. In
this approach, we first calculate the best possible clock period and the am
ount of motion required for each latch, The latches are then relocated in a
n attempt to achieve this period. Area, as measured by the number of latche
s in the circuit can be optimized by solving a linear program. We apply eff
icient pruning techniques to reduce the size of this linear program, while
preserving optimality. Since generating the linear program is a major part
of the computational requirements of minarea retiming, we present technique
s for efficient generation of the reduced linear program. This enables us t
o perform area optimization of large circuits clocked by symmetric multipha
se clocks in very reasonable time, without sacrificing optimality, We prese
nt results on circuits with up to 56000 gates, performing period optimizati
on in under 20 s and area optimization in under 1.5 h.