Parallel Multi Channel Convolution using General Matrix Multiplication 基于广义矩阵乘法的并行多通道卷积 论文详解

论文：Parallel Multi Channel Convolution using General Matrix Multiplication （基于广义矩阵乘法的并行多通道卷积）

作者：Liyu Gong，Qiang Cheng

来源：CVPR 2019

论文链接：https://arxiv.org/abs/1704.04428v2

github链接：未开源代码

CNNs是进行图片分类、视频处理的一种非常成功的机器学习技术。其主要的计算部分在于卷积层使用多个卷积核进行多通道的图片卷积计算。现有的一种使用最广泛的方法是将图片转换成向量矩阵（im2col），然后通过现有的并行广义矩阵k（GEMM）库来进行多通道多卷积核（MCMK）的卷积运算。但是im2col转换大大增加了输入矩阵的内存占用，因为它将输入图像分解成更大的列矩阵，并且im2col的数据冗余减少了数据的局部性。

文中提出了新的基于GEMM库而不是im2col，用于进行MCMK卷积计算的新方法kn2row或kn2col。这种方法对比im2col而言，提高了数据的局部性。文中已经在CPU处理器和嵌入式ARM处理器上实现了该算法的几个变体。在CPU上运行，这种算法在大多数情况下都比im2col快。

1 相关介绍

用到的一些定义

• im2col：image into a column matrix
• GEMM：General Matrix Multiplication 通用矩阵乘法
• MCMK：Multiple Channel Multiple Kernel 多通道多卷积核
• SCSK：Single Channel Single Kernel 单通道单卷积核
• MCSK：Multiple Channel Single Kernel 多通道单卷积核

Toeplitz矩阵：托普利兹矩阵，简称为T型矩阵。托普利兹矩阵的主对角线上的元素相等，平行于主对角线的线上的元素也相等；矩阵中的各元素关于次对角线对称，即T型矩阵为次对称矩阵。例如

$T=\left(\begin{array}{ccccc}{t_{0}} & {t_{1}} & {t_{2}} & {\cdots} & {t_{n-1}} \\ {t_{-1}} & {t_{0}} & {t_{1}} & {\cdots} & {t_{n-2}} \\ {t_{-2}} & {t_{-1}} & {t_{0}} & {\cdots} & {t_{n-3}} \\ {\vdots} & {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {t_{-n+1}} & {t_{-n+2}} & {t_{-n+3}} & {\cdots} & {t_{0}}\end{array}\right)$T=⎝⎜⎜⎜⎜⎜⎛​t0​t−1​t−2​⋮t−n+1​​t1​t0​t−1​⋮t−n+2​​t2​t1​t0​⋮t−n+3​​⋯⋯⋯⋱⋯​tn−1​tn−2​tn−3​⋮t0​​⎠⎟⎟⎟⎟⎟⎞​

背景

CNN要求巨大的计算量，因此充分利用可用的硬件资源是非常重要的，这些硬件资源可能是CPU、GPU、DSP或者是一些矢量架构。然而，为了更好地利用硬件来解决计算密集型问题，常常需要对代码进行仔细的调优，以便更好地利用内存层次结构、寄存器和矢量并行性。

在新的加速器或者处理器上实现CNN时，可以使用已经存在的BLAS库的GEMM程序。2D卷积可以通过将一个输入矩阵转换为Toeplitz矩阵的矩阵乘法来实现。这涉及到跨不同矩阵列多次复制图像像素。一旦构造了Toeplitz矩阵，就可以使用针对目标体系结构的高度调优的GEMM库来实现卷积。

im2col方法很成功地被应用于Caffe，Theano，Torch等DNN框架。然而，im2col的一个主要缺点是建立列矩阵时很容易引起空间爆炸。例如，一个2D$k × k$k×k的卷积核矩阵，列矩阵比原始图片大。深度学习系统通常在部署时最有用，但是列矩阵所需的空间可能太大，嵌入式系统的内存无法满足。即使在嵌入式环境之外，增加的内存需求可能会扩展片上本地内存和缓存的限制，这可能会增加执行时间和内存流量。

contributions

这篇论文提出了一种新的DNN卷积方法，它使得我们可以利用现有的优化的加速器和处理器程序，不需要代价很大的输入转换操作，具体有以下一些贡献：

• 提出了对non-replicated输入图片进行操作的问题。这使得可以将问题表示为一个或一个矩阵乘法序列
• 在嵌入式处理器(ARM®Cortex®-A57)和通用CPU (Intel®CoreTM i5-4570)上使用高度优化的GEMM并行版本对提出的方法进行了实验评估
• 新的基于GEMM的方法在大多数测试场景中都比基于im2col的表现得更好

2 CNN

多通道卷积是单通道卷积的和

一个SCSK二维卷积定义如下：
$\tag{1} conv 2 D_{x, y}(\mathcal{I}, \mathcal{K})=\sum_{i=0}^{i=k-1} \sum_{j=0}^{j=k-1} \mathcal{I}\left(x-\left\lfloor\frac{k}{2}\right\rfloor+ i,y-\left\lfloor\frac{k}{2}\right\rfloor+ j\right) \times \mathcal{K}(i, j)$conv2Dx,y​(I,K)=i=0∑i=k−1​j=0∑j=k−1​I(x−⌊2k​⌋+i,y−⌊2k​⌋+j)×K(i,j)(1)

• 输入：$\mathcal{I} \in \mathbb{R}^{H \times W}$I∈RH×W
• 卷积核：$\mathcal{K} \in \mathbb{R}^{k \times k}$K∈Rk×k
• 输出：$\mathcal{O} \in \mathbb{R}^{Q \times P}$O∈RQ×P

MCSK可以通过SCSK表示：

$\tag{2} M C S K\left(\mathcal{I}_{C}, \mathcal{K}_{C}\right)=\sum_{c=0}^{c=C-1} conv 2 D(\mathcal{I}(c), \mathcal{K}(c))$MCSK(IC​,KC​)=c=0∑c=C−1​conv2D(I(c),K(c))(2)

• $C$C表示输入和卷积核的通道数
• $\mathcal{I}(c)$I(c)表示输入的第$c$c个通道
• • $\mathcal{K}(c)$K(c)表示卷积核的第$c$c个通道

MCMK可以通过MCSK表示：

$\tag{3} M C M K\left(\mathcal{I}_{C}, \mathcal{K}_{C}^{M}\right)=M C S K\left(\mathcal{I}_{C}, \mathcal{K}_{C}^{0}\right)\|\cdots\| \operatorname{MCSK}\left(\mathcal{I}_{C}, \mathcal{K}_{C}^{M}\right)$MCMK(IC​,KCM​)=MCSK(IC​,KC0​)∥⋯∥MCSK(IC​,KCM​)(3)

• $\mathcal{K}_{C}^{M}$KCM​表示有$C$C个通道的$M$M个卷积核

im2col

im2col方法将MCMK问题转化成GEMM问题的研究已经有很多了。im2col是使用Toeplitz矩阵来实现2维MCMK的方法。实现MCMK最广泛使用的方法是im2col，但它占用了大量内存，因为它将输入图像分解成更大的列矩阵，并且由于数据冗余造成了数据局部性的降低。img2col方法如下：

• 输入：$\mathcal{I} \in \mathbb{R}^{H \times W \times C}$I∈RH×W×C
• $M$M个卷积核：$\mathcal{K} \in \mathbb{R}^{M \times k \times k \times C}$K∈RM×k×k×C
• 输出：$\hat{\mathcal{O}} \in \mathbb{R}^{H \times \bar{W} \times M}$O^∈RH×Wˉ×M

同理，可以实现im2row方法。

3 新方法

im2col是用来优化卷积运算的，它的核心是将卷积核感受野部分转化成一行（列）来存储，目的都是为了在计算时读取连续的内存，这样可以优化运算速度，减少内存访问时间。但是im2col的缺点是构造的input-patch-matrix是$k ×k$k×k维的，可能比原来的输入图片大。

一种基于GEMM的MCMK算法消除了输入中的数据重复的缺点，因此可以有效的减少在嵌入式系统中的内存限制的问题，并且可以在在任何架构提高数据局部性。但是，这种基于GEMM的MCMK算法代价是增大了输出的大小。

• 上图是一个多通道输入和多通道卷积核的卷积运算
• 此代码中没有对边缘边界进行特殊处理
• 此处卷积核大小$k=1$k=1
• 上述代码等价于一个$M×C$M×C的卷积核和一个$[C]×[H×W]$[C]×[H×W]的输入矩阵进行二维矩阵乘法，得到一个$[M]×[H×W]$[M]×[H×W]的输出矩阵
• $[M]×[H×W]$[M]×[H×W]叫做一个$M$M个通道的$[H] × [W]$[H]×[W]维的矩阵的多通道表示（multi-channel representation）

结论：一个$1 × 1$1×1的MCMK可以很简单地在没有数据重复的情况下用GEMM实现。

Kernel to Row(kn2row) and Kernel to Column (kn2col)

加深现在能够计算没有数据重复的$1 × 1$1×1的MCMK，那么如何实现$k × k$k×k的MCMK呢$(k>1)$(k>1)？
可以将$k × k$k×k的卷积分解成$k^2$k2个独立的$1 × 1$1×1的卷积之和，而求和操作的计算时间可以忽略不计。
由上面的介绍可知，一个$1 × 1$1×1的卷积可以生成一个的$[M] × [H × W]$[M]×[H×W]维的矩阵。

不能简单地将每个结果矩阵逐点相加，因为每个结果矩阵对应于$k × k$k×k的卷积核的不同值。但是，这些矩阵的加法可以通过在最终加入之前将这些矩阵的多通道表示的每个通道中的每个像素进行垂直和/或水平(行和列偏移)偏移一个或多个位置来解决。

• 例如，当计算一个$3 × 3$3×3的卷积时，计算$3 × 3$3×3的卷积核的中心点的$1 × 1$1×1MCMK的结果与最终的求和矩阵结果完全一致。
  对$3 × 3$3×3的左上角的值计算$1 × 1$1×1的MCMK在加入到最终计算$3 × 3$3×3MCMK之前必须向上偏移一个位置，向左偏移一个位置（在它的多通道表示中）。
• 注意，当$1 × 1$1×1的卷积的中间结果被偏移时，偏移后的矩阵的一些值落在最终结果矩阵的边界之外。当计算$1 × 1$1×1的卷积的和时，这些越界值被简单地丢弃。

kn2row算法

• 对核矩阵重新排序，使通道数据连续地排列，即$M$M是外部维数，$C$C是内部维数。这种数据重新安排可以提前静态地进行，并在以后在用于计算MCMK时调用。
• 使用一个GEMM调用，就可以将$\left[k^{2} \times M\right] \times[C]$[k2×M]×[C]的核矩阵和一个$[C]×[H ×W]$[C]×[H×W]的输入矩阵进行矩阵乘法运算，得到一个$\left[k^{2} \times M\right] \times[H \times W]$[k2×M]×[H×W]的输出矩阵。 - 通过在多通道表示中使用适当的偏移对大小为$M×[H×W]$M×[H×W]的$M^2$M2个子矩阵进行求和，来执行 移位-相加（shift-add） 的操作。
• 结果矩阵是一个$M×[H×W]$M×[H×W]的，就是文中MCMK算法的输出，并把这个算法叫做kn2row算法。

如果交换核矩阵的维度使得通道数$C$C不是最深的维度并且交换输入矩阵的维度，使得通道数$C$C是最深的维度，那么就可以得到kn2col算法。这个算法中的GEMM：

• 输入矩阵：$H ×W ]×[C]$H×W]×[C]
• 核矩阵：$[C] \times\left[k^{2} \times M\right]$[C]×[k2×M]
• 输出矩阵：$[H \times W] \times\left[k^{2} \times M\right]$[H×W]×[k2×M]

4. 实验结果

实验设置

• ARM® Cortex®-A57 处理器, 4核，128位宽的SIMD单元
• Intel Core i5-4570处理器，4核，256位宽的SIMD单元
• GCC version 7.1
• OpenBLAS library version 0.2.19 提供GEMM操作
• 测试的CNN架构：AlexNet，VGG-16，GoogLeNet

还和Intel’s MKL-DNN实现的卷积进行了对比，MKL-DNN支持AVX2和AVX-512处理器，并集成了一个代码生成器，该生成器为卷积生成高度优化的SIMD代码。

实验发现，文中基于GEMM的方法通常比任何直接方法都要快得多，甚至常常超过英特尔MKL-DNN生产的高度优化的代码。

性能趋势

在图5和图6中的每个图中从从左到右输入通道数量增加，但是输入的feature map在减小。

im2row的性能在数据以行矩阵布局而不是列矩阵布局时，性能比im2col更好，这种情况下使用im2row而不是im2col可以使得空间局部性得到显著改善，因为连续的patch元素在内存中是连续的。虽然im2col操作在GPU平台上表现良好，但实验结果表明，在CPU上实现卷积效果很糟糕。

基于网络中卷积层深度的所有基准测试方法之间存在很大差异。有的方法在前面的层时比较适合，有的方法在后面的层时比较适合，因此可以考虑对卷积进行一种混合实现的策略，从而可以提高卷积的峰值性能。

• 对于VGG-16的第一层来说，直接卷积是非常高性能的(图5a, 6a)，但是随着我们在网络中的深入，基于GEMM的方法很快就超越了它。这表明，使用直接卷积实现第一层，其余层使用基于GEMM的卷积，可以实现性能的峰值。
• 但是，对于AlexNet来说，情况有所不同(图5c, 6c)。在这里，基于GEMM的方法总是更快。
• 基于GEMM的方法本身也有类似的可变性;一些基于GEMM的方法非常适合前面的层，一些非常适合后面的层，但是没有一种方法在所有上下文中都有良好的性能。

相关工作

• High performance convolutional neural networks for document processing，2006-第一篇使用im2col来实现MCMK的
• Caffe:Convolutional architecture for fast feature embedding，2014-通过GPU和其他加速器用于在Caffe深度学习系统中的DNN进行了加速。现在im2col用于Caffe, Theano and Torch等深度学习框架
• cudnn: Efficient primitives for deep learning，2014-提出了一种基于im2col的基于GEMM的卷积方法
• Opencl caffe:Accelerating and enabling a cross platform machine learning framework，2016-将im2col应用于一个batch的输入图像，为多个输入图像创建列矩阵。实验发现，通过将输入矩阵大小与GEMM库的最佳大小匹配，使用批处理可以提高吞吐量
• Performance-portable autotuning of opencl kernels for convolutional layers of deep neural networks，2016-为MCMK提供一组可配置的OpenCL内核