Page 100 - 《软件学报》2024年第6期

2676 软件学报 2024 年第 35 卷第 6 期

基于上述对一个优化算法理论总开销的建模方式, 进一步提出优化加速比的概念, 以综合比较不同优化算法
所带来的性能差异, 并作为 AutoConfig 选择最优算法的依据. 优化加速比的定义是: 相对于某个基准算法, 在相同
的编译优化流程和硬件执行环境下, 优化算法的理论总开销与基准算法的比值. 具体而言, 对于优化算法 A 和优化
算法 B 而言, A 相较于 B 的优化加速比可表示为:

Cost A
SpeedUp = All (3)
All B
Cost
All
在优化分析时, 还可以在计算、访存、特殊指令等不同方面定义局部优化加速比 SpeedUp Arith 、 SpeedUp Memory
和 SpeedUp SpecIns , 它们能够帮助分析不同算法在不同方面的优劣情况. 以计算方面为例, 当 A 和 B 两种算法的计算
开销重要性系数保持一致时, 其局部优化加速比可表示为:

Cost A λ Arith FPO A FPO A
SpeedUp = Arith = = (4)
Arith B B B
Cost λ Arith FPO FPO
Arith
此时通过分别统计两种算法的浮点运算指令个数, 就可以求得两者在计算方面的局部优化加速比. 第 4.2 节
会借助该指标来探究不同算法在计算、访存方面的优化表现.

4.2 算法特性分析

4.2.1 标量算法与向量算法的特性分析
矩阵乘法是一种典型的深度学习计算负载. 设两个输入矩阵分别为 M × K 的矩阵 A 和 K × N 的矩阵 B, 输出
M × N 的矩阵 C, 下面基于优化分析模型, 对朴素的标量算法和向量化的 Broadcast 算法做建模分析.
矩阵为
标量算法采用 3 层嵌套循环完成计算逻辑, 总的循环次数为 MNK . 在每一次循环中, 会进行一次 FMA 操作,
MNK . 此外在每一次循环中, 默认会涉及到对矩阵 和 各一次的读操作和对
因此其浮点运算指令个数为 A、B C
矩阵 C 的一次写操作, 但是在实际实现时可以把对矩阵 C 的读和写操作提取到长度为 K 的内层循环外面, 因此内

存访问指令个数为 2MN +2MNK . 标量算法没有特殊指令执行开销.
基于 Broadcast 算法的向量化实现可通过参数 vs 来调节向量化长度, 以对长度为 N 的最内层循环做向量化.
1 1
在 Broadcast 算法中, 总的循环次数为 MNK , 因此浮点运算指令个数为 MNK , 每个 FMA 操作同时对 vs 个
vs vs
元素进行乘加运算. 在进入最内层循环之前, 需要使用一种标量广播的特殊指令将矩阵 A 的单个元素广播成长度
MK 次. 在每次运算的过程中, 分别需要对矩阵 B 和 C vs 的向
为 vs 的向量数组, 该指令共需调用 进行一次长度为
量读操作, 将其与广播后的向量数组进行乘加运算, 并在最内层循环结束后将结果向量写回矩阵 C. 因此该算法的
1
内存访问指令个数为 MK +3MNK .
vs
设将向量化长度设置为 vs 时, 执行一条向量 FMA 指令的计算开销为 Cost FMA [vs] , 以向量数组的形式访问内
vs = 1 时的向量操作, 则对标量算法与向量算法的特性分析结果
存的访存开销为 Cost Memory [vs] , 将标量操作视为
如表 1 所示. 从中可以看出, 向量算法通过引入了特殊的广播指令并改变了原先的访存模式来为向量化提供优化
vs 过大时, 一方面负载的输入尺寸规模可能较小, 可向量化的空
空间. 一般来说 vs 越大, 则向量化越充分. 但是当
间不足. 另一方面向量化所带来的计算便利可能难以弥补寄存器溢出的开销. 因此硬件平台信息会对向量化长度
的配置形成约束, 而基于优化分析模型也容易探究不同向量化长度对算法在计算、访存等方面上的影响.

表 1 标量算法与向量算法的特性分析

分类 标量算法 向量算法 局部优化加速比
1 1 Cost FMA [vs]
浮点运算指令个数 MNK MNK ×
vs vs Cost FMA [1]
1
1 K +3NK
内存访问指令个数 2MN +2MNK MK +3MNK vs Cost Memory [vs]
vs ×
2N +2NK Cost Memory [1]
特殊指令个数 0 MK ∞