An Analytical Model for Domain-Specific Accelerator Deploying Sparse LU Factorization

The Lower-Upper (LU) factorization for sparse linear equations is the main bottleneck of many scientific computation problems, including the SPICE-like circuit simulation in modern VLSI design. However, the highly sparse and irregular data structure, the vast floating-point computing operations, and the strong data dependency are restricting the parallelism of LU factorization on general-purpose processors. Aimed to evaluate the acceleration potential of customized chips for LU factorization before implementation, we build an analytic model to estimate the performance of domain-specific accelerator deploying LU factorization. We first propose a Left-Right-Looking hybrid algorithm by analyzing the workloads of basic LU factorization algorithms to improve the utilization rate of process elements. Furthermore, we design a typical minimal domain-specific architecture (DSA) optimized for parallelism with strong floating-point computing power. Finally, we build an analytical model to estimate the performance while mapping the hybrid algorithm onto the DSA platform. Taking the UFMC sparse matrix collection as the benchmark, we list the estimated performance through MATLAB profiling. It can achieve two orders of magnitude speedup than the KLU/NICSLU solvers on CPU. The proposed model can be generalized for other accelerator exploration in the early design stage.