An efficient incremental algorithm for min-area retiming

ABSTRACT

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 benchmarks is at least 60 x faster than the best existing approach.

REFERENCES

• 1: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 2: G. Even, I. Y. Spillinger, L. Stok. Retiming revisited and reversed. IEEE TCAD, 15(3):348--357, Mar. 1996.
• 3: D. S. Hochbaum. A new---old algorithm for minimum-cut and maximum-flow in closure graphs. Networks, 37(4):171--193, Jul. 2001.
• 4: Aaron P. Hurst , Alan Mishchenko , Robert K. Brayton, Fast Minimum-Register Retiming via Binary Maximum-Flow, Proceedings of the Formal Methods in Computer Aided Design, p.181-187, November 11-14, 2007 [doi>10.1109/FMCAD.2007.21]
• 5: C. E. Leiserson and J. B. Saxe. Retiming synchronous circuitry. Algorithmica, 6(1):5--35, 1991.
• 6: H. Lerchs and I. F. Grossmann. Optimum design of open-pit mines. Trans C.I.M., 68:17--24, 1965.
• 7: Chuan Lin , Hai Zhou, An efficient retiming algorithm under setup and hold constraints, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147149]
• 8: N. Maheshwari and S. S. Sapatnekar. Efficient retiming of large circuits. IEEE TVLSI, 6(1):74--83, Mar. 1998.
• 9: S. S. Sapatnekar and R. B. Deokar. Utilizing the retiming-skew equivalence in a practical algorithm for retiming large circuits. IEEE TCAD, 15(10):1237--1248, Oct. 1996.
• 10: Narendra Shenoy , Richard Rudell, Efficient implementation of retiming, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.226-233, November 06-10, 1994, San Jose, California, United States
• 11: Deshanand P. Singh , Valavan Manohararajah , Stephen D. Brown, Incremental retiming for FPGA physical synthesis, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065694]
• 12: H. J. Touati, R. K. Brayton. Computing the initial states of retimed circuits. IEEE TCAD, 12(1):157--162, Jan. 1993.
• 13: Hai Zhou, Deriving a new efficient algorithm for min-period retiming, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120774]
• 14: Berkeley Logic Synthesis and Verification Group. ABC---a system for sequential synthesis and verification. http://www.eecs.berkeley.edu/~alanmi/abc/.
• 15: CAD Group at Politecnico di Torino. ITC '99 benchmarks (2nd release). http://www.cad.polito.it/tools/itc99.html.
• 16: CS2 version 4.3. Andrew Goldberg's network optimization library. http://www.avglab.com/andrew/soft.html.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms

Keywords:
retiming