GPU集群加速近似逆预条件CG并行求解器

发布时间：2018-12-18 20:27

【摘要】：针对GPU集群系统,研究了分解近似逆(approximate inverse,AINV)和对称逐次超松弛-近似逆(symmetric successive over relaxation approximate inverse,SSOR-AI)两类近似逆预条件的并行算法。采用多级k-路图划分方法,通过子图的内点和边界点识别方法以及稀疏矩阵的置换技术,提出了将稀疏矩阵转换为分块箭形矩阵的并行方法。基于所形成的分块箭形矩阵,结合块内稀疏矩阵近似逆串行、块间并行的策略给出了近似逆预条件的并行方法,实现了AINV和SSOR-AI并行算法,解决了AINV预条件难以并行的问题。基于CPU与GPU协同计算、主机端页锁定内存和设备端计算与通信重叠的优化技术,实现了并行近似逆预条件与共轭梯度(conjugate gradient,CG)算法相结合的线性方程组混合并行求解器。数值实验表明,所提方法对AINV和SSOR-AI两类近似逆预条件,在多GPU上获得了很好的可扩展性和加速效果。
[Abstract]:For GPU cluster systems, parallel algorithms for decomposing approximate inverse (approximate inverse,AINV) and symmetric successive overrelaxation approximate inverse (symmetric successive over relaxation approximate inverse,SSOR-AI (symmetric successive over relaxation approximate inverse,SSOR-AI) are studied. A parallel method of converting sparse matrix into block quiver matrix is proposed by using the method of multi-level k-path graph partition, the method of identifying interior and boundary points of subgraph and the technique of replacing sparse matrix. Based on the block quiver matrix, the parallel method of approximate inverse precondition is given by combining the strategy of approximate inverse serial and inter-block parallelism of sparse matrix in block. The parallel algorithm of AINV and SSOR-AI is realized, and the problem that AINV precondition is difficult to parallel is solved. Based on the cooperative computation of CPU and GPU, the optimization technique of memory locking on the host side and the overlap of computing and communication on the device side, a hybrid parallel solver for linear equations is implemented, which combines the parallel approximate inverse precondition with the conjugate gradient (conjugate gradient,CG) algorithm. Numerical experiments show that the proposed method can achieve good scalability and acceleration on multiple GPU for two kinds of approximate inverse preconditioners: AINV and SSOR-AI.
【作者单位】：中国科学院计算机网络信息中心;中国科学院大学;
【基金】：国家重点基础研究发展计划(973计划)No.2011CB309702 数学工程与先进计算国家重点实验室开放基金No.2014A03~~
【分类号】：TP338.6

【共引文献】