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

蔡雨 等:异构 HPL 算法中 CPU 端高性能 BLAS 库优化 2295

的寄存器数[4,6,6]整除.
(3) 计算适应度(fitness)
适应度函数就是 DGEMM 测试程序,其性能作为判断适应度高低的标准.性能高的分块参数会遗传给下一
代种群,性能低的分块参数就会被淘汰.
(4) 选择(selection)
基本遗传算法仅仅使用 selection、crossover 和 mutation 这 3 种算子是没有办法收敛于全局最优解的,因为
简单地进行杂交,可能反而会把较好的组合破坏掉.本文采用精英保留策略,也就是把目前最优个体不进行任何
操作直接复制到下一代种群中.选择方法有很多种,包括比例选择法、排序选择等.本文采用比例选择法和精英
保留策略结合,种群中每一个个体的适应度占总适应度的比例越大,其被选择的概率就越大,同时这一代种群最
优秀个体无条件复制到下一代.
(5) 交叉(crossover)
单点交叉、双点交叉、均匀交叉等都适合二进制编码和浮点数编码,根据 GEMM 分块参数只有 3 个,选择
单点交叉,按某一概率将两个个体的某一位置参数互换.交叉率设置越大,新个体产生越快,其全局搜索能力就
会越强,但是优秀个体被破坏的可能性也就越高,综合考虑,设置交叉概率为 0.8.
(6) 变异(mutation)
变异的主要目的是改善局部搜索能力以及维持种群个体的多样性,变异方法采用均匀变异,按某一概率在
一个范围内随机生成一个数替换原来个体中某一位置的参数.变异概率不宜设置过大,导致丢失优秀个体而变
成随机搜索.考虑设置参数范围已经在合理范围内,本文按 0.1 的概率对每一个个体的某一参数进行变异.
(7) 终止条件判断(iteration)
种群中所有的个体适应度计算完成后要判断设置的终止条件是否满足,以判断程序是否结束退出.如果不
满足终止条件就进行 selection、crossover 和 mutation 操作,形成下一个同等规模的个体集合(种群).
Auto-tuning 自适应调优算法完成后,需要进行 DGEMM 测试,BLIS 库中 config 目录是存放不同平台 kernel
的配置信息,其中 DGEMM 分块参数通过 bli_kernel.h 头文件中的 BLIS_DEFAULT_MC_D、BLIS_DEFAULT_
KC_D 和 BLIS_DEFAULT_NC_D 这 3 个宏定义配置.
Auto-tuning 的具体测试流程如下:
(1) 在包含初始分块的更大的范围内随机生成一组满足遗传算法个体要求的分块参数[m c ,k c ,n c ],并用其替
换掉 blis_kernel.h 中的分块参数.
(2) 自动编译 BLIS 库,生成此分块参数下的动态链接库 libblis.so.
(3) 调用 libblis.so 执行测试程序 DGEMM,主程序将性能值记录并返回.
通过 Auto-tuning 的不断迭代,根据算法模型,我们会得到一个全局最优解,这组参数就是性能更高的 DGEMM
分块参数,实测数据分块参数由[1080,120,8400]优化为[792,822,8628],将这组参数替换进BLIS中,并使用高性能计
算标准测试程序 HPL 和单独的 DGEMM 测试程序进行测试,具体测试对比数据参考第 5 节性能分析.
2.3 矩阵打包

连续的内存访问比非连续的内存访问要快.异构 HPL 中传给 DGEMM 的矩阵 A、B 和 C 的索引是初始化
矩阵的某个位置指针,矩阵元素通过 leading-dimension 索引,leading-dimension 表示列优先存储方式的矩阵同一
行(或行优先存储方式的矩阵同一列)中两相邻元素的距离,也就是实际存储矩阵的二维数组的第 1 维(或第 2
维)的大小.矩阵 A、B 和 C 的行或列间跨度通过 LDA、LDB 和 LDC 表示,这 3 个数值可能会非常大.比如异构
HPL 求解问题 Ax=b,其矩阵规模 N 的最大取值可以使矩阵 A 的存储空间占用内存 80%左右,则 LDA 不能小于
N.在算法实现中,大 kernel 算法会不断地对 A 和 B 的不同分块进行打包,形成 A c 和 B c ;而小 kernel 算法只将原始
矩阵 B 进行一次打包,形成行优先存储(row-major)的 B packed .如图 5 所示,其中假设 n r 等于 6,矩阵 B 是以列优先
存储(column-major)方式存储数据,且行数 k 和列数 n 都是 n r 的整数倍.