卷积优化

gemm优化（CPU）

通用矩阵乘（GEMM）优化算法

本文简要介绍通用矩阵乘（General Matrix Multiplication）优化的基本概念和方法、神经网络量化中的优化方法。旨在帮助大家在概念中建立一些直觉，无甚高论。

https://zhenhuaw.me/blog/2019/gemm-optimization.html

基于算法分析的方法

• Strassen 算法

• Coppersmith–Winograd 算法

通过展开循环，尽量减少访存指令占比

for (int m = 0; m < M; m++) {
  for (int n = 0; n < N; n++) {
    C[m][n] = 0;
    for (int k = 0; k < K; k++) {
      C[m][n] += A[m][k] * B[k][n];
    }
  }
}

for (int m = 0; m < M; m++) {
  for (int n = 0; n < N; n += 4) {
    C[m][n + 0] = 0;
    C[m][n + 1] = 0;
    C[m][n + 2] = 0;
    C[m][n + 3] = 0;
    for (int k = 0; k < K; k++) {
      C[m][n + 0] += A[m][k] * B[k][n + 0];
      C[m][n + 1] += A[m][k] * B[k][n + 1];
      C[m][n + 2] += A[m][k] * B[k][n + 2];
      C[m][n + 3] += A[m][k] * B[k][n + 3];
    }
  }
}

for (int m = 0; m < M; m += 4) {
  for (int n = 0; n < N; n += 4) {
    C[m + 0][n + 0..3] = 0;
    C[m + 1][n + 0..3] = 0;
    C[m + 2][n + 0..3] = 0;
    C[m + 3][n + 0..3] = 0;
    for (int k = 0; k < K; k++) {
      C[m + 0][n + 0..3] += A[m + 0][k] * B[k][n + 0..3];
      C[m + 1][n + 0..3] += A[m + 1][k] * B[k][n + 0..3];
      C[m + 2][n + 0..3] += A[m + 2][k] * B[k][n + 0..3];
      C[m + 3][n + 0..3] += A[m + 3][k] * B[k][n + 0..3];
    }
  }
}

for (int m = 0; m < M; m += 4) {
  for (int n = 0; n < N; n += 4) {
    C[m + 0..3][n + 0..3] = 0;
    C[m + 0..3][n + 0..3] = 0;
    C[m + 0..3][n + 0..3] = 0;
    C[m + 0..3][n + 0..3] = 0;
    for (int k = 0; k < K; k += 4) {
      C[m + 0..3][n + 0..3] += A[m + 0..3][k + 0] * B[k + 0][n + 0..3];
      C[m + 0..3][n + 0..3] += A[m + 0..3][k + 1] * B[k + 1][n + 0..3];
      C[m + 0..3][n + 0..3] += A[m + 0..3][k + 2] * B[k + 2][n + 0..3];
      C[m + 0..3][n + 0..3] += A[m + 0..3][k + 3] * B[k + 3][n + 0..3];
    }
  }
}

对于支持SIMD的平台，进行向量化的支持

优化内存布局，减少cache miss

QNNPACK

QNNPACK 实现揭秘

QNNPACK 是 Facebook 开发的专门用于量化神经网络计算的加速库，其卓越的性能表现一经开源就击败了几乎全部已公开的加速算法。

https://zhenhuaw.me/blog/2019/reveal-qnnpack-implementation.html

卷积优化（CPU）

卷积神经网络优化算法

随着技术的发展，研究人员提出了多种卷积优化算法，包括 Im2col、Winograd 等等。本文简要介绍几种常见的优化方法，并讨论作者在该领域的一些经验。

https://zhenhuaw.me/blog/2019/convolution-neural-networks-optimization.html

im2col

内存布局的影响

• 输出：两种布局都一样，因为输出没有访存复用

• 输入：NHWC优于NCHW，因为前者在小块间的局部性更高

• filter：NCHW优于NHWC，因为前者在小块间的局部性更高。但是通常filter可以在模型准备阶段转换内存布局，因为一般filter的内容是固定的

空间组合优化算法

Winograd算法

详解卷积中的Winograd加速算法

1. 为什么会引入WinoGrad？做过ACM/OI的朋友大家应该对FFT并不陌生，我们知道对于两个序列的乘法通过FFT可以从原始O(n^2)复杂度变成O(nlogn)，所以我们就会想着FFT这个算法是否可以应用到我们计算卷积中来呢？当然…

https://zhuanlan.zhihu.com/p/260109670

卷积神经网络优化算法

随着技术的发展，研究人员提出了多种卷积优化算法，包括 Im2col、Winograd 等等。本文简要介绍几种常见的优化方法，并讨论作者在该领域的一些经验。

https://zhenhuaw.me/blog/2019/convolution-neural-networks-optimization.html

AI算法基础 [4]：Winograd算法原理

简介 Winograd算法起源于1980年，作者Shmuel Winograd 在文章《On multiplication of polynomials modulo a polynomial》中提出的减少FIR滤波器计算量的一个算法。他指出，对于输出个数为mmm，参数个数为rrr的FIR滤波器，不需要m×rm×rm×r次乘法计算，而只需要u(F(m,r))=m+r−1u(F(m,r))=m+r-

https://no5-aaron-wu.github.io/2021/11/16/AI-Algorithm-4-Winograd/

Winograd卷积原理 - 极术社区 - 连接开发者与智能计算生态

Winograd算法最早于1980年由Shmuel Winograd在《Arithmetic complexity of computations(1980)》中提出，主要用来减少FIR滤波器的计算量。 该算法类似FFT，将数据映射到另一个空间上，用加减运算代替部分乘法运算，在“加减运算速度远高于乘法运算”的前提下达到明显的加速效果（与FFT不同的是，Winograd将数据映射到一个...

https://aijishu.com/a/1060000000005409

1D

2D

计算量的讨论

工程实现

AI算法基础 [5]：MNN中的Winograd实现

前言 主要针对CPU后端，基于/source/backend/cpu/compute/ConvolutionWinograd.cpp源码展开。 部分章节以输入大小：1 x 8 x 224 x 224，权重大小: 16 x 8 x 3 x 3, 输出1 x 16 x 222 x 222 为例进行辅助说明。 MNN卷积相关运算统一使用CAFFE_C4格式，即MNN自创的NC4HW4格式，具体排布介绍：

https://no5-aaron-wu.github.io/2021/11/16/AI-Algorithm-5-WinogradInMnn/

误差来源

间接卷积优化算法

深入浅出GPU优化系列：GEMM优化（一）

本篇文章是深入浅出GPU优化系列的第两个专题，主要是 介绍如何对GPU中的矩阵乘法（GEMM）进行优化。目前针对GEMM的优化，网络上已经有非常多的教程和示例了。大部分的重要资料我都看了看。但总的来说，还是不够接…

https://zhuanlan.zhihu.com/p/435908830

CUDA SGEMM矩阵乘法优化笔记——从入门到cublas

1 Introduction最近开始入门CUDA，初步了解GPU的工作原理后，选择了单精度矩阵乘法作为练习的kernal，尝试从最简单的SGEMM kernal开始，逐步优化到cublas的性能水平。 下面的两张图是在自己的笔记本上（古老的GTX1…

https://zhuanlan.zhihu.com/p/518857175

global memory → shared memory

shared memory → register

register分块

数据的prefetch

针对cache的优化？