More Web Proxy on the site http://driver.im/

Article

CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model

Authors:

Xianlong HongAuthors Info & Claims

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

Pages 630 - 635

https://doi.org/10.1145/1118299.1118447

Published: 24 January 2006 Publication History

Abstract

Routing tree construction is a fundamental problem in modern VLSI design. In this paper we propose CDC-Tree, an Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) heuristic algorithm to construct an OARSMT. CDC-Tree is based on the current driven circuit (CDC) model mapped from an escape graph. The circuit structure comes from the topology of the escape graph, with each edge replaced by a resistor indicating the wirelength of that edge. By performing DC analysis on the circuit and selecting the edges according to the current distribution to construct an OARSMT, the wirelength of the resulting tree is short. The algorithm has been implemented and tested on cases of different scales and with different shapes of obstacles. Experiments show that CDCTree can achieve shorter wirelength than the existing best algorithm, An-OARSMan, when the terminal number of a net is less than 50.

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 path connections and its applications", IRE Trans. on Electronic Computers, 1961, 10: pp. 345--346.]]

[3]

S. B. Akers, "A Modifi cation of Lee's Path Connection Algorithm", IEEE Trans. on Electronic Computer, 1967, 16 (4): pp. 97--98.]]

[4]

J. Soukup, "Fast Maze Router", In Proc. of the 15th IEEE/ACM Design Automation Conferece, 1978: pp. 100--102.]]

Digital Library

[5]

Hadlock, "A Shortest Path Algorithm for Grid Graphs", Networks, 1977(7): pp. 323--334.]]

[6]

F. Rubin, "The Lee Connection Algorithm", IEEE Trans. on Computer, 1974(23): pp. 907--914.]]

[7]

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

Digital Library

[8]

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

[9]

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

[10]

M. Zachariasen and P. Winter, "Obstacle-avoiding Euclidean Steiner trees in the plane: an exact algorithm", extended abstract presented at the Workshop on Algorithm Engineering and Experimentation (ALENEX), 1999.]]

Digital Library

[11]

Y. Yang, Q. Zhu, T. Jing, X. L. Hong, and Y. Wang, "Rectilinear Steiner Minimal Tree among Obstacles", in Proc. of IEEE ASICON, Beijing, China, 2003: pp. 348--351.]]

[12]

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 and Computational Science, 2004, 1(3): 107--116.]]

[13]

Yu Hu, Tong Jing, Xianlong Hong, Zhe Feng, Xiaodong Hu, and Guiying Yan, "An-OARSMan: Obstacle-Avoiding Routing Tree Construction with Good Length Performance", in Proc. of IEEE/ACM Asia and South Pacific Design Automation Conference, 2005, Shanghai, China, pp. 7--12.]]

Digital Library

[14]

Y. F. Wu, P. Widmayer, M. D. F. Schlag, and C. K. Wong, "Rectilinear Shortest Paths and Minimum Spanning Trees in the Presence of Rectilinear Obstacles", IEEE Trans. on Computers, 1987, 36(3): pp. 321--331.]]

Digital Library

[15]

Yiyu Shi, Bike Xie and Yanjie Mao, "Circuit Model in Mathematical Modeling", Journal of Mathematical Engineering, 2004, 21(7): pp. 43--48.]]

[16]

Ho C, Ruehli, Brennan P. "The Modified Nodal Approach to Network Analysis", IEEE Trans. Circuits and Systems, 1975, 39(22): pp. 504--509.]]

[17]

D. S. Kershaw, "The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations", Journal of Computational Physics, 26 I (Jan.) (1978), 43--65.]]

[18]

J. Wang, D. Xie and Y. Yao, "The Modified Solutoin for Large Sparse Symmetric Linear Systems in Electromagnetic Field Analysis", Transactions of China Electrotechnical Society, 2001 16(2): pp. 26--29.]]

Cited By

Kundu SRoy SMukherjee S(2021)An Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Method Using PB-SATIETE Journal of Research10.1080/03772063.2021.196779069:6(3346-3356)Online publication date: 1-Sep-2021
https://doi.org/10.1080/03772063.2021.1967790
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
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

Index Terms

CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model

Recommendations

MP-Trees: A Packing-Based Macro Placement Algorithm for Modern Mixed-Size Designs

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the MP-tree is very efficient, effective, and ...
MP-trees: a packing-based macro placement algorithm for mixed-size designs
DAC '07: Proceedings of the 44th annual Design Automation Conference

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various ...
A robust detailed placement for mixed-size IC designs
ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

The rapid increase in IC design complexity and wide-spread use of intellectual-property (IP) blocks have made the so-called mixed-size placement a very important topic in recent years. Although several algorithms have been proposed for mixed-sized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

January 2006

998 pages

ISBN:0780394518

General Chair:
Fumiyasu Hirose
Cadence Design Systems, Japan

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
171
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kundu SRoy SMukherjee S(2021)An Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction Method Using PB-SATIETE Journal of Research10.1080/03772063.2021.196779069:6(3346-3356)Online publication date: 1-Sep-2021
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
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
Chow WLi LYoung ESham C(2014)Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approachIntegration, the VLSI Journal10.1016/j.vlsi.2013.08.00147:1(105-114)Online publication date: 1-Jan-2014
Chuang JLin J(2011)Efficient multi-layer obstacle-avoiding preferred direction rectilinear Steiner tree constructionProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950922(527-532)Online publication date: 25-Jan-2011
Chuang JLin J(2011)Efficient multi-layer obstacle-avoiding preferred direction rectilinear Steiner tree construction16th Asia and South Pacific Design Automation Conference (ASP-DAC 2011)10.1109/ASPDAC.2011.5722246(527-532)Online publication date: Jan-2011
Li LQian ZYoung ERoychowdhury J(2009)Generation of optimal obstacle-avoiding rectilinear Steiner minimum treeProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687405(21-25)Online publication date: 2-Nov-2009
Liu CYuan SKuo SWang S(2009)High-performance obstacle-avoiding rectilinear steiner tree constructionACM Transactions on Design Automation of Electronic Systems10.1145/1529255.152926714:3(1-29)Online publication date: 4-Jun-2009
Chen HChang Y(2009)Global and detailed routingElectronic Design Automation10.1016/B978-0-12-374364-0.50019-9(687-749)Online publication date: 2009
(2009)Electronic Design AutomationundefinedOnline publication date: 11-Mar-2009
Show More Cited By

View Options

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