Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction
Date Issued
2007
Date
2007
Author(s)
Lin, Chung-Wei
DOI
en-US
Abstract
Given a set of pins and a set of obstacles on a plane, an obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) connects these pins by vertical/horizontal edges, possibly through some additional points (called Steiner points), and avoids running through any obstacle to construct a tree with a minimal total wirelength. The OARSMT problem becomes more important than ever for modern nanometer IC designs which need to consider numerous routing obstacles incurred from power networks, prerouted nets, IP blocks, feature patterns for manufacturability improvement, etc. Consequently, the OARSMT problem has received dramatically increasing attention recently. Besides, because modern nanometer IC designs are processed layer by layer, it is a new challenge for designers to deal with the multi-layer OARSMT (ML-OARSMT) problem where pins are connected by vertical/horizontal edges within layers and vias between layers. Nevertheless, the presences of obstacles and multi-layers significantly increase the problem complexity, and thus most previous works for the OARSMT problem on a layer suffer from either poor quality or expensive running time. Based on the obstacle-avoiding spanning graph (OASG), this thesis presents an efficient algorithm with some theoretical optimality guarantees for the OARSMT construction on a layer. Unlike previous heuristics, our algorithm guarantees to find an optimal solution for any 2-pin net and many higher-pin nets. Furthermore, we identify key different properties of the ML-OARSMT problem from the single-layer counterpart and present the first algorithm to solve the ML-OARSMT problem. This algorithm can also guarantee an optimal solution for any 2-pin net and many higher-pin nets. Extensive experiments show that our algorithms result in significantly shorter wirelengths than all state-of-the-art works.
Subjects
實體設計
繞線
史坦納樹
生成樹
多層平面
physical design
routing
Steiner tree
spanning tree
multi-layer
Type
thesis