1 Introduction 1
1.1 The Need for Parasitic Extraction 1
1.2 The Methods for RC Extraction and Field Solver 2
1.3 Book Outline 4
1.4 Summary 6
2 Basic Field-Solver Techniques for RC Extraction 7
2.1 Problem Formulation 7
2.2 Overview of the Numerical Methods 10
2.3 Indirect Boundary Element Method 11
2.4 Direct Boundary Element Method 14
2.5 Floating Random Walk Method 16
2.6 Summary 18
3 Fast Boundary Element Methods for Capacitance Extraction(Ⅰ) 19
3.1 Basics of Indirect Boundary Element Methods 19
3.2 Fast Multipole Methods 20
3.2.1 Introduction 20
3.2.2 Multipole Expansions 22
3.2.3 Local Expansions 23
3.2.4 Fast Multipole Algorithm 24
3.3 Low-Rank Matrix Compression-Based Fast Iterative Solvers 26
3.3.1 Why Compression? 26
3.3.2 Matrix Compression Can Reduce the Complexity to Linear 27
3.3.3 Compression Possible? 28
3.3.4 Basics of Matrix Compression Using SVD and QR 30
3.3.5 Compression Without Building Entire Matrix Beforehand 32
3.4 Matrix Compression by Adaptive Cross Approximation 34
3.4.1 Adaptive Cross Approximation(ACA) 35
3.4.2 Recompression of Adaptive Cross Approximation 36
3.5 Summary 37
4 Fast Boundary Element Methods for Capacitance Extraction(Ⅱ) 39
4.1 Direct Boundary Element Method for Multi-dielectric Capacitance Extraction 40
4.2 The Quasi-multiple Medium Approach 43
4.2.1 Basic Idea 43
4.2.2 Decomposition of Dielectrics and Boundary Element Partition 45
4.2.3 Algorithm Description and Analysis 47
4.3 Equation Organization and Solving Techniques 49
4.3.1 Organization of the Coefficient Matrix 49
4.3.2 Extended Jacobi and MN Preconditioners 51
4.4 Numerical Results 54
4.4.1 The Comparison with GIMEI 54
4.4.2 The Comparison with ODDM 55
4.4.3 The Results for Structures from Real Design 57
4.4.4 The Comparison with FastCap 59
4.5 Efficient Techniques for Handling Floating Metal Fills 61
4.5.1 Basic Idea 64
4.5.2 Equation Formation and Solution 65
4.5.3 Numerical Results 66
4.6 Summary 70
5 Resistance Extraction of Complex 3-D Interconnects 71
5.1 Analytical Resistance Formulation 72
5.2 Field Solver for Interconnect Resistance 72
5.2.1 Resistance Network of Multiterminal Regions 73
5.2.2 Resistance Calculation Using Direct BEM 74
5.3 Fast BEM Solver Using Linear Boundary Elements 74
5.3.1 Physics-Based Nonuniform Virtual Cutting 75
5.3.2 Discarding Conductors Not in the Path of Direct Current 80
5.3.3 Dividing Elements Only in One Direction When Possible 80
5.3.4 Linear Boundary Elements for Straight Conductors 81
5.3.5 Efficiency Summary 82
5.4 Analytical QBEM Extraction 83
5.4.1 General Analytical QBEM Algorithm 83
5.4.2 Distinguish Between Regular and Irregular Subregions 84
5.4.3 Compute the Resistance Network of the Whole Region 84
5.4.4 Numerical Result and Analysis 85
5.5 Summary 86
Appendix 5.A 86
6 Substrate Resistance Extraction with Boundary Element Method 91
6.1 Field Solver for Substrate Resistance 92
6.2 Efficient Field-Solver Techniques 95
6.2.1 Nonuniform Meshing 95
6.2.2 Numerical Reduction of Linear Equation System 96
6.2.3 Quasi-multiple Medium Technique to Sparsify Matrix 99
6.3 Numerical Experiments 100
6.3.1 Simple One-Layer Substrate 100
6.3.2 The 52-Contact Structure with Three Doping Profiles 102
6.3.3 Test Structure with Lateral Resistivity Variation 104
6.4 Summary 106
7 Extracting Frequency-Dependent Substrate Parasitics 107
7.1 Field Solver for Substrate Capacitance and Resistance 108
7.2 Direct Boundary Element Method for Substrate Impedance Extraction 109
7.3 The Two-Step Approach 110
7.3.1 Frequency-Dependent Entries in Matrix A 111
7.3.2 Perturbed Equation System and Its Efficient Solution 112
7.4 Efficient Technique for Solving the Real-Valued System 114
7.5 Overall Algorithm Flow and Discussion 115
7.6 Numerical Results 116
7.6.1 Substrate with 52 Contacts 116
7.6.2 More Numerical Experiments 118
7.7 Summary 119
8 Process Variation-Aware Capacitance Extraction 121
8.1 Motivation 121
8.2 The Incremental BEM for Variation-Aware Capacitance Library Building 124
8.2.1 Basic Idea 125
8.2.2 Modification of the Coefficient Matrix and the Solving Technique 126
8.2.3 Numerical Results 127
8.3 Preliminaries of Variation-Aware Statistical Capacitance Extraction 128
8.3.1 Grid-Based Process Variation Model 128
8.3.2 The Hermite Polynomial Collocation Method 130
8.4 Chip-Level Statistical Capacitance Extraction Considering Spatial Correlation 133
8.4.1 Intra-window Capacitance Extraction with the Grid-Based Variation Model 134
8.4.2 Calculation of Inter-window Capacitance Covariance 137
8.4.3 Complexity Analysis of the Inter-window Calculation 139
8.4.4 Statistical Model of Full-Path Capacitance 142
8.5 Experiments of Statistical Capacitance Extraction 144
8.5.1 Simple Cases with Parallel-Line Structure 145
8.5.2 A Large Case with Multilayered Structure 147
8.6 Summary 148
Appendix 8.A.Complete Proof of Theorem 8.3 148
9 Statistical Capacitance Extraction Based on Continuous-Surface Geometric Model 153
9.1 The Continuous-Surface Model for Geometric Variation 154
9.1.1 Three Geometric Variation Models 154
9.1.2 The Reasonable CSV Model for On-Chip Interconnect 156
9.1.3 The Comparison of Three Geometric Variation Models 158
9.2 Efficient Statistical Extraction Techniques 161
9.2.1 The Weighted PFA for Variable Reduction 162
9.2.2 Parallel Statistical Capacitance Extraction 163
9.2.3 Calculating the Inter-window Covariance of Capacitance 165
9.3 Fast Approaches to Model the Line-Edge Roughness 167
9.3.1 Background 167
9.3.2 The Adjoint Field Technique for Sensitivity Calculation 169
9.3.3 Two Efficient Approaches 170
9.3.4 Numerical Results 173
9.3.5 More Analysis Results and Discussion 176
9.4 Summary 177
10 Fast Floating Random Walk Method for Capacitance Extraction 179
10.1 The Basic Floating Random Walk Algorithms 180
10.1.1 Numerical Technique to Calculate Multi-dielectric Surface Green's Function 183
10.2 A Multi-dielectric FRW Algorithm with the Precharacterized Probabilities and Weight Values 184
10.2.1 The Basic Idea 184
10.2.2 The Details of the Precharacterization Procedure 185
10.2.3 The FRW Algorithm with Multi-dielectric GFTs and WVTs 189
10.3 The Techniques for Variance Reduction 190
10.3.1 Background 190
10.3.2 The Importance Sampling with the Weight Values Averaged 192
10.3.3 The Comprehensive Variance Reduction Scheme 195
10.4 The Space Management Technique and Parallel Implementation 198
10.4.1 The Space Management Technique 198
10.4.2 The Parallel Implementation 200
10.5 Numerical Results 201
10.5.1 Test Cases 201
10.5.2 Validating the Multi-dielectric FRW Algorithm 202
10.5.3 Validating the Variance Reduction Techniques 205
10.5.4 Comparing with the Fast Boundary Element Method 205
10.5.5 Validating the Efficiency of Parallel Computing 207
10.6 Summary 208
11 FRW-Based Solver for Chip-Scale Large Structures 209
11.1 Motivation 209
11.2 Basic Operations of Space Management and Accelerating Techniques 210
11.2.1 Basic Operations 211
11.2.2 Improving the Candidate Checking with Distance Limit 212
11.2.3 Incomplete Candidate List 215
11.2.4 Reducing the Time for Inquiring the Candidate List 216
11.3 Space Management Structures and Approaches 218
11.3.1 The Improved Octree-Based Approach 219
11.3.2 Two Grid-Based Approaches 220
11.3.3 The Hybrid Approach Using Grid and Octree 221
11.4 Numerical Results 223
11.4.1 Test Cases 223
11.4.2 Validating the Three Accelerating Techniques 224
11.4.3 Evaluating Different Space Management Approaches 226
11.4.4 RWCap2 with the Hybrid Approach Using Grid and Octree 229
11.4.5 The Results for Multi-dielectric Cases 230
11.5 Summary 231
References 233
Index 243