Hardware Acceleration of EDA Algorithms- P2

Hardware Acceleration of EDA Algorithms- P2: Single-threaded software applications have ceased to see significant gains in performanceon a general-purpose CPU, even with further scaling in very large scaleintegration (VLSI) technology. This is a significant problem for electronic designautomation (EDA) applications, since the design complexity of VLSI integratedcircuits (ICs) is continuously growing. In this research monograph, we evaluatecustom ICs, field-programmable gate arrays (FPGAs), and graphics processors asplatforms for accelerating EDA algorithms, instead of the general-purpose singlethreadedCPU....
Nội dung trích xuất từ tài liệu:
Hardware Acceleration of EDA Algorithms- P2List of Figures1.1 CPU performance growth [3] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.1 FPGA layout [14] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 Logic block in the FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.3 LUT implementation using a 16:1 MUX . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 SRAM configuration bit design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.5 Comparing Gflops of GPUs and CPUs [11] . . . . . . . . . . . . . . . . . . . . . . . . 142.6 FPGA growth trend [9] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.1 CUDA for interfacing with GPU device . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2 Hardware model of the NVIDIA GeForce GTX 280 . . . . . . . . . . . . . . . . 253.3 Memory model of the NVIDIA GeForce GTX 280 . . . . . . . . . . . . . . . . . 263.4 Programming model of CUDA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.1 Abstracted view of the proposed idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.2 Generic floorplan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.3 State diagram of the decision engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.4 Signal interface of the clause cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.5 Schematic of the clause cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.6 Layout of the clause cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.7 Signal interface of the base cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.8 Indicating a new implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.9 Computing backtrack level . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.10 (a) Internal structure of a bank. (b) Multiple clauses packed in one bank-row . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.11 Signal interface of the terminal cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.12 Schematic of a terminal cell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.13 Hierarchical structure for inter-bank communication . . . . . . . . . . . . . . . . 494.14 Example of implicit traversal of implication graph . . . . . . . . . . . . . . . . . . 515.1 Hardware architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.2 State diagram of the decision engine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.3 Resource utilization for clauses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.4 Resource utilization for variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.5 Computing aspect ratio (16 variables) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755.6 Computing aspect ratio (36 variables) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756.1 Data structure of the SAT instance on the GPU . . . . . . . . . . . . . . . . . . . . . 92 xxixxii List of Figures7.1 Comparing Monte Carlo based SSTA on GTX 280 GPU and Intel Core 2 processors (with SEE instructions) . . . . . . . . . . . . . . . . . . . . . . . . . 1168.1 Truth tables stored in a lookup table . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1238.2 Levelized logic netlist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1289.1 Example circuit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1379.2 CPT on FFR(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1429.3 Fault simulation on SR(k) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14510.1 Industrial_2 waveforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16410.2 Industrial_3 waveforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16411.1 CDFG example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17411.2 KDG example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17512.1 New parallel kernel GPUs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18412.2 Larrabee architecture from Intel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18512.3 Fermi architecture from NVIDIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18512.4 Block diagram of a single ...