Retiming control logic

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.