High-performance architectures for accelerating sparse LU computation

Sparse Lower-Upper (LU) Triangular Decomposition is important to many di erent applications, including power system analysis. High-performance sparse linear algebra software packages, executing on general-purpose processors, experience lower performance when processing power system matrices. This observation motivated previous work on the design of custom hardware, implemented, in FPGA, to improve performance of sparse LU. While improved performance was obtained, signi cant e ort was required to design and implement the hardware. This thesis investigates the combination of general purpose architectures and a hardware accelerator, for a crucial component of sparse LU, to achieve similar performance results without the design overhead. One architecture, combining a general-purpose processor with a hardware accelerator, achieves a 1.29X speedup over software for a 26K-Bus power system. The second architecture, a modi cation of the Data Pump Architecture, provides a 2.27X speedup over software on the 26K-bus power system. These results show that speedup for sparse LU is possible, without designing a complete custom hardware solution, using a small hardware accelerator, provided a tightly coupled architecture is available to feed data to the accelerator.M.S., Computer Engineering -- Drexel University, 201