Novel Algorithms for Fast Statistical Analysis of Scaled Circuits (eBook)

Introduction 7
Background and Motivation 7
Major Contributions 9
SiLVR: Nonlinear Response Surface Modeling and Dimensionality Reduction 9
Fast Monte Carlo Simulation Using Quasi-Monte Carlo 10
Statistical Blockade: Estimating Rare Event Statistics, with Application to High Replication Circuits 10
Preliminaries 11
Organization 12
Contents 13
SiLVR: Projection Pursuit for Response Surface Modeling 16
Motivation 16
Prevailing Response Surface Models 19
Linear Model 19
Quadratic Model 20
PROjection Based Extraction (PROBE): A Reduced-Rank Quadratic Model 21
Latent Variables and Ridge Functions 23
Latent Variable Regression 23
Ridge Functions and Projection Pursuit Regression 25
Approximation Using Ridge Functions: Density and Degree of Approximation 28
Density: What Can Ridge Functions Approximate? 29
Degree of Approximation: How Good Are Ridge Functions? 31
Projection Pursuit Regression 33
Smoothing and the Bias-Variance Tradeoff 34
Convergence of Projection Pursuit Regression 36
SiLVR 42
The Model 42
Model Complexity 46
On the Convergence of SiLVR 46
Interpreting the SiLVR Model 48
Relative Global Sensitivity 49
Input-Referred Correlation 50
Training SiLVR 51
Initialization Using Spearman's Rank Correlation 52
The Levenberg-Marquardt Algorithm 53
Bayesian Regularization 56
Modified 5-Fold Cross-validation 58
Experimental Results 59
Master-Slave Flip-Flop with Scan Chain 60
Two-Stage RC-Compensated Opamp 62
Sub-1 V CMOS Bandgap Voltage Reference 67
Training Time 69
Future Work 70
Quasi-Monte Carlo for Fast Statistical Simulation of Circuits 73
Motivation 73
Standard Monte Carlo 75
The Problem: Bridging Computational Finance and Circuit Design 75
Pricing an Asian Option 75
Estimating Circuit Yield 77
The Canonical Problem 78
Monte Carlo for Numerical Integration: Some Convergence Results 78
Discrepancy: Uniformity and Integration Error 81
Variation in the Sense of Hardy and Krause 85
Low-Discrepancy Sequences 86
(t,m,s)-Nets and (t,s)-Sequences in Base b 86
Constructing Low-Discrepancy Sequences: The Digital Method 90
The Van der Corput Sequence: A Building Block 90
The Digital Method, Digital Nets and Digital Sequences 92
Comparing (t,s)-Sequences and Choosing One 95
The Sobol' Sequence 96
Choosing Primitive Polynomials for Good Sobol' Sequences 100
Choosing Initial Direction Numbers for Good Sobol' Sequences 100
Gray Code Construction 102
Latin Hypercube Sampling 102
Construction 103
Variance (and Integration Error) Reduction 104
LHS Sample Is a Scrambled (t,m,s)-Net 105
Quasi-Monte Carlo in High Dimensions 106
Effective Dimension of the Integrand 108
Why Is Quasi-Monte Carlo (Sobol' Points) Better Than Latin Hypercube Sampling? 112
Quasi-Monte Carlo for Circuits 115
The Proposed Flow 115
Estimating Integration Error 117
Estimating Monte Carlo Error 117
Estimating QMC Error with Scrambled Sequences 118
Scrambled Digital (t,m,s)-Nets and (t,s)-Sequences 120
Owen's Scrambling 120
Linear Matrix Scrambling: A Simpler Scheme 121
Scrambling Sobol' Sequences with Linear Matrix Scrambling 122
Experimental Results 122
Comparing LHS and QMC (Sobol' Points) 123
LHS (Almost) Exactly Removes One Dimensional Variance Contribution 123
Sobol' Points Are Better Than LHS for Functions with Significant Higher Dimensional Components 125
Experiments on Circuit Benchmarks 127
Analysis of Results 130
Future Work 135
Statistical Blockade: Estimating Rare Event Statistics 137
Motivation 137
Modeling Rare Event Statistics 140
The Problem 140
Extreme Value Theory: Tail Distributions 142
Tail Regularity Conditions Required for F MDA(Hxi) 145
Estimating the Tail: Fitting the GPD to Data 147
Maximum Likelihood Estimation 148
Moment Matching 149
Probability-Weighted Moment Matching 149
Statistical Blockade 151
Classification 151
Support Vector Classifier 152
The Statistical Blockade Algorithm 156
Note on Choosing and Unbiasing the Classifier 158
Experimental Results 159
6T SRAM Cell 161
64-Bit SRAM Column 163
Master-Slave Flip-Flop with Scan Chain 167
Making Statistical Blockade Practical 169
Conditionals and Disjoint Tail Regions 169
The Problem 169
The Solution 172
Extremely Rare Events and Statistics 173
Extremely Rare Events 173
The Reason for Error in the MSFF Tail Model 175
The Problem 176
A Recursive Formulation of Statistical Blockade 177
Experimental Results 180
Future Work 183
Concluding Observations 184
Appendix A Derivations of Variance Values for Test Functions in Sect. 2.6.1 187
Variance of fc 187
One Dimensional Variance of fs 190
References 192
Index 203