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

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

2 国内外进展介绍

HPCG 的优化工作主要是针对热点函数 SpMV 和 SymGS 来开展.SpMV 的性能与存储格式以及计算方式
[7]
有关.Bell 等人 在 GPU 平台上实现了常用的 CSR、COO、ELL 等基本格式,提出了一种新的 HYB 格式来提
高 SpMV 的性能,并分析了不同矩阵适合使用的格式以及并行方法.另外,还有一些其他格式包括 ELLPACK-
[9]
[8]
R 、BRC 、BCCOO [10] 等被提出.还有一些学者研究稀疏矩阵的重排技术 [11] 及压缩格式 [12] ,以减少访存开销.
在计算方式方面,Williams 等人 [13] 在多种不同架构的多核平台上使用了线程分块、缓存分块、向量化等优化手
段,并取得了很好的结果.另外还有学者研究自动调优技术 [14] ,通过分析稀疏矩阵的特征来选择参数以提升
性能.
SymGS 的求解过程类似于稀疏三角解法器,其关键是如何在这种强依赖的限制下获得并行度.研究人员已
经提出了很多不同的并行方法,如 Park 等人 [15] 提出了 level scheduling 方法,这种方法使用层次遍历稀疏矩阵对
应的有向无环图,保证每一层的节点间没有依赖关系,从而可以并行更新.但是这种方法获得的并行度不高,且
各层之间的负载不均衡.Iwashita 等人 [16] 提出了适合结构化稀疏三角求解器问题的分块图着色技术,这种方法
以块为单位对图进行着色,保证一个块与其相邻块颜色不同,相同颜色的块一起执行.这种方法虽然会破坏部分
依赖,但是可以获得较大的并行度.
HPCG 的整体优化工作也受到了很多研究者们的关注.Kumahata 等人 [17] 在基于 CPU 的日本超级计算机 K
上的 HPCG 优化工作使用了分块图着色排序来挖掘 SymGS 中的并行度,并通过改变反向更新时的计算顺序来
提高 cache 命中率,在 82 944 个 CPU 上取得了 0.461 PFLOPS 的成绩,达到整机峰值性能的 4.34%.Phillips 等人 [18]
在 NVIDIA GPU 平台上使用图着色方法对 SymGS 进行并行.刘益群等人 [19,20] 基于天河 2 号超级计算机的特征
提出了混合的 CPU-MIC 协作的异构计算方法,通过区域划分充分利用 CPU 与 MIC 的计算资源,在整机
16 000 个节点上取得了 0.623 PFLOPS 的性能,位列 2014 年 11 月排行榜第一名.敖玉龙等人 [21] 设计了基于申威
架构的并行算法,该算法使用分块着色的方式挖掘 SymGS 中的并行度,并使用神威特色的片上寄存器通信机制
优化了核间的数据交换,在 163 840 个节点上取得了 0.481 PFLOPS 的性能.Ruiz 等人 [22] 基于 ARM 平台研究了
多色重排和分块多色重排两个算法的性能,并从 cache miss 等角度进行了分析.目前世界排名第一的是 IBM 研
制的超级计算机 Summit,其 HPCG 性能达到了 2.92 PFLOPS,是整机峰值性能的 1.5%,但目前还没有相关文献详
细介绍其并行算法和优化技术.面向一类国产复杂异构系统研制众核并行版 HPCG 软件,且峰值性能和整机效
率达到或超过 Summit 的水平,是一项具有巨大挑战的工作.

3 异构众核并行算法设计

GPU 是最近十几年被广泛使用的高性能计算机加速部件.一个 GPU 由多个计算单元(computing unit,简称
CU)组成,每个 CU 里有多个 SIMD,可以同时进行多路向量运算.CU 内部具有高速的软件可控缓存 LDS(local
data share).所有 CU 共享 L2 cache 和设备内存.程序运行时组织成多个 workgroup,每个 workgroup 可包含一个
或若干个 wavefront.每个 workgroup 只能在一个 CU 上运行,在我们使用的平台上,每个 wavefront 包含 64 个线
程,一个 workgroup 内所包含的线程数不能超过 1 024 个.在这种高并行度的复杂架构上并行和优化 HPCG,是一
个非常大的挑战.在并行算法层面,不仅要求高并行度,还要求整体迭代次数不能有较大增长.在优化方面,不仅
要从算法层面尽量减少访存和通信,并将通信与计算重叠,还需要充分利用硬件的特性减少访存开销.
3.1 分块着色+level scheduling算法
3.1.1 基本算法
如第 2 节所述,HPCG 中 SymGS 模块的经典优化方法包括点着色方法、按层计算方法(level scheduling)以
及分块着色算法等.考虑计算平台的特点及收敛速度的需求,我们选择了分块着色算法作为程序的基本框架.我
们将 SymGS 和 SpMV 等基本算子在分块着色算法的基础上进行并行化,并提出了针对 GPU 异构平台的优化
方法.