Scalable min-register retiming under timing and initializability constraints

ABSTRACT

We demonstrate that a maximum-flow-based approach to register-minimization is a useful platform for incorporating varied design constraints. In this work, we extend the flowbased formulation to include timing constraints and to guarantee the existence of an equivalent initial state. Reducing the register count is motivated by positive consequences for physical design, verification, and power consumption, but it is critically necessary for synthesis that these timing and functionality requirements are also met. Our solution is optimum in the number of registers under either or both constraints and also possesses several other distinct advantages: the runtime is significantly faster than comparable techniques, the algorithm is capable of early termination with a timing-feasible solution, and both maximum and minimum path constraints can be specified.

REFERENCES

• 1: Berkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification, Release 61104. http://www.eecs.berkeley.edu/~alanmi/abc/
• 2: Gianpiero Cabodi , Stefano Quer , Fabio Somenzi, Optimizing sequential verification by retiming transformations, Proceedings of the 37th conference on Design automation, p.601-606, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337591]
• 3: J. Cong and C. Wu, "Optimal FPGA mapping and retiming with efficient initial state computation", IEEE Trans. CAD, vol. 18(11), Nov. 1999, pp. 1595--1607.
• 4: G. Even, I. Y. Spillinger, and L. Stok, "Retiming revisited and reversed", IEEE Trans. CAD, vol. 15(3), March 1996, pp. 348--357.
• 5: A. Goldberg, Network optimization library. (Software tools) http://www.avglab.com/andrew/soft.html
• 6: 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]
• 7: M. Hutton and J. Pistorius, Altera QUIP benchmarks. http://www.altera.com/education/univ/research/unvquip.html
• 8: C. E. Leiserson and J. B. Saxe. "Retiming synchronous circuitry", Algorithmica, 1991, vol. 6, pp. 5--35.
• 9: N. Maheshwari and S. Sapatnekar, "Efficient retiming of large circuits", IEEE Trans VLSI, 6(1), March 1998, pp. 74--83.
• 10: Naresh Maheshwari , Sachin S. Sapatnekar, Minimum area retiming with equivalent initial states, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.216-219, November 09-13, 1997, San Jose, California, United States
• 11: Continuous retiming: algorithms and applications, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.116, October 12-15, 1997
• 12: Peichen Pan , Guohua Chen, Optimal Retiming for Initial State Computation, Proceedings of the 12th International Conference on VLSI Design - 'VLSI for the Information Appliance', p.366, January 10-13, 1999
• 13: S. S. Sapatnekar and R. B. Deokar, "Utilizing the retiming-skew equivalence in a practical algorithms for retiming large circuits", IEEE Trans. CAD, vol. 15(10), Oct.1996, pp. 1237--1248.
• 14: 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
• 15: 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]
• 16: L. Stok , I. Spillinger , G. Even, Improving initialization through reversed retiming, Proceedings of the 1995 European conference on Design and Test, p.150, March 06-09, 1995
• 17: H. J. Touati and R. K. Brayton, "Computing the initial states of retimed circuits", IEEE Trans. CAD, vol. 12(1), Jan 1993, pp. 157--162.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

General Terms:
Algorithms, Design

Keywords:
initial state, min-area, retiming, sequential optimization