OOLU: An Operation-Based Optimized Sparse LU Decomposition Accelerator for Circuit Simulation

As scientific and engineering challenges grow in complexity and scale, the demand for effective solutions for sparse matrix computations becomes increasingly critical. LU decomposition, known for its ability to reduce computational load and enhance numerical stability, serves as a promising approach. This study focuses on accelerating sparse LU decomposition for circuit simulations, addressing the prolonged simulation times caused by large circuit matrices. We present a novel Operation-based Optimized LU (OOLU) decomposition architecture that significantly improves circuit analysis efficiency. OOLU employs a VLIW-like processing element array and incorporates a scheduler that decomposes computations into a fine-grained operational task flow graph, maximizing inter-operation parallelism. Specialized scheduling and data mapping strategies are applied to align with the adaptable pipelined framework and the characteristics of circuit matrices. The OOLU architecture is prototyped on an FPGA and validated through extensive tests on the University of Florida sparse matrix collection, benchmarked against multiple platforms. The accelerator achieves speedups ranging from 3.48× to 32.25× (average 12.51×) over the KLU software package. It also delivers average speedups of 2.64× over a prior FPGA accelerator and 25.18× and 32.27× over the GPU accelerators STRUMPACK and SFLU, respectively, highlighting the substantial efficiency gains our approach delivers.