Routing Problems in the Physical Design of Integrated Circuits (Cad, Simulated Annealing, Channel Routing)
Leong, Hon Wai
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/69549
Description
Title
Routing Problems in the Physical Design of Integrated Circuits (Cad, Simulated Annealing, Channel Routing)
Author(s)
Leong, Hon Wai
Issue Date
1986
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)
Computer Science
Abstract
In this thesis, we study an approach to the physical design of integrated circuits in which some design flexibilities are incorporated into the routing step via suitable generalizations of the routing model. Better layouts are obtained using this approach since the router can make use of these flexibilities to reduce the wiring area.
Three different models for channel routing are considered--traditional channel routing, and generalizations to discretionary channel routing where we only require that each net connect some (not all) of its pins, and permutation channel routing where we allow some of the pins to be interchanged. We show that these generalizations can handle design flexibilities such as physically and logically equivalent pins, duplicated pins in macrocells, and input/output in assignments in programmable logic devices.
For the traditional model, we present a new simulated annealing channel routing algorithm whose performance is competitive with other well-known channel routers in the literature. Efficient algorithms for the discretionary and permutation channel routing problems are also presented. These algorithms have been implemented and tested on various data and our results show that they produce near-optimal solutions. More importantly, these results show that substantial savings in the wiring area can be achieved by using the generalized models.
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.