Hardware Acceleration of EDA Algorithms (eBook)
XXII, 192 Seiten
Springer US (Verlag)
978-1-4419-0944-2 (ISBN)
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.
Foreword 8
Preface 10
Acknowledgments 14
Contents 16
List of Tables 20
List of Figures 22
1 Introduction 24
1.1 Hardware Platforms Considered in This Research Monograph 26
1.2 EDA Algorithms Studied in This Research Monograph 26
1.2.1 Control-Dominated Applications 27
1.2.2 Control Plus Data Parallel Applications 27
1.3 Automated Approach for GPU-Based Software Acceleration 27
1.4 Chapter Summary 27
References 28
Part I Alternative Hardware Platforms 29
2 Hardware Platforms 31
2.1 Chapter Overview 31
2.2 Introduction 31
2.3 Hardware Platforms Studied in This Research Monograph 32
2.3.1 Custom ICs 32
2.3.2 FPGAs 32
2.3.3 Graphics Processors 32
2.4 General Overview and Architecture 33
2.5 Programming Model and Environment 36
2.6 Scalability 37
2.7 Design Turn-Around Time 38
2.8 Performance 38
2.9 Cost of Hardware 40
2.10 Floating Point Operations 40
2.11 Security and Real-Time Applications 41
2.12 Applications 41
2.13 Chapter Summary 42
References 42
3 GPU Architecture and the CUDA Programming Model 45
3.1 Chapter Overview 45
3.2 Introduction 45
3.3 Hardware Model 46
3.4 Memory Model 47
3.5 Programming Model 50
3.6 Chapter Summary 52
References 52
Part II Control-Dominated Category 53
4 Accelerating Boolean Satisfiability on a Custom IC 55
4.1 Chapter Overview 55
4.2 Introduction 56
4.3 Previous Work 58
4.4 Hardware Architecture 59
4.4.1 Abstract Overview 59
4.4.2 Hardware Overview 60
4.4.3 Hardware Details 61
4.4.3.1 Decision Engine 61
4.4.3.2 Clause Cell 62
4.4.3.3 Base Cell 65
4.4.3.4 Partitioning the Hardware 67
4.4.3.5 Inter-bank Communication 71
4.5 An Example of Conflict Clause Generation 72
4.6 Partitioning the CNF Instance 73
4.7 Extraction of the Unsatisfiable Core 75
4.8 Experimental Results 76
4.9 Chapter Summary 81
References 81
5 Accelerating Boolean Satisfiability on an FPGA 84
5.1 Chapter Overview 84
5.2 Introduction 85
5.3 Previous Work 85
5.4 Hardware Architecture 87
5.4.1 Architecture Overview 87
5.5 Solving a CNF Instance Which Is Partitioned into Several Bins 88
5.6 Partitioning the CNF Instance 90
5.7 Hardware Details 91
5.8 Experimental Results 93
5.8.1 Current Implementation 93
5.8.2 Performance Model 94
5.8.2.1 FPGA Resources 94
5.8.2.2 Clauses/Variable Ratio 95
5.8.2.3 Cycles Versus Bin Size 95
5.8.2.4 Bins Touched Versus Bin Size 96
5.8.2.5 Bin Size 97
5.8.3 Projections 98
5.9 Chapter Summary 101
References 101
6 Accelerating Boolean Satisfiability on a Graphics Processing Unit 103
6.1 Chapter Overview 103
6.2 Introduction 103
6.3 Related Previous Work 105
6.4 Our Approach 107
6.4.1 SurveySAT and the GPU 107
6.4.1.1 SurveySAT 107
6.4.1.2 SurveySAT on the GPU 110
6.4.1.3 SurveySAT Results on the GPU 112
6.4.2 MiniSAT Enhanced with Survey Propagation (MESP) 113
6.5 Experimental Results 116
6.6 Chapter Summary 118
References 118
Part III Control Plus Data Parallel Applications 120
7 Accelerating Statistical Static Timing Analysis Using Graphics Processors 123
7.1 Chapter Overview 123
7.2 Introduction 124
7.3 Previous Work 126
7.4 Our Approach 127
7.4.1 Static Timing Analysis (STA) at a Gate 127
7.4.2 Statistical Static Timing Analysis (SSTA) at a Gate 130
7.5 Experimental Results 131
7.6 Chapter Summary 134
References 134
8 Accelerating Fault Simulation Using Graphics Processors 137
8.1 Chapter Overview 137
8.2 Introduction 137
8.3 Previous Work 139
8.4 Our Approach 140
8.4.1 Logic Simulation at a Gate 141
8.4.2 Fault Injection at a Gate 143
8.4.3 Fault Detection at a Gate 144
8.4.4 Fault Simulation of a Circuit 145
8.5 Experimental Results 147
8.6 Chapter Summary 149
References 149
9 Fault Table Generation Using Graphics Processors 151
9.1 Chapter Overview 151
9.2 Introduction 152
9.3 Previous Work 154
9.4 Our Approach 154
9.4.1 Definitions 155
9.4.2 Algorithms: FSIM* and GFTABLE 157
9.4.2.1 Generating Vectors (Line 9) 158
9.4.2.2 Fault-Free Simulation (Line 10) 159
9.4.2.3 Computing Detectabilities and Cumulative Detectabilities (Lines 13, 14) 160
9.4.2.4 Fault Simulation of SR(s) (Lines 15, 16) 161
9.4.2.5 Generating the Fault Table (Lines 22--31) 164
9.5 Experimental Results 164
9.6 Chapter Summary 168
References 169
10 Accelerating Circuit Simulation Using Graphics Processors 171
10.1 Chapter Overview 171
10.2 Introduction 171
10.3 Previous Work 173
10.4 Our Approach 175
10.4.1 Parallelizing BSIM3 Model Computations on a GPU 176
10.4.1.1 Inlining if--then--else Code 176
10.4.1.2 Partitioning the BSIM3 Code into Kernels 177
10.4.1.3 Efficient Use of GPU Memory Model 178
10.4.1.4 Thread Scheduler and Code Statistics 179
10.5 Experiments 180
10.6 Chapter Summary 183
References 183
Part IV Automated Generation of GPU Code 184
11 Automated Approach for Graphics Processor Based Software Acceleration 185
11.1 Chapter Overview 185
11.2 Introduction 185
11.3 Our Approach 187
11.3.1 Problem Definition 187
11.3.2 GPU Constraints on the Kernel Generation Engine 188
11.3.3 Automatic Kernel Generation Engine 189
11.3.3.1 Node Duplication 191
11.3.3.2 Cost of a Partitioning Solution 192
11.4 Experimental Results 192
11.4.1 Evaluation Methodology 193
11.5 Chapter Summary 195
References 195
12 Conclusions 197
References 203
Index 204
| Erscheint lt. Verlag | 11.3.2010 |
|---|---|
| Zusatzinfo | XXII, 192 p. |
| Verlagsort | New York |
| Sprache | englisch |
| Themenwelt | Informatik ► Weitere Themen ► CAD-Programme |
| Technik ► Elektrotechnik / Energietechnik | |
| Schlagworte | algorithms • Architecture • Computer-Aided Design (CAD) • EDA • EDA Algorithm • Electronic Design Automation • field programmable gate array • FPGA • GPU • Graphics Processing Unit • hardware acceleration • Integrated circuit • micro-alloy transistor, MAT • Model • reconfigurable computing • Simulation • static-induction transistor |
| ISBN-10 | 1-4419-0944-3 / 1441909443 |
| ISBN-13 | 978-1-4419-0944-2 / 9781441909442 |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)Größe: 2,7 MB
DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Zusätzliches Feature: Online Lesen
Dieses eBook können Sie zusätzlich zum Download auch online im Webbrowser lesen.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
