PROJECT TITLE :

GPU-Accelerated Parallel Sparse LU Factorization Method for Fast Circuit Analysis - 2016

ABSTRACT:

Lower higher (LU) factorization for sparse matrices is the foremost necessary computing step for circuit simulation issues. However, parallelizing LU factorization on the graphic processing units (GPUs) turns out to be a difficult downside thanks to intrinsic data dependence and irregular memory access, that diminish GPU computing power. In this paper, we have a tendency to propose a brand new sparse LU solver on GPUs for circuit simulation and more general scientific computing. The new methodology, which is termed GPU accelerated LU factorization (GLU) solver (for GPU LU), is based on a hybrid right-trying LU factorization algorithm for sparse matrices. We show that additional concurrency can be exploited in the right-wanting technique than the left-trying methodology, which is a lot of standard for circuit analysis, on GPU platforms. At the identical time, the GLU additionally preserves the advantage of column-based mostly left-wanting LU methodology, such as symbolic analysis and columnlevel concurrency. We have a tendency to show that the resulting new parallel GPU LU solver allows the parallelization of all three loops within the LU factorization on GPUs. Whereas in contrast, the present GPU-based mostly left-looking LU factorization approach can only enable parallelization of 2 loops. Experimental results show that the proposed GLU solver can deliver 5.seventy one? and one.46x speedup over the one-threaded and the sixteen-threaded PARDISO solvers, respectively, nineteen.56x speedup over the KLU solver, 47.13x over the UMFPACK solver, and one.47x speedup over a recently proposed GPU-primarily based left-wanting LU solver on the set of typical circuit matrices from the University of Florida (UFL) sparse matrix collection. Furthermore, we tend to conjointly compare the proposed GLU solver on a group of general matrices from the UFL, GLU achieves half dozen.38x and 1.12x speedup over the singlethreaded and also the 16-threaded PARDISO solvers, respectively, thirty-nine.39x speedup over the KLU solver, 24.04x over the UMFPACK solver, and a couple of.35x speedup over the same GPU-based left-trying LU solver. Still, comparison on self-generated RLC mesh networks shows the same trend, which further validates the advantage of the proposed methodology over the present sparse LU solvers.