class="bi x0 y0 w1 h1"
Hardware Acceleration of EDA Algorithms

Kanupriya Gulati · Sunil P. Khatri
Hardware Acceleration
of EDA Algorithms
Custom ICs, FPGAs and GPUs
123
Kanupriya Gulati
109 Branchwood Trl
Coppell TX 75019
USA
[email protected]
Sunil P. Khatri
Department of Electrical & Computer
Engineering
Texas A & M University
College Station TX
77843-3128
214 Zachry Engineering Center
USA
[email protected]
ISBN 978-1-4419-0943-5 e-ISBN 978-1-4419-0944-2
DOI 10.1007/978-1-4419-0944-2
Springer New York Dordrecht Heidelberg London
Library of Congress Control Number: 2010920238
c

Springer Science+Business Media, LLC 2010
All rights reserved. This work may not be translated or copied in whole or in part without the written
permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,

performed in hardware, in parallel, (ii) an FPGA-based hardware approach to accel-
erate SAT in which the entire SAT search algorithm is implemented in the FPGA,
and (iii) a complete SAT approach which employs a new GPU-enhanced variable
ordering heuristic.
In this monograph, several EDA problems with varying degrees of control and
data parallelisms are accelerated using a general-purpose graphics processor. In par-
ticular we accelerate Monte Carlo based statistical static timing analysis, device
model evaluation (for accelerating circuit simulation), fault simulation, and fault
table generation on a graphics processor, with speedups of up to 800×. Addition-
ally, an automated approach is presented that accelerates (on a graphics proces-
sor) uniprocessor code that is executed multiple times on independent data sets
in an application. The key idea here is to partition the software into kernels in an
automated fashion, such that multiple independent instances of these kernels, when
vii
viii Foreword
executed in parallel on the GPU, can maximally benefit from the GPU’s hardware
resources.
We hope that this monograph can serve as a valuable reference to individuals
interested in exploring alternative hardware platforms and to those interested in
accelerating various EDA applications by harnessing the parallelism in these plat-
forms.
College Station, TX Kanupriya Gulati
College Station, TX Sunil P. Khatri
October 2009
Preface
In recent times, serial software applications have no longer enjoyed significant
gains in performance with process scaling, since microprocessor performance gains
have been hampered due to increases in power and manufacturability issues, which
accompany scaling. With the continuous growth of IC design complexities, this
problem is particularly significant for EDA applications. In this research mono-

In Part II of this monograph we present hardware implementations of a control-
dominated EDA problem, namely Boolean satisfiability (SAT). We present
approaches to accelerate SAT using each of the three hardware platforms under
consideration. In Chapter 4, we present a custom IC-based hardware approach to
accelerate SAT. In this approach, the traversal of the implication graph and con-
flict clause generation are performed in hardware, in parallel. Further, we propose a
hardware approach to extract the minimum unsatisfiable core for any unsatisfiable
formula. In Chapter 5, we discuss an FPGA-based hardware approach to accelerate
SAT. In this approach, we store the clauses in the FPGA slices. In order to solve
large SAT instances, we partition the instance into ‘bins,’ each of which can fit in
the FPGA. The solution of SAT clauses of any bin is performed in parallel. Our
approach also handles (in hardware) the fact that the original SAT instance is par-
titioned into bins. In Chapter 6, we present a SAT approach which employs a new
GPU-enhanced variable ordering heuristic. In this approach, we augment a CPU-
based complete procedure (MiniSAT), with a GPU-based approximate procedure
(survey propagation). In this manner, the complete procedure benefits from the high
parallelism of the GPU.
In Part III of this book, we study the acceleration of several EDA problems,
with varying amounts of control and data parallelism, on a GPU. In Chapter 7, we
exploit the parallelism in Monte Carlo based statistical static timing analysis and
accelerate it on a graphics processor. In this approach, we map the Monte Carlo
based SSTA computations to the large number of threads that can be computed in
parallel on a GPU. Our approach performs multiple delay simulations of a s ingle
gate in parallel and further benefits from a parallel implementation of the Mersenne
Twister pseudo-random number generator on the GPU, followed by Box–Muller
transformations (also implemented on the GPU). In Chapter 8, we study the accel-
eration of fault simulation on a GPU. Fault simulation is inherently parallelizable
and requires a large number of gate evaluations to be performed for each gate in
a design. The large number of threads that can be computed in parallel on a GPU
can be employed to perform a large number of these gate evaluations in parallel. We

Dr. Abhijit Jas, and Suganth Paul, for their assistance on the FPGA-based approach
for accelerating Boolean satisfiability; and Dr. John Croix and Rahm Shastry, who
helped in integrating our GPU-based accelerated code for model card evaluation
into a commercial fast SPICE tool.
We acknowledge the insightful comments of Dr. Peng Li, Dr. Hank Walker,
Dr. Desmond Kirkpatrick, and Dr. Jim Ji. We would also like to thank Intel Cor-
poration, Nascentric Inc., Accelicon Technologies Inc., and NVIDIA Corporation,
for supporting this research through research grants and an NVIDIA fellowship,
respectively.
xiii

Contents
1 Introduction 1
1.1 Hardware Platforms Considered in This Research Monograph . . . . 3
1.2 EDA Algorithms Studied in This Research Monograph . . . . 3
1.2.1 Control-DominatedApplications 4
1.2.2 ControlPlusDataParallelApplications 4
1.3 Automated Approach for GPU-Based Software Acceleration . . . . . 4
1.4 Chapter Summary . . . . . . 4
References 5
Part I Alternative Hardware Platforms
2 Hardware Platforms 9
2.1 Chapter Overview . . . . . . 9
2.2 Introduction 9
2.3 Hardware Platforms Studied in This Research Monograph . 10
2.3.1 CustomICs 10
2.3.2 FPGAs 10
2.3.3 Graphics Processors 10
2.4 General Overview and Architecture . . 11
2.5 Programming Model and Environment 14

4.7 Extraction of the Unsatisfiable Core . . 53
4.8 Experimental Results . . . 54
4.9 Chapter Summary . . . . . . 59
References 59
5 Accelerating Boolean Satisfiability on an FPGA 63
5.1 Chapter Overview . . . . . . 63
5.2 Introduction 64
5.3 PreviousWork 64
5.4 HardwareArchitecture 66
5.4.1 ArchitectureOverview 66
5.5 Solving a CNF Instance Which Is Partitioned into Several Bins . . . 67
5.6 Partitioning the CNF Instance 69
5.7 HardwareDetails 70
5.8 Experimental Results . . . 72
5.8.1 CurrentImplementation 72
5.8.2 Performance Model . 73
5.8.3 Projections 77
5.9 Chapter Summary . . . . . . 80
References 80
Contents xvii
6 Accelerating Boolean Satisfiability on a Graphics Processing Unit 83
6.1 Chapter Overview . . . . . . 83
6.2 Introduction 83
6.3 RelatedPreviousWork 85
6.4 Our Approach . . 87
6.4.1 SurveySATandtheGPU 87
6.4.2 MiniSAT Enhanced with Survey Propagation (MESP) . . . 93
6.5 Experimental Results . . . 96
6.6 Chapter Summary . . . . . . 98
References 98

9.4.1 Definitions 137
9.4.2 Algorithms: FSIM∗ andGFTABLE 139
9.5 Experimental Results . . . 146
9.6 Chapter Summary . . . . . . 150
References 151
10 Accelerating Circuit Simulation Using Graphics Processors 153
10.1 Chapter Overview . . . . . . 153
10.2 Introduction 153
10.3 PreviousWork 155
10.4 Our Approach . . 157
10.4.1 Parallelizing BSIM3 Model Computations on a GPU . . . . 158
10.5 Experiments 162
10.6 Chapter Summary . . . . . . 165
References 165
Part IV Automated Generation of GPU Code
11 Automated Approach for Graphics Processor Based Software
Acceleration 169
11.1 Chapter Overview . . . . . . 169
11.2 Introduction 169
11.3 Our Approach . . 171
11.3.1 Problem Definition . . 171
11.3.2 GPU Constraints on the Kernel Generation Engine 172
11.3.3 Automatic Kernel Generation Engine . . . . 173
11.4 Experimental Results . . . 176
11.4.1 Evaluation Methodology . . . . 177
11.5 Chapter Summary . . . . . . 179
References 179
12 Conclusions 181
References 187
Index 189