WinoGrad算法

WinoGrad论文

计算背景-卷积计算方法

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

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

什么是WinoGrad？

在一维卷积中它指出，对于输出个数为m，参数个数为r的FIR滤波器，不需要m×r次乘法运算，而只需要u(F(m,r)) = m+r-1次乘法计算即可。F(m,r)其中m是Output Size，r是Filter Size，卷积运算是对应位置相乘然后求和，输入信号每个位置都要进行至少一次的乘法，所以乘法数量最少与输入信号长度相同，即m+r-1次。

对于二维卷积，即在行列上分别进行一维卷积运算，F(m×n，r×s)，输出为m×n，卷积核大小为r×s，输入信号为(m+r-1)(n+s-1)，乘法数量至少为u(F(m×n,r×s))=u(F(m,r))u(F(n,s))=(m+r−1)(n+s−1)。如果安装滑动窗口计算卷积，一维时需要m×rm×r次乘法，二维时需要m×n×r×s次乘法。使用Winograd算法计算卷积乘法数量减少至(m+r−1)或(m+r−1)(n+s−1)。

案例

在神经网络推理阶段，卷积核上的元素是固定的，因此g上的运算可以提前算好，预测阶段只需计算一次，可以忽略，所以一共所需的运算次数为d与m上的运算次数之和，即4次乘法和8次加法。与直接运算的6次乘法和4次加法相比，乘法次数减少，加法次数增加。在计算机中，乘法一般比加法慢，通过减少减法次数，增加少量加法，可以实现加速。

1D WinoGrad

1D to 2D，F（2，3） to F（2×2，3×3）