TY - JOUR

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

AU - Singhee, Amith

AU - Rutenbar, Rob A.

N1 - Funding Information:
Manuscript received June 5, 2009; revised January 27, 2010 and May 14, 2010; accepted June 2, 2010. Date of current version October 20, 2010. This work was supported in part by the Semiconductor Research Corporation (SRC), and by C2S2, the Focus Center for Circuit and System Solutions, one of the five research centers funded under the Focus Center Research Program, an SRC program. This paper was recommended by Associate Editor M. Orshansky.

PY - 2010/11

Y1 - 2010/11

N2 - 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.

AB - 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.

KW - Latin hypercube sampling (LHS)

KW - Monte Carlo methods

KW - low-discrepancy sequence

KW - quasi-Monte Carlo (QMC)

KW - statistical circuit analysis

UR - http://www.scopus.com/inward/record.url?scp=77958450831&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77958450831&partnerID=8YFLogxK

U2 - 10.1109/TCAD.2010.2062750

DO - 10.1109/TCAD.2010.2062750

M3 - Article

AN - SCOPUS:77958450831

SN - 0278-0070

VL - 29

SP - 1763

EP - 1776

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 11

M1 - 5605333

ER -