Buffered Steiner trees for difficult instances

ABSTRACT

Buffer insertion has become an increasingly critical optimization in high performance design. The problem of finding a delay-optimal buffered Steiner tree has been an active area of research, and excellent solutions exist for most instances. However, current approaches fail to adequately solve a particular class of real-world “difficult” instances which are characterized by a large number of sinks, variations in sink criticalities, and varying polarity requirements. We propose a new Steiner tree construction called C-Tree for these instance types. When combined with van Ginneken style buffer insertion, C-Tree achieves higher quality solutions with fewer resources compared to traditional approaches.

REFERENCES

• 1: Charles Alpert , Anirudh Devgan, Wire segmenting for improved buffer insertion, Proceedings of the 34th annual conference on Design automation, p.588-593, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266291]
• 2: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion with accurate gate and interconnect delay computation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.479-484, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309983]
• 3: C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, D. Karger, "Prim-Dijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design," IEEE TCAD, 14(7), 1995, 890-896.
• 4: K.D. Boese, A. B. Kahng, B. A. McCoy, G. Robins, "Nearoptimal Critical Sink Routing Tree Constructions", IEEE Trans. on CAD, 14(12), Dec. 1995, pp. 1417-1436.
• 5: Chris C. N. Chu , D. F. Wong, Closed form solution to simultaneous buffer insertion/sizing and wire sizing, Proceedings of the 1997 international symposium on Physical design, p.192-197, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267712]
• 6: Jason Cong , Kwok-Shing Leung , Dian Zhou, Performance-driven interconnect design based on distributed RC delay model, Proceedings of the 30th international conference on Design automation, p.606-611, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165065]
• 7: T. F. Gonzalez, "Clustering to Minimize the Maximum Intercluster Distance", Theoretical Comp. Sci., 38, 293-306, 1985.
• 8: Minghorng Lai , D. F. Wong, Maze routing with buffer insertion and wiresizing, Proceedings of the 37th conference on Design automation, p.374-378, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337500]
• 9: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin , Ching-Yen Ho, New performance driven routing techniques with explicit area/delay tradeoff and simultaneous wire sizing, Proceedings of the 33rd annual conference on Design automation, p.395-400, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240594]
• 10: J. Lillis, C.-K. Cheng and T.-T. Y. Lin, "Optimal Wire Sizing and Buffer Insertion for Low Power and a Generalized Delay Model", IEEE J. Solid-State Circuits, 31(3), 1996, 437-447.
• 11: John Lillis , Chung-Kuan Cheng , Ting-Ting Y. Lin, Simultaneous Routing and Buffer Insertion for High Performance Interconnect, Proceedings of the 6th Great Lakes Symposium on VLSI, p.148, March 22-23, 1996
• 12: Takumi Okamoto , Jason Cong, Buffered Steiner tree construction with wire sizing for interconnect layout optimization, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.44-49, November 10-14, 1996, San Jose, California, United States
• 13: L. P. P. P. van Ginneken, "Buffer Placement in Distributed RC-tree Networks for Minimal Elmore Delay", Intl. Symposium on Circuits and Systems, 1990, pp. 865-868.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Buffering

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Design, Performance