More practical bounded-skew clock routing

ABSTRACT

Academic clock routing research results has often hadlimited impact on industry practice, since such practical considerationsas hierarchical buffering, rise-time and overshoot constraints,obstacle- and legal location-checking, varying layer parasitics andcongestion, and even the underlying design flow are often ignored.This paper explores directions in which traditional formulationscan be extended so that the resulting algorithms are more usefulin production design environments. Specifically, the following issuesare addressed: (i) clock routing for varying layer parasiticswith nonzero via parasitics; (ii) obstacle-avoidance clock routing;(iii) a new topology design rule for prescribed-delay clock routing;and (iv) predictive modeling of the clock routing itself. Wedevelop new theoretical analyses and heuristics, and present experimentalresults that validate our new approaches.

REFERENCES

• 1: M. Borah, R. M. Owens, and M. J. Irwin, "An edge-based heuristic for rectilinear steiner trees", IEEE Trans. Computer-Aided Design, 13(12):1563-1568, December 1994.
• 2: T.-H. Chao, Y. C. Hsu, J. M. Ho, K. D. Boese, and A. B. Kahng, "Zero skew clock routing with minimum wirelength", IEEE Trans. Cilvuits and Systems, 39(11):799-814, November 1992.
• 3: Jason Cong , Andrew B. Kahng , Cheng-Kok Koh , C.-W. Albert Tsao, Bounded-skew clock and Steiner routing under Elmore delay, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.66-71, November 05-09, 1995, San Jose, California, United States
• 4: J. Cong and C.-K. Koh, "Minimum-cost bounded-skew clock routing", P1vc. IEEE Intl. Syrup. Ci~vuits and Systems, volume 1, pp. 215-218, April 1995.
• 5: M. Edahiro, "Minimum skew and minimum path length routing in vlsi layout design. NEC Resealvh and Development, 32(4):569-575, 1991.
• 6: Masato Edahiro, A clustering-based optimization algorithm in zero-skew routings, Proceedings of the 30th international conference on Design automation, p.612-616, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165066]
• 7: M. Edahiro, "Delay Minimization for Zero-Skew Routing" P~vc. IEEE Intl. Conf. Computer-Aided Design, pp, 563-566, November, 1993.
• 8: John P. Fishburn, Clock Skew Optimization, IEEE Transactions on Computers, v.39 n.7, p.945-951, July 1990 [doi>10.1109/12.55696]
• 9: E.G. Friedman, editor. Clock Distribution networks in VLSI Circuits and Systems: A Selected Reprint Volume. IEEE Press, 1995.
• 10: Subir Kumar Ghosh , David M. Mount, An output-sensitive algorithm for computing visibility, SIAM Journal on Computing, v.20 n.5, p.888-910, Oct. 1991 [doi>10.1137/0220055]
• 11: J. Hershberger, S. Suri, "Efficient computation of Euclidean shortest paths in the plane", P~v. 34th IEEE Syrup. on Foundations of Computer Science., pp. 508-17, 1993.
• 12: Dennis J. H. Huang , Andrew B. Kahng , Chung-Wen Albert Tsao, On the bounded-skew clock and Steiner routing problems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.508-513, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217579]
• 13: A. B. Kahng and G. Robins. On Optimal Intelvonnections for VLSI, Kluwer Academic Publishers, 1995.
• 14: A. B. Kahng and C.-W. Albert Tsao, "Planar-DME: A single-layer zero-skew clock tree router. IEEE Trans. Computer-AidedDesign, 15(1), January 1996.
• 15: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 16: Chung-Wen Tsao , Andrew B. Kahng, Vlsi clock net routing, 1996
• 17: Joe G. Xi , Wayne W.-M. Dai, Useful-skew clock routing with gate sizing for low power design, Proceedings of the 33rd annual conference on Design automation, p.383-388, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240592]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

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

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

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