Ic Modeling And Simulation Algorithms Based On Nested Sparse Grid Stochastic Collocation Method

The great improvements of the semiconductor industry depend on continuously technology scaling down, which provides integrated circuit (IC) with better performance and exponentially increasing integration capability. When the semiconductor technology enters the nanometer regime, random process variations have been introduced due to the complex nano-technology, such as sub-wavelength lithography and chemical-mechanical polishing. Process variations will cause the variations of geometrical and electrical parameters of devices and interconnects, thereby degrade the performances of the fabricated circuits from the design specifications, and seriously deteriorate the yield. In order to give circuit designers more accurate simulation results, stochastic analysis should be introduced to the whole IC simulation flow to consider the effects of random process variations.Among all the stochastic analysis methods, Monte Carlo Method (MCM) is the most straightforward and simple one. However, in order to get a better result, tens of thousands of sampling points should be used by MCM, and the computation time is too long for most of the applications. Recently, Stochastic Collocation Method (SCM) has been introduced to the field of stochastic analysis of integrated circuits due to its high computation accuracy and efficiency. However, the quadrature nodes constructed by all the existing SCMs, which are based on one-dimensional traditional Gaussian quadrature and multidimensional non-nested sparse grid quadrature, do not satisfy the nested property that quadrature nodes with low accuracy are not contained in the quadrature nodal set with high accuracy. Since sparse grid quadrature is constructed from one-dimensional quadratures with different accuracy, non-nested quadrature nodes can not be shared and reused by these quadratrures with different accuracy. Therefore, the computation accuracy and efficiency of SCMs based on non-nested sparse grid quadrature are degraded for practical applications.Under the framework of the stochastic collocation method, we have studied the impact of collocation points on the computation accuracy and efficiency, and proposed several modified stochastic collocation methods based on nested sparse grid technique, which further improve the computation accuracy and efficiency of the stochastic collocation method.1. In order to overcome the "non-nested" disadvantage of the existing Sparse grid based Stochastic Collocation Method (SSCM), we propose a Nested Sparse grid based Stochastic Collocation Method (NSSCM) based on extended Gaussian quadrature and nested sparse grid technique. Compared with SSCM, the proposed NSSCM greatly improves the computation accuracy and efficiency of the stochastic collocation method.2. To further improve the efficiency of NSSCM, we propose a Modified Nested Sparse grid based Stochastic Collocation Method (MNSSCM), which only uses those sparse grids that significantly contribute to the computation accuracy. The proposed MNSSCM can remarkably reduce the number of collocation points and the computation time with acceptable accuracy.3. In order to capture the nonlinearity of process variations, the existing stochastic collocation methods, including SSCM, NSSCM and MNSSCM, use the second order non-nested or nested sparse grids as collocation points, whose number is proportional to the square of the number of random variables. To further improve the computation efficiency of the proposed MNSSCM, we prosed a first order nested sparse grid based Quasi Quadratic Stochastic Collocation Method (QQSCM), where the number of collocation points increases linearly with respect to the number of random variables. In QQSCM, we propose an error recovery technique to correct the numercal errors resulted from computing quadratic polynomial expansion coefficients using first order nested sparse grid quadrature.In the field of modeling and simulation of integrated circuits under process variations, one of the key problem is Statistical Static Timing Analysis (SSTA), of which gate and interconnect delay modeling are the two fundemantal problems.1. To overcome the disadvantages of the existing SSCM based gate delay modeling, we apply the proposed NSSCM to gate delay modeling. Numerical results show that compared with the existing SSCM based gate delay modeling, the proposed NSSCM based gate delay modeling has higher compution accuracy with the same amount of collocation points.2. For interconnect capacitance extraction, the key of interconnect delay modeling, we apply the proposed MNSSCM and QQSCM to interconnect capacitance extraction problem. Numercial results show that compared with the existint SSCM, the prosed MNSSCM and QQSCM has much higher computation efficiency with comparable computation accuracy.3. Based on gate and interconnect delay modeling, we propose a Modified Adaptive Stochastic Collocation Method (MASCM) based on the proposed MNSSCM, and apply it to SSTA problem. The proposed MASCM employs an improved adaptive strategy derived from the existing Adaptive Stochastic Collocation Method (ASCM) to approximate the key operator MAX during timing analysis. In contrast to ASCM which uses non-nested sparse grid and tensor product quadratures to approximate the MAX operator for weakly and strongly nonlinear conditions respectively, MASCM proposes a modified nested sparse grid quadrature to approximate the MAX operator for both weakly and strongly nonlinear conditions. Compared with the tensor product quadrature, the modified nested sparse grid quadrature greatly reduced the computational cost, while still maintains sufficient accuracy for the MAX operator approximation. As a result, the proposed MASCM provides comparable accuracy while remarkably reduces the computational cost compared with ASCM. The numerical results show that with comparable accuracy MASCM has 50% reduction in run time compared with ASCM.