Singhee / Rutenbar Novel Algorithms for Fast Statistical Analysis of Scaled Circuits

2009
ISBN: 978-90-481-3100-6
Verlag: Springer Netherlands
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 46, 195 Seiten

Reihe: Lecture Notes in Electrical Engineering

As VLSI technology moves to the nanometer scale for transistor feature sizes, the impact of manufacturing imperfections result in large variations in the circuit performance. Traditional CAD tools are not well-equipped to handle this scenario, since they do not model this statistical nature of the circuit parameters and performances, or if they do, the existing techniques tend to be over-simplified or intractably slow. Novel Algorithms for Fast Statistical Analysis of Scaled Circuits draws upon ideas for attacking parallel problems in other technical fields, such as computational finance, machine learning and actuarial risk, and synthesizes them with innovative attacks for the problem domain of integrated circuits. The result is a set of novel solutions to problems of efficient statistical analysis of circuits in the nanometer regime.

Autoren/Hrsg.

Singhee, Amith

Rutenbar, Rob A.

Inhaltsverzeichnis

1;Introduction;7
1.1;Background and Motivation;7
1.2;Major Contributions;9
1.2.1;SiLVR: Nonlinear Response Surface Modeling and Dimensionality Reduction;9
1.2.2;Fast Monte Carlo Simulation Using Quasi-Monte Carlo;10
1.2.3;Statistical Blockade: Estimating Rare Event Statistics, with Application to High Replication Circuits;10
1.3;Preliminaries;11
1.4;Organization;12
2;Contents;13
3; SiLVR: Projection Pursuit for Response Surface Modeling;16
3.1;Motivation;16
3.2;Prevailing Response Surface Models;19
3.2.1;Linear Model;19
3.2.2;Quadratic Model;20
3.2.3;PROjection Based Extraction (PROBE): A Reduced-Rank Quadratic Model;21
3.3;Latent Variables and Ridge Functions;23
3.3.1;Latent Variable Regression;23
3.3.2;Ridge Functions and Projection Pursuit Regression;25
3.4;Approximation Using Ridge Functions: Density and Degree of Approximation;28
3.4.1;Density: What Can Ridge Functions Approximate?;29
3.4.2;Degree of Approximation: How Good Are Ridge Functions?;31
3.5;Projection Pursuit Regression;33
3.5.1;Smoothing and the Bias-Variance Tradeoff;34
3.5.2;Convergence of Projection Pursuit Regression;36
3.6;SiLVR;42
3.6.1;The Model;42
3.6.1.1;Model Complexity;46
3.6.2;On the Convergence of SiLVR;46
3.6.3;Interpreting the SiLVR Model;48
3.6.3.1;Relative Global Sensitivity;49
3.6.3.2;Input-Referred Correlation;50
3.6.4;Training SiLVR;51
3.6.4.1;Initialization Using Spearman's Rank Correlation;52
3.6.4.2;The Levenberg-Marquardt Algorithm;53
3.6.4.3;Bayesian Regularization;56
3.6.4.4;Modified 5-Fold Cross-validation;58
3.7;Experimental Results;59
3.7.1;Master-Slave Flip-Flop with Scan Chain;60
3.7.2;Two-Stage RC-Compensated Op62
3.7.3;Sub-1 V CMOS Bandgap Voltage Reference;67
3.7.3.1;Training Time;69
3.8;Future Work;70
4; Quasi-Monte Carlo for Fast Statistical Simulation of Circuits;73
4.1;Motivation;73
4.2;Standard Monte Carlo;75
4.2.1;The Problem: Bridging Computational Finance and Circuit Design;75
4.2.1.1;Pricing an Asian Option;75
4.2.1.2;Estimating Circuit Yield;77
4.2.1.3;The Canonical Problem;78
4.2.2;Monte Carlo for Numerical Integration: Some Convergence Results;78
4.2.3;Discrepancy: Uniformity and Integration Error;81
4.2.3.1;Variation in the Sense of Hardy and Krause;85
4.3;Low-Discrepancy Sequences;86
4.3.1;(t,m,s)-Nets and (t,s)-Sequences in Base b;86
4.3.2;Constructing Low-Discrepancy Sequences: The Digital Method;90
4.3.2.1;The Van der Corput Sequence: A Building Block;90
4.3.2.2;The Digital Method, Digital Nets and Digital Sequences;92
4.3.2.3;Comparing (t,s)-Sequences and Choosing One;95
4.3.3;The Sobol' Sequence;96
4.3.3.1;Choosing Primitive Polynomials for Good Sobol' Sequences;100
4.3.3.2;Choosing Initial Direction Numbers for Good Sobol' Sequences;100
4.3.3.3;Gray Code Construction;102
4.3.4;Latin Hypercube Sampling;102
4.3.4.1;Construction;103
4.3.4.2;Variance (and Integration Error) Reduction;104
4.3.4.3;LHS Sample Is a Scrambled (t,m,s)-Net;105
4.4;Quasi-Monte Carlo in High Dimensions;106
4.4.1;Effective Dimension of the Integrand;108
4.4.2;Why Is Quasi-Monte Carlo (Sobol' Points) Better Than Latin Hypercube Sampling?;112
4.5;Quasi-Monte Carlo for Circuits;115
4.5.1;The Proposed Flow;115
4.5.2;Estimating Integration Error;117
4.5.2.1;Estimating Monte Carlo Error;117
4.5.2.2;Estimating QMC Error with Scrambled Sequences;118
4.5.3;Scrambled Digital (t,m,s)-Nets and (t,s)-Sequences;120
4.5.3.1;Owen's Scrambling;120
4.5.3.2;Linear Matrix Scrambling: A Simpler Scheme;121
4.5.3.3;Scrambling Sobol' Sequences with Linear Matrix Scrambling;122
4.6;Experimental Results;122
4.6.1;Comparing LHS and QMC (Sobol' Points);123
4.6.1.1;LHS (Almost) Exactly Removes One Dimensional Variance Contribution;123
4.6.1.2;Sobol' Points Are Better Than LHS for Functions with Significant Higher Dimensional Components;125
4.6.2;Experiments on Circuit Benchmarks;127
4.6.2.1;Analysis of Results;130
4.7;Future Work;135
5; Statistical Blockade: Estimating Rare Event Statistics;137
5.1;Motivation;137
5.2;Modeling Rare Event Statistics;140
5.2.1;The Problem;140
5.2.2;Extreme Value Theory: Tail Distributions;142
5.2.3;Tail Regularity Conditions Required for F MDA(Hxi);145
5.2.4;Estimating the Tail: Fitting the GPD to Data;147
5.2.4.1;Maximum Likelihood Estimation;148
5.2.4.2;Moment Matching;149
5.2.4.3;Probability-Weighted Moment Matching;149
5.3;Statistical Blockade;151
5.3.1;Classification;151
5.3.2;Support Vector Classifier;152
5.3.3;The Statistical Blockade Algorithm;156
5.3.3.1;Note on Choosing and Unbiasing the Classifier;158
5.3.4;Experimental Results;159
5.3.4.1;6T SRAM Cell;161
5.3.4.2;64-Bit SRAM Column;163
5.3.4.3;Master-Slave Flip-Flop with Scan Chain;167
5.4;Making Statistical Blockade Practical;169
5.4.1;Conditionals and Disjoint Tail Regions;169
5.4.1.1;The Problem;169
5.4.1.2;The Solution;172
5.4.2;Extremely Rare Events and Statistics;173
5.4.2.1;Extremely Rare Events;173
5.4.2.2;The Reason for Error in the MSFF Tail Model;175
5.4.2.3;The Problem;176
5.4.3;A Recursive Formulation of Statistical Blockade;177
5.4.4;Experimental Results;180
5.5;Future Work;183
6; Concluding Observations;184
7;Appendix A Derivations of Variance Values for Test Functions in Sect. 2.6.1;187
7.1;Variance of fc;187
7.2;One Dimensional Variance of fs;190
8;References;192
9;Index;203