Files in this item



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


Title:Routing algorithms in the physical design of VLSI circuits
Author(s):Cong, Jingsheng
Doctoral Committee Chair(s):Liu, C.L.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Engineering, Electronics and Electrical
Physics, Electricity and Magnetism
Computer Science
Abstract:In this thesis, we solve several important routing problems in the physical design of VLSI circuits. We successfully apply combinatorial optimization techniques to these problems and obtain very effective and efficient algorithms. The experimental results presented in this thesis show that these algorithms produce high quality routing solutions on a wide range of test circuits using reasonable amount of computation time.
Chapter 2 and 3 address some global routing problems in the physical design of VLSI circuits. In Chapter 2, we present a global routing algorithm for standard cell design which connects all the nets in parallel. We show that only a linear number of possible connections need to be considered by our algorithm. In Chapter 3, we present an algorithm which combines the pin assignment step and the global routing step in the general cell design style. The complexity of the combined problem is reduced based on the block boundary decomposition.
In Chapter 4 and 5, we study some detailed routing problems. In Chapter 4, we show how to enhance channel compaction results by modifying the initial grid-based routing solution. We show that proper track permutation and local re-routing lead to significant reduction in channel routing area. In Chapter 5, we study a new channel routing model called over-the-cell channel routing. We show that the over-the-cell routing problem can be solved in three steps and we present efficient solutions to the sub-problems at each step.
In Chapter 6, we study the planar subset problem and the topological via minimization in multi-layer routing models. We show that the general problems are NP-hard and we give efficient solutions to the restricted problems.
Issue Date:1990
Rights Information:Copyright 1990 Cong, Jingsheng
Date Available in IDEALS:2011-05-07
Identifier in Online Catalog:AAI9114210
OCLC Identifier:(UMI)AAI9114210

This item appears in the following Collection(s)

Item Statistics