Files in this item
|(no description provided)|
|Title:||Routing Problems in the Physical Design of Integrated Circuits (Cad, Simulated Annealing, Channel Routing)|
|Author(s):||Leong, Hon Wai|
|Department / Program:||Computer Science|
|Degree Granting Institution:||University of Illinois at Urbana-Champaign|
|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.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1986.
|Date Available in IDEALS:||2014-12-15|