Stochastic Collocation With Non-Gaussian Correlated Process Variations: Theory, Algorithms, and Applications

Chunfeng Cui, Zheng Zhang

TL;DR

This paper introduces a novel stochastic collocation method to accurately quantify uncertainties in electronic and photonic systems caused by non-Gaussian, correlated process variations. By developing new basis functions and an optimization-based quadrature rule, the method achieves significant speedups over traditional Monte Carlo simulations while maintaining high accuracy.

What Problem Does This Paper Address?

Manufacturing processes for electronic and photonic integrated circuits are inherently imperfect, leading to variations in device parameters. These variations can significantly impact circuit performance and yield. While existing methods like Monte Carlo simulations can handle these uncertainties, they are computationally expensive. Stochastic spectral methods, particularly polynomial chaos expansions, offer faster alternatives but typically assume that these process variations are either independent or follow a Gaussian distribution. This assumption is often violated in real-world scenarios where parameters can be correlated and exhibit non-Gaussian behavior. Handling these non-Gaussian correlated variations presents a fundamental challenge, especially in defining appropriate basis functions and performing accurate numerical integration (projection) in such complex parameter spaces.

Methods

The paper proposes a two-pronged approach:

  1. New Orthonormal Basis Functions: They introduce a set of smooth orthonormal basis functions designed to capture the effects of non-Gaussian correlated process variations. These are generated using a Gram-Schmidt approach, adapted for functional expectations instead of vector inner products. This allows for analytical or semi-analytical extraction of statistical moments.
  2. Optimization-Based Quadrature Rule: To perform the crucial projection step in stochastic collocation, the authors develop an optimization-based method to determine quadrature nodes and weights. This approach reformulates the problem as a nonlinear least-squares optimization, aiming to accurately estimate integrals of the newly defined basis functions. A block coordinate descent solver is employed to handle the high dimensionality of the problem. To initialize this solver, a weighted complete linkage clustering algorithm is proposed.

Datasets

The paper evaluates its method on several benchmarks:

  • Synthetic Example: A smooth function of two correlated parameters is used to demonstrate the accuracy and convergence rate of the proposed algorithm.
  • 3-Stage CMOS Electronic Ring Oscillator: This benchmark tests the method's ability to quantify uncertainties in a realistic electronic circuit.
  • Parallel Coupled Ring Resonator Optical Filter: This photonic integrated circuit example showcases the method's application to non-Gaussian correlated uncertainties in waveguide lengths and ring parameters.
  • Arrayed Waveguide Grating (AWG): This is another photonic device example used to validate the method's performance with geometric uncertainties.

The paper notes that for general cases, process variations are often described by measurement data, and their joint density function is fitted using density estimators like Gaussian mixtures.

Key Insights and Ideas

  • Breaking the Gaussian/Independence Assumption: The core contribution is a practical framework for handling non-Gaussian correlated uncertainties, a significant limitation of prior work.
  • Optimization for Quadrature: Instead of relying on fixed quadrature rules, optimizing nodes and weights based on the basis functions themselves leads to more accurate and efficient integration.
  • Initialization Matters: The success of the nonlinear optimization for quadrature hinges on a good initial guess, which is addressed by a novel weighted clustering approach on Monte Carlo samples.
  • Theoretical Guarantees: The paper provides theoretical bounds on the number of quadrature samples required and the resulting approximation error, offering confidence in the method's reliability.
  • Near-Exponential Convergence: The proposed method demonstrates a convergence rate that is nearly exponential with respect to the order of the basis functions, a significant improvement over linear convergence often seen in other methods.

Key Results

  • Significant Speedup: The proposed stochastic collocation method achieves speedups of 700x to 6000x compared to Monte Carlo simulations on various practical benchmarks.
  • High Accuracy: The method consistently achieves high accuracy, often matching or exceeding that of Monte Carlo with orders of magnitude fewer simulation samples. For instance, in the synthetic example, 17 quadrature points achieved the same precision as 10^5 Monte Carlo samples.
  • Practical Applicability: The method is demonstrated on realistic electronic (CMOS ring oscillator) and photonic (optical filter, AWG) integrated circuit examples, showing its practical utility.
  • Efficient Sample Usage: The number of quadrature samples required by the proposed method is shown to be close to the theoretical lower bound, indicating efficient use of computational resources.

Limitations and Future Work

  • Minimum Quadrature Samples: While theoretical bounds for the number of quadrature samples are provided, determining the absolute minimum required for a specific accuracy remains an open problem. The authors' experiments suggest the practical number is close to the theoretical lower bound.
  • Non-Smooth Solutions: The theoretical error bounds are derived under the assumption that the stochastic unknown output is "smooth enough." The behavior for highly non-smooth solutions might require further investigation.
  • Optimization Solver: The convergence of the nonlinear optimization for quadrature can be challenging for very high-order basis functions. The authors suggest that developing better nonlinear optimization solvers could further improve the method's performance and reduce the number of quadrature samples needed.
  • Rare Distributions: While the method handles many non-Gaussian distributions, it might not hold for extremely rare cases like log-normal distributions where high-order moments are not bounded.

Summary updated

Abstract

Stochastic spectral methods have achieved a great success in the uncertainty quantification of many engineering problems, including variation-aware electronic and photonic design automation. State-of-the-art techniques employ generalized polynomial-chaos expansions and assume that all random parameters are independent or Gaussian correlated. This assumption is rarely true in real applications. How to handle non-Gaussian correlated random parameters is a long-standing and fundamental challenge: It is not clear how to choose basis functions and to perform a projection step in a correlated uncertain parameter space. This paper first presents a new set of basis functions to well capture the impact of non-Gaussian correlated parameters and then proposes an automatic and optimization-based quadrature method to perform projection-based stochastic collocation with a few simulation samples in the correlated parameter space. We further provide some theoretical proofs for the complexity and error bound of our proposed method. The numerical experiments on several synthetic, electronic, and photonic integrated circuit examples show the nearly exponential convergence rate of our approach and its significant ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$700 \times $ </tex-math></inline-formula> – <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$6000 \times $ </tex-math></inline-formula> ) speedup than Monte Carlo. Many other open problems with non-Gaussian correlated uncertainties can be further solved based on this paper.
BibTeX
@article{cui2018stochastic,
  author = {Chunfeng Cui and Zheng Zhang},
  title = {{Stochastic Collocation With Non-Gaussian Correlated Process Variations: Theory, Algorithms, and Applications}},
  journal = {IEEE Transactions on Components Packaging and Manufacturing Technology},
  year = {2018},
}
Figure