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

Description

The Monte Carlo method is one of the top 10 algorithms in the 20th century. This book is focusing on the Monte Carlo method for solving deterministic partial differential equations (PDEs), especially its application to electronic design automation (EDA) problems. Compared with the traditional method, the Monte Carlo method is more efficient when point values or linear functional of the solution are needed, and has the advantages on scalability, parallelism, and stability of accuracy. This book presents a systematic introduction to the Monte Carlo method for solving major kinds of PDEs, and the detailed explanation of relevant techniques for EDA problems especially the cutting-edge algorithms of random walk based capacitance extraction. It includes about 100 figures and 50 tables, and brings the reader a close look to the newest research results and the sophisticated algorithmic skills in Monte Carlo simulation software. 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