Title :
Parallelizing sparse LU decomposition on FPGAs
Author :
Guiming Wu ; Xianghui Xie ; Yong Dou ; Junqing Sun ; Dong Wu ; Yuan Li
Author_Institution :
State Key Lab. of Math. Eng. & Adv. Comput., China
Abstract :
Sparse LU decomposition is the core computation in the direct method that solves sparse systems of linear equations. Only little work has been conducted on parallelizing it on FPGAs. In this paper, we study parallelization strategies for sparse LU decomposition on FPGAs. We first analyze how to parallelize the right-looking algorithm and find that this algorithm is not suitable for FPGAs. Then the left-looking algorithm is analyzed and considered as better candidate than the right-looking version. Our design derived from the left-looking algorithm is based on a simple yet efficient parallel computational model for FPGAs. Our design mainly consists of multiple parallel processing elements (PEs). A total of 14 PEs can be integrated into a Xilinx Virtex-5 XC5VLX330. Unlike related work, where their designs are applied to sparse matrices from particular application domains, our hardware design can be applied to any symmetric positive definite or diagonally dominant matrices.
Keywords :
field programmable gate arrays; parallel algorithms; sparse matrices; FPGA; PE; Xilinx Virtex-5 XC5VLX330; diagonally dominant matrices; hardware design; left-looking algorithm parallelization; linear equation sparse systems; parallel computational model; parallel processing elements; right-looking algorithm parallelization; sparse LU decomposition parallelization; symmetric positive definite matrices; Algorithm design and analysis; Field programmable gate arrays; Hardware; Matrix decomposition; Parallel processing; Random access memory; Sparse matrices;
Conference_Titel :
Field-Programmable Technology (FPT), 2012 International Conference on
Conference_Location :
Seoul
Print_ISBN :
978-1-4673-2846-3
Electronic_ISBN :
978-1-4673-2844-9
DOI :
10.1109/FPT.2012.6412160
