FastRoute: a step to integrate global routing into placement

ABSTRACT

Because of the increasing dominance of interconnect issues in advanced IC technology, placement has become a critical step in the IC design flow. To get accurate interconnect information during the placement process, it is desirable to incorporate global routing into it. However, previous global routers are computationally expensive. It is impractical to perform global routing repeatedly during placement.

In this paper, we present an extremely fast and high-quality global router called FastRoute. In traditional global routing approaches, congestion is not considered during Steiner tree construction. So they have to rely on the time-consuming maze routing technique to eliminate routing congestion. Different from traditional approaches, we proposed a congestion-driven Steiner tree topology generation technique and an edge shifting technique to determine the good Steiner tree topologies and Steiner node positions. Based on the congestion-driven Steiner trees, we only need to apply maze routing to a small percentage of the two-pin nets once to obtain high quality global routing solutions. We also proposed a new cost function based on logistic function to direct the maze routing.

Experimental results show that FastRoute generates less congested solutions in 132x and 64x faster runtimes than the state-of-the-art academic global routers Labyrinth [1] and Chi Dispersion router [2], respectively. It is even faster than the highly-efficient congestion estimator FaDGloR [3]. The promising results make it possible to incorporate global routing directly into placement process without much runtime penalty. This could dramatically improve the placement solution quality. We believe this work will fundamentally change the way the EDA community look at and make use of global routing in the whole design flow.

REFERENCES

• 1: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Predictable routing, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 2: Raia T. Hadsell , Patrick H. Madden, Improved global routing through congestion estimation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775842]
• 3: Jurjen Westra , Patrick Groeneveld, Is probabilistic congestion estimation worthwhile?, Proceedings of the 2005 international workshop on System level interconnect prediction, April 02-03, 2005, San Francisco, California, USA [doi>10.1145/1053355.1053377]
• 4: Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, Timing driven placement using physical net constraints, Proceedings of the 38th conference on Design automation, p.780-783, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379065]
• 5: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 6: U. Brenner, A. Rohe. An effective congestion-driven placement framework. In IEEE Trans. on Computer-Aided Design, vol. 22(4), pp. 387--394, 2003.
• 7: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 8: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 9: C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. In IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, 20:622--631, 2001.
• 10: B. M. Riess, and G. G. Ettelt. SPEED: fast and efficient timing driven placement. Proc. Intl. Symp. on Circuits and Systems, pp. 377--380, 1995.
• 11: William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]
• 12: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Timing-driven placement using design hierarchy guided constraint generation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.177-180, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774598]
• 13: Guenter Stenz , Bernhard M. Riess , Bernhard Rohfleisch , Frank M. Johannes, Timing driven placement in interaction with netlist transformations, Proceedings of the 1997 international symposium on Physical design, p.36-41, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267676]
• 14: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 15: Jurjen Westra , Chris Bartels , Patrick Groeneveld, Probabilistic congestion prediction, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981110]
• 16: Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639942]
• 17: R. W. Hamming. Error-detecting and error-correcting codes. Bell System Technical Journal, 29(2):147--160, 1950.
• 18: Chris Chu , Yiu-Chung Wong, Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055145]
• 19: M. Hanan. On Steiner's problem with rectilinear distance. SIAM Journal of Applied Mathematics, 14:25--265, 1966.
• 20: D. von Seggern. CRC Standard Curves and Surfaces. Boca Raton, FL: CRC Press, 1993.
• 21: http://www.spec.org/

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids
  B.m MISCELLANEOUS
      Subjects: Design management

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

General Terms:
Algorithms, Design, Performance