An-OARSMan: An Obstacle-Avoiding Rectilinear Steiner Tree Algorithm with Good Length Performance
首发时间:2005-02-01
Abstract: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
点击查看论文中文信息
An-OARSMan: An Obstacle-Avoiding Rectilinear Steiner Tree Algorithm with Good Length Performance
摘要: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.
关键词: physical design, rectilinear Steiner minimum tree (RSMT), obstacles
论文图表:
引用
No.1529177341107241****
同行评议
共计0人参与
勘误表
An-OARSMan: An Obstacle-Avoiding Rectilinear Steiner Tree Algorithm with Good Length Performance
评论
全部评论0/1000