RC(L) interconnect sizing with second order considerations via posynomial programming

ABSTRACT

There has been substantial work on interconnect sizing algorithms for delay and area optimization in terms of the Elmore delay. Recently, however, signal integrity issues have become of equal or greater importance than delay and area for deep submicron designs. Modeling signal integrity requires more than the Elmore delay approximation, especially when interconnect inductance effects are considered. This paper studies a new interconnect sizing formulaðtion with signal attenuation and transition time constraints that capðtures the same global optimality as the Elmore delay based approaches. With the signal attenuation (or the signal transition time) modeled by the second order central moment of the circuit response, we formulate a provably posynomial optimization probðlem for RC trees such that the well studied algorithms for geometric programming can be applied with guaranteed convergence to a gloðbal minima. For RCL cases we demonstrate that this formulation remains convex and posynomial under reasonable conditions. Suffiðcient conditions are given in terms of the technology parameters and termination conditions.

REFERENCES

• 1: M. Celik and L. T. Pileggi, "Metrics and bounds of phase delay and signal attenuation in RC(L) clock trees", IEEE Trans. Computer-Aided Design, vol. 18, no. 3, Mar. 1999
• 2: Chung-Ping Chen , Chris C. N. Chu , D. F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.617-624, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289097]
• 3: 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
• 4: 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
• 5: 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]
• 6: Florentin Dartu , Lawrence T. Pileggi, Calculating worst-case gate delays due to dominant capacitance coupling, Proceedings of the 34th annual conference on Design automation, p.46-51, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266033]
• 7: J. G. Ecker, "Geometric programming: Methods, Computations, and Applications", SIAM review, vol. 22, no. 3, pp. 338-362, July 1980
• 8: W. C. Elmore, "The transient response of damped linear networks with particular regard to wideband amplifiers," Journal of Applied Physics, vol. 19, no. 1, 1998
• 9: J. P. Fishburn and A. E. Dunlop, "TILOS: A posynomial programming approach to transistor sizing", Proc. Init. Conf. on Computer-Aided Design, Nov. 1985
• 10: R. Gupta, B. Tutuianu, L. T. Pileggi, "The Elmore Delay as a Bound for RC trees with Generalized Input Signals," IEEE trans. Computer-Aided Design, vol. 16, no. 1, 1997
• 11: R. Kay and L. T. Pileggi, "EWA: Efficient Wiring-Sizing Algorithm for Signal Nets and Clock Nets", IEEE trans. Computer-AIded Design, vol. 17 No. 1, Jan. 1998
• 12: N. Menezes, R. Baldick, and L. T. Pileggi, "A sequential quadratic programming approach to concurrent gate and interconnect sizing," IEEE trans. Computer-Aided Design, Aug. 1997
• 13: 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]
• 14: S. S. Sapatnekar, "Wire sizing as a convex optimization problem: exploring the area-delay tradeoff", IEEE trans. Computer-Aided Design, August 1996
• 15: Q. Zhu and W. M. Dai, "High-speed clock network sizing optimization based on distributed RC and Lossy RLC interconnect models", IEEE trans. Computer Aided Design, vol. 15, no. 9, Sept. 1996
• 16: Qingjian Yu , Ernest S. Kuh, Exact moment matching model of transmission lines and application to interconnect delay estimation, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.2, p.311-322, June 1995 [doi>10.1109/92.386230]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Quadratic programming methods

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

General Terms:
Algorithms, Design, Theory

Keywords:
RC trees, VLSI design automation, central moments, convex programming, interconnect optimization, posynomiality