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

2346 Journal of Software 软件学报 Vol.32, No.8, August 2021

进行相加.这种方法保证对矩阵 A 的读取都是连续访存(coalesced access),因而能够充分利用内存带宽.
对 SymGS 函数,我们对每一 level 采用类似的方式在一个 workgroup 内运行.这就需要对整个矩阵进行重排,
使之在计算开始之前,就按分块之后所需要的顺序排列好.在 SymGS 函数被调用时,矩阵 A 也能实现连续访存.
由于 level 内并行度较小,我们将 workgroup 大小定为一个 wavefront 的大小,即 64 线程.
在进行归约操作时,我们通过实验不同的归约方法,选出了一种尽量充分利用处理器单元的方式.
3.2 分块图着色算法
由于 HPCG 采用 27 点 stencil 格式进行离散,第 3.1 节分块方式使得每个子块内部网格点依赖关系比较强,
只有严格保持其依赖关系整个问题才能收敛.而上一节提到,块内采用 level scheduling 的并行方式不能有效
利用硬件资源,所以本节提出一种新的分块图着色算法,如图 6 所示.将网格 y 方向一条作为一个块进行处理,
这样块内依赖较少,可以对其进行并行计算,同时块内向量 x 可以进行重用,以提升访存带宽利用率.将所有子
块进行着色,每一个颜色的子块并行执行.着色方案需要精细设计,以确保整个算法可以以较少的迭代次数收
敛,从而提升整体性能.

Fig.6 Blocked graph coloring algorithm
图 6 分块图着色算法
该方案可以实现两级并行:同色子块并行执行和子块内部网格点并行执行.这样可以更好的利用 GPU 的硬
件资源,充分发挥硬件的性能.同时块内可以利用 LDS 对向量 x 进行重用,从而减少向量 x 从设备内存访存的次
数,提升访存带宽利用率.
4 图着色算法研究

第 3.2 节的方案中需要对所有子块进行着色,且着色算法对整个 HPCG 的迭代次数有很大的影响.本文首先
尝试了国际上著名的并行图着色算法 JPL [24] 、CC [25] 等,基于国产处理器进行了并行实现并将其运用于 HPCG
中.对 JPL 算法,本文尝试了贪心着色策略和随机着色策略.对 CC 算法,本文也进行了多种尝试,如每轮迭代的遍
历次数选为 1,2,3,13,27 这 5 种.对于 256×256×256 的测试规模,迭代次数介于 58~67 之间,且最低迭代次数时颜
色数为 70.这些算法的测试结果无论颜色数还是迭代次数都偏高.
经过分析可知,传统的 JPL 和 CC 算法只考虑一层依赖,即着色时每个网格点只考虑其周围最临近网格点
的依赖关系,而实际上依赖关系是会传递的,如图 7 中,1 号点和 2 号点有依赖,2 号点和 3 号点有依赖,则 1 号
点和 3 号点也有依赖.考虑这种依赖传递将有可能在并行算法中保持更多的依赖关系,从而降低迭代次数.为
了降低迭代次数的同时减少颜色数(增加并行度),本文还考虑了 x,y,z 这 3 个方向的差异,设计了一些实验,验
证了这 3 个方向有一个为强依赖方向,其他两个为弱依赖方向.对强依赖方向使用较多的颜色,对弱依赖方向
使用较少的颜色,期望整体颜色数尽量减少.最终本文使用了 33 色对整个网格进行着色.经测试,对于 256×
256×256 规模,单进程运行时迭代次数为 55 次,相比于 JPL 和 CC 算法的最少迭代次数降低了 3 次,即整体性
能可提升 6%.