Routing algorithms in the physical design of VLSI circuits
Cong, Jingsheng
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19656
Description
Title
Routing algorithms in the physical design of VLSI circuits
Author(s)
Cong, Jingsheng
Issue Date
1990
Doctoral Committee Chair(s)
Liu, C.L.
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Physics, Electricity and Magnetism
Computer Science
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
