Paper Info
Title
Why Quasi-Monte Carlo is Better Than Monte Carlo or Latin Hypercube Sampling for Statistical Circuit Analysis
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 we-the integrated circuit community-alone 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 domain-quasi-Monte Carlo (QMC) simulation-can 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.
Year
DOI
Venue
2010
10.1109/TCAD.2010.2062750
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions
Keywords
Field
DocType
Monte Carlo methods,network analysis,statistical analysis,Latin hypercube sampling,analog circuits,circuit size,computational finance share,digital circuits,integrated circuit community,pseudorandom Monte Carlo sampling,quasiMonte Carlo simulation,simulation time,size 45 nm,size 90 nm,statistical circuit analysis,Latin hypercube sampling (LHS),Monte Carlo methods,low-discrepancy sequence,quasi-Monte Carlo (QMC),statistical circuit analysis
Statistical physics,Monte Carlo method,Computer science,Quasi-Monte Carlo method,Electronic engineering,Probability distribution,Low-discrepancy sequence,Network analysis,Latin hypercube sampling
Journal
Volume
Issue
ISSN
29
11
0278-0070
Citations 
PageRank 
References 
39
1.64
23
Authors
2
Name
Order
Citations
PageRank
Amith Singhee134722.94
Rob A. Rutenbar22283280.48