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

2020-04-26 16:22:01 浏览数 (1)

目录

  • 写在前面
  • 问题定义
  • 一个例子 F(2, 3)
  • 1D winograd
  • 1D to 2D，F(2, 3) to F(2x2, 3x3)
  • 卷积神经网络中的Winograd
  • 总结
  • 参考

博客：blog.shinelee.me | 博客园 | CSDN

写在前面

随便翻一翻流行的推理框架（加速器），如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，与算法对应着仔细推敲还是挺直观的。

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

总结

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

参考

  • arxiv: Fast Algorithms for Convolutional Neural Networks
  • video: Fast Algorithms for Convolutional Neural Networks by Andrew Lavin and Scott Gray
  • video: Even Faster CNNs Exploring the New Class of Winograd Algorithms
  • arxiv: Sparse Winograd Convolutional neural networks on small-scale systolic arrays
  • ARM-software/ComputeLibrary
css 卷积神经网络 编程算法 机器学习 神经网络

0 人点赞