Page 61 - 《软件学报》2021年第8期

刘芳芳 等:国产异构系统上的 HPCG 并行算法及高效实现 2343

的点为内点,计算区域所依赖的邻居进程的点构成的区域为外区,其对应的点为外点.由于我们使用的是 27 点
stencil,所以每个进程最多有 26 个邻居进程.
在 HPCG 中,该线性系统使用预处理共轭梯度(preconditioned conjugate gradient,简称 PCG)法来求解,计算
流程如图 2 所示.
CG 算法中一次迭代计算包含 3 个向量点积操作(第 4、7、10 行)和 3 个向量更新操作(WAXPBY,第 6、8、
9 行)以及 1 个稀疏矩阵向量乘操作(SpMV,第 7 行).
HPCG 中使用的预条件子 M –1 是基于 V-cycle 几何多重网格,其计算流程如图 3 所示.多重网格通过将细网
格上频率变化较缓慢的低频分量映射到粗网格上来处理,以达到加快收敛速度的目的.作为预条件子,多重网格
的计算同样包含 4 个主要操作:前磨光操作(第 4 行)和后磨光操作(第 8 行)、限制算子(第 5 行)、插值算子(第 7
行)、底部解法器(第 2 行).在 HPCG 中,多重网格的层数被固定为 4 层,前后磨光操作以及底部解法器都是使用
对称 Gauss-Seidel 迭代法的一次迭代来实现,并且磨光操作只执行一次,不可修改.使用 SymGS(x,r)表示一次对
称 Gauss-Seidel 迭代,其中 r 是右端项,x 是解向量的初始猜测值.

Fig.2 Conjugate gradient algorithm Fig.3 Multigrid pre-conditioner
图 2 共轭梯度法 图 3 多重网格预条件子

在 HPCG 中主要存在两种通信类型:全局通信和邻居通信.
1. 全局通信.主要为 MPI_Allreduce 通信,发生在向量点积操作中.在一次 CG 迭代中总共需要计算 3 次向
量的点积,因此需要调用 3 次 MPI_Allreduce.
2. 邻居通信.主要发生在与稀疏矩阵相关的两个核心函数中:SpMV 和 SymGS,使用 MPI 点到点的通信实
现 halo 区数据交换.HPCG 采用 27 点 stencil 格式,每个网格点的计算依赖周围紧邻的 26 个邻居.在 SpMV 和
SymGS 计算开始前,需要与周围的邻居进程交换边界数据(halo),以便将计算过程中所需要访问到的邻居数据
传输到本地进程中.
3. 目前超级计算机的体系结构日趋复杂,早已从同构转向异构,且同节点异构部件的运算性能比差异越来
越大,这对异构并行算法的设计将有很大的影响.本文主要面向一类国产复杂异构超级计算机研究 HPCG 异构
众核并行算法.首先介绍了国内外进展,然后提出两种适用于该平台的 HPCG 异构众核并行算法.对于实际使用
的第 2 种算法中,还存在图着色的问题,本文也开展了相关工作,并单独使用一节进行介绍.接下来介绍在该超级
计算机上的实现问题,包括 CPU 和 GPU 之间的任务划分、为了隐藏邻居通信实现的内外区划分方法,以及一些
稀疏矩阵重排等优化方法,最后介绍了实验结果.