An Efficient Incremental Algorithm for Min-Area Retiming

As one of the most effective sequential optimization tech-niques, retiming is a structural transformation that relocates flip-flops in a circuit without changing its functionality. The min-area retiming problem seeks a solution with the mini-mum flip-flop area (or number) under a given clock period. Even though having polynomial runtime, the best existing algorithms for this problem still need to first construct a dense path graph and then find a min-cost network flow on it, thus incur huge storage and time expenses for large cir-cuits. Recently, provable incremental algorithms have been discovered for min-period retiming, and heuristic incremen-tal algorithms have been proposed for min-area retiming. However, given the complexity of the problem, min-area re-timing is still resisting an efficient provable incremental algo-rithm. In this paper, we fill the gap by presenting an efficient algorithm to solve the min-area retiming problem incremen-tally and optimally. Contrary to existing approaches, no dense path graph is constructed; only the active timing con-straints are dynamically generated in the algorithm. Exper-imental results show that the total runtime of our algorithm for all the benchmarks is at least 60 × faster than the best existing approach