Stochastic spectral methods are efficient techniques for uncertainty quantification. Recently they have shown excellent performance in the statistical analysis of integrated circuits. In stochastic spectral methods, one needs to determine a set of orthonormal polynomials and a proper numerical quadrature rule. The former are used as the basis functions in a generalized polynomial chaos expansion. The latter is used to compute the integrals involved in stochastic spectral methods. Obtaining such information requires knowing the density function of the random input a-priori. However, individual system components are often described by surrogate models rather than density functions. In order to apply stochastic spectral methods in hierarchical uncertainty quantification, we first propose to construct physically consistent closed-form density functions by two monotone interpolation schemes. Then, by exploiting the special forms of the obtained density functions, we determine the generalized polynomial-chaos basis functions and the Gauss quadrature rules that are required by a stochastic spectral simulator. The effectiveness of our proposed algorithm is verified by both synthetic and practical circuit examples.

Uncertainties have become a major concern in integrated circuit design. In order to avoid the huge number of repeated simulations in conventional Monte Carlo flows, this paper presents an intrusive spectral simulator for statistical circuit analysis. Our simulator employs the recently developed generalized polynomial chaos expansion to perform uncertainty quantification of nonlinear transistor circuits with both Gaussian and non-Gaussian random parameters. We modify the nonintrusive stochastic collocation (SC) method and develop an intrusive variant called stochastic testing (ST) method. Compared with the popular intrusive stochastic Galerkin (SG) method, the coupled deterministic equations resulting from our proposed ST method can be solved in a decoupled manner at each time point. At the same time, ST requires fewer samples and allows more flexible time step size controls than directly using a nonintrusive SC solver. These two properties make ST more efficient than SG and than existing SC methods, and more suitable for time-domain circuit simulation. Simulation results of several digital, analog and RF circuits are reported. Since our algorithm is based on generic mathematical models, the proposed ST algorithm can be applied to many other engineering problems.

In this paper we present an efficient algorithm for variation-aware interconnect extraction. The problem we are addressing can be formulated mathematically as the solution of linear systems with matrix coefficients that are dependent on a set of random variables. Our algorithm is based on representing the solution vector as a summation of terms. Each term is a product of an unknown vector in the deterministic space and an unknown direction in the stochastic space. We then formulate a simple nonlinear optimization problem which uncovers sequentially the most relevant directions in the combined deterministic-stochastic space. The complexity of our algorithm scales with the sum (rather than the product) of the sizes of the deterministic and stochastic spaces, hence it is orders of magnitude more efficient than many of the available state of the art techniques. Finally, we validate our algorithm on a variety of onchip and off-chip capacitance and inductance extraction problems, ranging from moderate to very large size, not feasible using any of the available state of the art techniques.

In this paper we present a stochastic model order reduction technique for interconnect extraction in the presence of process variabilities, i.e. variation-aware extraction. It is becoming increasingly evident that sampling based methods for variation-aware extraction are more efficient than more computationally complex techniques such as stochastic Galerkin method or the Neumann expansion. However, one of the remaining computational challenges of sampling based methods is how to simultaneously and efficiently solve the large number of linear systems corresponding to each different sample point. In this paper, we present a stochastic model reduction technique that exploits the similarity among the different solves to reduce the computational complexity of subsequent solves. We first suggest how to build a projection matrix such that the statistical moments and/or the coefficients of the projection of the stochastic vector on some orthogonal polynomials are preserved.We further introduce a proximity measure, which we use to determine apriori if a given system needs to be solved, or if it is instead properly represented using the currently available basis. Finally, in order to reduce the time required for the system assembly, we use the multivariate Hermite expansion to represent the system matrix. We verify our method by solving a variety of variation-aware capacitance extraction problems ranging from on-chip capacitance extraction in the presence of width and thickness variations, to off-chip capacitance extraction in the presence of surface roughness. We further solve very large scale problems that cannot be handled by any other state of the art technique.

Due to technology scaling, integrated circuit manufacturing techniques are producing structures with large variabilities in their dimensions. To guarantee high yield, the manufactured structures must have the proper electrical characteristics despite such geometrical variations. For a designer, this means extracting the electrical characteristics of a whole family of structure realizations in order to guarantee that they all satisfy the required electrical characteristics. Sensitivity extraction provides an efficient algorithm to extract all realizations concurrently. This paper presents a complete framework for efficient resistance sensitivity extraction. The framework is based on both the Finite Element Method (FEM) for resistance extraction and the adjoint method for sensitivity analysis. FEM enables the calculation of resistances of interconnects of arbitrary shapes, while the adjoint method enables sensitivity calculation in a computational complexity that is independent of the number of varying parameters. The accuracy and efficiency of the algorithm are demonstrated on a variety of complex examples.

With the adoption of ultra regular fabric paradigms for controlling design printability at the 22nm node and beyond, there is an emerging need for a layout-driven, pattern-based parasitic extraction of alternative fabric layouts. In this paper, we propose a hierarchical floating random walk (HFRW) algorithm for computing the 3D capacitances of a large number of topologically different layout configurations that are all composed of the same layout motifs. Our algorithm is not a standard hierarchical domain decomposition extension of the well established floating random walk technique, but rather a novel algorithm that employs Markov Transition Matrices. Specifically, unlike the fast-multipole boundary element method and hierarchical domain decomposition (which use a far-field approximation to gain computational efficiency), our proposed algorithm is exact and does not rely on any tradeoff between accuracy and computational efficiency. Instead, it relies on a tradeoff between memory and computational efficiency. Since floating random walk type of algorithms have generally minimal memory requirements, such a tradeoff does not result in any practical limitations. The main practical advantage of the proposed algorithm is its ability to handle a set of layout configurations in a complexity that is basically independent of the set size. For instance, in a large 3D layout example, the capacitance calculation of 120 different configurations made of similar motifs is accomplished in the time required to solve independently just 2 configurations, i.e. a 60x speedup.

Recent CAD methodologies of Design-for-Manufacturability (DFM) have naturally led to a significant increase in the number of process and layout parameters that have to be taken into account in design-rule checking. Methodological consistency requires that a similar number of parameters be taken into account during layout parasitic extraction. Because of the inherent variability of these parameters, the issue of efficiently extracting deterministic parasitic sensitivities with respect to such a large number of parameters must be addressed. In this paper, we tackle this very issue in the context of capacitance sensitivity extraction. In particular, we show how the adjoint sensitivity method can be efficiently integrated within a finite-difference (FD) scheme to compute the sensitivity of the capacitance with respect to a large set of BEOL parameters. If np is the number of parameters, the speedup of the adjoint method is shown to be a factor of np/2 with respect to direct FD sensitivity techniques. The proposed method has been implemented and verified on a 65nm BEOL cross section having 10 metal layers and a total number of 59 parameters. Because of its speed, the method can be advantageously used to prune out of the CAD flow those BEOL parameters that yield a capacitance sensitivity less than a given threshold.

Lithographic limitations and manufacturing uncertainties are resulting in fabricated shapes on wafer that are topologically equivalent, but geometrically different from the corresponding drawn shapes. While first-order sensitivity information can measure the change in pattern parasitics when the shape variations are small, there is still a need for a high-order algorithm that can extract parasitic variations incrementally in the presence of a large number of simultaneous shape variations. This paper proposes such an algorithm based on the wellknown method of floating random walk (FRW). Specifically, we formalize the notion of random path sharing between several conductors undergoing shape perturbations and use it as a basis of a fast capacitance sensitivity extraction algorithm and a fast incremental variational capacitance extraction algorithm. The efficiency of these algorithms is further improved with a novel FRW method for dealing with layered media. Our numerical examples show a 10X speed up with respect to the boundary-element method adjoint or finite-difference sensitivity extraction, and more than 560X speed up with respect to a non-incremental FRW method for a high-order variational extraction.