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

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

6 HPCG 优化方法

6.1 稀疏矩阵存储格式
HPCG 参考版本里矩阵存储采用的是 CSR 格式,如图 9 所示,矩阵的非零元素和其对应的列索引分别存放
在各自的数组里,并用一个指针数组记录每一行的起始位置.这样数据的内存分配比较离散,局部性不高.为了
解决这个问题,我们采用了如图 10 所示的 ELL 格式,按照矩阵中非零元最多的行对其他行进行填充,使每行的
长度一样,这样数据在内存中占据了一块连续的空间,在知道这个长度和矩阵起始地址的情况下可以算出每一
行的起始位置,节省了 CSR 格式中每行起始位置的索引数组.

Fig.9 Storage format used by the reference version of HPCG
图 9 HPCG 参考版使用的存储格式

Fig.10 Optimized ELL format
图 10 优化 ELL 格式

对规模为 256×256×256 的矩阵而言,总非零元个数为 450 629 374,CSR 格式总存储量为 5.20 GB,ELL 格式
总存储量为 5.06 GB,减少了 3%.
6.2 稀疏矩阵重排
由于使用了分块图着色算法,相同颜色块一起计算,而在原存储空间中,相同颜色的块都是不相邻的,这样
无法充分利用 L2 Cache,因此,我们根据分块着色的结果对矩阵进行了重排,如图 11 所示,我们将相同颜色的块
放在一起,进一步提高数据局部性.相应的,我们对解向量 x 和右端项 y 也做了同样的重排.

Fig.11 Blocked graph coloring and reordering
图 11 分块图着色以及重排