SpringerLink

Incluye referencias bibliográficas e índice

Preface; Contents; 1 Introduction; 1.1 Circuit Simulation; 1.1.1 Mathematical Formulation; 1.1.2 LU Factorization; 1.1.3 Simulation Flow; 1.2 Challenges of Parallel Circuit Simulation; 1.2.1 Device Model Evaluation; 1.2.2 Sparse Direct Solver; 1.2.3 Theoretical Speedup; 1.3 Focus of This Book; References; 2 Related Work; 2.1 Direct Parallel Methods; 2.1.1 Parallel Direct Matrix Solutions; 2.1.2 Parallel Iterative Matrix Solutions; 2.2 Domain Decomposition; 2.2.1 Parallel BBD-Form Matrix Solutions; 2.2.2 Parallel Multilevel Newton Methods; 2.2.3 Parallel Schwarz Methods.

2.2.4 Parallel Relaxation Methods2.3 Parallel Time-Domain Simulation; 2.3.1 Parallel Numerical Integration Algorithms; 2.3.2 Parallel Multi-Algorithm Simulation; 2.3.3 Time-Domain Partitioning; 2.3.4 Matrix Exponential Methods; 2.4 Hardware Acceleration Techniques; 2.4.1 GPU Acceleration; 2.4.2 FPGA Acceleration; References; 3 Overall Solver Flow; 3.1 Overall Flow; 3.2 Pre-analysis; 3.2.1 Zero-Free Permutation/Static Pivoting; 3.2.2 Matrix Ordering; 3.2.3 Symbolic Factorization; 3.3 Numerical Full Factorization; 3.3.1 Symbolic Prediction; 3.3.2 Numerical Update; 3.3.3 Partial Pivoting.

3.3.4 Pruning3.4 Numerical Re-factorization; 3.4.1 Factorization Method Selection; 3.5 Right-Hand-Solving; 3.5.1 Forward/Backward Substitutions; 3.5.2 Iterative Refinement; References; 4 Parallel Sparse Left-Looking Algorithm; 4.1 Parallel Full Factorization; 4.1.1 Data Dependence Representation; 4.1.2 Task Scheduling; 4.1.3 Algorithm Flow; 4.1.4 Implementation Details; 4.2 Parallel Re-factorization; 4.2.1 Data Dependence Representation; 4.2.2 Task Scheduling; 4.2.3 Algorithm Flow; 4.2.4 Implementation Details; References; 5 Improvement Techniques; 5.1 Map Algorithm; 5.1.1 Motivation.

5.1.2 Map Definition and Construction5.1.3 Sequential Map Re-factorization; 5.1.4 Parallel Map Re-factorization; 5.2 Supernodal Algorithm; 5.2.1 Motivation; 5.2.2 Supernode Definition and Storage; 5.2.3 Supernodal Full Factorization; 5.2.4 Supernodal Re-factorization; 5.3 Fast Full Factorization; 5.3.1 Motivation and Pivoting Reduction; 5.3.2 Sequential Fast Full Factorization; 5.3.3 Parallel Fast Full Factorization; References; 6 Test Results; 6.1 Experimental Setup; 6.2 Performance Metric; 6.2.1 Speedups; 6.2.2 Performance Profile; 6.3 Results of Benchmark Test.

6.3.1 Comparison of Different Algorithms6.3.2 Relative Speedups; 6.3.3 Speedups; 6.3.4 Other Comparisons; 6.4 Results of Simulation Test; References; 7 Performance Model; 7.1 DAG-Based Performance Model; 7.2 Results and Analysis; 7.2.1 Theoretical Maximum Relative Speedup; 7.2.2 Predicted Relative Speedup; 7.2.3 Bottleneck Analysis; 8 Conclusions; Reference; Index.

This book describes algorithmic methods and parallelization techniques to design a parallel sparse direct solver which is specifically targeted at integrated circuit simulation problems. The authors describe a complete flow and detailed parallel algorithms of the sparse direct solver. They also show how to improve the performance by simple but effective numerical techniques. The sparse direct solver techniques described can be applied to any SPICE-like integrated circuit simulator and have been proven to be high-performance in actual circuit simulation. Readers will benefit from the state-of-the-art parallel integrated circuit simulation techniques described in this book, especially the latest parallel sparse matrix solution techniques. · Introduces complicated algorithms of sparse linear solvers, using concise principles and simple examples, without complex theory or lengthy derivations; · Describes a parallel sparse direct solver that can be adopted to accelerate any SPICE-like integrated circuit simulator and makes circuit simulators more efficient on modern parallel processors; · Uses experimental results from practical applications to demonstrate the performance of the parallel sparse direct solver.