Algorithmic Aspects of Vlsi Circuit Layout (Channel Routing, Logic Array)

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.