Optimal wire-sizing function with fringing capacitance consideration

ABSTRACT

In this paper, we consider non-uniform wire-sizing under theElmore delay model.Given a wire segment of length L, letf(x) be the width of the wire at position x, 0 ¿ x ¿ L.It was shown in [Optimal Wire-sizing formula under the Elmore delay model, Shaping a distributed-RC line to minimize Elmore delay] that the optimal wire-sizing functionwhich minimizes delay is an exponential tapering functionf(x) = ae{-bx}, where a > 0 and b > 0 are constants.Unfortunately, [Optimal Wire-sizing formula under the Elmore delay model, Shaping a distributed-RC line to minimize Elmore delay] did not consider fringing capacitancewhich is at least comparable in size to area capacitance indeep submicron designs.As a result, exponential taperingis no longer the optimal strategy.In this paper, we showthat the optimal wire-sizing function, taking fringing capacitanceinto consideration, is f(x) = \frac{{ - c_f }}{{2c_0 }}(\frac{1}{{W(\frac{{ - c_f }}{{ae^{ - bx} }})}} + 1) whereW(x) = \sum\nolimits_{n = 1}^\infty{\frac{{( - n)^{n - 1} }}{{n!}}} x^n is the Lambert's W function, c{f}and c{0} are the respective fringing capacitance and area capacitanceof wire per unit square, a > 0 and b> 0 are constants.The optimal wire-sizing function degenerates into an exponentialtapering function as c}{f} = 0, and degenerates into asquare-root tapering function (f(x)=\sqrt {b - ax}, where a > 0and b > 0) as c{f} ¿ ¿.Our experimental results show thatthe optimal wire-sizing function can significantly reduce theinterconnection delay of exponentially tapered wires.In thecase where lower and upper bounds on the wire widths aregiven, the optimal wire-sizing function is a truncated versionof the above function.Finally, our optimal wire-sizing functioncan be iteratively applied to optimally size all the wiresegments in a routing tree for objectives such as minimizingweighted sink delay, minimizing maximum sink delay, orminimizing area subject to delay bounds at the sinks.

REFERENCES

• 1: 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
• 2: 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]
• 3: C.-P. Chen, D. F. Wong. "A fast algorithm for optimal wire-sizing under Elmore delay model" Proc. IEEE ISCAS, 1996.
• 4: Chung Chen , D. F. Wong, Optimal Wire-Sizing Function with Fringing Capacitance Consideration, University of Texas at Austin, Austin, TX, 1996
• 5: J. P. Fishburn and C. A. Schevon, "Shaping a distributed-RC line to minimize Elmore delay", IEEE Transactions on Circuits and Systems-I: Fundamental Theory and Applications, Vol. 42, No. 12, pp. 1020-1022, December 1995.
• 6: 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
• 7: B. W. Char et al., The Maple V Language Reference Manual, Springer-Verlag, 1991.
• 8: R. M. Corless et al., "On Lambert's W Function", Technical report CS-93-03, Dept. of Computer Science, U. of Waterloo, Canada. (Also available via ftp://daisy.uwaterloo.ca/maple/5.3/ share/LambertW.ps)
• 9: L. Euler, "De Serie Lambertina Plurismique Eius Insignibus Proprietatibus," Leonhardi Euleri Opera Omnia, Set. 1. Opera Mathematica, Bd 6, 1921 (orid. date 1779)
• 10: J. H. Lambert, "Observationses variae in Mathesin Puram," Acta Helvetica, physicomathematico-anatomico-botanico-medica, 3, Basel, (1758), 128-168.
• 11: T. Sakurai and K. Tamaru, "Simple Formulas for Two- and Three-Dimensional Capacitances," IEEE Trans. Electron. Device ED-30,183-185, Feb. 1983.
• 12: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide band amplifiers", J. Applied Physics, 19 (1), 1948.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

Additional Classification:
  C. Computer Systems Organization

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

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