GPU加速不完全Cholesky分解预条件共轭梯度法

GPU-Accelerated Incomplete Cholesky Factorization Preconditioned Conjugate Gradient Method

不完全Cholesky分解预条件共轭梯度(incomplete Cholesky factorization preconditioned conjugate gradient,ICCG)法是求解大规模稀疏对称正定线性方程组的有效方法.然而ICCG法要求在每次迭代中求解2个稀疏三角方程组,稀疏三角方程组求解固有的串行性成为了ICCG法在GPU上并行求解的瓶颈.针对稀疏三角方程组求解,给出了一种利用GPU加速的有效方法.为了增加稀疏三角方程组求解在GPU上的多线程并行性,提出了对不完全Cholesky分解产生的稀疏三角矩阵进行分层调度(level scheduling)的方法.为了进一步提高稀疏三角方程组求解的并行性能,提出了在分层调度前通过近似最小度(approximate minimum degree,AMD)算法对系数矩阵进行重排序、在分层调度后对稀疏三角矩阵进行层排序的方法,降低了分层调度过程中产生的层数,优化了稀疏三角方程组求解的GPU内存访问模式.数值实验表明,与利用NVIDIA CUSPARSE实现的ICCG法相比,采用上述方法性能可以获得平均1倍以上的提升.

Incomplete Cholesky factorization preconditioned conjugate gradient （ICCG ） method is effective to solve large sparse symmetric positive definite linear systems . However ,ICCG method requires solving two sparse triangular linear systems during each iteration .The inherent serialism of solving sparse triangular becomes a bottleneck which prevents high efficient parallelization of ICCG method on GPU platform .In this paper ,an effective method to accelerate solving sparse triangular on GPU platform is proposed . In order to increase the multi‐thread parallelism of solving sparse triangular on GPU platform ,level scheduling is exploited for the sparse triangular matrixes which incomplete Cholesky factorization generates .For further improving the parallel performance of solving sparse triangular ,approximate minimum degree （AMD） algorithm is used to reorder the coefficient matrix before level scheduling .Moreover ,a novel method ,taking advantage of the level information to reorder the sparse triangular matrices after level scheduling ,is applied .These two methods can decrease the number of levels during level scheduling and optimize GPU memory access pattern to utilize memory coalescing in solving sparse triangular ,respectively .Numerical experiments indicate that compared with ICCG method implemented with NVIDIA CUSPARSE , applying the above methods can obtain more than 100% performance improvement on average .