Abstract
In very large scale integration (VLSI) design, a rectilinear Steiner tree (RST) is usually used to guide router to connect signals for a net. However, In current technology, there are more and more rectilinear obstacles, such as power networks, macro cells, IP blocks and pre-routed nets. Therefore, a concept of obstacle-avoiding rectilinear Steiner minimal tree (OARSMT) has been noticed that can be applied on the routing problem. Besides, in modern nano-technology designs, there are multiple metal layers can be used for routing, at the same time, the preferred directions constraint limits the orientations of routing in each layer for the signal integrity consideration. As a result, the obstacle-avoiding preferred direction Steiner tree (OAPDST) problem has been proposed to cop with these practical problems. In this thesis, we present a novel, robust, and high quality OAPDST construction algorithm for this problem. Our algorithm is based on nding suitable Steiner points on a graph, and guided by an RST. Several shortest path nding algorithms were also proposed to connect every Steiner points and their neighbors with minimal wirelength. Besides, our approach can be easily extended to deal with multi-layer obstacle-avoiding rectilinear Steiner minimal tree (ML-OARSMT) problem. The experimental results show our algorithm performs well in total cost, both on OAPDST and ML-OARSMT problems.