An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane

ABSTRACT

Routing is one of the important phases in VLSI/ULSI physical design. The obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing since macro cells, IP blocks, and pre-routed nets are often regarded as obstacles in the routing phase. Efficient OARSMT algorithms can be employed in practical routers iteratively. Recently, IC routing and related researches have been extended from Manhattan architecture (λ2-geometry) to Y- / X-architecture (λ3- / λ4-geometry) to improve the chip performance. This paper presents an O(nlogn) heuristic, λ-OASMT, for obstacle-avoiding Steiner minimal tree construction in the λ-geometry plane. Based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by a novel method called zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with two most recent works on OARSMT problem, λ-OASMT obtains up to 30Kx speedup with an even better quality solution. We have tested randomly generated cases with up to 1K terminals and 10K rectilinear obstacles within 3 seconds on a Sun V880 workstation (755MHz CPU and 4GB memory). The high efficiency and accuracy of λ-OASMT make it extremely practical and useful in the routing phase, as well as interconnect estimation in the process of floorplanning and placement.

REFERENCES

• 1: M. R. Garey and D. S. Johnson, "The rectilinear Steiner tree problem is NP-complete", SIAM Journal on Applied Mathematics, 1977, 32: pp.826--834.
• 2: C.Y. Lee, "An Algorithm for Connections and Its Application", IRE Trans. on Electronic Computer, 1961, pp.346--365.
• 3: F. Rubin, "The Lee Connection Algorithm", IEEE Trans. on Computer, 1974, 23: pp.907--914.
• 4: K. Mikami and K. Tabuchi, "A Computer Program for Optimal Routing of Printed Circuit Connectors", IFIPS Proc., 1968, H47, pp.1475--1478.
• 5: David W. Hightower, A solution to line-routing problems on the continuous plane, Proceedings of the 6th annual conference on Design Automation, p.1-24, January 1969 [doi>10.1145/800260.809014]
• 6: J. L. Ganley and J. P. Cohoon, "Routing a multi-terminal critical net: Steiner tree construction in the presence of obstacles", In: Proc. of IEEE ISCAS, London, UK, 1994, pp.113--116.
• 7: Z. Zhou, C. D. Jiang, and L. S. Huang, "Finding Obstacle-Avoiding Shortest Path Using Generalized Connection Graph with O(t) Edges", Chinese J. of Software, 2003, 14(2): pp.166--174.
• 8: Z. Zhou, C. D. Jiang, and L. S. Huang, "On optimal rectilinear shortest paths and 3-steiner tree routing in presence of obstacles", Journal of Software, 2003, 14(9): pp.1503--1514.
• 9: Y. Yang, Q. Zhu, T. Jing, and X.L. Hong, "Rectilinear Steiner Minimal Tree among Obstacles", In: Proc. of IEEE ASICON, Beijing, China, 2003, pp.348--351.
• 10: Yu Hu, Zhe Feng, Tong Jing, Xianlong Hong, Yang Yang, Ge Yu, Xiaodong Hu, Guiying Yan, "FORst: A 3-Step Heuristic for Obstacle-Avoiding Rectilinear Steiner Minimal Tree Construction", Journal of Information & Computational Science, 2004, 1(3): pp.107--116.
• 11: Yu Hu , Tong Jing , Xianlong Hong , Zhe Feng , Xiaodong Hu , Guiying Yan, An-OARSMan: obstacle-avoiding routing tree construction with good length performance, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120732]
• 12: X Initiative Home Page. http://www.xinitiative.com, 2001.
• 13: Hongyu Chen , Chung-Kuan Cheng , Andrew B. Kahng , Ion Mandoiu , Qinke Wang, Estimation of wirelength reduction for λ-geometry vs. manhattan placement and routing, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639944]
• 14: S.Q. Zheng, J.S. Lim, and S.S. Iyengar, "Finding obstacle-avoiding shortest paths using implicit connection graphs", IEEE Trans. on Computer Aided Design, 1996, 15(1): pp.103--110.
• 15: M. Sarrafzadeh and C. K.Wong, "Hierarchical Steiner tree construction in uniform orientations," IEEE Trans. on Computer-Aided Design, 11(9): pp.1095--1103, 1992.
• 16: S. Fortune, "A sweepline algorithm for Voronoi diagrams. Algorithmica", 2(2): pp.153--174, 1987.
• 17: R.C. Prim, "Shortest connection networks and some generalizations", Bell System Tech. J. 36(1957): pp.1389--1401.
• 18: Martin Zachariasen, "Rectilinear Full Steiner Tree Generation", Technical Report DIKU-TR-97/29, Department of Computer Science University of Copenhagen, 1997.
• 19: Jan-ming Ho , G. Vijayan , C. K. Wong, A new approach to the rectilinear Steiner tree problem, Proceedings of the 26th ACM/IEEE conference on Design automation, p.161-166, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74410]
• 20: H. Schenck, "Computational Algebraic Geometry", Cambridge University Press, November 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

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

Keywords:
λ-geometry, O(nlogn), Steiner tree construction, obstacle-avoiding