Hardware Acceleration of EDA Algorithms- P2: Single-threaded software applications have ceased to see significant gains in performance on a general-purpose CPU, even with further scaling in very large scale integration (VLSI) technology. This is a significant 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, field-programmable gate arrays (FPGAs), and graphics processors as platforms for accelerating EDA algorithms, instead of the general-purpose singlethreaded CPU | List of Figures CPU performance growth 3 . 2 FPGA layout 14 . 12 Logic block in the FPGA. 12 LUT implementation using a 16 1 MUX. 13 SRAM configuration bit design. 13 Comparing Gflops of GPUs and CPUs 11 . 14 FPGA growth trend 9 . 17 CUDA for interfacing with GPU device. 24 Hardware model of the NVIDIA GeForce GTX 280 . 25 Memory model of the NVIDIA GeForce GTX 280 . 26 Programming model of CUDA. 28 Abstracted view of the proposed idea. 37 Generic floorplan . 38 State diagram of the decision engine . 39 Signal interface of the clause cell. 40 Schematic of the clause cell. 41 Layout of the clause cell. 43 Signal interface of the base cell. 43 Indicating a new implication. 44 Computing backtrack level . 46 a Internal structure of a bank. b Multiple clauses packed in one bank-row. 47 Signal interface of the terminal cell . 47 Schematic of a terminal cell. 48 Hierarchical structure for inter-bank communication. 49 Example of implicit traversal of implication graph. 51 Hardware architecture . 67 State diagram of the decision engine . 71 Resource utilization for clauses. 73 Resource utilization for variables. 74 Computing aspect ratio 16 variables . 75 Computing aspect ratio 36 variables . 75 Data structure of the SAT instance on the GPU. 92 xxi xxii List of Figures Comparing Monte Carlo based SSTA on GTX 280 GPU and Intel Core 2 processors with SEE instructions .116 Truth tables stored in a lookup Levelized logic Example CPT on FFR fc .142 Fault simulation on SR .145 Industrial_2 waveforms .164 Industrial_3 waveforms .164 CDFG KDG New parallel kernel Larrabee architecture from Fermi architecture from Block diagram of a single shared multiprocessor SM in Block diagram of a .
