GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis
- 27 April 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Very Large Scale Integration (VLSI) Systems
- Vol. 24 (3) , 1140-1150
Abstract
Lower upper (LU) factorization for sparse matrices is the most important computing step for circuit simulation problems. However, parallelizing LU factorization on the graphic processing units (GPUs) turns out to be a difficult problem due to intrinsic data dependence and irregular memory access, which diminish GPU computing power. In this paper, we propose a new sparse LU solver on GPUs for circuit simulation and more general scientific computing. The new method, which is called GPU accelerated LU factorization (GLU) solver (for GPU LU), is based on a hybrid right-looking LU factorization algorithm for sparse matrices. We show that more concurrency can be exploited in the right-looking method than the left-looking method, which is more popular for circuit analysis, on GPU platforms. At the same time, the GLU also preserves the benefit of column-based left-looking LU method, such as symbolic analysis and columnlevel concurrency. We show that the resulting new parallel GPU LU solver allows the parallelization of all three loops in the LU factorization on GPUs. While in contrast, the existing GPU-based left-looking LU factorization approach can only allow parallelization of two loops. Experimental results show that the proposed GLU solver can deliver 5.71χ and 1.46x speedup over the single-threaded and the 16-threaded PARDISO solvers, respectively, 19.56x speedup over the KLU solver, 47.13x over the UMFPACK solver, and 1.47x speedup over a recently proposed GPU-based left-looking LU solver on the set of typical circuit matrices from the University of Florida (UFL) sparse matrix collection. Furthermore, we also compare the proposed GLU solver on a set of general matrices from the UFL, GLU achieves 6.38x and 1.12x speedup over the singlethreaded and the 16-threaded PARDISO solvers, respectively, 39.39x speedup over the KLU solver, 24.04x over the UMFPACK solver, and 2.35x speedup over the same GPU-based left-looking LU solver. In addition, comparison on self-generated RLC mesh networks shows a similar trend, which further validates the advantage of the proposed method over the existing sparse LU solvers.Keywords
Funding Information
- NSF (No. CCF1017090)
- 985 research funds from Shanghai Jiao Tong University and University of Electronic Science and Technology of China
This publication has 17 references indexed in Scilit:
- GPU-Accelerated Sparse LU Factorization for Circuit Simulation with Performance ModelingIEEE Transactions on Parallel and Distributed Systems, 2015
- Parallel Thermal Analysis of 3-D Integrated Circuits With Liquid Cooling on CPU-GPU PlatformsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2014
- NICSLU: An Adaptive Sparse Matrix Solver for Parallel Circuit SimulationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013
- An EScheduler-Based Data Dependence Analysis and Task Scheduling for Parallel Circuit SimulationIEEE Transactions on Circuits and Systems II: Express Briefs, 2011
- Algorithm 907ACM Transactions on Mathematical Software, 2010
- Towards dense linear algebra for hybrid GPU accelerated manycore systemsParallel Computing, 2010
- Dense linear algebra solvers for multicore with GPU accelerators2010
- LU-GPU: Efficient Algorithms for Solving Dense Linear Systems on Graphics Hardware2005
- An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian EliminationSIAM Journal on Matrix Analysis and Applications, 1999
- Sparse Partial Pivoting in Time Proportional to Arithmetic OperationsSIAM Journal on Scientific and Statistical Computing, 1988