Routing algorithms in the physical design of VLSI circuits

In this thesis, we solve several important routing problems in the physical design of VLSI circuits. We successfully apply combinatorial optimization techniques to these problems and obtain very effective and efficient algorithms. The experimental results presented in this thesis show that these algorithms produce high quality routing solutions on a wide range of test circuits using reasonable amount of computation time.Chapter 2 and 3 address some global routing problems in the physical design of VLSI circuits. In Chapter 2, we present a global routing algorithm for standard cell design which connects all the nets in parallel. We show that only a linear number of possible connections need to be considered by our algorithm. In Chapter 3, we present an algorithm which combines the pin assignment step and the global routing step in the general cell design style. The complexity of the combined problem is reduced based on the block boundary decomposition.In Chapter 4 and 5, we study some detailed routing problems. In Chapter 4, we show how to enhance channel compaction results by modifying the initial grid-based routing solution. We show that proper track permutation and local re-routing lead to significant reduction in channel routing area. In Chapter 5, we study a new channel routing model called over-the-cell channel routing. We show that the over-the-cell routing problem can be solved in three steps and we present efficient solutions to the sub-problems at each step.In Chapter 6, we study the planar subset problem and the topological via minimization in multi-layer routing models. We show that the general problems are NP-hard and we give efficient solutions to the restricted problems.U of I OnlyETDs are only available to UIUC Users without author permissio