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

作     者：陈尧 赵永华 赵慰 赵莲 Chen Yao;Zhao Yonghua;Zhao Wei;Zhao Lian

作者机构：中国科学院计算机网络信息中心北京100190 中国科学院大学北京100190 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2015年第52卷第4期

页      面：843-850页

核心收录：

学科分类：08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家自然科学基金项目(60873113) 国家自然科学基金重大研究计划项目(91430214) 国家"九七三"重点基础研究发展计划基金项目(2011CB309702) 国家"八六三"高技术研究发展计划基金项目(2012AA01A309) 数学工程与先进计算国家重点实验室开放基金项目(2014A03) 

主　　题：不完全Cholesky分解 预条件 共轭梯度法 重排序 图形处理器 

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