An efficient technique for device and interconnect optimization in deep submicron designs

ABSTRACT

In this paper, we formulate a new class of optimization problem, named the general CH-posynomial program, and reveal the general dominance property. We propose an efficient algorithm based on the extended local refinement operation to compute lower and upper bounds of the exact solution to the general CH-posynomial program. We apply the algorithm to solve the simultaneous transistor and interconnect sizing (STIS) problem under the table-based device model, and the global interconnect sizing and spacing (GISS) problem with consideration of the crosstalk capacitance. Experiment results show that our algorithm can handle many device and interconnect modeling issues in deep submicron designs and is very efficient.

REFERENCES

• 1: Jason Cong , Lei He, An efficient approach to simultaneous transistor and interconnect sizing, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.181-186, November 10-14, 1996, San Jose, California, United States
• 2: 3. Cong, L. He, C. Koh, and Z. Pan, =Global interconnect sizing and spacing wit}l consideration of coupling capadtance~ Tech. Rep. 970031, UCLA CS Dept, 1997.
• 3: Jason Cong , Lei He , Cheng-Kok Koh , Zhigang Pan, Global interconnect sizing and spacing with consideration of coupling capacitance, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.628-633, November 09-13, 1997, San Jose, California, United States
• 4: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 5: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.206-212, November 06-10, 1994, San Jose, California, United States
• 6: 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
• 7: 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
• 8: 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]
• 9: Chris C. N. Chu , D. F. Wong, A new approach to simultaneous buffer insertion and wire sizing, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.614-621, November 09-13, 1997, San Jose, California, United States
• 10: Semiconductor Industry Association, National Technology Roadmap for Semiconductors, 1994.
• 11: K. Nabors and J. White, "Fastcap: A multipole accelerated 3-d capadtance extraction program," in IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1447-1459, Nov. 1991.
• 12: Lieven Vandenberghe , Stephen Boyd , Abbas El Gamal, Optimal wire and transistor sizing for circuits with non-tree topology, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.252-259, November 09-13, 1997, San Jose, California, United States
• 13: J. Cong and L. He, "Theory and algorithm of local refinement based optimization with application to transistor and interconnect sizing,~ Tech. Rep. 970034, UCLA CS Dept, Sept. 1997.
• 14: Jason Cong , Lei He, Optimal wiresizing for interconnects with multiple sources, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.568-574, November 05-09, 1995, San Jose, California, United States
• 15: 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," in Proc. IEEE Int. Solid-State Circuits Conf., pp. 30-31, 1994.
• 16: Jason Cong , Lei He , Andrew B. Kahng , David Noice , Nagesh Shirali , Steve H.-C. Yen, Analysis and justification of a simple, practical 2 1/2-D capacitance extraction methodology, Proceedings of the 34th annual conference on Design automation, p.627-632, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266303]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing
  B.8 Performance and Reliability

General Terms:
Algorithms, Design, Experimentation, Performance, Theory