Hardware Acceleration of EDA Algorithms- P7: 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 | 102 Part-III Control Plus Data Parallel Applications NVIDIA GeForce GTX 280 GPU card. Experimental results indicate that this approach can obtain an average speedup of about 818 x as compared to a serial CPU implementation. With the recently announced cards with quad GTX 280 GPUs we estimate that our approach would attain a speedup of over 2 400x. Accelerating Fault Simulation on a Graphics Processor In today s complex digital designs with possibly several million gates the number of faulty variations of the design can be dramatically higher. Fault simulation is an important but expensive step of the VLSI design flow and it helps to identify faulty designs. Given a digital design and a set of input vectors V defined over its primary inputs fault simulation evaluates the number of stuck-at faults Fsim that are tested by applying the vectors V. The ratio of Fsim to the total number of faults in the design Ftotal is a measure of the fault coverage. The task of finding this ratio is often referred to as fault grading in the industry. Given the high computational cost for fault simulation it is extremely important to explore ways to accelerate this application. The ideal fault simulation approach should be fast scalable and cost effective. In Chapter 8 we study the acceleration of fault simulation on a GPU. Fault simulation is inherently parallelizable and the large number of threads that can be executed in parallel on a GPU can be employed to perform a large number of gate evaluations in parallel. We implement a pattern and fault parallel fault simulator which fault-simulates a circuit in a levelized fashion. We ensure that all threads of the GPU compute identical instructions but on different data. Fault injection is also performed along with gate evaluation with each thread using a different fault injection mask. Since GPUs have an extremely large memory bandwidth we implement each of our fault simulation threads which execute in parallel with no data dependencies .
