Files in this item



application/pdf9114483.pdf (5MB)Restricted to U of Illinois
(no description provided)PDF


Title:Algorithms for VLSI routing
Author(s):Zhou, Dian
Doctoral Committee Member(s):Preparata, Franco P.
Department / Program:Electrical and Computer Engineering
Discipline:Electrical and Computer Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Computer Science
Abstract: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.
Issue Date:1990
Rights Information:Copyright 1990 Zhou, Dian
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9114483
OCLC Identifier:(UMI)AAI9114483

This item appears in the following Collection(s)

Item Statistics