Files in this item



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


Title:Routing Problems in the Physical Design of Integrated Circuits (Cad, Simulated Annealing, Channel Routing)
Author(s):Leong, Hon Wai
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:1986
Description:177 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1986.
Other Identifier(s):(UMI)AAI8610954
Date Available in IDEALS:2014-12-15
Date Deposited:1986

This item appears in the following Collection(s)

Item Statistics