date: 2019/08/21


Winograd算法最早于1980年由Shmuel Winograd在《Arithmetic complexity of computations(1980)》中提出,主要用来减少FIR滤波器的计算量。

该算法类似FFT,将数据映射到另一个空间上,用加减运算代替部分乘法运算,在“加减运算速度远高于乘法运算”的前提下达到明显的加速效果(与FFT不同的是,Winograd将数据映射到一个实数空间而非复数空间)。

比如,

直接实现一个输出、参数的FIR滤波器 ,一共需要次乘法运算;

但使用Winograd算法,忽略变换过程的话,仅仅需要次乘法运算。


F(2,3)

如果直接计算F(2,3)

其中,

为连续的两个输入序列;

为FIR的三个参数;

这个过程一共需要6次乘法,和4次加法


而Winograd算法指出,F(2,3)可以这样计算

其中,


该用矩阵运算可以表示成:

其中,表示点乘,而


这……似乎反而把问题变得十分复杂,但实际上它的计算量却真真切切地减少了——

  1. 由于是固定的FIR滤波器参数,那么可以提前计算并得到一个的列向量
  2. 由于是变化的输入序列,所以每次计算FIR的时候都需要对输入做一个变换,得到一个的列向量,这个过程需要4次加法(注意矩阵的元素值)
  3. 然后进行点乘,共计4次乘法
  4. 最后做乘法,共计4次加法


过程1可以提前完成,变换过程2和计算过程3、4共计4次乘法和8次加法,相比于直接FIR的6次乘法、4次加法,乘法次数下降为原来的(推广到一般情况,直接FIR跟Winograd的乘法次数分别是)。

但天下没有免费的午餐,既然速度得到提升,那么肯定需要付出代价——算法的加速往往是需要以额外的空间为代价的:原先FIR只需要存储3个参数,但现在需要存储4个参数(推广到一般情况,分别是);


F(2x2, 3x3)

参考arm的一份幻灯片:Even Faster CNNs: Exploring the New Class of Winograd Algorithms


接下来我们将一维的扩展到二维的,有两种扩展方式,一是通过堆叠来实现,二是通过嵌套来实现。后者计算量减小幅度更大,但前者占用内存更少。以k3s1的卷积为例——

为了跟幻灯片的符号统一,在这一部分中用来表示输入,表示权重,表示输出

conv_k3s1.jpg


对直接卷积来说,该过程一共需要36次乘法和32次加法。


参考Even Faster CNNs: Exploring the New Class of Winograd Algorithms,将输入按滑窗分块后展开成向量并堆叠成矩阵,将权重展开成向量——

F_2x2_3x3_1.jpg


对矩阵和向量进行分块——

F_2x2_3x3_2.jpg


堆叠实现

其中,对应的输入序列,也即卷积输入的第


也就是说,在这里分成了6次以及4次额外的加法,总计24次乘法和44次加法(注意:虽然这里做了6次但是输入序列的变换只需要做4次,所以加法次数是44次而非52次),相比于直接卷积的36次乘法和32次加法,乘法次数跟一维的一样,也下降为原来的,同理也需要付出3倍于额外的空间代价(三个


嵌套实现

参考:《卷积神经网络中的Winograd快速卷积算法 | shinelee, 博客园

也即,

其中,


同理,可以推导出,需要 16次乘法和56次加法过程32次加法、过程16次乘法、过程24次加法),相比于直接卷积的 36次乘法和32次加法,乘法次数下降为原来的。计算量的减少比堆叠实现要明显,但也需要更多的额外空间代价:直接计算只需要存储9个参数的则需要存储16个参数的(推广到一般情况,分别为)  


后续讨论中,如非特别说明,二维Winograd均指的是嵌套实现。


G、BT、AT

Winograd算法需要推导出相应的变换矩阵,但具体的推导过程似乎有些复杂,我现在还没弄懂。所幸 wincnn | github提供了一个解算的工具,除了前述的,常用的还有,它们对应的变换矩阵如下:


注意:与不同,由于出现了非的元素,所以除了点乘过程,还会引入额外的乘法运算。


变换过程的计算优化

的变换矩阵相当有规律,无论是输入、输出还是权重的变换都有多的中间结果能够被复用;

为例,我们将一些相关联的元素标上颜色——

F43_trans_matrix.jpg


/



以下“运算”指乘加运算——包括加法(、乘法(

实际包含两次乘法和一次加法即3次乘加运算


总计12次运算,总计8次运算,总计10次运算。      

扩展到二维,总计次运算,总计次运算,总计次运算。  


论文《Fast algorithms for convolutional neural(CVPR2016)为13次,可能是由于的计算过程不同导致的,

如果按上述过程计算,会多出一次乘加运算。


同理,对于

F63_trans_matrix.jpg

总计26次运算,总计13次运算,总计20次运算。      

扩展到二维,总计次运算,总计次运算,总计次运算。 

complexity.jpg



计算复杂度分析

假设输入特征图与输出特征图大小一致,均为,卷积输入通道数、输出通道数,批大小为

点乘的乘法复杂度为:


变换过程的运算复杂度为:


归一化(保持和M一致的量纲):


那么,整个卷积过程的计算复杂度为:


事实上,


比较

接下来我们对的效果做一简单比较。

Winograd原始乘法次数Win乘法次数理论加速比权重内存增长

输入内存增长

641.501.33

2

1262.002.00

1.5

1882.252.67

1.33

36241.501.33

2

144722.002.00

1.5

3241442.252.67

1.33

36162.251.78

4

144364.004.00

2.25

324645.067.11

1.78



Winograd卷积

以上介绍了一维和二维的Winograd算法,但实际在神经网络的特征图却通常都是三维的,没法直接往上套。不过前文在介绍二维Winograd的时候,我们除了嵌套之外还用了堆叠一维Winograd来达到二维Winograd的结果,同样的也可以用堆叠的二维Winograd来将其应用到三维的卷积当中。

以k3s1卷积和为例——


标准的卷积过程:

standard_conv.gif


Winograd的卷积过程:

winograd_conv.gif


  1. 由于winograd要求每次都固定的输入大小(这里),所以需要pad到合适的大小
  2. 每次输入上取一个tile(这里每个tile的大小为)并变换成V,与U做哈达马乘积运算后再反变换得到一组输出(这里每组输出大小为),每个tile以为间隔(这里为2)
  3. 最后得到一个的输出,由于最后一行和最后一列的由pad元素多算出来的,所以剪掉他们得到的最终输出
  4. 这里演示的是如何用多次完成单通道特征图的Winograd卷积,对于多通道的情况以此类推即可


前述只讨论了一些比较简单的情况,事实上在CNN中,由于输入的特征图只需要变换一次,而却会被多个滤波器复用,所以输入变换过程的额外开销会被平摊——卷积的滤波器(也即输出通道)越多,那么输入变换产生的额外开销的影响就越小。



本文gif动图由以下工具绘制获得——