Abstract: This paper shows the study on the parallel algorithm of AINV (approximate inverse) and SSOR-AI (symmetric successive over relaxation approximate inverse) preconditioners on GPU cluster systems. With multilevel k-way graph partitioning, this paper proposes the parallel method which can transform a sparse matrix into block arrow form based on a method to identify interior/boundary vertex of subgraphs and a permutation. Based on the block arrow matrix, with the strategy of sequential computation approximate inverse of inner block and parallel computation between the different blocks, the parallel algorithm of AINV and SSOR-AI is obtained. Based on the optimization techniques of collaborative computing between CPU and GPU, page-locked host memory and overlapping transfers with computation on device, this paper combines parallel approximate inverse preconditioner with CG (conjugate gradient) algorithm to obtain a hybrid parallel solver for linear systems. Numerical experiments indicate that applying the above methods can obtain very good acceleration effect and scalability both AINV parallel implementation and SSOR-AI parallel implementation on cluster-GPU.

Key words: approximate inverse, preconditioner, iterative method, heterogeneous parallel computing, GPU cluster

摘要： 针对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上获得了很好的可扩展性和加速效果。

关键词: 近似逆, 预条件, 迭代法, 异构并行计算, GPU集群