A Fast Retiming Algorithm Integrated with Rewiring for Flip-Flop Reductions

Traditional retiming processes are mostly MILP based with the physical interconnect information less correctly reflected, thus could be very CPU intensive and incorrect on the final clock period estimations. Moreover, the number of flip-flops tends to be undesirably increased after the retiming process, which can cause a significant area/power penalty on the retimed circuit. To overcome these major drawbacks of the conventional retiming technique, we first propose a fast retiming algorithm which avoids solving MILP, and with both gate and interconnect delay formulated together. For a more accurate delay estimation, all interconnect delays are formulated and calculated based on real placements. Additionally, we integrate it with a specific rewiring algorithm to cut down the number of flip-flops (FFs) without sacrificing retimed clock periods. Experimental results show that our pure retiming algorithm can achieve an average of 5.75% optimization on the clock period in a very fast speed. With a rewiring algorithm targeting for FF reduction applied, a FF reduction of up to 31.2% (11.3% on average) can be obtained without the compromise on the retimed clock period compared to the pure retimed results.