Delay driven AIG restructuring using slack budget management

ABSTRACT

Timing optimizations during logic synthesis has become a necessary step to achieve timing closure in VLSI designs. This often involves "shortening" all paths found in the circuit at a cost of increasing the circuit area. In contrast, we present a synthesis approach which leverages slack budgeting to effectively minimize the critical path length without increasing the area of the design. Our results confirm that this is an effective method to control area while optimizing for delay. When compared to an area driven logic synthesis flow, we achieve a 32% reduction in logic depth and an 11% reduction in circuit delay when placed by VPR [1]; and when compared against a depth controlled logic synthesis flow without slack budgeting, we achieve an 8% reduction in logic depth and a 3% reduction in circuit delay when placed by VPR [1]. In both cases, the area penalty is negligible.

REFERENCES

• 1: Vaughn Betz , Jonathan Rose, VPR: A new packing, placement and routing tool for FPGA research, Proceedings of the 7th International Workshop on Field-Programmable Logic and Applications, p.213-222, September 01-03, 1997
• 2: J. Cortadella, "Timing-driven logic bi-decomposition," IEEE Journal on Technology in Computer Aided Design, vol. 22, no. 6, pp. 675--685, June 2003.
• 3: S. Ghiasi , E. Bozorgzadeh , S. Choudhuri , M. Sarrafzadeh, A unified theory of timing budget management, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.653-659, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382657]
• 4: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, DAG-aware AIG rewriting a fresh look at combinational logic synthesis, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1147048]
• 5: Andrew C. Ling , Jianwen Zhu , Stephen D. Brown, BddCut: Towards Scalable Symbolic Cut Enumeration, Proceedings of the 2007 conference on Asia South Pacific design automation, p.408-413, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.358020]
• 6: Boris V. Cherkassky , Andrew V. Goldberg , Tomasz Radzik, Shortest paths algorithms: theory and experimental evaluation, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.516-525, January 23-25, 1994, Arlington, Virginia, United States
• 7: Alan Mishchenko , Satrajit Chatterjee , Robert Brayton, Improvements to technology mapping for LUT-based FPGAs, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117208]
• 8: A. Mishchenko and R. Brayton, "Scalable logic synthesis using a simple circuit structure," in IWLS, 2006, pp. 15--22.
• 9: Andrew V. Goldberg, An efficient implementation of a scaling minimum-cost flow algorithm, Journal of Algorithms, v.22 n.1, p.1-29, Jan. 1997 [doi>10.1006/jagm.1995.0805]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Experimentation, Performance

Keywords:
aig, budget management, logic synthesis, network flow