Khatri / Gulati Hardware Acceleration of EDA Algorithms

Custom ICs, FPGAs and GPUs
1. Auflage 2010
ISBN: 978-1-4419-0944-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 192 Seiten

Single-threaded software applications have ceased to see signi?cant gains in p- formance on a general-purpose CPU, even with further scaling in very large scale integration (VLSI) technology. This is a signi?cant problem for electronic design automation (EDA) applications, since the design complexity of VLSI integrated circuits (ICs) is continuously growing. In this research monograph, we evaluate custom ICs, ?eld-programmable gate arrays (FPGAs), and graphics processors as platforms for accelerating EDA algorithms, instead of the general-purpose sing- threaded CPU. We study applications which are used in key time-consuming steps of the VLSI design ?ow. Further, these applications also have different degrees of inherent parallelism in them. We study both control-dominated EDA applications and control plus data parallel EDA applications. We accelerate these applications on these different hardware platforms. We also present an automated approach for accelerating certain uniprocessor applications on a graphics processor. This monograph compares custom ICs, FPGAs, and graphics processing units (GPUs) as potential platforms to accelerate EDA algorithms. It also provides details of the programming model used for interfacing with the GPUs.

Autoren/Hrsg.

Khatri, Sunil P

Gulati, Kanupriya

Inhaltsverzeichnis

1;Foreword;8
2;Preface;10
3;Acknowledgments;14
4;Contents;16
5;List of Tables;20
6;List of Figures;22
7;1 Introduction;24
7.1;1.1 Hardware Platforms Considered in This Research Monograph;26
7.2;1.2 EDA Algorithms Studied in This Research Monograph;26
7.2.1;1.2.1 Control-Dominated Applications;27
7.2.2;1.2.2 Control Plus Data Parallel Applications;27
7.3;1.3 Automated Approach for GPU-Based Software Acceleration;27
7.4;1.4 Chapter Summary;27
7.5;References;28
8;Part I Alternative Hardware Platforms;29
8.1;2 Hardware Platforms;31
8.1.1;2.1 Chapter Overview;31
8.1.2;2.2 Introduction;31
8.1.3;2.3 Hardware Platforms Studied in This Research Monograph;32
8.1.3.1;2.3.1 Custom ICs;32
8.1.3.2;2.3.2 FPGAs;32
8.1.3.3;2.3.3 Graphics Processors;32
8.1.4;2.4 General Overview and Architecture;33
8.1.5;2.5 Programming Model and Environment;36
8.1.6;2.6 Scalability;37
8.1.7;2.7 Design Turn-Around Time;38
8.1.8;2.8 Performance;38
8.1.9;2.9 Cost of Hardware;40
8.1.10;2.10 Floating Point Operations;40
8.1.11;2.11 Security and Real-Time Applications;41
8.1.12;2.12 Applications;41
8.1.13;2.13 Chapter Summary;42
8.1.14;References;42
8.2;3 GPU Architecture and the CUDA Programming Model;45
8.2.1;3.1 Chapter Overview;45
8.2.2;3.2 Introduction;45
8.2.3;3.3 Hardware Model;46
8.2.4;3.4 Memory Model;47
8.2.5;3.5 Programming Model;50
8.2.6;3.6 Chapter Summary;52
8.2.7;References;52
9;Part II Control-Dominated Category;53
9.1;4 Accelerating Boolean Satisfiability on a Custom IC;55
9.1.1;4.1 Chapter Overview;55
9.1.2;4.2 Introduction;56
9.1.3;4.3 Previous Work;58
9.1.4;4.4 Hardware Architecture;59
9.1.4.1;4.4.1 Abstract Overview;59
9.1.4.2;4.4.2 Hardware Overview;60
9.1.4.3;4.4.3 Hardware Details;61
9.1.4.3.1;4.4.3.1 Decision Engine;61
9.1.4.3.2;4.4.3.2 Clause Cell;62
9.1.4.3.3;4.4.3.3 Base Cell;65
9.1.4.3.4;4.4.3.4 Partitioning the Hardware;67
9.1.4.3.5;4.4.3.5 Inter-bank Communication;71
9.1.5;4.5 An Example of Conflict Clause Generation;72
9.1.6;4.6 Partitioning the CNF Instance;73
9.1.7;4.7 Extraction of the Unsatisfiable Core;75
9.1.8;4.8 Experimental Results;76
9.1.9;4.9 Chapter Summary;81
9.1.10;References;81
9.2;5 Accelerating Boolean Satisfiability on an FPGA;84
9.2.1;5.1 Chapter Overview;84
9.2.2;5.2 Introduction;85
9.2.3;5.3 Previous Work;85
9.2.4;5.4 Hardware Architecture;87
9.2.4.1;5.4.1 Architecture Overview;87
9.2.5;5.5 Solving a CNF Instance Which Is Partitioned into Several Bins;88
9.2.6;5.6 Partitioning the CNF Instance;90
9.2.7;5.7 Hardware Details;91
9.2.8;5.8 Experimental Results;93
9.2.8.1;5.8.1 Current Implementation;93
9.2.8.2;5.8.2 Performance Model;94
9.2.8.2.1;5.8.2.1 FPGA Resources;94
9.2.8.2.2;5.8.2.2 Clauses/Variable Ratio;95
9.2.8.2.3;5.8.2.3 Cycles Versus Bin Size;95
9.2.8.2.4;5.8.2.4 Bins Touched Versus Bin Size;96
9.2.8.2.5;5.8.2.5 Bin Size;97
9.2.8.3;5.8.3 Projections;98
9.2.9;5.9 Chapter Summary;101
9.2.10;References;101
9.3;6 Accelerating Boolean Satisfiability on a Graphics Processing Unit;103
9.3.1;6.1 Chapter Overview;103
9.3.2;6.2 Introduction;103
9.3.3;6.3 Related Previous Work;105
9.3.4;6.4 Our Approach;107
9.3.4.1;6.4.1 SurveySAT and the GPU;107
9.3.4.1.1;6.4.1.1 SurveySAT;107
9.3.4.1.2;6.4.1.2 SurveySAT on the GPU;110
9.3.4.1.3;6.4.1.3 SurveySAT Results on the GPU;112
9.3.4.2;6.4.2 MiniSAT Enhanced with Survey Propagation (MESP);113
9.3.5;6.5 Experimental Results;116
9.3.6;6.6 Chapter Summary;118
9.3.7;References;118
10;Part III Control Plus Data Parallel Applications;120
10.1;7 Accelerating Statistical Static Timing Analysis Using Graphics Processors;123
10.1.1;7.1 Chapter Overview;123
10.1.2;7.2 Introduction;124
10.1.3;7.3 Previous Work;126
10.1.4;7.4 Our Approach;127
10.1.4.1;7.4.1 Static Timing Analysis (STA) at a Gate;127
10.1.4.2;7.4.2 Statistical Static Timing Analysis (SSTA) at a Gate;130
10.1.5;7.5 Experimental Results;131
10.1.6;7.6 Chapter Summary;134
10.1.7;References;134
10.2;8 Accelerating Fault Simulation Using Graphics Processors;137
10.2.1;8.1 Chapter Overview;137
10.2.2;8.2 Introduction;137
10.2.3;8.3 Previous Work;139
10.2.4;8.4 Our Approach;140
10.2.4.1;8.4.1 Logic Simulation at a Gate;141
10.2.4.2;8.4.2 Fault Injection at a Gate;143
10.2.4.3;8.4.3 Fault Detection at a Gate;144
10.2.4.4;8.4.4 Fault Simulation of a Circuit;145
10.2.5;8.5 Experimental Results;147
10.2.6;8.6 Chapter Summary;149
10.2.7;References;149
10.3;9 Fault Table Generation Using Graphics Processors;151
10.3.1;9.1 Chapter Overview;151
10.3.2;9.2 Introduction;152
10.3.3;9.3 Previous Work;154
10.3.4;9.4 Our Approach;154
10.3.4.1;9.4.1 Definitions;155
10.3.4.2;9.4.2 Algorithms: FSIM* and GFTABLE;157
10.3.4.2.1;9.4.2.1 Generating Vectors (Line 9);158
10.3.4.2.2;9.4.2.2 Fault-Free Simulation (Line 10);159
10.3.4.2.3;9.4.2.3 Computing Detectabilities and Cumulative Detectabilities (Lines 13, 14);160
10.3.4.2.4;9.4.2.4 Fault Simulation of SR(s) (Lines 15, 16);161
10.3.4.2.5;9.4.2.5 Generating the Fault Table (Lines 22--31);164
10.3.5;9.5 Experimental Results;164
10.3.6;9.6 Chapter Summary;168
10.3.7;References;169
10.4;10 Accelerating Circuit Simulation Using Graphics Processors;171
10.4.1;10.1 Chapter Overview;171
10.4.2;10.2 Introduction;171
10.4.3;10.3 Previous Work;173
10.4.4;10.4 Our Approach;175
10.4.4.1;10.4.1 Parallelizing BSIM3 Model Computations on a GPU;176
10.4.4.1.1;10.4.1.1 Inlining if--then--else Code;176
10.4.4.1.2;10.4.1.2 Partitioning the BSIM3 Code into Kernels;177
10.4.4.1.3;10.4.1.3 Efficient Use of GPU Memory Model;178
10.4.4.1.4;10.4.1.4 Thread Scheduler and Code Statistics;179
10.4.5;10.5 Experiments;180
10.4.6;10.6 Chapter Summary;183
10.4.7;References;183
11;Part IV Automated Generation of GPU Code;184
11.1;11 Automated Approach for Graphics Processor Based Software Acceleration;185
11.1.1;11.1 Chapter Overview;185
11.1.2;11.2 Introduction;185
11.1.3;11.3 Our Approach;187
11.1.3.1;11.3.1 Problem Definition;187
11.1.3.2;11.3.2 GPU Constraints on the Kernel Generation Engine;188
11.1.3.3;11.3.3 Automatic Kernel Generation Engine;189
11.1.3.3.1;11.3.3.1 Node Duplication;191
11.1.3.3.2;11.3.3.2 Cost of a Partitioning Solution;192
11.1.4;11.4 Experimental Results;192
11.1.4.1;11.4.1 Evaluation Methodology;193
11.1.5;11.5 Chapter Summary;195
11.1.6;References;195
11.2;12 Conclusions;197
11.2.1;References;203
12;Index;204