1. λ-OAT: λ-Geometry Obstacle-Avoiding Tree Construction With O(n log n) Complexity.
- Author
-
Tom Tong Jing, Zhe Feng, Yu Hu, Hong, Xianlong L., Hu, Xiaodong D., and Yan, Guiying Y.
- Subjects
- *
ROUTING (Computer network management) , *STEINER systems , *COMPUTER architecture , *INTEGRATED circuits , *COMPUTER terminals , *INFORMATION technology - Abstract
Obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) construction is an essential part of routing. 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(n log n) heuristic, λ-OAT, for obstacle-avoiding Steiner minimal tree construction in the A-geometry plane (λ-OASMT). In this paper, based on obstacle-avoiding constrained Delaunay triangulation, a full connected tree is constructed and then embedded into λ-OASMT by zonal combination. To the best of our knowledge, this is the first work addressing the λ-OASMT problem. Compared with most recent works on OARSMT problem, A-OAT obtains up to 30-Kx speedup with quality solution. We have tested randomly generated cases with up to 10 K terminals and 10-K rectilinear obstacles within 4 seconds on a Sun V880 workstation (755-MHz CPU and 4-GB memory). The high efficiency and accuracy of λ-OAT make it extremely practical and useful in the routing phase. [ABSTRACT FROM AUTHOR]
- Published
- 2007
- Full Text
- View/download PDF