PaperlayerView exact revision on arXiv

Source-linked AI summary

Stochastic Testing Method for Transistor-Level Uncertainty Quantification Based on Generalized Polynomial Chaos

Zheng Zhang, Tarek A. El-Moselhy, Ibrahim, M. Elfadel, Luca Daniel

arXiv:1409.4831v1cs.CE

TL;DR

Transistor-level uncertainty quantification is costly because Monte Carlo requires huge numbers of repeated simulations, especially when circuit uncertainties include non-Gaussian variations. The paper develops an intrusive gPC-based stochastic testing simulator that combines fewer testing nodes, decoupled solution, and adaptive time stepping. Across reported circuit simulations, ST is substantially faster than Monte Carlo, SG, and SC, including a 1700× speedup over Monte Carlo in one DC sweep.

  • Problem

    Monte Carlo uncertainty quantification requires thousands to millions of repeated transistor-level simulations, while non-Gaussian variations are not easily handled by existing PC-based tools.

  • Method

    The paper develops an intrusive stochastic testing simulator using generalized polynomial chaos for nonlinear transistor circuits with Gaussian and non-Gaussian random parameters.

  • Results

    ST is reported as hundreds to thousands of times faster than Monte Carlo and tens to hundreds of times faster than SG; one DC sweep achieves a 1700× Monte Carlo speedup.

  • Takeaways & Limitations

    ST combines fewer nodes, adaptive time stepping, and decoupled simulation, making it more efficient than SC and SG for the reported circuit analyses.

Abstract

from arXiv · show

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 to accelerate the numerical simulation. Compared with the stochastic Galerkin (SG) method, the resulting coupled deterministic equations from our proposed ST method can be solved in a decoupled manner at each time point. At the same time, ST uses 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.

I. INTRODUCTION

Transistor-level uncertainty quantification is difficult because circuit uncertainties arise from device and manufacturing variation, while Monte Carlo requires many repeated simulations. The paper proposes intrusive stochastic testing using gPC to address Gaussian and non-Gaussian uncertainties with more efficient simulation.

  • Device-level uncertainties can propagate to circuit and system levels, affecting chip performance and yield.
  • Existing polynomial-chaos spectral methods accelerate uncertainty quantification but have primarily targeted Gaussian parameters and limited EDA applications of gPC.gPC extends spectral methods to non-Gaussian variations, but prior EDA work cited here focused mainly on linear circuits or models.
  • The paper proposes an intrusive gPC-based stochastic testing simulator for transistor-level uncertainty quantification.ST modifies interpolation-based stochastic collocation by using collocation testing to construct a coupled equation, then applying decoupling to accelerate computation.
  • ST uses fewer testing nodes, supports adaptive time stepping, and applies decoupling inside the intrusive solver.These properties distinguish it from mainstream SC and SG approaches for time-domain simulation.
  • The simulator is implemented in a SPICE-type environment with semiconductor device models and is presented as applicable to general engineering problems.The paper states that its mathematical derivation does not make restrictive assumptions in stochastic DAEs.
  • Monte Carlo is inefficient because its slow convergence requires thousands to millions of transistor-level samples and repeated simulations.The excessive sample count can make statistical characterization prohibitively expensive.

B. PC-based SG and SC Methods

Polynomial-chaos methods approximate stochastic circuit responses with orthogonal polynomial expansions and compute their coefficients through intrusive Galerkin or nonintrusive collocation procedures. Generalized polynomial chaos extends this framework to non-Gaussian parameters, under the paper’s assumption of mutually independent random variables.

  • SG substitutes the polynomial expansion into the stochastic equation, applies Galerkin testing, and directly solves a coupled deterministic system of dimension nK.
  • SC selects quadrature or sparse-grid samples, solves the deterministic circuit at each point, and post-processes the solutions to obtain polynomial-chaos coefficients.
  • gPC generalizes Hermite-type PC and efficiently handles Gaussian and non-Gaussian random parameters through distribution-dependent orthonormal polynomials.The univariate basis polynomial is selected according to the probability density of each random variable.
  • A truncated order-p gPC expansion uses K basis functions, whose coefficients can provide the mean and standard deviation of the stochastic state.
  • The method assumes mutually independent random parameters; constructing orthogonal bases for arbitrary probability measures is more involved.

III. STOCHASTIC TESTING SIMULATOR

The stochastic testing simulator represents the stochastic circuit state with multivariate gPC basis functions and replaces the exact solution in the stochastic DAE with a truncated expansion. Its unknowns are the time-dependent gPC coefficients collected into one vector.

  • The stochastic state is represented using indexed multivariate orthonormal gPC basis functions.
  • Replacing the exact stochastic-DAE solution with the truncated gPC expansion produces a residual function for the simulator to solve.
  • The unknown vector X(t) concatenates the K time-dependent gPC coefficient vectors and has dimension N = nK.

A. Basic Idea of the ST Method

ST enforces the residual at selected testing points to form an intrusive deterministic DAE, then exploits Jacobian structure to decouple its solution at each time point. This directly computes gPC coefficients while supporting adaptive time stepping and efficient linear solves.

  • A. Basic Idea of the ST Method: ST selects K testing points and enforces the residual function to zero at each point, producing a larger deterministic DAE.The resulting equation is formed by collocation testing from the gPC-based formulation.
  • A. Basic Idea of the ST Method: ST passes the coupled DAE to a specialized transient solver that directly computes gPC coefficients and exploits matrix structures inside Newton iterations.Backward-Euler integration is demonstrated, with Trapezoidal and Gear-2 schemes implemented similarly.
  • A. Basic Idea of the ST Method: Adaptive time stepping accepts a solution when local truncation error is below a threshold and reduces the step size otherwise; decoupled evaluations also permit parallel implementation.The state is recomputed after a rejected step.
  • A. Basic Idea of the ST Method: For a CMOS LNA with n=14, l=p=3 and K=20, the Jacobian has nonzero off-diagonal blocks, making direct solution of the coupled system inefficient.The direct linear-system cost is O(N^3) = O(K^3n^3), while iterative solution costs m̂O(K^2n).
  • A. Basic Idea of the ST Method: ST rewrites the coupled Jacobian and solves the resulting linear equation in a decoupled manner using its block-diagonal structure.The inverse of the Vandermonde-like matrix is computed once and reused at all time points.
  • A. Basic Idea of the ST Method: The decoupled solve gives ST only linear dependence on K, contrasting with cubic or quadratic dependence when the coupled linear equation is solved directly.After independent block solves, a sparse matrix-vector product costs O(nK).

C. Testing Node Selection

ST constructs a large candidate set with Gaussian-quadrature tensor products, then retains only K testing nodes, where K is much smaller than the candidate count.

  • C. Testing Node Selection: ST generates (p+1)^l candidate nodes using a Gaussian-quadrature tensor product rule.The candidate set is built from one-dimensional quadrature nodes and weights.
  • C. Testing Node Selection: Only K nodes are selected from the candidate nodes as final testing points, with K ≪ (p+1)^l.The earlier method in uses all (p+1)^l sampling nodes, which are ST's candidates.
  • C. Testing Node Selection: Gaussian quadrature evaluates a one-dimensional stochastic integral using a random parameter, its probability density function, quadrature points, and weights.Multidimensional nodes are then formed through tensor products.

1) Candidate Node Generation:

Candidate nodes are generated from one-dimensional Gaussian quadrature and combined into a tensor-product grid in the multidimensional stochastic space.

  • 1) Candidate Node Generation:: Gaussian quadrature uses the support Ω_k and PDF ρ_k(ξ_k) to determine a quadrature rule for each random parameter.The quadrature rule supplies points and corresponding weights.
  • 1) Candidate Node Generation:: The one-dimensional quadrature points and weights are combined through a tensor product to evaluate multivariate stochastic integrals.Tensor products or sparse grids can construct multidimensional quadrature points.
  • 1) Candidate Node Generation:: With n̂=p+1, the tensor-product construction produces N̂=n̂^l quadrature nodes and an index matrix I for the l-dimensional stochastic space.Each index identifies a quadrature point in the corresponding one-dimensional support.
  • 1) Candidate Node Generation:: Algorithm 1 constructs the candidate quadrature nodes and weights before selecting the final testing nodes.The algorithm begins by constructing N̂ l-D Gaussian quadrature nodes and weights.

2) Selecting Testing Nodes:

Testing-node selection balances statistical importance with numerical stability: high-weight candidates are preferred, but nodes are retained only when they improve the testing basis.

  • 2) Selecting Testing Nodes:: Candidates are prioritized by large absolute weights, while the matrix Φ must remain full-rank and well conditioned.These criteria jointly favor statistically important and numerically stable testing sets.
  • 2) Selecting Testing Nodes:: Algorithm 1 reorders candidates from largest to smallest absolute weight and selects the first node before considering the remaining candidates.The threshold β controls the selection procedure.
  • 2) Selecting Testing Nodes:: A candidate is added only when its vector H has a sufficiently large component orthogonal to the span of previously selected testing vectors.Adding such a node increases the dimensionality of the spanned vector space.
  • 2) Selecting Testing Nodes:: When l is large, candidates and the index matrix can be generated implicitly by ordering weights and constructing each needed candidate on demand.Candidates failing the orthogonality test are omitted and not stored.
  • 2) Selecting Testing Nodes:: Optimal testing-node selection remains an open problem, although Leja sequences provide another possible construction based on a greedy approximation to Fekete nodes.The paper identifies multiple possible selection strategies rather than a settled optimum.

A. Comparison with Stochastic Galerkin (SG) Method

Stochastic Galerkin and stochastic testing produce intrusive coupled systems of the same dimension, but SG is substantially more expensive. Its costs arise from multivariate stochastic integration and an inseparable Jacobian, whereas ST enables decoupled solution.

  • Numerical quadrature or Monte Carlo integration can be used to obtain the stochastic inner products required by SG.
  • SG and ST are both intrusive methods with coupled deterministic equations of the same dimension, but SG is much more expensive.
  • SG evaluates multivariate stochastic integrals at many quadrature or sampling nodes, making semiconductor device-model evaluations costly.Each BISM3 evaluation can involve tens of thousands of lines of code.
  • SG's Jacobian cannot be decoupled, so direct solution requires O(N^3) = O(K^3n^3) at each time point.An iterative solver still has cost proportional to m̂O(K^2n) when m̂ iterations are used.

1) SC for Nonlinear Circuits:

SC reconstructs generalized polynomial-chaos coefficients from deterministic simulations at selected sampling points, but requires common time grids for transient waveforms. ST and SG compute coefficients directly through coupled formulations, while ST combines decoupling and adaptive stepping for greater efficiency.

  • For transient waveform reconstruction, SC’s fixed-step requirement can cause excessive cost, while interpolation between adaptive solutions can produce inaccurate higher-order coefficients.
  • SC solves deterministic equations at selected samples and reconstructs gPC coefficients afterward through numerical integration.
  • SG and ST directly compute gPC coefficients by simulating one larger coupled deterministic DAE.
  • ST uses decoupled simulation and adaptive time stepping, making it more efficient than SC and SG.SC typically requires the same time grid for every deterministic DAE when reconstructing time-domain coefficients.
  • In the common-source amplifier study, order-3 ST used 35 basis functions and 35 testing nodes selected from 256 candidates, matching Monte Carlo accuracy.

1) ST versus MC:

Across circuit experiments, ST matches reference statistical or spectral results while substantially reducing computational cost. The reported gains arise from using fewer nodes, decoupled computation, and adaptive time stepping, including for nonlinear circuits with non-Gaussian parameters.

  • 0.928 mW expected power dissipation and 22.07 µW standard deviation were obtained by both ST and Monte Carlo at Vin = 1.4V.
  • 1700× speedup was achieved for the common-source amplifier DC sweep: ST required 5.4 seconds versus 2.6 hours for Monte Carlo.
  • ST’s gPC-coefficient error decreased below 10^-4 at order p = 3, while ST, SC, and SG all converged rapidly as order increased.
  • 29× speedup was reported for transient common-source-amplifier simulation, although SC used about 7× as many nodes as ST.Adaptive time stepping contributed an additional speedup factor of about 4.
  • For the LNA, ST had nearly the same accuracy as SC and SG in DC analysis and required the smallest CPU time.
  • 56 seconds versus 26 minutes yielded a 28× speed advantage for ST over SG in the LNA transient analysis, with indistinguishable first-four-cycle waveforms.

C. 6-T SRAM Cell

The paper applies stochastic testing to transistor-level uncertainty analysis across digital, analog, and RF circuits. In the SRAM example, device mismatch affects transient waveforms, while the amplifier and mixer examples demonstrate uncertainty analysis with substantially lower simulation cost than conventional alternatives.

  • 6-T SRAM Cell: Gaussian variations in SRAM transistor gate widths are used to study uncertainty in transient waveforms for power and timing analysis.The analysis concerns a 6-T SRAM cell and excludes rare failure events.
  • 6-T SRAM Cell: 35 testing nodes are selected from 256 candidates for the SRAM transient simulation.The method uses p = 3 and examines uncertainties during [0, 1]µs.
  • 6-T SRAM Cell: 6 minutes of ST simulation replaces several hours with SG for the SRAM cell, while SC and MC are prohibitively expensive under sharp state transitions.SC and MC require a very small uniform step size in this case.
  • BJT Feedback Amplifier: 20 testing nodes selected from 64 candidates achieve similar accuracy to MC using 105 samples for the BJT feedback amplifier.The amplifier includes Gamma-type resistor uncertainties and Gaussian temperature uncertainty.
  • BJT Feedback Amplifier: ST and MC produce indistinguishable transfer-function error bars and signal-gain PDFs, while simulation times are 3.6 seconds and over 2000 seconds, respectively.The PDF comparison is reported at f = 8697.49 Hz.
  • BJT Double-Balanced Mixer: For the double-balanced mixer, ST uses 10 testing nodes from 16 candidates, while SG, SC, and MC are prohibitively expensive for the multi-rate RF simulation.The mixer output uncertainty is measured for Vout1 − Vout2.

F. Discussion: Speedup Factor of ST over SC

The paper compares ST with tensor-product and sparse-grid stochastic collocation methods. ST benefits from fewer testing nodes and, in transient analysis, additional speedup from adaptive time stepping, especially for digital and multi-rate RF circuits.

  • Node Selection: SC-TP uses (p + 1)^l nodes, whereas ST selects K testing nodes; SC-SP requires a level-p+1 sparse grid for p-th-order coefficients.The comparison uses tensor-product and Fejér nested sparse-grid constructions.
  • DC Analysis: In DC analysis, ST’s speedup over SC equals NSC/K because both methods use decoupled solvers with costs linear in node count.NSC and K denote the numbers of SC and ST nodes, respectively.
  • DC Analysis: For p ≤ 3, ST’s speedup over SC-SP is below 10; for p ≥ 4, it can exceed 10 and increases with p.ST is more efficient because it uses the smallest number of nodes.
  • Transient Simulation: Transient ST speedup exceeds the DC speedup because adaptive time stepping contributes an additional factor κ.κ is case dependent and can be significantly large for digital cells and multi-rate RF circuits, where SC may require small uniform steps.
  • Transient Simulation: ST directly solves the coupled DAE and computes gPC coefficients while retaining adaptive step-size control.This contrasts with nonintrusive solvers that use larger sampling-node sets.
  • Overall Comparison: ST is reported to be hundreds to thousands of times faster than Monte Carlo while handling Gaussian and non-Gaussian variations.The paper attributes this result to decoupled simulation, adaptive step sizes, and avoidance of multivariate integration.
Loading 1409.4831v1…