Closed form solutions to simultaneous buffer insertion/sizing and wire sizing

ABSTRACT

In this paper, we consider the delay minimization problem of an interconnect wire by simultaneously considering buffer insertion, buffer sizing and wire sizing. We consider three cases, namely using no buffer (i.e., wire sizing alone), using a given number of buffers, and using the optimal number of buffers. We provide elegant closed form optimal solutions for all three problems. These closed form solutions are useful in early stages of the VLSI design flow such as logic synthesis and floorplanning.

REFERENCES

• 1: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 2: CHEN, C.-P., AND WONG, D. F. 1996. A fast algorithm for optimal wire-sizing under Elmore delay model. In Proceedings of the IEEE ISCAS, vol. 4, pp. 412-415.
• 3: Chung-Ping Chen , D. F. Wong, Optimal wire-sizing function with fringing capacitance consideration, Proceedings of the 34th annual conference on Design automation, p.604-607, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266295]
• 4: Chung-Ping Chen , Yao-Wen Chang , D. F. Wong, Fast performance-driven optimization for buffered clock trees based on Lagrangian relaxation, Proceedings of the 33rd annual conference on Design automation, p.405-408, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240596]
• 5: Chung-Ping Chen , Yao-Ping Chen , D. F. Wong, Optimal wire-sizing formula under the Elmore delay model, Proceedings of the 33rd annual conference on Design automation, p.487-490, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240611]
• 6: Chung-Ping Chen , Hai Zhou , D. F. Wong, Optimal non-uniform wire-sizing under the Elmore delay model, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.38-43, November 10-14, 1996, San Jose, California, United States
• 7: Chris C. N. Chu , D. F. Wong, Closed form solution to simultaneous buffer insertion/sizing and wire sizing, Proceedings of the 1997 international symposium on Physical design, p.192-197, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267712]
• 8: CHU,C.C.N.,AND WONG, D. F. 1999a. A quadratic programming approach to simultaneous buffer insertion/sizing and wire sizing. IEEE Trans. Computer-Aided Des. 18, 6 (June.), pp. 787-798.
• 9: CHU,C.C.N.,AND WONG, D. F. 1999b. A polynomial time optimal algorithm for simultaneous buffer and wire sizing. IEEE Trans. Computer-Aided Des. 18, 9 (Sept.), pp. 1297-1304.
• 10: Jason Cong , Lei He, Optimal wiresizing for interconnects with multiple sources, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.4, p.478-511, Oct. 1996 [doi>10.1145/238997.239018]
• 11: Jason Cong , Kwok-Shing Leung, Optimal wiresizing under the distributed Elmore delay model, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.634-639, November 07-11, 1993, Santa Clara, California, United States
• 12: CONG,J.,AND PAN, Z. 1998. Interconnect performance estimation models for synthesis and design planning. In Proceedings of the ACM/IEEE International Workshop on Logic Synthesis.
• 13: J. Cong , C. Koh , K. Leung, Simultaneous buffer and wire sizing for performance and power optimization, Proceedings of the 1996 international symposium on Low power electronics and design, p.271-276, August 12-14, 1996, Monterey, California, United States
• 14: DHAR,S.,AND FRANKLIN, M. A. 1991. Optimum buffer circuits for driving long uniform lines. IEEE J. Solid-State Circ. 26, 1 (Jan.), pp. 32-40.
• 15: DUFFIN, R. J., PETERSON, E. L., AND ZENER, C. 1967. Geometric Programming - Theory and Application. J Wiley, New York.
• 16: ELMORE, W. C. 1948. The transient response of damped linear network with particular regard to wideband amplifiers. J. Appl. Phys. 19, pp. 55-63.
• 17: J. P. Fishburn, Shaping a VLSI Wire to Minimize Elmore Delay, Proceedings of the 1997 European conference on Design and Test, p.244, March 17-20, 1997
• 18: FISHBURN,J.P.,AND SCHEVON, C. A. 1995. Shaping a distributed-RC line to minimize Elmore delay. IEEE Trans. Circuits and Systems-I: Fundamental Theory and Applications, 42, 12 (Dec.), pp. 1020-1022.
• 19: Youxin Gao , D. F. Wong, Optimal shape function for a bi-directional wire under Elmore delay model, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.622-627, November 09-13, 1997, San Jose, California, United States
• 20: HEDENSTIERNA,N.,AND JEPPSON, K. O. 1987. CMOS circuit speed and buffer optimization. IEEE Trans. Comput-Aided Des. CAD-6, 2 (Mar.), pp. 270-281.
• 21: JAEGER, R. C. 1975. Comments on 'An optimized output stage for MOS integrated circuits'. IEEE J. Solid-State Circ. SC-10, 3 (June.), pp. 185-186.
• 22: Rony Kay , Gennady Bucheuv , Lawrence T. Pileggi, EWA: exact wiring-sizing algorithm, Proceedings of the 1997 international symposium on Physical design, p.178-185, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267710]
• 23: LILLIS, J., CHENG, C.-K., AND LIN, T.-T. 1995. Optimal and efficient buffer insertion and wire sizing. In Proceedings of the Custom Integrated Circuits Conference, pp. 259-262.
• 24: LILLIS, J., CHENG, C.-K., AND LIN, T.-T. 1996. Optimal wire sizing and buffer insertion for low power and a generalized delay model. IEEE J. Solid-State Circ. 31, 3 (Mar.), pp. 437-447.
• 25: LIN,H.C.,AND LINHOLM, L. W. 1975. An optimized output stage for MOS integrated circuits. IEEE J. Solid-State Circ. SC-10, 2 (Apr.), pp. 106-109.
• 26: Noel Menezes , Ross Baldick , Lawrence T. Pileggi, A sequential quadratic programming approach to concurrent gate and wire sizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.144-151, November 05-09, 1995, San Jose, California, United States
• 27: Noel Menezes , Satyamurthy Pullela , Florentin Dartu , Lawrence T. Pillage, RC interconnect synthesis—a moment fitting approach, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.418-425, November 06-10, 1994, San Jose, California, United States
• 28: SANCHETI,P.K.,AND SAPATNEKAR, S. S. 1994. Interconnect design using convex optimization. In Proceedings of the IEEE Custom Integrated Circuits Conference, pp. 549-552.
• 29: Semiconductor Industry Association. 1997. The National Technology Roadmap for Semiconductors.
• 30: VAN GINNEKEN, L. P. P. P. 1990. Buffer placement in distributed RC-tree networks for minimal Elmore delay. In Proceedings of the International Symposium on Circuits and Systems, pp. 865- 868.
• 31: Tianxiong Xue , Ernest S. Kuh , Qinjian Yu, A Sensitivity-Based Wiresizing Approach to Interconnect Optimization of Lossy Transmission Line Topologies, Proceedings of the 1996 IEEE Multi-Chip Module Conference (MCMC '96), p.117, February 06-07, 1996
• 32: D. Zhou , X. Y. Liu, Minimization of chip size and power consumption of high-speed VLSI buffers, Proceedings of the 1997 international symposium on Physical design, p.186-191, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267711]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

General Terms:
Design, Performance, Theory

Keywords:
buffer insertion, buffer sizing, closed form solution, interconnect optimization, wire sizing