| The advancement of the very large scaled integrated circuit (VLSI) technology has been following the Moore's Law closely in the past few decades resulting in larger and faster chips every year. Nevertheless, the gap between the advances and the utilization of the deep submicron (DSM) technology is widening as the new generation of technology is introduced faster than ever. This gap is caused by sophisticated physical phenomena that need to be accurately modeled so that they can be used to guide the CAD tools to complete the designs. In this dissertation, we propose to develop CAD algorithms for the design and manufacturing VLSI circuits and systems.; First, we present a maze routing method that considers the optical effect in the routing algorithm. The problem is first formulated as a constrained maze routing problem, then it is shown to be a multiple constrained shortest path problem, which has been proved to be strongly NP-complete. Based on the Lagrangian method, an effective heuristic is designed to solve the problem.; Second, we present an algorithm to fix the antenna problem. The antenna problem is a phenomenon of plasma induced gate oxide degradation. It directly affects manufacturability of VLSI circuits. Diode insertion is an effective way to solve this problem. We propose a diode insertion and routing problem based on a network flow formulation.; Third, we show that the problem of finding a minimum-delay buffered routing path with transition time constraints can be formulated as a shortest path problem. Instead of using the commonly used Elmore delay model which is only a first-order approximation of signal delay and is hard to handle transition time constraints, our algorithm is robust enough so that different very accurate delay models (e.g., transmission line model, delay look-up table from SPICE, etc.) can be used.; Finally, we present an algorithm to generate the global wire bus configuration with minimum delay uncertainty under timing constraints. The timing window information from the timing budget (or specified in IPs) is integrated with the modern accurate crosstalk noise models in the proposed algorithm. This global wire bus configuration can be adopted in early wire planning to improve the timing closure problem and increase the accuracy of the timing budget. |
