Vlsi Physical Design Of The Rectangular Steiner Tree Problem

At first, this thesis introduces the VLSI physical design process, based on this leads to the rectilinear Steiner tree problem. Many known algorithms take into account the rectilinear Steiner tree problem with obstacles, but there is little consideration of the boundary. The boundary of the routing area cannot be simply regarded as the spliced obstacles of one-dimensional, because this will go on cutting the concave boundary, so that wires run to the region outside the routing area. And it will bring unnecessary operations in the case of irregular boundary of the routing area.In this thesis, the problem can be well overcome by the weighted Lee algorithm,the time complexity of which is O(n~2(n+m)~2 log(n + m)), where n is the number of terminals, m is the number of vertices of obstacles and boundary.At the same time, the minimum convex polygon technology is proposed in this thesis. It greatly reduces the routing area, and proves the existence of the optimal solution within the minimum convex polygon, and then computes sub-optimal solution by the weighted Lee algorithm.The algorithm mentioned herein could get rid of the obstacles that is useless in the operation, thus further reducing the computing scale. Practice has proved that the routing algorithm runs in higher efficiency when the boundary of the routing area is irregular, or the terminals are arranged in a diagonal-shaped array.For multi-layer routing model, this thesis extends the weighted Lee algorithm to three-dimensional, while the technology of minimum convex polygon extended to the one of minimum convex polyhedron. By adjusting the corresponding edge weight of the extended Hanan grid, we achieve the objective of reducing the number of vias.Finally, this thesis gives the definition of the rectilinear Steiner tree problem in more higher-dimensional space, and the corresponding structure of the minimum convex polyhedron.