Article

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

Authors:

Guiying YanAuthors Info & Claims

ISPD '06: Proceedings of the 2006 international symposium on Physical design

Pages 48 - 55

https://doi.org/10.1145/1123008.1123020

Published: 09 April 2006 Publication History

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.

Digital Library

[4]

K. Mikami and K. Tabuchi, "A Computer Program for Optimal Routing of Printed Circuit Connectors", IFIPS Proc., 1968, H47, pp.1475--1478.

[5]

D.W. Hightower, "A Solution to the Line Routing Problem on the Continous Plane", Proc. of the 6th Design Automation Workshop, 1969, pp.1--24.

Digital Library

[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", In: Proc. of IEEE/ACM ASP-DAC, 2005, Shanghai, China, pp.7--12.

Digital Library

[12]

X Initiative Home Page. http://www.xinitiative.com, 2001.

[13]

Hongyu Chen, Chung-Kuan Cheng, Andrew B. Kahng, Ion Mandoiu, and Qinke Wang, "Estimation of Wirelength Reduction for λ-Geometry vs. Manhattan Placement and Routing", SLIP'03, April 5-6, 2003, Monterey, CA, USA.

Digital Library

[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.

Digital Library

[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.

Digital Library

[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]

Janming Ho, G. Vijayan, and C. K. Wong, "A new approach to the rectilinear Steiner tree problem", Proc. of the 26th ACM/IEEE conference on Design Automation, Las Vegas, Nevada, USA, 1989, pp.161--166.

Digital Library

[20]

H. Schenck, "Computational Algebraic Geometry", Cambridge University Press, November 2003.

Cited By

Zhang TLü ZDing J(2024)Guiding Solution Based Local Search for Obstacle-Avoiding Rectilinear Steiner Minimal Tree ProblemIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.33062418:1(440-453)Online publication date: Feb-2024
https://doi.org/10.1109/TETCI.2023.3306241
Guo JKong HFeng L(2024)A Rule-Based High Efficient Obstacle-Avoiding RSMT Algorithm for VLSI Routing2024 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS58744.2024.10558430(1-5)Online publication date: 19-May-2024
https://doi.org/10.1109/ISCAS58744.2024.10558430
You JZhu YHuang XYang LLiu G(2023)Obstacle-Avoidance X-Architecture Steiner Minimal Tree Algorithm Based on Deep Reinforcement Learning2023 International Conference on Artificial Intelligence of Things and Systems (AIoTSys)10.1109/AIoTSys58602.2023.00046(165-172)Online publication date: 19-Oct-2023
https://doi.org/10.1109/AIoTSys58602.2023.00046
Show More Cited By

Index Terms

An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the λ-geometry plane
1. Hardware
  1. Electronic design automation
    1. Physical design (EDA)

Recommendations

Efficient obstacle-avoiding rectilinear steiner tree construction
ISPD '07: Proceedings of the 2007 international symposium on Physical design

Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins, possibly through some additional points (called Steiner points), and avoids running through any obstacle to ...
Obstacle-avoiding rectilinear Steiner tree construction
ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design

In today's VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a ...
High-performance obstacle-avoiding rectilinear steiner tree construction

Rectilinear Steiner trees are used to route signal nets by global and detail routers in VLSI design for a long time. However, in current IC industry, there are significantly increasing obstacles to be considered, such as large-scale power networks, pre-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISPD '06: Proceedings of the 2006 international symposium on Physical design

April 2006

232 pages

ISBN:1595932992

DOI:10.1145/1123008

General Chair:
Lou Scheffer
Cadence

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 April 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ISPD06

Sponsor:

ISPD06: International Symposium on Physical Design 2006

April 9 - 12, 2006

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 62 of 172 submissions, 36%

Upcoming Conference

ISPD '25

Sponsor:
sigda

International Symposium on Physical Design

March 16 - 19, 2025

Austin , TX , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
640
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)4

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang TLü ZDing J(2024)Guiding Solution Based Local Search for Obstacle-Avoiding Rectilinear Steiner Minimal Tree ProblemIEEE Transactions on Emerging Topics in Computational Intelligence10.1109/TETCI.2023.33062418:1(440-453)Online publication date: Feb-2024
https://doi.org/10.1109/TETCI.2023.3306241
Guo JKong HFeng L(2024)A Rule-Based High Efficient Obstacle-Avoiding RSMT Algorithm for VLSI Routing2024 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS58744.2024.10558430(1-5)Online publication date: 19-May-2024
https://doi.org/10.1109/ISCAS58744.2024.10558430
You JZhu YHuang XYang LLiu G(2023)Obstacle-Avoidance X-Architecture Steiner Minimal Tree Algorithm Based on Deep Reinforcement Learning2023 International Conference on Artificial Intelligence of Things and Systems (AIoTSys)10.1109/AIoTSys58602.2023.00046(165-172)Online publication date: 19-Oct-2023
https://doi.org/10.1109/AIoTSys58602.2023.00046
Lee MJan GLuo C(2020)An Efficient Rectilinear and Octilinear Steiner Minimal Tree Algorithm for Multidimensional EnvironmentsIEEE Access10.1109/ACCESS.2020.29778258(48141-48150)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.2977825
Hsie MWu MHuang C(2019)Optimal urban sewer layout design using Steiner tree problemsEngineering Optimization10.1080/0305215X.2018.156043651:11(1980-1996)Online publication date: 22-Jan-2019
https://doi.org/10.1080/0305215X.2018.1560436
Lin KLin YLi YLin R(2018)A Maze Routing-Based Methodology With Bounded Exploration and Path-Assessed Retracing for Constrained Multilayer Obstacle-Avoiding Rectilinear Steiner Tree ConstructionACM Transactions on Design Automation of Electronic Systems10.1145/317787823:4(1-26)Online publication date: 9-May-2018
https://dl.acm.org/doi/10.1145/3177878
Lin KLin YLi YLin RBehjat LHan JVelev MChen D(2017)A Maze Routing-Based Algorithm for ML-OARST with Pre-Selecting and Re-Building Steiner PointsProceedings of the Great Lakes Symposium on VLSI 201710.1145/3060403.3060448(399-402)Online publication date: 10-May-2017
https://dl.acm.org/doi/10.1145/3060403.3060448
Dong GYang ZSong LYe KLi G(2015)The Global Shortest Path Visualization Approach with ObstructionsJournal of Robotics and Mechatronics10.20965/jrm.2015.p057927:5(579-585)Online publication date: 20-Oct-2015
https://doi.org/10.20965/jrm.2015.p0579
Held SSpirkl SSze CDavoodi A(2014)A fast algorithm for rectilinear steiner trees with length restrictions on obstaclesProceedings of the 2014 on International symposium on physical design10.1145/2560519.2560529(37-44)Online publication date: 30-Mar-2014
https://dl.acm.org/doi/10.1145/2560519.2560529
Dong GYang ZSong LYe K(2014)Global shortest path visualization approach with obstructionsProceedings of the 2014 International Conference on Advanced Mechatronic Systems10.1109/ICAMechS.2014.6911577(393-397)Online publication date: Aug-2014
https://doi.org/10.1109/ICAMechS.2014.6911577
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents