| Automatic routing is one of the oldest and most fundamental problems in computer-aided design of integrated circuits (IC). It has been studied extensively for over thirty years. However, recent advances in processing technology and design methodology have brought new challenges to the routing automation problem. As the VLSI technology reaches deep sub-micro devices and gigahertz clock frequencies, interconnect has become the dominating factor in determining the performance, power and reliability of the circuit. Various optimization algorithms are needed to handle the delay, power and noise problems. These algorithms impose variable width and variable spacing design rule requirements on the routing algorithm. Moreover, the complexity of IC design problem has increased significantly with the shrinking of the transistor feature size. This imposes a serious scaling problem for the full-chip level routing.; These advancements in the IC technology brings several challenges to the detailed routing problem as well as the overall routing systems. First, an efficient multi-layer gridless routing engine is needed to route the interconnects with variable width and variable spacing constraints. Second, a highly scalable and flexible routing system is needed to integrate various optimization algorithms and the gridless detailed routing algorithms to handle the routing problem.; In this dissertation, we present a multi-layer general-area detailed routing system. It features an efficient gridless point-to-point detailed routing algorithm as the routing engine. An implicit representation of a non-uniform grid graph is proposed as the underlying routing graph and a path-based maze searching engine is developed to search for the paths on the graph. Our gridless detailed routing system also features a unique wire planning algorithm. The planning algorithm not only guides our gridless detailed routing engine but also provides ripup and re-routing capabilities for the detailed routing system. Lastly, we propose a routing system featuring a multilevel framework. The proposed framework is highly scalable to large routing problems and flexible in integrating various optimization algorithms into the routing system. The proposed routing system can be used for high performance IC, multi-chip module (MCM), or printed circuit board (PCB) designs. It can also be used in full custom IC layout, as for the cell library design and the analog circuit design. |
