Why quasi-Monte Carlo is better than Monte Carlo or Latin hypercube sampling for statistical circuit analysis

Amith Singhee, Rob A. Rutenbar

Research output: Contribution to journalArticlepeer-review

Abstract

At the nanoscale, no circuit parameters are truly deterministic; most quantities of practical interest present themselves as probability distributions. Thus, Monte Carlo techniques comprise the strategy of choice for statistical circuit analysis. There are many challenges in applying these techniques efficiently: circuit size, nonlinearity, simulation time, and required accuracy often conspire to make Monte Carlo analysis expensive and slow. Are wethe integrated circuit communityalone in facing such problems? As it turns out, the answer is no. Problems in computational finance share many of these characteristics: high dimensionality, profound nonlinearity, stringent accuracy requirements, and expensive sample evaluation. We perform a detailed experimental study of how one celebrated technique from that domainquasi-Monte Carlo (QMC) simulationcan be adapted effectively for fast statistical circuit analysis. In contrast to traditional pseudorandom Monte Carlo sampling, QMC uses a (shorter) sequence of deterministically chosen sample points. We perform rigorous comparisons with both Monte Carlo and Latin hypercube sampling across a set of digital and analog circuits, in 90 and 45 nm technologies, varying in size from 30 to 400 devices. We consistently see superior performance from QMC, giving 2 × to 8× speedup over conventional Monte Carlo for roughly 1% accuracy levels. We present rigorous theoretical arguments that support and explain this superior performance of QMC. The arguments also reveal insights regarding the (low) latent dimensionality of these circuit problems; for example, we observe that over half of the variance in our test circuits is from unidimensional behavior. This analysis provides quantitative support for recent enthusiasm in dimensionality reduction of circuit problems.

Original languageEnglish (US)
Article number5605333
Pages (from-to)1763-1776
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume29
Issue number11
DOIs
StatePublished - Nov 1 2010

Keywords

  • Latin hypercube sampling (LHS)
  • Monte Carlo methods
  • low-discrepancy sequence
  • quasi-Monte Carlo (QMC)
  • statistical circuit analysis

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Why quasi-Monte Carlo is better than Monte Carlo or Latin hypercube sampling for statistical circuit analysis'. Together they form a unique fingerprint.

Cite this