Adapting Sparse Triangular Solution to GPUs
Authors:
- Brad SuchoskiBSBrad Suchoski
- Caleb SevernCSCaleb Severn
- Manu ShantharamMSManu Shantharam
- Padma RaghavanPRPadma Raghavan
- 1 September 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 01903918,p. 140-148
Abstract
High performance computing systems are increasingly incorporating hybrid CPU/GPU nodes to accelerate the rate at which floating point calculations can be performed for scientific applications. Currently, a key challenge is adapting scientific applications to such systems when the underlying computations are sparse, such as sparse linear solvers for the simulation of partial differential equation models using semi-implicit methods. Now, a key bottleneck is sparse triangular solution for solvers such as preconditioned conjugate gradients (PCG). We show that sparse triangular solution can be effectively mapped to GPUs by extracting very large degrees of fine-grained parallelism using graph coloring. We develop simple performance models to predict these effects at intersection of the data and hardware attributes and we evaluate our scheme on a Nvidia Tesla M2090 GPU relative to the level set scheme developed at NVIDIA. Our results indicate that our approach significantly enhances the available fine-grained parallelism to speed-up PCG iteration time compared to the NVIDIA scheme, by a factor with a geometric mean of 5.41 on a single GPU, with speedups as high as 63 in some cases.Keywords
This publication has 6 references indexed in Scilit:
- Accelerating Sparse Matrix Vector Multiplication in Iterative Methods Using GPU2011
- Scalable Multi-coloring Preconditioning for Multi-core CPUs and GPUs2011
- Implementing sparse matrix-vector multiplication on throughput-oriented processors2009
- Little's Law2008
- Efficient Parallel Sparse Triangular Solution Using Selective InversionParallel Processing Letters, 1998
- Scalable iterative solution of sparse linear systemsParallel Computing, 1994