An-OARSMan: An Obstacle-Avoiding Rectilinear Steiner Tree Algorithm with Good Length Performance

Yu Hu; Tong Jing; Xianlong Hong; feng zhe; hu xiaodong; yan guiying

Chinese︱Feedback︱Save this page

• Elaborating Academic Views 　　　　 • Exchanging Innovative Ideas
• Protecting Intellectual Properties 　　• Fast Sharing Science Papers

Sponsored by the Center for Science and Technology Development of the Ministry of Education
Supervised by Ministry of Education of the People's Republic of China

Home > Papers

An-OARSMan: An Obstacle-Avoiding Rectilinear Steiner Tree Algorithm with Good Length Performance

Yu Hu 1 #,Tong Jing 1 * #,Xianlong Hong 2 #,feng zhe 1,hu xiaodong 3,yan guiying 3

1.Tsinghua University

2.Tsinghua University,Institute of Applied Mathematics-Chinese Academy of Sciences

3.Institute of Applied Mathematics-Chinese Academy of Sciences

*Correspondence author

#Submitted by

Subject:

Funding: 教育部博士点基金、国家自然科学基金、国家863项目等（No.20020003008）

Opened online: 1 February 2005

Accepted by: none

Citation: Yu Hu,Tong Jing,Xianlong Hong.An-OARSMan: An Obstacle-Avoiding Rectilinear Steiner Tree Algorithm with Good Length Performance[OL]. [ 1 February 2005] http://en.paper.edu.cn/en_releasepaper/content/1529

Routing is one of the important steps in VLSI/ULSI physical design. The rectilinear Steiner minimal tree (RSMT) 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, obstacle-avoiding RSMT (OARSMT) algorithms are useful for practical routing applications. This paper focuses on the OARSMT problem and presents an algorithm, named An-OARSMan, based on ant colony optimization. A greedy obstacle penalty distance (OP-distance) local heuristic is used in the algorithm and performed on the track graph. The algorithm has been implemented and tested on different kinds of obstacles. Experimental results show that An-OARSMan can handle complex obstacle cases including both convex and concave polygon obstacles with good length performance. It can always achieve the optimal solution in the cases with no more than 7 terminals.

Keywords:physical design, rectilinear Steiner minimum tree (RSMT), obstacles

For this paper

● PDF (0B)
● Revision 0 　　
● Print this paper
● Recommend this paper to a friend
● Add to my favorite list

Saved Papers

Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags

Add yours

Related Papers

Statistics

PDF Downloaded	605
Bookmarked	0
Recommend	5
Comments	Array

Submit your papers

Alert Name:
Alerting to:
Authentication email will be sent to your email address in 24 hours
Frequency:
Email Message Format:	Plain text Graphical(HTML)

Complete the form below and we will recommend the selected titles to your friends on your behalf. * Indicates a required field.
Your name*:
Your email address*:
Recipient's name*:
Recipient's email address*:
(multiple recipient's names and email addresses should be separated with semicolons)
Your comments:	I thought you would find the page(s) useful.

Your name:
Your email address:
Recipient's name:
Recipient's email address:
(multiple recipient's names and email addresses should be separated with semicolons)
Your comments:	I thought you would find this page useful.

Disclaimer: This message was sent to your friend using the "Send it to a friend" facility on the Sciencepaper Online’ WWW site, http://www.paper.edu.cn/en. The Sciencepaper Online is not responsible for the content of this email, and anything said in this email does not necessarily reflect the Sciencepaper Online's views.

	Check out RSS, or use RSS reader to subscribe this item

Saved Papers