Bounded-skew clock and Steiner routing under Elmore delay

ABSTRACT

We study the minimum-cost bounded-skew routing tree problem under the Elmore delay model. We present two approaches to construct bounded-skew routing trees: (i) the Boundary Merging and Embedding (BME) method which utilizes merging points that are restricted to the boundaries of merging regions, and (ii) the Interior Merging and Embedding (IME) algorithm which employs a sampling strategy and dynamic programming to consider merging points that are interior to, rather than on the boundary of, the merging regions. Our new algorithms allow accurate control of Elmore delay skew, and show the utility of merging points inside merging regions.

REFERENCES

• 1: K. D. Boese and A. B. Kahng, "Zero-Skew Clock Routing Trees With Minimum Wirelength", P1vc. IEEE 5th Intl. ASIC Conf., Rochester, September 1992, pp. 1.1.1 - 1.1.5.
• 2: K. D. Boese, A. B. Kahng, B. A. McCoy and G. Robins, "Near-Optimal Critical Sink Routing Tree Constructions," to appear in IEEE Trans. on CAD, 1995.
• 3: M. Borah, R. M. Owens and M. J. Irwin, "An Edge-Based Heuristic for Rectilinear Steiner Trees", IEEE Trans. on CAD, to appear, Dec. 1994, pp. 1563-1568.
• 4: T.-H. Chao , J.-M. Ho , Y.-C. Hsu, Zero skew clock net routing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.518-523, June 08-12, 1992, Anaheim, California, United States
• 5: 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. on Cilvuits and Systems 39(11), Nov. 1992, pp. 799-814.
• 6: J. Cong, A. B. Kahng, C.-K. Koh and C.-W. A. Tsao, "Bounded-Skew Clock and Steiner Routing Under Elmore Delay," UCLA Computer Science Department Technical Report 950030, Aug. 1995.
• 7: 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]
• 8: J. Cong and C.-K. Koh, "Minimum-Cost Bounded-Skew Clock Routing," P1vc. IEEE Intl. Syrup. on Ci~vuits and Systems, Vol 1, Apr. 1995, pp. 215-218.
• 9: J. Cong and K.-S. Leung, "Optimal Wiresizing Under Elmore Delay Model," IEEE Trans. on Computer-AidedDesign, Mar. 1995, pp. 321-336.
• 10: M. Edahiro, "Minimum Path-Length Equi-Distant Routing," P~vc. IEEE Asia- Pacific Conf. on Cilvuits and Systems, Dec. 1992, pp. 41-46.
• 11: 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]
• 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, "A New Class of Iterative Steiner Tree Heuristics with Good Performance", IEEE Transactions on Computer-Aided Design, 11(7), Jul. 1992, pp. 893-902.
• 14: A. B. Kahng and G. Robins, On Optimal Intelvonnectionsfor VLSI, Kluwer Academic Publishers, 1994.
• 15: Chung-Wen Albert Tsao , Andrew B. Kahng, Planar-DME: improved planar zero-skew clock routing with minimum pathlength delay, Proceedings of the conference on European design automation, p.440-445, September 19-23, 1994, Grenoble, France
• 16: Andrew B. Kahng , Chung-Wen Albert Tsao, Low-cost single-layer clock trees with exact zero Elmore delay skew, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.213-218, November 06-10, 1994, San Jose, California, United States
• 17: R.S. Tsay, "An Exact Zero-Skew Clock Routing Algorithm,"IEEE Transactions on Computer-Aided Design, 12(2), Feb. 1993, pp. 242-249.
• 18: Qing Zhu , Wayne Wei-Ming Dai, Perfect-balance planar clock routing with minimal path-length, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.473-476, November 1992, Santa Clara, California, United States

INDEX TERMS

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

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

General Terms:
Algorithms, Measurement, Theory

Keywords:
bounded-skew, zero-skew, clock routing, Elmore delay, pathlength delay, zero-skew, VLSI, routing trees, global routing