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

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

2.2 Auto-tuning自适应分块参数调优
DGEMM 计算量大,计算访存比高,除上述 kernel 算法层面的优化外,对 BLIS 框架内矩阵分块参数进行优化
还可以提高 cache 命中率,提高性能.矩阵乘法循环分块的大小是通过 BLIS 库中 DGEMM 的分块参数来决定的,
分块参数的选择可以影响 cache 命中率,不合适的参数可能导致流水线停顿,从而使 DGEMM 性能下降.因此,
DGEMM 分块参数的选择至关重要.BLIS 中 DGEMM 分块是通过开发人员的经验和测试选择的一组数值,手动
测试不能保证测试覆盖率,也不能保证得到的是最优解.因此本文采用了 Auto-tuning 遗传算法自适应调优技术,
更高效地优化 DGEMM 分块参数.
遗传算法基本算法思想是从可能具有潜在解集的一个种群开始的,种群是基因编码后形成的一组个体集
合,在这个种群基础上通过选择(selection)、交叉(crossover)和变异(mutation)操作,优胜劣汰,不断地进化出最优
的个体.Auto-tuning 自适应调优就是应用遗传算法对 DGEMM 分块参数进行智能优化选择,将分块参数作为个
体,一定范围内的多个个体形成一个种群进行自适应迭代进化,从而针对具体平台体系结构产生最优的
DGEMM 矩阵分块参数.文献[29]在 Intel 平台上对遗传算法在 DGEMM 的分块参数智能优化选择上的实现做
了详细介绍.如图 4 所示是遗传算法的基本流程.
• 首先初始化种群,以分块参数[m c ,k c ,n c ]为一个个体,随机生成一组个体的集合.
• 然后计算种群每个个体的适应度,适应度大小决定遗传概率.
• 接着判断迭代次数,如果没有达到预设的最大值,则进行 selection、crossover 和 mutation 的遗传算法进
化步骤.
• 最后,经过 selection、crossover 和 mutation 这 3 个步骤后生成一个新的种群,与原始种群大小一致,但
个体都经过优胜劣汰,进化到了更好的水平.重复上述步骤,直到满足终止条件退出.

Fig.4 Generic algorithm flow chart
图 4 遗传算法流程图

根据上述遗传算法的介绍,自适应程序的实现需要经过编码个体、建立种群、计算适应度、选择(selection)、
交叉(crossover)、变异(mutation)和终止条件判断这几个步骤.
(1) 个体编码
编码方法有二进制编码、格雷编码、浮点数编码和符号编码等多种方式,根据 DGEMM 分块参数特点,采
取浮点数编码更适合.也就是将分块参数[m c ,k c ,n c ]这 3 个浮点数直接作为参数传入.
(2) 建立种群(population)
个体集合的建立过程就是要在一个确定范围内去随机生成一定数量的个体.种群范围的确定可以根据
[7]
cache 的大小进行理论计算得出 ,HBLIS 分块参数原始值是[1080,120,8600],在原始参数值的基础上扩大范围
至[512<m c <2400,60<k c <2400,4800<n c <12000],随机生成的分块参数要保证能够被内核参数整除,也就是被分配