Paper Info
Title
An O(nlogn) algorithm for obstacle-avoiding routing tree construction in the lambda-geometry plane
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.
Year
DOI
Venue
2006
10.1145/1123008.1123020
ISPD
Keywords
DocType
Citations 
λ-geometry,onlogn,steiner tree construction,obstacle-avoiding
Conference
1
PageRank 
References 
Authors
0.36
9
6
Name
Order
Citations
PageRank
Zhe Feng1515.25
Yu Hu2759.62
Tong Jing314913.43
Xianlong Hong41307132.32
Xiaodong Hu562847.63
Guiying Yan619622.92