Efficient LU Factorization on FPGA-based Machines

X. Wang, S.G. Ziavras, and J. Savir (USA)


FPGA, LU factorization, matrix inversion, parallelprocessing, SOPC.


Configurable computing has demonstrated its ability to significantly improve performance for many computation intensive applications. With steady advances in silicon technology, Field-Programmable Gate Array (FPGA) technologies have enabled the implementation of robust System-On-a-Programmable-Chip (SOPC) computing platforms, which, in turn, have given significant boost to the field of (re)configurable computing. With innovative approaches, it is now possible to implement various specialized parallel computing machines in FPGAs. LU factorization is widely used in engineering and science to solve efficiently large systems of linear equations. We describe here our design and implementation of a parallel machine on an SOPC development board, using multiple copies of the Altera soft configurable processor, namely Nios ; we use this design for the LU factorization of large, sparse matrices. Such matrices are ubiquitous in several application areas, including electrical power flow. Our implementation facilitates the efficient solution of linear equations at a cost much lower than that of supercomputers and networks of workstations. The intricacies of our FPGA-based design are presented along with tradeoff choices made for the purpose of illustration. Performance results prove the viability of our FPGA based approach.

Important Links:

Go Back