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 -