Optimal wire sizing and buffer insertion for low power and a generalized delay model

ABSTRACT

We present efficient, optimal algorithms for timing optimization by discrete wire sizing and buffer insertion. Our algorithms are able to minimize dynamic power dissipation subject to given timing constraints. In addition, we compute the complete power-delay tradeoff curve for added flexibility. We extend our algorithm to take into account the effect of signal slew on buffer delay which can contribute substantially to overall delay. The effectiveness of these methods is demonstrated experimentally.

REFERENCES

• 1: J.J. Cong, K.S. Leung, "Optimal Wiresizing Under Elmore Delay Model," IEEE Trans. on CAD, v. 14 no. 3 (1995) pp. 321-336.
• 2: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.408-425, Dec. 1994 [doi>10.1109/92.335010]
• 3: Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
• 4: W.C. Elmore, "The Transient Response of Damped Linear Network with particular Regard to Wideband Amplifiers," J. Applied Physics 19 (1948), pp 55-63.
• 5: N. Hedenstierna and K.O. Jeppson, "CMOS Circuit Speed and Buffer Optimization," IEEE Transactions on Computer-Aided Design, Mar. 1987, pp 270-281.
• 6: Lalgudi N. Kannan , Peter R. Suaris , Hong-Gee Fang, A methodology and algorithms for post-placement delay optimization, Proceedings of the 31st annual conference on Design automation, p.327-332, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196399]
• 7: J. Lillis, C.K. Cheng, T.T. Lin, "Optimal and Efficient Buffer Insertion and Wire Sizing," Proc of Custom Integrated Circuits Conference 1995.
• 8: Sachin S. Sapatnekar, RC interconnect optimization under the Elmore delay model, Proceedings of the 31st annual conference on Design automation, p.387-391, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196430]
• 9: Synopsys 3.1 Release Manual: Appendix B, "Static Timing Analysis."
• 10: Herve Jacques Touati, Performance-oriented technology mapping, University of California at Berkeley, Berkeley, CA, 1991
• 11: L.P.P.P van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay," Proc. International Symposium on Circuits and Systems, 1990, pp 865-868.
• 12: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Algorithms, Theory

Keywords:
Timing Optization, Elmore Delay, Dynamic Power Dissipation, Dynamic Programming, Signal Slew