Algorithmic Advancements and a Comparative Investigation of Left and Right Looking Sparse LU Factorization on GPU Platform for Circuit Simulation

Abstract

Sparse LU factorization is a key tool in the solution of large linear set of algebraic equations encompassing a wide range of computing applications. Recent advances in this field exploit the massively parallel architecture of the GPUs via left-looking algorithm (LLA) and right-looking algorithm (RLA). In this paper, adaptive cluster mode is proposed to improve the state-of-the-art in LLA for GPU platforms. The proposed method takes into consideration of varying sparsity at different levels during cluster mode execution, to adaptively configure the GPU block size and the number of parallel columns. The new refinements for LLA are also integrated with the dynamic parallelism that is available in modern GPU architectures. The paper also provides a comprehensive performance comparison of the LLA and hybrid RLA along with state-of-the-art advances on the same GPU platform. The results indicate that, when implemented with similar refinements and on a same platform, LLA provides better performance compared to the hybrid-RLA. The results would be useful to the scientific community while making decision on adopting LLA or RLA algorithms for sparse LU factorization.

Keywords

• Circuit simulation
• GPU
• LU factorization
• multi-core
• parallel simulation
• sparse matrices