Parallel sparse matrix solution for direct circuit simulation on a multiple FPGA system

SPICE, from the University of California, at Berkeley, is the de facto world standard for circuit simulation. SPICE is used to model the behaviour of electronic circuits prior to manufacturing to decrease defects and hence reduce costs. However, accurate SPICE simulations of today's sub micron circuits can often take days or weeks on conventional processors. In a nutshell, a SPICE simulation is an iterative process that consists of two phases per iteration, namely, model evaluation followed by a matrix solution. The model evaluation phase has been found to be easily parallelisable unlike the subsequent phase, which involves the solution of highly sparse and asymmetric matrices. In this thesis, we present an FPGA implementation of a sparse matrix solver hardware, geared towards matrices that arise in SPICE circuit simulations. As such, we demonstrate how we extract parallelism at different granularities to accelerate the solution process. Our approach combines static pivoting with symbolic analysis to compute an accurate task flow-graph which efficiently exploits parallelism at multiple granularities and sustains high floating-point data rates. We also present a quantitative comparison between the performance of our hardware prototype and state-of-the-art software package running on a general purpose PC equipped with a 2.67 GHz six-core 12 thread Intel Core Xeon X5650 microprocessor and 6 GB memory. We report average speedups of 9.65x, 11.83x, 17.21x against UMFPACK, KLU, and Kundert Sparse matrix packages respectively. We also detail our approach to adapt our sparse LU hardware prototype from a single-FPGA architecture to a multi-FPGA system to achieve higher acceleration ratios up to 38x for certain circuit matrices