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

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

4.3 并行化问题
多线程并行化并不是总会对计算带来帮助,为了进一步提高性能,需要综合考虑以下问题.
(1) 动态多线程
创建和启动多线程的开销在计算量很小的情况下会变得突出,从而导致程序性能下降.所以需要设置一个
或多个特定的阈值来进行线程数的切换.具体是设置一个阈值将多线程直接切换到单线程,还是设置多个阈值
将线程数分段递减,需要具体的 BLAS 函数结合特定的输入数据进行大量的测试归纳(profiling).在 DGEMM 的
多线程优化中,我们设计了精确的运算量模型.DGEMM 需要计算一个 m×k 阶矩阵 A 和 k×n 阶矩阵 B 的乘积,
其主要计算量和乘积 mkn 成正比.考虑到矩阵 A 的规模 m·k,矩阵 B 的规模 k·n 等都对最终运算性能造成影响,
我们使用最小二乘法拟合矩阵计算的性能公式,假设不同线程数目下运算时间根据式(2)计算.
T = a mkn a mk+ + a mn a nk+ + a m a n a k+ + + a (2)
1 2 3 4 5 6 7 8
于是对于输入参数为 m i 、k i 和 n i ,运行时间为 t i 的测试数据,对应拟合数据中的一行如式(3)所示.
,
,
,
(m k n m km n n km i , , ,1n k i ) (3)
,
i i
i i
i
i i i
i i
所有这些拟合数据组成 N×8 阶矩阵 P,其中 N 是采样数,而所有的采集时间构成对应的列向量 b,于是构成
式(4)的拟合方程.
T
T
P Px = P b (4)
解方程得出的 8 阶变量 x 的各分量就是 a 1 ,a 2 ,…,a 8 的最小二乘拟合结果.分别对单线程、4 线程、8 线程和
32 线程测试拟合公式,在运行中根据拟合结果动态切换线程数据,得到如图 10 所示的性能结果.

Fig.10 Performance speedup of DGEMM in 32 threads
图 10 DGEMM 在 32 个线程中的性能加速比

实践中还发现,不同的 kernel 实现方式以及硬件设置等因素也会影响到阈值的选取.比如,在异构 HPL 的
DGEMV 函数的优化过程中,根据不同的“OMP_NUM_THREADS”、不同的 CPU 主频以及矩阵 A 的列数 N(M
方向做并行)设置不同的多个阈值.
(2) 均衡余量(remainder)处理
当使用多线程将求解问题切分成多块后,往往会遇到不能均分的情况.所谓不能“均分”,是指整体的运算量
不能均匀地分配到每个线程中去.此时有两个选择:或者将所有多出的运算量全部放到某一个线程中,比如最后
一个线程;或者将余量再次均分到所有线程中.Remainder 处理的问题在线程数较少时(比如 6 个线程)不会那么
关键,但在线程数较多时(比如 32 个线程)会变得突出.因为此时的木桶效应更加明显,整体运算的同步结束取决
于拥有最大余量的那个线程.根据本文 HPL 算法测试分析后,采取了将 remainder 分配给每个线程处理,得到的
性能结果最优.
(3) 循环展开与多线程的均衡
循环展开的程度和线程的数量需要均衡考虑.在使用动态多线程去加速运算的过程中,往往会有多种求解
方法去完成同一个运算.考虑以下场景:异构 HPL 中的 DGEMM 运算在 M 较小时,比如 M=28,此时可以使用 4
个线程各处理 6 个 M 维度的行,然后使用 1 个线程处理剩下的 4 个 M 行;或者使用 5 个线程各处理 5 个 M 维
度的行,然后使用 3 个线程处理各处理一个 M 行,如式(5)所示.