An efficient approach to simultaneous transistor and interconnect sizing

ABSTRACT

In this paper, we study the simultaneous transistor and interconnect sizing (STIS) problem. We define a class of optimization problems as CH-posynomial programs and reveal a general dominance property for all CH-posynomial programs. We show that the STIS problems under a number of transistor delay models are CH-posynomial programs and propose an efficient and near-optimal STIS algorithm based on the dominance property. When used to solve the simultaneous driver/buffer and wire sizing problem for real designs, it reduces the maximum delay by up to 16.1%, and more significantly, reduces the power consumption by a factor of 1.63X, when compared with the original designs. When used to solve the transistor sizing problem, it achieves a smooth area-delay trade-off. Moreover, the algorithm optimizes a clock net of 367 drivers/buffers and 59304 /spl mu/m-long wire in 120 seconds, and a 32-bit adder with 1026 transistors in 66 seconds on a SPARC-5 workstation.

REFERENCES

• 1: Michel R. C. M. Berkelaar , Jochen A. G. Jess, Gate sizing in MOS digital circuits with linear programming, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
• 2: Guangqiu Chen , Hidetoshi Onodera , Keikichi Tamaru, An iterative gate sizing approach with accurate delay evaluation, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.422-427, November 05-09, 1995, San Jose, California, United States
• 3: 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]
• 4: C. Chien, P. Yang, E. Cohen, R. Jain, and H. Samueli, "A 12.7Mchip/s All-Digital BPSK Direct Sequence Spread- Spectrum IF Transceiver in 1.2#m CMOS," Proc. IEEE Int'l Solid-State Circuits Conf., 1994, pp. 30-31.
• 5: W. Chuang, S. S. Sapatnekar and I. N. Hajj, "Timing and Area Optimization for Standard-Cell VLSI Circuit Design", IEEE Tran. on CAD, March 1995, pp. 308-320.
• 6: 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]
• 7: J. Cong and L. He, "Simultaneous Transistor and Interconnect Sizing Based on the General Dominance Property", UCLA Computer Science, Technical Report 95-000~6, Dec. 1995 (at http://ballade.cs.ucla.edu/- cong /publications.html).
• 8: 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]
• 9: 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
• 10: 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]
• 11: J. Cong and K. S. Leung, "Optimal Wiresizing Under the Distributed Elmore Delay Model", IEEE Trans. on CAD, 14(3), March 1995, pp. 321-336.
• 12: J. Cong and P. H. Madden, "Performance Driven Routing with Multiple Sources," Proc. ISCAS, 1995, pp. 1157-1169.
• 13: J. G. Ecker, "Geometric Programming: Methods, Computations and Appicaltions", SIAM Review, Vol. 22, No. 3, July 1980, pp. 338-362.
• 14: J. P. Fishburn and A. E. Dunlop, "TILOS: A Psoynomial Programming Approach to Transistor Sizing", Proc. ICCAD, 1985, pp. 326-328.
• 15: N. Hedenstierna, and K. O. Jeppson, "CMOS Circuit Speed and Buffer Optimization", IEEE Tran. on CAD, 1987, pp. 270- 281.
• 16: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Optimal wire sizing and buffer insertion for low power and a generalized delay model, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.138-143, November 05-09, 1995, San Jose, California, United States
• 17: 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]
• 18: S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang, "An Exact Solution to the Transistor Sizing Problem for CMOS Circuits Using Convex Optimization", IEEE Tran. on CAD, November 1993, pp. 1621-1634.
• 19: 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
• 20: Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
• 21: J. K. Ousterhout, "A Switch-Level Timing Verifier for Digital MOS VLSI, " IEEE Trans. on CAD, 4(3)(1983)pp. 336-349.
• 22: D. J. Pilling and J. G. Skalnik, "A Circuit Model for Predicting Transient Delays in LSI Logic Systems", Proc. 6th Asilomar Conf. on Circuits and Systems, 1972, pp. 424-428.
• 23: 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
• 24: J. Rubinstein, P. Penfield, and M. A. Horowitz, "Signal Delay in RC Tree Networks", IEEE Trans. on CAD, 2(3) (1983) pp. 202-211.
• 25: Tianxiong Xue , Ernest S. Kuh, Post routing performance optimization via multi-link insertion and non-uniform wiresizing, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.575-580, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
CH-posynomial programs, STIS, circuit CAD, driver/buffer, transistor and interconnect sizing, transistor sizing, wire sizing problem