ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (4): 843-850.doi: 10.7544/issn1000-1239.2015.20131919

• 系统结构 • 上一篇    下一篇

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

陈尧1,2, 赵永华1,赵慰1,赵莲1   

  1. 1(中国科学院计算机网络信息中心 北京 100190); 2(中国科学院大学 北京 100190) (cheny_1988@126.com)
  • 出版日期: 2015-04-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(60873113);国家“九七三”重点基础研究发展计划基金项目(2011CB309702);国家“八六三”高技术研究发展计划基金项目(2012AA01A309);国家自然科学基金重大研究计划项目(91430214);数学工程与先进计算国家重点实验室开放基金项目(2014A03)

GPU-Accelerated Incomplete Cholesky Factorization Preconditioned Conjugate Gradient Method

Chen Yao1,2,Zhao Yonghua1,Zhao Wei1,Zhao Lian1   

  1. 1(Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190); 2(University of Chinese Academy of Sciences, Beijing 100190)
  • Online: 2015-04-01

摘要: 不完全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倍以上的提升.

关键词: 不完全Cholesky分解, 预条件, 共轭梯度法, 重排序, 图形处理器

Abstract: 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.

Key words: incomplete Cholesky factorization, preconditioner, conjugate gradient method, reordering, graphic processing unit (GPU)

中图分类号: