Algorithms for VLSI design planning
With shrinking feature sizes, much more transistors can be integrated on a single chip. Moore’s Law has been followed closely in the past decades, resulting in larger and faster chips every year. In order to design larger and faster chips in deep submicron (DSM) technology, it is necessary to perform early design planning. In this dissertation, we present several algorithms for a number of VLSI design planning problems. First, we propose a method to integrate interconnect planning with floorplanning. Our approach is based on the Wong-Liu floorplanning algorithm. We perform pin assignment and fast global routing during every iteration of floorplanning. We use a multi-stage simulated annealing approach in which different interconnect planning methods are used in different ranges of temperatures to reduce running time. A temperature adjustment scheme is designed to give smooth transitions between different stages of simulated annealing. Second, floorplanning problems typically have relatively small number of blocks (e.g., 50-100) but have a large number of nets (e.g. 20K). Since existing floorplanning algorithms use simulated annealing which needs to examine a large number of floorplans, this has made interconnect-centric floorplanning computationally very expensive. We present approaches that can dramatically improve the run time of problems with large number of nets and at the same time improve solution quality. Third, we propose a method for simultaneous power supply planning and noise avoidance in floorplan design. Without careful power supply planning in layout design, the design of chips will suffer from mostly signal integrity problems including IR-drop, I noise, and IC reliability. Post-route methodologiesin solving signal integrity problem have been applied but they will cause a long turn-around time, which adds costly delays to time-to-market. We show that the noise avoidance in power supply planning problem can be formulated as a constrained maximum flow problem. Fourth, I/O placement has been a concern in modern IC design. Due to flipchip and multi-chip module technologies, I/O can be placed throughout the whole chip without long wires from the periphery of the chip. However, because of I/O placement constraints and I/O buffer site building cost, the decision of positions for placing I/O buffers has become critical. Our objective is to reduce the number of I/O buffer sites and to decide their positions in an existing standard cell placement. We formulate it as a minimum cost flow problem.