卷积神经网络中的Winograd快速卷积算法

李拜六不开鑫

修改于 2020-04-26 16:22:01

2.2K0

修改于 2020-04-26 16:22:01

写在前面

随便翻一翻流行的推理框架（加速器），如NCNN、NNPACK等，可以看到，对于卷积层，大家不约而同地采用了Winograd快速卷积算法，该算法出自CVPR 2016的一篇 paper：Fast Algorithms for Convolutional Neural Networks。

本文将尝试揭开Winograd算法的神秘面纱。

问题定义

一个例子 F(2, 3)

1D winograd

整个计算过程在逻辑上可以分为4步：

Input transform
Filter transform
Hadamar product
Output transform

注意，这里写成矩阵形式，并不意味着实现时要调用矩阵运算的接口，一般直接手写计算过程速度会更快，写成矩阵只是为了数学形式。

1D to 2D，F(2, 3) to F(2x2, 3x3)

将卷积核的元素拉成一列，将输入信号每个滑动窗口中的元素拉成一行。注意图中红线划分成的分块矩阵，每个子矩阵中重复元素的位置与一维时相同，同时重复的子矩阵也和一维时相同，如下所示

此时，Winograd算法的乘法次数为16（上图4×4），而直接卷积的乘法次数为36，降低了2.25倍的乘法计算复杂度。

卷积神经网络中的Winograd

要将Winograd应用在卷积神经网络中，还需要回答下面两个问题：

上面我们仅仅是针对一个小的image tile，但是在卷积神经网络中，feature map的尺寸可能很大，难道我们要实现\(F(224, 3)\)吗？
在卷积神经网络中，feature map是3维的，卷积核也是3维的，3D的winograd该怎么做？

第一个问题，在实践中，会将input feature map切分成一个个等大小有重叠的tile，在每个tile上面进行winograd卷积。

第二个问题，3维卷积，相当于逐层做2维卷积，然后将每层对应位置的结果相加，下面我们会看到多个卷积核时更巧妙的做法。

这里直接贴上论文中的算法流程：

整体仍可分为4步，

Input transform
Filter transform
Batched-GEMM（批量矩阵乘法）
Output transform

算法流程可视化如下，图片出自论文Sparse Winograd Convolutional neural networks on small-scale systolic arrays，与算法对应着仔细推敲还是挺直观的。

An overview of Winograd convolution layer

注意图中的Matrix Multiplication，对应3维卷积中逐channel卷积后的对应位置求和，相当于\((m+r-1)^2\)个矩阵乘积，参与乘积的矩阵尺寸分别为\(\lceil H / m\rceil\lceil W / m\rceil \times C\)和\(C \times K\)，把Channel那一维消掉。

总结

Winograd算法通过减少乘法次数来实现提速，但是加法的数量会相应增加，同时需要额外存储transform矩阵，随着卷积核和tile的尺寸增大，就需要考虑加法和存储的代价，所以一般Winograd只适用于较小的卷积核和tile（对大尺寸的卷积核，可使用FFT加速），在目前流行的网络中，小尺寸卷积核是主流，典型实现如\(F(6\times 6, 3\times 3)\)、\(F(2\times 2, 3\times 3)\)等，可参见NCNN、FeatherCNN、ARM-ComputeLibrary等源码实现。
就卷积而言，Winograd算法和FFT类似，都是先通过线性变换将input和filter映射到新的空间，在那个空间里简单运算后，再映射回原空间。
与im2col+GEMM+col2im相比，winograd在划分时使用了更大的tile，就划分方式而言，\(F(1\times 1, r\times r)\)与im2col相同。