Nano Technology Integrated Circuit Interconnect Parasitic Capacitance Parameter Extraction

The great improvements of the semiconductor industry depend on continuouslytechnology scaling down, which provides integrated circuit with better performanceand exponentially increasing integration capability. However, the pace of scalingdown also introduces new challenges to the IC design. It is because of this that ICdesign tools and methodologies need to constantly evolve in order to overcome thenew challenges.At the end of last century, IC design was interconnect-centric. This is dueprimarily to the fact that interconnects had become the dominant factor in determiningcircuit performance and reliability in deep submicron designs. Signal integrityproblems such as crosstalk noise, IR-drop and coupling-induced delay variation werebecoming increasingly more significant, largely due to the more and more severeparasitic effects associated with an increasing complexity of interconnect structureand an increased circuit density in the integrated circuit. Since the turn of the century,the miniatnrizing is approaching its physical limit, and process variations become themajor one of challenges of the IC design and manufacture. Nowadays, IC technologyreaches 45nm node. Complex nano-technologies such as sub-wavelength lithographyand Chemical-Mechanical Polishing (CMP) cause more and more large processvariations and therefore seriously deteriorate the yield. Yield loss problem hasbecome a fateful and critical problem for nano-VLSI design. IC design is nowentering into a new era of DFM/DFY (Design For Manufacturability and Design ForYield) that the gap between design and manufacture has to be bridged.The interconnects, of which the performance dominates the circuit performance,now need to be accurately modeled not only capturing the parasitic effects ofinterconnects, but also taking into account the geometric variations caused by nanotechnologies.To this end, variation-aware parasitic extraction of interconnects is oneof the key techniques in DFM/DFY that provides the designers with the accnratevariation-aware model of interconnects. Many other nano-VLSI design techniquessuch as SSTA (Statistical Static Timing Analysis) rely on this model to analysis thetinting and performance of the interconnect circuits under process variations. Themajor difficulty of variation-aware parasitic extraction is the random nature ofgeometric variation and the resulting stochastic problem of parasitic extraction. Thisdissertation studies the problem of variation-aware capacitance extraction, andproposes two Stochastic Collocation Methods to solve the stochastic problem. As oneof the stochastic spectral methods, stochastic collocation method has the optimal(exponential) convergence rate for solving the stochastic PDE (Partial DifferentialEquation) problem. Benefited from this, it is very promising to use the stochasticcollocation method to handle the stochastic problem of process variations as thesemiconductor keeps scaling down.The major contributions of this dissertation include 1) a Stochastic CollocationMethod (SCM) for variation-aware capacitance extraction that the geometricvariations are assumed to have Gaussian random distribution; and 2) a generalizedStochastic Collocation Method (gSCM) that has optimal (exponential) convergencerate for real geometric variations which have arbitrary random distribution. Therelative work has been published in IEEE conference of Design, Automation and Testin Europe. This is the first work that applies the stochastic spectral method to theproblem of parasitic extraction. In the following year, Tsinghua University, University of California Riverside and Massachusetts Institute of Technology allpublish their stochastic spectral methods based on this paper. The advantages of theproposed Stochastic Collocation Method (SCM) and generalized StochasticCollocation Method (gSCM) compared with the existing methods are summarized inthe following.1) Compared with the existing perturbation approach for capacitance extraction,the proposed Stochastic Collocation Method (SCM) has optimal (exponential)convergence rate for solving the stochastic problem. The perturbation approach wasproposed by University of Wisconsin-Madison in ICCAD'2005, which is based on theTaylor expansion. It is well know that the convergence of the perturbation method isnot guaranteed for large variation. The numerical results clearly show that the secondorderperturbation approach doesn't have much accuracy improvement compared withthe first-order perturbation, while the first order SCM can achieve the same accuracycompared with the second-order perturbation approach.2) Principal Component Analysis in the perturbation approach involves solvingan eigen-problem, of which the computational time becomes dominant when thenumber of panels is large. The proposed SCM use K-L expansion instead, whichapplies a more efficient numerical approach to overcome this bottle-neck problem.3) The Sparse Grid and the generalized Sparse Grid numerical quadratures areapplied respectively in SCM and gSCM, and serve as the collocation points of randomspace. The Sparse Grid is regarded as "the Blessing of Dimensionality". It avoids theproblem in Direct Tensor Product approaches that the number of collocation pointsincreases exponentially w.r.t, the dimensionality, and can save orders ofcomputational time compared with the Monte Carlo approach.4) One of the advantages of SCM is that it transforms the stochastic problem todeterministic problems at collocation points. A recycling technique based on theMinimum Spanning Tree is further proposed to help selecting the initial value andconstructing preconditioning matrix at each collocation points, which allows furtherimprovement of the computation efficiency.5) It is very important to realize that the optimal (exponential) convergence rateof Stochastic Spectral method is mostly due to the orthogonality of the HomogeneousChaos. SCM uses Hermite polynomials based on the Gaussian random distributionassumption of the geometric variations. However, when geometric variations aremeasured from the real test chip, they are not necessarily Gaussian, which willsignificantly compromise the optimal (exponential) convergence property of SCM. Inorder to pursue the exponential convergence, a generalized stochastic collocationmethod (gSCM) is proposed for variation-aware capacitance extraction that furtherconsiders the arbitrary random probability of real geometric variations. The proposedgSCM can use the real geometric variations as the input and construct the generalizedPolynomial Chaos and generalized Sparse Grid "on-the-fly". The optimal(exponential) convergence of the proposed gSCM is clearly shown in the numericalresults for the geometric variations with arbitrary random probability.