Fast and flexible buffer trees that navigate the physical layout environment

ABSTRACT

Buffer insertion is an increasingly critical optimization for achieving timing closure, and the number of buffers required increases significantly with technology migration. It is imperative for an automated buffer insertion algorithm to be able to efficiently optimize tens of thousands of nets. One must also be able to effectively navigate the existing layout, including handling large blockages, blockages with holes specifically for buffers, specially allocated buffer blocks, placement porosity, and routing congestion. The algorithm must also be flexible enough to know when to use and when not to use expensive layout resources. Although several previous works have addressed buffer insertion in the presence of blockages, this is the first to present a complete solution that can manage the physical layout environment.

REFERENCES

• 1: Charles J. Alpert , Gopal Gandham , Miloš Hrkić , Jiang Hu , Stephen T. Quay, Porosity aware buffered steiner tree construction, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640035]
• 2: C. J. Alpert, G. Gandham, M. Hrkic, et al., "Buffered Steiner Trees for Difficult Instances", IEEE Transactions on CAD, 21(1), pp. 3--14, Jan. 2002.
• 3: Charles J. Alpert , Jiang Hu , Sachin S. Sapatnekar , Paul Villarrubia, A practical methodology for early buffer and wire resource allocation, Proceedings of the 38th conference on Design automation, p.189-194, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378461]
• 4: C. J. Alpert, J. Hu, S. Sapatnekar, and C.-N. Sze, "A Fast Oracle for Interconnect Delay Prediction", ACM Tau Workshop, 2004, pp. 39--45.
• 5: J. Cong, "Challenges and Opportunities for Design Innovations in Nanometer Tech.", SRC Working Papers, 1997.
• 6: Jason Cong , Xin Yuan, Routing tree construction under fixed buffer locations, Proceedings of the 37th conference on Design automation, p.379-384, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337502]
• 7: Miloš Hrkić , John Lillis, S-Tree: a technique for buffered routing tree synthesis, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514066]
• 8: Ashok Jagannathan , Sung-Woo Hur , John Lillis, A fast algorithm for context-aware buffer insertion, Proceedings of the 37th conference on Design automation, p.368-373, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337496]
• 9: 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]
• 10: 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]
• 11: 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.
• 12: Prashant Saxena , Noel Menezes , Pasquale Cocchini , Desmond A. Kirkpatrick, The scaling challenge: can correct-by-construction design help?, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640014]
• 13: Xiaoping Tang , Ruiqi Tian , Hua Xiang , D. F. Wong, A new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 14: 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.
• 15: Hai Zhou , D. F. Wong , I-Min Liu , Adnan Aziz, Simultaneous routing and buffer insertion with restrictions on buffer locations, Proceedings of the 36th ACM/IEEE conference on Design automation, p.96-99, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309885]

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
buffer insertion, global routing, physical synthesis