Winograd算法是一类通过数学变换减少乘法运算次数从而加速卷积计算的优化算法。它的核心思想是用更多低成本的加法操作去替换高成本的乘法操作。在计算机中乘法运算的时钟周期通常远高于加法因此这种“以加代乘”的策略能有效提升计算速度。 核心思想从一维卷积F(2,3)看起我们通过一个经典的一维卷积例子F(2,3)来理解其原理。F(m, r)表示输出为m个点卷积核大小为r。这里F(2,3)指输入4个点d0, d1, d2, d3卷积核3个点g0, g1, g2输出2个点。1. 直接卷积的计算量直接计算输出r0和r1需要6次乘法和4次加法r0 d0*g0 d1*g1 d2*g2r1 d1*g0 d2*g1 d3*g22. Winograd的数学变换Winograd算法通过巧妙的变量替换来减少乘法。它定义了一组中间变量m1, m2, m3, m4使得输出r0, r1可以表示为它们的加减组合r0 m1 m2 m3r1 m2 - m3 - m4而这四个m变量是这样计算的m1 (d0 - d2) * g0m2 (d1 d2) * ((g0 g1 g2) / 2)m3 (d2 - d1) * ((g0 - g1 g2) / 2)m4 (d1 - d3) * g23. 加速的关键预计算在这个变换中m2和m3的计算涉及卷积核g的组合(g0g1g2)/2和(g0-g1g2)/2。由于卷积核在模型推理阶段是固定不变的这些与g相关的表达式可以预先计算好。因此在实际推理时每个输入块的计算只需4次乘法计算m1到m48次加法4次用于计算m变量4次用于组合得到最终输出r0, r1对比结果将乘法次数从6次减少到4次减少了33%的乘法运算。 从一维到二维F(2x2, 3x3)实际应用中卷积是二维的。Winograd算法可以扩展应用到二维场景例如处理3x3的卷积核输出2x2的结果记作F(2x2, 3x3)。在这个经典配置下直接卷积需要进行36次乘法3x3卷积核在4x4输入上滑动2x2次每次9次乘法。而采用Winograd算法乘法次数可以大幅减少至16次计算量降低了2.25倍。 在CNN中的实践分而治之对于大型特征图Winograd算法采用“分块”策略切块 (Tiling)将大的输入特征图划分为多个有重叠的、大小一致的小块Tile。独立变换对每个小块独立执行Winograd变换与卷积核进行高效计算。合并结果将所有小块的输出结果拼接得到最终的输出特征图。 总结Winograd算法的核心优势在于用加法换乘法来降低计算复杂度但其有效性高度依赖于小卷积核如3x3和特定的分块大小。同时其变换过程可能引入额外的数值误差在与模型量化等技术结合时需要谨慎处理。总的来说Winograd算法是一个在实践中被证明非常有效的卷积加速手段在追求极致推理性能的场景下扮演着重要角色。1 Fast Algorithms for Convolutional Neural Networks https://arxiv.org/pdf/1509.09308.pdf2 WinogradGEMM算法综述CNN中高效卷积实现上https://blog.csdn.net/qq_32998593/article/details/861771513 WinogradGEMM算法综述CNN中高效卷积实现下https://blog.csdn.net/qq_32998593/article/details/861816634 卷积神经网络中的Winograd快速卷积算法 https://www.cnblogs.com/shine-lee/p/10906535.html5 NCNN winograd详解一 https://zhuanlan.zhihu.com/p/72149270