ISLU: Indexing-Efficient Sparse LU Factorization for Circuit Simulation on GPUs
Dan Niu, Yiyang Tao, Zhou Jin, Yichao Dong, Chao Wang, Changyin Sun · 2024
Sparse LU factorization is a vital technique in solving circuit linear equations, However, irregular data access patterns contribute to unsatisfactory computational efficiency and excessive memory usage. Conventional LU factorization methods generally involve two approaches: either they utilize space-intensive dense matrices for direct index-to-data mapping, or they inefficiently scour through indices to locate the positions of updated data elements. To resolve these challenges, we propose the Indexing-Efficient Sparse LU factorization (ISLU) in this work. A novel indexing-efficient member union is put forwarded to achieve efficient retrieval of indices within compressed formats, thereby significantly enhancing the LU decomposition efficiency. Furthermore, to expedite the establishment of indexing-efficient member union, we design, for the first time, parallel creating member union strategy for GPU platforms, which remarkably reduces the time overhead associated with constructing the proposed structures. Extensive experimental comparisons on 49 benchmark matrices and real SPICE transient simulations demonstrate that the performance enhancements by our proposed ISLU method are substantial, outperforming various excellent GPU and CPU solvers including commercial solvers.