Retiming is a powerful technique for delay and area optimization that opera
tes by relocating the flip-flops in a circuit. This movement of flip-flops
in control logic changes the state encoding of finite state machines, requi
ring the preservation of initial (reset) states. Unfortunately, traditional
retiming algorithms pay no regard to maintaining the initial state. While
some work has been carried out on finding a retiming of a circuit with equi
valent initial states, it has concentrated on achieving a specified clock p
eriod without regard to the number of flip-flops. However, if the number of
flip-flops is not explicitly minimized the retimed circuit may have a very
large number of flip-flops. This work targets the problem of minimizing th
e number of flip-flops in control logic subject to a specified clock period
and with a guarantee of an equivalent initial state. The problem is formul
ated as a mixed-integer linear program and bounds on the retiming variables
are used to guarantee an equivalent initial state. These bounds also lead
to a simple method for calculating an equivalent initial state for the reti
med circuit. The mixed-integer linear program formulation is capable of mod
eling the maximum sharing of different types of flip-flops at the fanout of
a gate. Experimental results on circuits of up to 9000 gates and are shown
to be close to a (perhaps unachievable) lower bound. (C) 1999 Elsevier Sci
ence B.V. All rights reserved.