## Files in this item

FilesDescriptionFormat

application/pdf

9114483.pdf (5MB)
(no description provided)PDF

## Description

 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 Degree: Ph.D. Genre: Dissertation 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 Type: Text Language: English URI: http://hdl.handle.net/2142/20933 Rights Information: Copyright 1990 Zhou, Dian Date Available in IDEALS: 2011-05-07 Identifier in Online Catalog: AAI9114483 OCLC Identifier: (UMI)AAI9114483
﻿