Practical Optimizations for Conjugate Gradient Method Acceleration using CUDA

Abstract

This dissertation presents a series of optimizations for preconditioned and nonpreconditioned the Conjugate Gradient(henceforth, CG) method using CUDA. Each lines of CG algorithm has data dependency on adjacent lines but each step is parallelizable operation like matrix-vector multiplication, dot product, and axpy operation. Because each step is well-known parallelizable operation, overall CG algorithm speed can be accelerated by GPUs and meaningful speedup can be seen with the optimization methods presented in this dissertation. First, we describe performance issues from na¨ıve version of CUDA based CG implemented using an widely adopted CUDA library package: cuBLAS. This library provides generic low level algorithms that can be useful to implement high level algorithms without being focused on writing performant CUDA kernels. However, device-host synchronizations limit the performance gains from CUDA acceleration due to the data dependency of conjugate gradient algorithm steps if that is implemented without a care. GPUs could be i severely under-utilized between each step and GPUs cannot be run at full speed. We proposed a simple but practical optimization technique to avoid device and host synchronizations: Lazy residual evaluation. In this thesis, the overall runtime performance gain by eliminating devicehost synchronizations are explained one by one as the number of synchronizations per iteration is reduced. In the meantime, the changes on CPU and GPU pipeline are explained with illustration as well. Then, the performance gain from the proposed method, Lazy residual evaluation, and advantages or disadvantages are compared against other backend implementations with different level of device-host synchronizations. Finally, importance of device and host synchronization minimization is expressed in details when accelerating iterative algorithms similar to CG using GPUs.