Algorithmic Aspects of Vlsi Circuit Layout (Channel Routing, Logic Array)
Wong, Martin Ding Fat
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/69570
Description
Title
Algorithmic Aspects of Vlsi Circuit Layout (Channel Routing, Logic Array)
Author(s)
Wong, Martin Ding Fat
Issue Date
1987
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
The thesis addresses the algorithmic design aspect of VLSI circuit layout. We study several optimization problems that arise from various stages of circuit layout. In particular, we consider problems chosen from the area of floorplan design, module synthesis, and routing.
In chapter 2, we present an algorithm to construct slicing floorplans for rectangular modules. Our major contributions are: (1) a new representation of floorplans which enables us to carry out neighborhood search effectively, and (2) a simultaneous minimization of area and interconnections in the final solution.
In chapter 3, we present an unified approach to generate: (1) floorplans for rectangular and L-shape modules, (2) non-slicing floorplans for rectangular modules, and (3) slicing floorplans for rectangular modules.
In chapter 4, we present an algorithm for folding Programmable Logic Arrays. Our algorithm can perform multiple folding as well as simple folding. We also show how our algorithm can be extended to handle constrained folding.
In chapter 5, we present an algorithm that solves a general array optimization problem. Our algorithm can be used for compacting Gate Matrix layouts, SLAs, Weinberger Arrays, and for multiple folding of PLAs.
In chapter 6, we study the channel routing problem in which via size on the total routing area is considered. We introduce a track permutation technique to produce routing solutions that contain no horizontally adjacent vias and a close to minimum number of vertically and diagonally adjacent vias. Such solutions lead to compaction that will reduce total routing area.
All of our algorithms except those in chapter 7 for channel routing employ the technique of simulated annealing. Our research not only produced good algorithms for a number of important problems in the area of VLSI circuit layout, but also illustrated that the technique of simulated annealing is an effective and valuable algorithmic design methodology.
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.
