共计 4459 个字符，预计需要花费 12 分钟才能阅读完成。
作者：于雄雄 陈其友 | 旷视 MegEngine 架构师
背景
在 CV 畛域中，卷积计算是裁减像素的感触野的无效办法，模型大多数的计算量都是卷积操作奉献的。因而在 CV 模型的推理性能优化中，最重要的一项工作是对卷积的优化。MegEngine 在长期的工业界实际和反馈的根底上总结得出卷积优化的根本办法有：
- 间接卷积计算优化
该办法的计算过程为逐通道进行卷积滑窗计算并累加，该优化办法对卷积的参数敏感，为了达到最优的性能，会依据各个卷积参数别离进行 kernel 优化，通用性弱，然而在 Depthwise 的卷积中却是最高效的办法。
- FFT 卷积计算优化
依据卷积的性质，利用傅立叶变换能够将卷积转换为频域上的乘法，在频域上的计算对应乘法，再应用傅立叶变换逆变换，就能够失去卷积对应的计算结果。该办法应用高性能的傅立叶变换算法，如 FFT，能够实现卷积计算的优化，算法性能齐全取决于傅立叶变换的性能以及相应卷积参数。
- Im2col+matmul 卷积计算优化
因为卷积计算中有大量的乘加运算，和矩阵乘具备很多类似的特点，因而该办法应用 Im2col 的操作将卷积运算转化为矩阵运算，最初调用高性能的 Matmul 进行计算。该办法适应性强，反对各种卷积参数的优化，在通道数稍大的卷积中性能根本与 Matmul 持平，并且能够与其余优化办法造成互补。
- Winograd 卷积计算优化
Winograd 办法是依照 Winograd 算法的原理将卷积运行进行转变，达到缩小卷积运算中乘法的计算总量。其次要是通过将卷积中的乘法应用加法来替换，并把一部分替换进去的加法放到 weight 的提前解决中，从而达到减速卷积计算的目标。Winograd 算法的优化局限为在一些特定的罕用卷积参数才反对。
因为 direct 卷积能够间接由公式得来，而 FFT 卷积对于以后业界用到的各种参数的卷积，其性能劣势远没有其余优化办法显著，对于这两者本文不做具体开展。这里次要讲述 Im2col 和 Winograd 算法的实现以及优化办法。
Im2col+Matmul 优化
Im2col 算法简介
Im2col+Matmul 办法次要包含两个步骤：
- 应用 Im2col 依照卷积核的须要将输出矩阵开展一个大的矩阵，矩阵的每一列示意卷积核须要的一个输出数据。
- 应用下面转换的矩阵进行 Matmul 运算，失去的数据就是最终卷积计算的后果。
具体 Im2col 的步骤如上图所示：
- 将输出数据依照卷积窗进行开展并存储在矩阵的列中，多个输出通道的对应的窗开展之后将拼接成最终输入 Matrix 的一列。
- 以卷积的 stride 为步长开展后续的卷积窗并存在 Matrix 的下一列中。
实现 im2col 的操作之后会失去一个输出矩阵，卷积的 weights 也能够转换为一个矩阵，此时对 weights 的矩阵和 Im2col 的输入矩阵进行 Matmul 计算，就能够失去最终的卷积计算结果。
算法优化
下面介绍的过程是原始 Im2col+Matmul 的过程，理论处理器在执行下面的过程中性能达不到最优，以输出 Tensor 的 shape 为 (1, IC, IH, IW)，weights 的 shape 为 (OC，IC，Fh，Fw)，输入 Tensor 的 shape 为 (1, OC, OH, OW) 为例，次要起因在于：
- Im2col 的输出 Tensor 须要的 CPU 内存大小为 IC*IH*IW，而依照下面 Im2col 之后所须要的内存大小为 IC*Fh*Fw*OH*OW，当卷积的 stride=1 的时候，Im2col 之后须要的内存比之前大很多。
- 因为 Im2col 之后的数据量比拟大，难以全副保留在 CPU 的 Cache 中，造成后续 Matmul 计算时，读取数据会存在 Cache Miss。
- Im2col 过程中会将输出进行 relayout 操作，而在后续 Matmul 的计算中，须要对该数据进行 Pack，Pack 操作会引入非必要的读写过程。影响算法理论性能。
优化 1：对 Im2col+Matmul 过程进行分块
下面提到在 Im2col 之后，耗费的内存会超过 CPU 的 Cache 的容量，为了使这部分数据可能保留在 Cache 中，须要对 Im2col+Matmul 的整个过程进行分块，每次 Im2col+Matmul 都只对一个分块进行操作，这样就能够解决内存占用过大，超过 CPU Cache 后造成 Cache Miss 的问题。
分块优化如上图所示：Im2col 每次只对 block_size 大小的数据进行计算，失去的 Fh*Fw*IC*block_size 的数据能够保留在 Cache 中。Im2col 失去数据后，对其间接进行 Matmul 计算，将计算失去的后果写入到输入 Tensor 对应的 block_size 处就能够失去该分块处卷积的计算结果。计算完该分块之后，顺次进行下一个 block_size 的计算，直到整个输出计算实现。
联合 Matmul 的相干优化常识，在进行 Matmul A*B=C 计算时将分块 Im2col 失去的数据视作 B 矩阵，A 矩阵为卷积的权重矩阵，依据 sgemm 的分块规定，以及 cache 的性质，A 矩阵会被调度并保留在 L2 上，B 矩阵基于最内层分块的一列和 A 矩阵基于最内存分块的一行以及 C 矩阵基于最内层的局部分块会被调度保留在 L1 上，因而能够通过 L1，L2 的大小以及 A 矩阵的大小，计算出所有的分块大小。上面是分块优化性能的试验后果，能够看出分块优化能无效的缩小存储应用，而且还能够晋升算子的计算性能。
优化 2：交融 Im2col 和 Matmul PACK 数据操作局部
Im2col 过程中将多个窗的开展同时进行时，实际上是对内存的 copy 以及数据的 relayout 的过程，后续 Matmul 的 Pack 操作业是对数据的 copy 的 relayout，因而能够将下面两次数据的 copy 和 relayout 进行合并优化，缩小该过程中对内存的读写次数。
如上图所示 Im2col+Matmul 的 algo 中实现了将 Im2col 和 Matmul 的 Pack 交融的优化，这样可能缩小一次数据的读写操作。因为该 fuse 过程和卷积的参数间接相干，不同的卷积参数将对应不同的交融 kernel，所以不具备通用性。通用状况下咱们会应用之前的 Im2col+Matmul 的做法，另外针对一些通用的卷积如：kernel=3×3，stride=2 等，因为参数固定，因而能够间接进行上述交融优化，利用这样的组合优化，既能够保障 im2col 算法的通用性，也能够确保大部分常见的卷积的性能。
对交融之后的卷积进行性能测试，如下所示为对应的计算吞吐：
能够看出，大多数状况下，交融之后卷积会有显著的性能晋升。
Winograd 优化
Winograd 算法简介
Winograd 算法可能优化卷积计算的乘法计算量，乘法计算量的优化原理能够参考相干论文。在此就不做过多介绍了。尽管 Winograd 能够优化乘法的计算量，然而会减少加法的计算量，优化这些加法的存在能够进一步提高 Winograd 算法的性能。如能够把一部分加法计算提前到 weights 的预处理中，能够把局部加法暗藏在 Winograd 预处理中的 relayout 中。相似这样的优化能够达到缩小卷积计算量的目标。
如下图所示为 Winograd 卷积算法的根本步骤，次要包含：
- 把输出的 feature map 和 weight 进行 Winograd 转换；
- 把转换后 feature map 和 weight 做批量 Matmul；
- 把矩阵乘的后果进行输入转换，失去最终后果。
在这些次要步骤中，要如何进行 Winograd 转换，如何 relayout，以及如何进行输入转换呢？上面以 Winograd F(2×2, 3×3) 为例，具体阐明下这些过程。
如上图所示，上半局部是 weights 的转换，下半局部是输出 FeatureMap 的转换。其中包含了 Winograd 转换以及 relayout 的过程。
对于 weights 的转换，首先通过 Winograd 变换矩阵 G 和 GT 别离将 3×3 的 weight 转换为 4×4 的矩阵，而后将该矩阵中雷同地位的点（如图中蓝色为地位 1 的点）relayout 为一个 IC*OC 的矩阵，最终造成 4×4=16 个转换之后 weights 矩阵。
对于 FeatureMap 的转换，首先将输出 FeatureMap 依照 4×4 tile 进行切分，而后将每个 tile 通过 B 和 BT 转换为 4×4 的矩阵，矩阵 B 和 BT 为 FeatureMap 对应的 Winograd 变换矩阵，而后进行与 weight 解决类似的 relayout，转换为 16 个 nr_tiles*IC 的 FeatureMap 矩阵。
如上图所示，将上述转换后两批矩阵做矩阵乘，失去 16 个 nr_tiles*OC 的矩阵，而后将雷同地位的 16 个点转换为 nr_tiles*OC 个 4×4 矩阵，再应用输入的 Winograd 变换矩阵 A 和 AT 将这些 4×4 的矩阵转换为 2×2 的输入矩阵，最初将这些矩阵写回输入矩阵中就能够失去 Winograd 卷积的最终后果。
算法优化
优化 1：weight 提前解决
在上述 Winograd 算法的根底上，鉴于模型中的权重数据在整个 Inference 的时候曾经是常量不会再扭转，因而能够在真正 Inference 之前就能够对模型进行了 weights 的转换，这样能够优化在 Inference 的时候 weights 转换的开销，特地是在 IC 和 OC 较大时，weight 转换的开销十分大，所以 weights 提前转换，尤其对 Winograd 优化特地重要，下图是 Winograd 中进行 weight 提前转换和不进行 weight 提前转换时各自的性能：
从上图能够看出 weight 转换在 Winograd 中耗时占比很大，进行 weight 提前转换能够带来很大的性能收益。
优化 2：Winograd 分块优化
上述的 Winograd 算法，还会有以下毛病：
- 输出转换须要跨 channel 读写整个 feature map，数据读写对 Cache 不敌对。
- feature map 转换之后，矩阵乘时须要再 PACK，数据访存减少。
针对这些问题，能够对 Winograd 算法的整个计算流程做进一步的优化，这些优化次要包含：
- 输出转换时，分块 feature map 的 tiles 进行分块，每次只进行肯定数量的 tiles 计算；
- 调整分块大小适配 CPU L1 Cache，使得矩阵乘不须要 PACK；
对整个输出 feature map 进行分块后，每次只计算一个分块的 nr 个 tiles，这样就能够保障每个批量矩阵的输出数据（除了转换之后的 weight 数据）保留于 L1 Cache，不会呈现 Cache miss，而且矩阵乘时不须要 PACK。
上面是分块优化前后的速度比照，能够看出分块优化对性能有显著的晋升。
总结
CPU 上 Inference 中无关卷积的优化有很多的路径，这里咱们次要介绍了 Im2col+matmul 卷积以及 Winograd 卷积中的一些进一步优化的技术手段，通过这些办法能够进一步减速卷积计算的性能，从而减速整个模型的 Inference 性能。如下图所示是 float32 的经典网络开启相干优化后，在骁龙 855 上的测试速度：
对于具体的优化细节，大家能够联合 MegEngine 的代码实现进行钻研，欢送大家提出宝贵意见。
