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

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

分块着色算法的基础是将三维网格分块,然后对每一个数据块进行着色.在预条件子中使用的四重网格里,
每一层网格都需要分块及着色.参考文献[21]的工作,我们选取了类似的分块着色算法,既方便数据在 GPU 上的
分配,又保证了较高的并行度,且不会大幅度增加迭代次数.如图 4 所示,三维空间中相邻的 8 个数据块使用 8 种
不同的颜色,每次 SymGS 计算时,同样颜色的数据块被同时处理.

Fig.4 Block coloring algorithm
图 4 分块着色算法
3.1.2 数据及任务映射
块内 SymGS 需要严格保持依赖关系,否则迭代次数将大幅度上升.因此,本文采用 level scheduling 算法进行
并行,方程 4x+2y+z=k 所定义的平面上的点都可以算作一层(每个点的坐标为(x,y,z)),因为它们所依赖的数据都
已经计算完毕.如图 5 所示,从上到下是时间轴,第 1 个点的计算不需要本次迭代的任何数据,可以在此数据块处
理过程的第 1 次迭代进行更新;然后,下一个点仅依赖于第 1 个点,而第 1 个点已经有最新数据,因此第 2 个点可
以进行计算,此为第 2 层;再然后,我们可以分析出第 3 层,第 4 层,...,直到整块数据被处理完.依照这种排序,每层
数据的更新可以并行操作.通过实验不同的块大小,我们选出能够适应高速缓存 LDS 大小且保证一定的块间及
块内并行度的分块方案.

Fig.5 Data dependence and levels inside a block
图 5 块内数据依赖及分层
3.1.4 SymGS 内核优化
在分块着色+块内 level scheduling 算法的基础上,我们对 SpMV 和 SymGS 的内核函数进行了优化.SpMV
函数的优化参考文献[23]的方法,每线程计算一个双精度乘法,将中间结果保存在 LDS 中,然后将 LDS 中的乘积