A full-scale solution to the rectilinear obstacle-avoiding Steiner problem
文献类型：期刊论文
| 作者 | Jing, Tom Tong1,2; Hu, Yu1,2; Feng, Zhe1,2; Hong, Xian-Long2; Hu, Xiaodong3 ; Yan, Guiying3
|
| 刊名 | INTEGRATION-THE VLSI JOURNAL
 |
| 出版日期 | 2008-05-01 |
| 卷号 | 41期号:3页码:413-425 |
| 关键词 | routing rectilinear Steiner minimal tree obstacle avoiding ant colony optimization track graph hypergraph full Steiner tree detour |
| ISSN号 | 0167-9260 |
| DOI | 10.1016/j.vlsi.2007.10.002 |
| 英文摘要 | Routing is one of the important steps in very/ultra large-scale integration (VLSI/ULSI) physical design. Rectilinear Steiner minimal tree (RSMT) construction is an essential part of routing. 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. However, OARSMT algorithms for multi-terminal net routing still cannot meet the requirements of practical applications. This paper focuses on the OARSMT problem and gives a solution to full-scale nets based on two algorithms, namely An-OARSMan and FORSTer. (1) Based on ant colony optimization (ACO), An-OARSMan can be used for common scale nets with less than 100 terminals in a circuit. An heuristic, greedy obstacle penalty distance (OP-distance), is used in the algorithm and performed on the track graph. (2) FORSTer is a three-step heuristic used for large-scale nets with more than 100 terminals in a circuit. In Step 1, it first partitions all terminals into some subsets in the presence of obstacles. In Step 2, it then connects terminals in each connected graph with one or more trees, respectively. In Step 3, it finally connects the forest consisting of trees constructed in Step 2 into a complete Steiner tree spanning all terminals while avoiding all obstacles. (3) These two graph-based algorithms have been implemented and tested on different kinds of cases. Experimental results show that An-OARSMan can handle both convex and concave polygon obstacles with short wire length. It achieves the optimal solution in the cases with no more than seven terminals. The experimental results also show that FORSTer has short running time, which is suitable for routing large-scale nets among obstacles, even for routing a net with one thousand terminals in the presence of 100 rectangular obstacles. (C) 2007 Elsevier B.V. All rights reserved. |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| WOS记录号 | WOS:000256572800008 |
| 出版者 | ELSEVIER SCIENCE BV |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/6289]  |
| 专题 | 应用数学研究所 |
| 通讯作者 | Jing, Tom Tong |
| 作者单位 | 1.Univ Calif Los Angeles, Dept Elect Engn, Los Angeles, CA 90095 USA 2.Tsinghua Univ, Comp Sci & Technol Dept, Beijing 100084, Peoples R China 3.Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Jing, Tom Tong,Hu, Yu,Feng, Zhe,et al. A full-scale solution to the rectilinear obstacle-avoiding Steiner problem[J]. INTEGRATION-THE VLSI JOURNAL,2008,41(3):413-425. |
| APA | Jing, Tom Tong,Hu, Yu,Feng, Zhe,Hong, Xian-Long,Hu, Xiaodong,&Yan, Guiying.(2008).A full-scale solution to the rectilinear obstacle-avoiding Steiner problem.INTEGRATION-THE VLSI JOURNAL,41(3),413-425. |
| MLA | Jing, Tom Tong,et al."A full-scale solution to the rectilinear obstacle-avoiding Steiner problem".INTEGRATION-THE VLSI JOURNAL 41.3(2008):413-425. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。