目录
写在前面
问题定义
一个例子 F(2, 3)
- 1D winograd
- 1D to 2D,F(2, 3) to F(2x2, 3x3)
卷积神经网络中的 Winograd
总结
参考
博客: https://blog.shinelee.me/ | 博客园 | CSDN https://blog.csdn.net/blogshinelee
写在前面
随便翻一翻流行的推理框架(加速器), 如 NCNN https://github.com/Tencent/ncnn , https://github.com/Maratyszcza/NNPACK 等, 可以看到, 对于卷积层, 大家不约而同地采用了 Winograd 快速卷积算法, 该算法出自 CVPR 2016 的一篇 paper:Fast Algorithms for Convolutional Neural Networks https://arxiv.org/abs/1509.09308 .
本文将尝试揭开 Winograd 算法的神秘面纱.
问题定义
将一维卷积运算定义为 \(F(m, r)\),\(m\)为 Output Size,\(r\)为 Filter Size, 则输入信号的长度为 \(m+r-1\), 卷积运算是对应位置相乘然后求和, 输入信号每个位置至少要参与 1 次乘法, 所以乘法数量最少与输入信号长度相同, 记为
\[ \mu(F(m, r))=m+r-1 \]
在行列上分别进行一维卷积运算, 可得到二维卷积, 记为 \(F(m\times n, r\times s)\), 输出为 \(m\times n\), 卷积核为 \(r\times s\), 则输入信号为 \((m+r-1)(n+s-1)\), 乘法数量至少为
\[ \begin{aligned} \mu(F(m \times n, r \times s)) &=\mu(F(m, r)) \mu(F(n, s)) \\ &=(m+r-1)(n+s-1) \end{aligned} \]
若是直接按滑动窗口方式计算卷积, 一维时需要 \(m\times r\)次乘法, 二维时需要 \(m\times n \times r \times s\)次乘法, 远大于上面计算的最少乘法次数.
使用 Winograd 算法计算卷积快在哪里? 一言以蔽之: 快在减少了乘法的数量, 将乘法数量减少至 \(m+r-1\)或 \((m+r-1)(n+s-1)\).
怎么减少的? 请看下面的例子.
一个例子 F(2, 3)
先以 1 维卷积为例, 输入信号为 \(d=\left[ \begin{array}{llll}{d_{0}} & {d_{1}} & {d_{2}} & {d_{3}}\end{array}\right]^{T}\), 卷积核为 \(g=\left[ \begin{array}{lll}{g_{0}} & {g_{1}} & {g_{2}}\end{array}\right]^{T}\), 则卷积可写成如下矩阵乘法形式:
\[ F(2, 3) = \left[ \begin{array}{lll}{d_{0}} & {d_{1}} & {d_{2}} \\ {d_{1}} & {d_{2}} & {d_{3}}\end{array}\right] \left[ \begin{array}{l}{g_{0}} \\ {g_{1}} \\ {g_{2}}\end{array}\right]=\left[ \begin{array}{c}{r_0} \\ {r_1}\end{array}\right] \]
如果是一般的矩阵乘法, 则需要 6 次乘法和 4 次加法, 如下:
\[ \begin{array}{l}{r_{0}=\left(d_{0} \cdot g_{0}\right)+\left(d_{1} \cdot g_{1}\right)+\left(d_{2} \cdot g_{2}\right)} \\ {r_{1}=\left(d_{1} \cdot g_{0}\right)+\left(d_{2} \cdot g_{1}\right)+\left(d_{3} \cdot g_{2}\right)}\end{array} \]
但是, 卷积运算中输入信号转换成的矩阵不是任意矩阵, 其中有规律地分布着大量的重复元素, 比如第 1 行和第 2 行的 \(d_1\)和 \(d_2\), 卷积转换成的矩阵乘法比一般矩阵乘法的问题域更小, 这就让优化存在了可能.
Winograd 是怎么做的呢?
\[ F(2,3)=\left[ \begin{array}{lll}{d_{0}} & {d_{1}} & {d_{2}} \\ {d_{1}} & {d_{2}} & {d_{3}}\end{array}\right] \left[ \begin{array}{l}{g_{0}} \\ {g_{1}} \\ {g_{2}}\end{array}\right]=\left[ \begin{array}{c}{m_{1}+m_{2}+m_{3}} \\ {m_{2}-m_{3}-m_{4}}\end{array}\right] \]
其中,
\[ \begin{array}{ll}{m_{1}=\left(d_{0}-d_{2}\right) g_{0}} & {m_{2}=\left(d_{1}+d_{2}\right) \frac{g_{0}+g_{1}+g_{2}}{2}} \\ {m_{4}=\left(d_{1}-d_{3}\right) g_{2}} & {m_{3}=\left(d_{2}-d_{1}\right) \frac{g_{0}-g_{1}+g_{2}}{2}}\end{array} \]
乍看上去, 为了计算 \(\begin{array}{l}{r_{0}=m_1 + m_2 + m_3 } \\ {r_{1}=m_2 - m_3 - m_4}\end{array}\), 需要的运算次数分别为:
输入信号 \(d\)上: 4 次加法(减法)
卷积核 \(g\)上: 3 次加法 (\(g_1+g_2\) 中间结果可保留),2 次乘法(除法)
输出 \(m\)上: 4 次乘法, 4 次加法
在神经网络的推理阶段, 卷积核上的元素是固定的, 因此 \(g\)上的运算可以提前算好, 预测阶段只需计算一次, 可以忽略, 所以一共所需的运算次数为 \(d\)与 \(m\)上的运算次数之和, 即 4 次乘法和 8 次加法.
与直接运算的 6 次乘法和 4 次加法相比, 乘法次数减少, 加法次数增加. 在计算机中, 乘法一般比加法慢, 通过减少减法次数, 增加少量加法, 可以实现加速.
1D winograd
上一节中的计算过程写成矩阵形式如下:
\[ Y=A^{T}\left[(G g) \odot\left(B^{T} d\right)\right] \]
其中,\(\odot\)为 element-wise multiplication(Hadamard product)对应位置相乘,
- \[ B^{
- T
- }=\left[ \begin{
- array
- }{
- cccc
- }{
- 1
- } & {
- 0
- } & {
- -1
- } & {
- 0
- } \\ {
- 0
- } & {
- 1
- } & {
- 1
- } & {
- 0
- } \\ {
- 0
- } & {
- -1
- } & {
- 1
- } & {
- 0
- } \\ {
- 0
- } & {
- 1
- } & {
- 0
- } & {
- -1
- }\end{
- array
- }\right] \]
- \[ G=\left[ \begin{
- array
- }{
- ccc
- }{
- 1
- } & {
- 0
- } & {
- 0
- } \\ {
- \frac{
- 1
- }{
- 2
- }
- } & {
- \frac{
- 1
- }{
- 2
- }
- } & {
- \frac{
- 1
- }{
- 2
- }
- } \\ {
- \frac{
- 1
- }{
- 2
- }
- } & {
- -\frac{
- 1
- }{
- 2
- }
- } & {
- \frac{
- 1
- }{
- 2
- }
- } \\ {
- 0
- } & {
- 0
- } & {
- 1
- }\end{
- array
- }\right] \]
- \[ A^{
- T
- }=\left[ \begin{
- array
- }{
- llll
- }{
- 1
- } & {
- 1
- } & {
- 1
- } & {
- 0
- } \\ {
- 0
- } & {
- 1
- } & {
- -1
- } & {
- -1
- }\end{
- array
- }\right] \]
- \[ g=\left[ \begin{
- array
- }{
- lll
- }{
- g_{
- 0
- }
- } & {
- g_{
- 1
- }
- } & {
- g_{
- 2
- }
- }\end{
- array
- }\right]^{
- T
- } \]
- \[ d=\left[ \begin{
- array
- }{
- llll
- }{
- d_{
- 0
- }
- } & {
- d_{
- 1
- }
- } & {
- d_{
- 2
- }
- } & {
- d_{
- 3
- }
- }\end{
- array
- }\right]^{
- T
- } \]
\(g\): 卷积核
\(d\): 输入信号
\(G\):Filter transform 矩阵, 尺寸 \((m+r-1)\times r\)
\(B^T\):Input transform 矩阵, 尺寸 \((m+r-1)\times (m+r-1)\)
\(A^T\):Output transform 矩阵, 尺寸 \(m \times (m+r-1)\)
整个计算过程在逻辑上可以分为 4 步:
- Input transform
- Filter transform
- Hadamar product
- Output transform
注意, 这里写成矩阵形式, 并不意味着实现时要调用矩阵运算的接口, 一般直接手写计算过程速度会更快, 写成矩阵只是为了数学形式.
1D to 2D,F(2, 3) to F(2x2, 3x3)
上面只是看了 1D 的一个例子, 2D 怎么做呢?
论文中一句话带过:
- A minimal 1D algorithm F(m, r) is nested with itself to obtain a minimal 2D algorithm,F(m*m, r*r).
- \[ Y=A^{
- T
- }\left[\left[G g G^{
- T
- }\right] \odot\left[B^{
- T
- } d B\right]\right] A \]
其中,\(g\)为 \(r \times r\) Filter,\(d\)为 \((m+r-1)\times (m+r-1)\)的 image tile.
问题是: 怎么 nested with itself?
这里继续上面的例子 \(F(2, 3)\), 扩展到 2D,\(F(2\times 2, 3 \times 3)\), 先写成矩阵乘法, 见下图, 图片来自 SlideShare, 注意数学符号的变化,
将卷积核的元素拉成一列, 将输入信号每个滑动窗口中的元素拉成一行. 注意图中红线划分成的分块矩阵, 每个子矩阵中重复元素的位置与一维时相同, 同时重复的子矩阵也和一维时相同, 如下所示
令 \(D_0 = [k_0, k_1, k_2, k_3]^T\), 即窗口中的第 0 行元素,\(D_1 \ D_2 \ D_3\)表示第 1,2,3 行;\(W_0=[w_0, w_1, w_2]^T\),
\[\begin{aligned} \left[ \begin{array}{c}{r_0} \\ {r_1} \\ {r_2} \\ {r_3}\end{array}\right] &= \left[ \begin{array}{c}{R_0} \\ {R_1}\end{array}\right] = \left[ \begin{array}{c}{K_0 W_0 + K_1 W_1 + K_2 W_2} \\ {K_1 W_0 + K_2 W_1 + K_3 W_2} \end{array} \right] \\ &= \left[ \begin{array}{c} {A^{T}\left[(G W_0) \odot\left(B^{T} D_0 \right)\right] + A^{T}\left[(G W_1) \odot\left(B^{T} D_1 \right)\right] + A^{T}\left[(G W_2) \odot\left(B^{T} D_2 \right)\right]} \\ {A^{T}\left[(G W_0) \odot\left(B^{T} D_1 \right)\right] + A^{T}\left[(G W_1) \odot\left(B^{T} D_2 \right)\right] + A^{T}\left[(G W_2) \odot\left(B^{T} D_3 \right)\right]} \end{array} \right] \\ \\ &=A^{T}\left[\left[G [W_0 \ W_1 \ W_2 ] G^{T}\right] \odot\left[B^{T} [d_0 \ d_1 \ d_2 \ d_3] B\right]\right]A \\ \\ &=A^{T}\left[\left[G g G^{T}\right] \odot\left[B^{T} d B\right]\right] A \end{aligned} \]
卷积运算为对应位置相乘再相加, 上式中,\(A^{T}\left[(G W_0) \odot\left(B^{T} D_0 \right)\right]\)为列向量 \(W_0\)与 \(D_0\)的卷积, 结果为长度为 2 的列向量, 而 \(A^{T}\left[(G W_0) \odot\left(B^{T} D_0 \right)+ (G W_1) \odot\left(B^{T} D_1 \right) + (G W_2) \odot\left(B^{T} D_2 \right)\right]\)方括号内对应位置相乘再相加, 相当于在构成的行向量上卷积, 据此, 上面的推导就不难看出了.
所谓的 nested with itself 如下图所示,
此时, Winograd 算法的乘法次数为 16(上图 \(4\times 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 / m\rceil\lceil W / m\rceil \times C\)和 \(C \times K\), 把 Channel 那一维消掉.
总结
Winograd 算法通过减少乘法次数来实现提速, 但是加法的数量会相应增加, 同时需要额外存储 transform 矩阵, 随着卷积核和 tile 的尺寸增大, 就需要考虑加法和存储的代价, 所以一般 Winograd 只适用于较小的卷积核和 tile(对大尺寸的卷积核, 可使用 FFT 加速), 在目前流行的网络中, 小尺寸卷积核是主流, 典型实现如 \(F(6\times 6, 3\times 3)\),\(F(2\times 2, 3\times 3)\)等, 可参见 NCNN,,ARM-ComputeLibrary 等源码实现.
就卷积而言, Winograd 算法和 FFT 类似, 都是先通过线性变换将 input 和 filter 映射到新的空间, 在那个空间里简单运算后, 再映射回原空间.
与 im2col+GEMM+col2im 相比, winograd 在划分时使用了更大的 tile, 就划分方式而言,\(F(1\times 1, r\times r)\)与 im2col 相同.
参考
- arxiv: Fast Algorithms for Convolutional Neural Networks https://arxiv.org/abs/1509.09308
- video: Fast Algorithms for Convolutional Neural Networks by Andrew Lavin and Scott Gray https://www.bilibili.com/video/av50718398
- video: Even Faster CNNs Exploring the New Class of Winograd Algorithms https://www.bilibili.com/video/av53072685
- arxiv: Sparse Winograd Convolutional neural networks on small-scale systolic arrays https://arxiv.org/abs/1810.01973
- https://github.com/ARM-software/ComputeLibrary
来源: https://www.cnblogs.com/shine-lee/p/10906535.html