Algorithms for VLSI routing

This thesis considers the problems arising from VLSI routing design. Algorithms are proposed for solving both global and local routing problems.For routing multiterminal nets in the gate array and sea-of-gates technologies, we present a global router which upper bounds the global density of the routing by 2$s\sp{\*}$, where $s\sp{\*}$ is the span of the nets. For standard cell technology, we present a global router which achieves the optimal horizontal density while upper bounding the vertical density by 2$s\sp{\*}$. The parallel implementations of the proposed global routing algorithms are presented.For the local routing problem, we first investigate the efficiency of the Manhattan routing model. We study in detail how the grid points are used in the Manhattan model and, consequently, establish a general lower bound on the channel width for routing two-terminal nets in a channel. All of the previous known results (lower bounds on the channel width) can be derived from our general lower bound. Furthermore, an asymptotically tight lower bound is obtained. We are also able to establish the lower bounds on the routing area for routings in L-, S-, T- and X-junctions in both the Manhattan and knock-knee models.For routing in an arbitrary rectilinear polygon, which is a generalization of many local routing problems, we present a sublinear time algorithm running in O(m log$\sp2$ m), where m is the number of edges in the boundary of the polygon. The presented algorithm produces the minimal routing area. For routing in the restricted wire-overlap model, we present an optimal algorithm which constructs a routing with minimum channel width. In the routing produced by the algorithm, the length of the wire overlap between any two nets is upper bounded by O(k), where k is the multiplicity of the nets.U of I OnlyETDs are only available to UIUC Users without author permissio