Effective GPU Strategies for LU Decomposition

Abstract

GPUs (graphics processing units) are becoming an attractive computing platform not only for traditional graphics computation but also for general-purpose computation, because of the computational power, programming capabilities and comparatively low cost modern GPUs have. This improvement of GPUs with highly parallel programming capabilities such as CUDA has lead to a variety of complex applications with remarkable performance improvements. This practice is known as GPGPU (General Purpose computation on Graphics Processing Units). The LU decomposition represents a fundamental step in many computationally intensive scientific applications and it is often the costly step in the solution process because scale of the matrix highly impacts on computation cost. The use of GPUs can accelerate the computation many times than the speed of a single CPU. In this project, we implement different CUDA based heterogeneous parallel implementation solutions for the LU decomposition algorithm (Right-looking Algorithm) in a GPU and then investigate most significant implementations of LU decomposition to fit the massively parallel architecture of modern GPUs. Using our experimental results we can illustrate that highly parallel architecture of GPU with different memory hierarchy and access patterns of those memories can be used to add significant speedup for LU decomposition.