Hardware Acceleration of EDA Algorithms

by Gulati, Kanupriya; Khatri, Sunil P.

• ISBN13: 9781441909435
• ISBN10: 1441909435
• Edition: 1st
• Format: Hardcover
• Copyright: 2010-04-03
• Publisher: Springer Verlag

Summary

This book deals with the acceleration of EDA algorithms using hardware platforms such as FPGAs and GPUs. Widely applied CAD algorithms are evaluated and compared for potential acceleration on FPGAs and GPUs. Coverage includes discussion of conditions under which it is preferable to use one platform over another, e.g., when an EDA problem has a high degree of data parallelism, the GPU is typically the preferred platform, whereas when the problem has more control, an FPGA may be preferred. Results are presented for the acceleration of several CAD algorithms (fault simulation, fault table generation, model card evaluation in SPICE, Monte Carlo statistical static timing analysis), demonstrating speedups from 30X to 800X. This book serves as a valuable guide on how best to leverage parallelism to accelerate CAD algorithms. It also presents a methodology to extract automatically SIMD parallelism from regular uniprocessor code. With this approach, uniprocessor code can automatically be converted to GPU code, allowing for significant acceleration. This approach is particularly useful, since different GPUs have vastly different specifications, making the manual generation of GPU code an unscalable proposition.

Table of Contents

Introduction	p. 1
Hardware Platforms Considered in This Research Monograph	p. 3
EDA Algorithms Studied in This Research Monograph	p. 3
Control-Dominated Applications	p. 4
Control Plus Data Parallel Applications	p. 4
Automated Approach for GPU-Based Software Acceleration	p. 4
Chapter Summary	p. 4
References	p. 5
Alternative Hardware Platforms
Hardware Platforms	p. 9
Chapter Overview	p. 9
Introduction	p. 9
Hardware Platforms Studied in This Research Monograph	p. 10
Custom ICs	p. 10
FPGAs	p. 10
Graphics Processors	p. 10
General Overview and Architecture	p. 11
Programming Model and Environment	p. 14
Scalability	p. 15
Design Turn-Around Time	p. 16
Performance	p. 16
Cost of Hardware	p. 18
Floating Point Operations	p. 18
Security and Real-Time Applications	p. 19
Applications	p. 19
Chapter Summary	p. 20
References	p. 20
GPU Architecture and the CUDA Programming Model	p. 23
Chapter Overview	p. 23
Introduction	p. 23
Hardware Model	p. 24
Memory Model	p. 25
Programming Model	p. 28
Chapter Summary	p. 30
References	p. 30
Control-Dominated Category
Accelerating Boolean Satisfiability on a Custom IC	p. 33
Chapter Overview	p. 33
Introduction	p. 34
Previous Work	p. 36
Hardware Architecture	p. 37
Abstract Overview	p. 37
Hardware Overview	p. 38
Hardware Details	p. 39
An Example of Conflict Clause Generation	p. 50
Partitioning the CNF Instance	p. 51
Extraction of the Unsatisfiable Core	p. 53
Experimental Results	p. 54
Chapter Summary	p. 59
References	p. 59
Accelerating Boolean Satisfiability on an FPGA	p. 63
Chapter Overview	p. 63
Introduction	p. 64
Previous Work	p. 64
Hardware Architecture	p. 66
Architecture Overview	p. 66
Solving a CNF Instance Which Is Partitioned into Several Bins	p. 67
Partitioning the CNF Instance	p. 69
Hardware Details	p. 70
Experimental Results	p. 72
Current Implementation	p. 72
Performance Model	p. 73
Projection	p. 77
Chapter Summary	p. 80
References	p. 80
Accelerating Boolean Satisfiability on a Graphics Processing Unit	p. 83
Chapter Overview	p. 83
Introduction	p. 83
Related Previous Work	p. 85
Our Approach	p. 87
SurveySAT and the GPU	p. 87
MiniSAT Enhanced with Survey Propagation (MESP)	p. 93
Experimental Results	p. 96
Chapter Summary	p. 98
References	p. 98
Control Plus Data Parallel Applications
Accelerating Statistical Static Timing Analysis Using Graphics Processors	p. 105
Chapter Overview	p. 105
Introduction	p. 106
Previous Work	p. 108
Our Approach	p. 109
Static Timing Analysis (STA) at a Gate	p. 109
Statistical Static Timing Analysis (SSTA) at a Gate	p. 112
Experimental Results	p. 113
Chapter Summary	p. 116
References	p. 116
Accelerating Fault Simulation Using Graphics Processors	p. 119
Chapter Overview	p. 119
Introduction	p. 199
Previous Work	p. 121
Our Approach	p. 122
Logic Simulation at a Gate	p. 123
Fault Injection at a Gate	p. 125
Fault Detection at a Gate	p. 126
Fault Simulation of a Circuit	p. 127
Experimental Results	p. 129
Chapter Summary	p. 131
References	p. 131
Fault Table Generation Using Graphics Processors	p. 133
Chapter Overview	p. 133
Introduction	p. 134
Previous Work	p. 136
Our Approach	p. 136
Definitions	p. 137
Algorithms: FSIM* and GFTABLE	p. 139
Experimental Results	p. 146
Chapter Summary	p. 150
References	p. 151
Accelerating Circuit Simulation Using Graphics Processors	p. 153
Chapter Overview	p. 153
Introduction	p. 153
Previous Work	p. 155
Our Approach	p. 157
Parallelizing BSIM3 Model Computations on a GPU	p. 158
Experiments	p. 162
Chapter Summary	p. 165
References	p. 165
Automated Generation of GPU Code
Automated Approach for Graphics Processor Based Software Acceleration	p. 169
Chapter Overview	p. 169
Introduction	p. 169
Our Approach	p. 171
Problem Definition	p. 171
GPU Constraints on the Kernel Generation Engine	p. 172
Automatic Kernel Generation Engine	p. 173
Experimental Results	p. 176
Evaluation Methodology	p. 177
Chapter Summary	p. 179
References	p. 179
Conclusions	p. 181
References	p. 187
Index	p. 189
Table of Contents provided by Ingram. All Rights Reserved.