Process variation aware interconnect simulation and optimization in VLSI design

Due to increasing integration density and soaring clock frequency, uncertainties associated with parameter variations become a first-tier concern for Very Large Scale Integration (VLSI) chip design, especially in the nanometer regime. Typically, the source of variations includes process-induced and environmental variations. In this dissertation, we focus on modeling, analysis and optimization of large-sized on-chip power grid networks considering manufacturing process variations. It consists of three major topics and a number of contributions have been made in each of these topics: Firstly, efficient algorithms to reduce the voltage noise of on-chip power grid networks without considering process variations in VLSI design have been proposed. The algorithms are based on the sequence of linear programming (SLP) as the optimization engine and a localized scheme through circuit-partitioning to handle large-sized circuits. The SLP algorithm is capable of delivering much better quality in terms of decoupling capacitor (decap) budget than existing methods. The partitioning strategy further improves the scalability of the algorithm and makes it much efficient to simulate and optimize large-sized circuits.;Secondly, the variability of the interconnect systems has been investigated. We propose a statistical model order reduction technique called Statistical Spectrum Model Order Reduction (SSMOR). The analysis is based on the Hermite polynomial chaos representation of random processes. This algorithm is capable of considering both intra-die and inter-die process variations with spatial correlations. The SSMOR generates order-reduced variational circuit models originated from any given variational interconnect circuits. The reduced model can be used for fast statistical performance analysis of interconnect design with variational power sources.;Lastly, a stochastic method has been proposed to analyze the variation of voltage drop in on-chip power grid networks considering log-normal leakage current variations with spatial correlations. In addition, a novel noise reduction technique for power grid networks in VLSI design is proposed in the presence of variational leakage current sources. The proposed algorithm inserts decaps into power grid networks to avoid voltage fluctuation and considers the variability of power sources statistically. The optimization engines are based on both sensitivity-based conjugate gradient method and sequence of linear programming approach.