Can I read An Efficient Incremental Algorithm for Min-area Retiming on EtoBox?

An Efficient Incremental Algorithm for Min-area Retiming by Jia Wang; Hai Zhou is a scholarly article available to read on EtoBox.

What is An Efficient Incremental Algorithm for Min-area Retiming about?

As one of the most effective sequential optimization techniques, 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 minimum 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 circuits. Recently, provable incremental algorithms have been discovered for min-period retiming, and heuristic incremental algorithms have been proposed for min-area retiming. However, given the complexity of the problem, min-area retiming is still resisting an efficient provable incremental algorithm. In this paper, we fill the gap by presenting an efficient algorithm to solve the min-area retiming problem incrementally and optimally. Contrary to existing approaches, no dense path graph is constructed; only the active timing constraints are dynamically generated in the algorithm. Experimental results show that the total runtime of our algorithm for all the ben

Author

Jia Wang; Hai Zhou

Publisher

ACM

Published

2008

Language

EN