Minimum area retiming with equivalent initial states
Naresh Maheshwari, Sachin S. Sapatnekar · 1997
Traditional minimum area retiming algorithms attempt to achieve their prescribed objective with no regard to maintaining the initial state of the system. This issue is important for circuits such as con-trollers, and our work addresses this problem. The procedure de-scribed generates bounds on the retiming variables that guarantee an equivalent initial state after retiming. A number of possible sets of bounds can be derived, and each set is used to solve a minimum area retiming problem that is set up as a 0/1 mixed integer linear program, using a new technique that models the maximal sharing of flip-flops at latch outputs. The best solution is found through enu-meration of these sets, terminated on achievement of a calculated lower bound. Experimental results show that after a small number of enumerations, optimal or near-optimal results are achievable. 1