New algorithms for physical design of VLSI circuits

Computer-aided design (CAD) tools for very large-scale integrated (VLSI) circuits have become indispensable as advances in silicon manufacturing shrink technology features and greatly increase device densities. As the number of gates grows, major re-inventions of CAD algorithms are needed to assist in management of expanding design complexities in all stages of circuit physical design flow. We investigate in this dissertation major challenges in design of new CAD tools in the era of very deep-submicron (DSM) technologies.; Floorplanning is the first step of physical design and has a great impact on all following design stages. Slicing tree based floorplanning has been shown to be an effective tool for floorplan design. However, non-slicing floorplans have become common-place in VLSI circuits, and finding new representations of non-slicing floorplans has become necessary. We show that slicing tree is a complete floorplan representation in the sense that it can be used to generate all non-slicing placements.; During circuit routing, buffer insertion and wire sizing are effective tools for interconnect optimization. We propose a novel formulation of circuit maze routing problem based on graph theory. Our new method performs maze routing with simultaneous buffer insertion and wire sizing. Wiring obstacles in chip area are also taken in consideration. Experiments have shown that the new formulation is very efficient.; Interconnect wiring delay has replaced gate delay and become a major factor of performance of VLSI circuits. New algorithms for minimizing inter-connect delay have been proposed. However, huge memory requirements of some of the proposed methods restrict their applicability. We provide a new memory-efficient approach for interconnect optimization.; Identically instantiated modules (repeated modules) have become popular in modern VLSI circuits. Efficient algorithms are needed for optimizing the performance of circuits with repeated modules. We model the pin assignment for repeated modules problem as a constrained optimization problem. In our formulation, all instances of a module type have identical pin assignment solutions. Based on this formulation, we propose a highly efficient approach to solve the problem.