Monte Carlo Methods for Partial Differential Equations With Applications to Electronic Design Automation

Preface
Acknowledgements
Contents
1 Introduction
1.1 Motivation
1.2 Monte Carlo Method
1.3 Simulation Problems in Electronic Design Automation
1.4 Book Outline
1.5 Summary
References
2 Monte Carlo Method for Solving PDE
2.1 Preliminaries
2.2 Discrete Random Walk Method
2.2.1 DRW Method for Circuit Simulation
2.2.2 Analysis with Markov Chain Theory
2.2.3 More Applications
2.3 Floating Random Walk Method
2.3.1 Walk on Spheres Method for Potential Computation
2.3.2 Analysis with Probabilistic Potential Theory
2.3.3 Floating Random Walk Method and Applications
2.4 Summary
References
3 A Monte Carlo Algorithm for Solving the Telegrapher's Equations
3.1 Motivation
3.2 Problem Formulation and Related Work
3.2.1 Problem Formulation
3.2.2 The Kac's Stochastic Model and the NMC Method in ch3acebron2016
3.3 The Kac's Model Based Monte Carlo Algorithm
3.3.1 Monte Carlo Algorithm Derived from Kac's Stochastic Model
3.3.2 Application to Problems in Higher Dimensions or on Bounded Domains
3.4 Numerical Results
3.4.1 1-D Examples
3.4.2 2-D Examples
3.5 Summary
References
4 Basics of Floating Random Walk Method for Capacitance Extraction of VLSI Interconnects
4.1 Background
4.2 Preliminaries
4.3 Sampling on the Gaussian Surface for a Complex Net
4.3.1 Motivation
4.3.2 A Virtual Gaussian Surface Sampling Approach
4.3.3 Optimize the Placement of Gaussian Surface
4.4 Parallel Space Management
4.4.1 The Pruning Skills for Judging Domination Relationships
4.4.2 Parallel Construction of the Octree
4.5 Experimental Results
4.5.1 Validate the VGSS Technique and Optimized Parameters
4.5.2 Validate the Improved Octree Construction Algorithm
4.5.3 Results of Full-Chip Capacitance Extraction
4.6 Summary
References
5 Pre-Characterization Techniques for the FRW Based Capacitance Extraction and Simulation
5.1 Motivation
5.2 The Basics of Dielectric Pre-Characterization
5.2.1 Numerical Technique to Calculate Multi-Dielectric Surface Green’s Function and Weight Value
5.2.2 The Dielectric Homogenization Pre-Characterization Method
5.3 Improving the FRW Algorithm Through Pre-Characterizing the Transition Cube with Three-Layer or Four-Layer Dielectrics
5.3.1 The Idea and Pre-Characterization Procedure
5.3.2 Usage of the Pre-Characterized GFTs and WVTs
5.3.3 The Improved FRW Algorithm
5.3.4 Numerical Results
5.4 A Unified Dielectric Pre-Characterization Method
5.4.1 Discussion of Existing Approaches
5.4.2 The Unified Dielectric Pre-Characterization Scheme
5.4.3 Experimental Results
5.5 Summary
References
6 FRW Based Techniques for Handling Cylindrical Inter-Tier-Vias
6.1 Motivation
6.2 Background
6.2.1 Modeling of ITV Capacitances in 3-D ICs
6.2.2 Review of the Floating Random Walk Method
6.2.3 Variance Reduction Techniques for the FRW Method
6.3 FRW Based Techniques for Extracting the Capacitances of Structure with Cylindrical ITVs
6.3.1 Walk with Manhattan Transition Cubes
6.3.2 Walk with Rotated Transition Cubes
6.3.3 Reduce the Time for Each Hop
6.3.4 Algorithm Flow and Discussions
6.4 Accelerating the FRW Procedure for Structures with TSVs
6.4.1 The Construction of Gaussian Surface Around a TSV
6.4.2 The Optimized Importance Sampling Scheme
6.5 The Application to the Sign-Off Verification
6.6 Numerical Results
6.6.1 Results for Small and Medium Cases
6.6.2 Results for Large Cases
6.6.3 The Acceleration for the TSV Cases
6.6.4 Results for Multi-Dielectric Cases
6.7 Summary
References
7 FRW Based Techniques for Handling Non-Manhattan Conductors
7.1 Motivation
7.2 Background
7.2.1 Review of the FRW Algorithm for Capacitance Extraction
7.2.2 Space Management Techniques for Manhattan Structure
7.3 Efficient Techniques for Handling Non-manhattan Conductors
7.3.1 Basic Considerations and Distance Calculation
7.3.2 The Generation of Gaussian Surface
7.3.3 The Algorithm Using Manhattan Transition Cube
7.3.4 The Algorithm Using Rotated Transition Cube
7.4 Numerical Results
7.4.1 Test Cases
7.4.2 Results of Algorithms Using Manhattan Transition Cube
7.4.3 Results of Algorithms Using Rotated Transition Cube
7.4.4 Further Accuracy and Efficiency Validation
7.4.5 Results of Multi-Dielectric Cases
7.5 Summary
References
8 An Approach to Handle General-Shape Floating Metals
8.1 Motivation
8.2 Background
8.2.1 The FRW Algorithm for 3-D Capacitance Extraction
8.2.2 The FRW Technique Considering Floating Dummy-Fills
8.3 The Approach Considering General-Shape Floating Metals
8.3.1 An Approach Based on the Central Difference Formula
8.3.2 Handling Multi-Rectangle Floating Metals
8.3.3 Considering Multi-Dielectric Environment and More
8.4 Numerical Results
8.4.1 Results on Cases with Floating Dummy Fills
8.4.2 Results on Cases of MIM Capacitor
8.5 Summary
References
9 Macromodel-Aware Random Walk Method for Capacitance Extraction
9.1 Motivation
9.2 Preliminaries
9.2.1 The Floating Random Walk Method
9.2.2 Building Macromodel for a Substructure with BEM
9.2.3 Markov Chain Based Random Walk
9.3 Macromodel-Aware Random Walk Algorithm
9.3.1 The Random Walk Scheme with Patch Regions
9.3.2 Algorithm Description and More Details
9.3.3 Application to Capacitance Extraction Problems
9.4 FDM Based Technique for Building the Macromodel
9.4.1 Basic Method
9.4.2 Reliability of the Macromodel Generated with FDM
9.4.3 A Modified FDM for Generating Reliable Macromodel
9.5 Numerical Results
9.5.1 Results on the Macromodel-Aware FRW Algorithm
9.5.2 Results Validating the FDM Based Macromodel Generation
9.6 Summary
9.7 Proof of Theorem 9.2
References
10 GPU-Friendly FRW Algorithms for Electrostatic Computation Problems
10.1 Motivation
10.2 Background
10.2.1 Review of the FRW Algorithm
10.2.2 GPU Architecture and CUDA
10.3 Accelerating the FRW Algorithm on GPUs
10.3.1 Task Dividing and the Iterative FRW Flow
10.3.2 Exclusive Memory Space and Extra Start Points
10.3.3 Hop with the Inverse Cumulative Probability Array
10.4 Techniques for Multi-Dielectric Capacitance Extraction
10.4.1 The Challenge for the Multi-Dielectric Problem
10.4.2 The Usage of a Variant FRW Scheme
10.4.3 Concurrent Extraction of Multiple Nets
10.5 Numerical Results
10.5.1 Smaller Cases Within Homogeneous Dielectric
10.5.2 Larger Cases Within Homogeneous Dielectric
10.5.3 Results for Multi-Dielectric Cases
10.5.4 Concurrent Extraction of Multiple Nets
10.6 Summary
References
11 Distributed Parallel FRW Algorithms for Capacitance Simulation
11.1 Motivation
11.2 Preliminaries
11.3 Distributed Parallel Random Walk Procedure
11.4 Distributed Parallel Space Management
11.5 Techniques to Realize the Numerical Reproducibility
11.5.1 An Approach Including Synchronization with Barrier
11.5.2 The Approach with Accuracy Criteria Allocation
11.6 Experimental Results
11.6.1 Distributed Computing with Cases from Touchscreeen Design
11.6.2 Distributed Computing with Cases from VLSI Design
11.6.3 Experiments on Reproducibility
11.7 Summary
References
12 A Hybrid Random Walk Algorithm for 3-D Thermal Analysis
12.1 Motivation
12.2 The Thermal Model and Related Work
12.2.1 3-D Thermal Model
12.2.2 The Random Walk Method
12.3 A Hybrid Random Walk Algorithm
12.3.1 The Basic Idea
12.3.2 Scalable Transition Domain and Its Characterization
12.3.3 Handling the Neumann and Convective Boundaries
12.4 Numerical Results
12.4.1 Test Cases
12.4.2 Efficiency and Accuracy Validation
12.5 Summary
References