New Strategies for High Performance VLSI Physical Design

Physical design plays an important role in connecting front-end design and back-end design in chip development. In this thesis, we solve several important problems in physical design of VLSI circuits. Chapter 2 addresses a floorplan problem that considers floorplanning and bus planning simultaneously. We propose an efficient evaluation algorithm to transform a sequence pair to a floorplan with buses inserted. Then simulated annealing is used to search for an optimal or near optimal solution. Chapter 3 addresses a wire planning problem with the bounded over-the-block constraint. Two exact polynomial-time algorithms are presented, and both algorithms guarantee to find an optimal routing solution for a two-pin net as long as one exists. Chapters 4 and 5 are based on a min-cost max-flow algorithm. In chapter 4, we present the first polynomial-time algorithm for simultaneous pin assignment and routing for all two-pin nets between one source block and all other blocks. In chapter 5, we propose a polynomial-time algorithm for integrated pin assignment and buffer insertion. Chapters 6 and 7 address ECO problems. Chapter 6 presents two algorithms to resolve overlaps between power rails and signal wires which are introduced by power rail redesign. In chapter 7, we propose an algorithm to eliminate capacitive crosstalk violations