0%

卷积计算优化方法：Winograd

发表于 更新于 分类于 阅读次数：
本文字数： 2k 阅读时长 ≈ 3 分钟

在卷积网络中，大部分的计算耗费在计算卷积的过程中，尤其是在端上设备中，对于性能的要求更为苛刻。程序的性能优化是一个复杂而庞大的话题。高性能计算就像系统设计一样，虽然有一些指导原则，但是，对于不同的场景需要有不同的设计方案，因此，对于同一个优化问题，不同的人可能会给出完全不同的优化方案。本文不是探讨硬件和代码级的优化，仅针对计算卷积的一个特定方法 —— Winograd 方法做一个简单的记述。

卷积计算方法

首先明确一点，这里说的卷积计算是指深度学习卷积网络（ConvNet）的计算方式，而不是高数中的卷积计算。目前常见的计算卷积的方式主要有以下集中方法：

  1. 滑动窗口：这种方法就是基本的计算方式，但是计算比较慢，因此一般不采用这种方法。
  2. im2col：目前几乎所有的主流计算框架包括 Caffe, MXNet 等都实现了该方法。该方法把整个卷积过程转化成了 GEMM 过程，而 GEMM 在各种 BLAS 库中都是被极致优化的，一般来说，速度较快。可以参考这篇文章：Caffe中的底层数学计算函数
  3. FFT: 傅里叶变换和快速傅里叶变化是在经典图像处理里面经常使用的计算方法，但是，在 ConvNet 中通常不采用，主要是因为在 ConvNet 中的卷积模板通常都比较小，例如 3×3 等，这种情况下，FFT 的时间开销反而更大。
  4. Winograd：Winograd 是存在已久，但是最近被重新发现的方法，在大部分场景中，Winograd 方法都显示和较大的优势，目前 CUDNN 中计算卷积就使用了该方法。

Winograd 方法

Winograd 方法简单来讲，就是用更多的加法计算来减少乘法计算。因此，一个前提就是，在处理器中，乘法计算的时钟周期数要大于加法计算的时钟周期数。

Winograd 计算卷积需要完成的乘法的次数为:

$r \times s$ 表示卷积核的大小，$m \times n$ 表示输出大小，根据这两个参数一般可以推算输入大小。

做一个简单的对比计算：假设卷积核大小为 $3 \times 3$，输出大小为 $2 \times 2$，那么，窗或者 im2col 需要的乘法计算次数为：$3 \times 3 \times 2 \times 2 = 36$，Winograd 需要的乘法计算次数为：$(3+2-1) \times (3+2-1) = 16$。可以看出，Winograd 的乘法次数大大减少，相应的加法次数增加了，但是绝大部门平台上，乘法的耗费大于加法，因此可以加速。

Winograd 的证明方法较为复杂，要用到数论中的一些知识，但是，使用起来很简单。只需要按照如下公式计算：

其中，$\odot$ 表示按元素乘，$A, G, B$ 表示根据输出大小和卷积核大小不同有不同的定义，并且是提前确定了的。每种输出大小和卷积核的 $A, G, B$ 具体是多少可以通过这种方法计算，$g$ 表示卷积核，$d$ 表示要进行卷积计算的数据，$g$ 的大小为 $r \times r$，$d$ 的大小为 $(m+r-1) \times (m+r-1)$。

以上描述的 Winograd 算法只展示了在二维的图像 (更确切的说是 tile) 上的过程，具体在 ConvNet 的多个 channel 的情况，直接逐个 channel 按照上述方法计算完然后相加即可。

实践经验

但是 Winograd 应用也有一些局限：

  • 在目前使用越来越多的 depthwise conv 中其优势不明显了。
  • 在 tile 较大的时候，Winograd 方法不适用，因为，在做 inverse transform 的时候的计算开销抵消了 Winograd 带来的计算节省。
  • Winograd 会产生误差，这个一定要注意，要做好相应的精度损失测试。

参考资料