CNN/HighPerformanceComputing/mnn/readme.md
MNN 是一个轻量级的深度学习端侧推理引擎，核心解决深度神经网络模型在端侧推理运行问题，涵盖深度神经网络模型的优化、转换和推理。 目前，MNN已经在手淘、手猫、优酷、聚划算、UC、飞猪、千牛等 20 多个 App 中使用， 覆盖直播、短视频、搜索推荐、商品图像搜索、互动营销、权益发放、安全风控等场景，每天稳定运行上亿次。 此外，菜鸟自提柜等 IoT 设备中也有应用。在 2018 年双十一购物节中，MNN 在天猫晚会笑脸红包、扫一扫、明星猜拳大战等场景中使用。
MNN整体架构
离线模型转换和图优化 + 在线预推理搜索最优策略+多终端op执行器
1.运行时半自动搜索架构
2.卷积算法优化创新
3.异构设备混合调度
半自动搜索，是在模型结构已知的情况下，在已有的高性能计算模块中，按照一定规则，搜索、组合出最适应该模型的计算方案。它是介于以 TVM 为代表的的全自动搜索（i.e. 自动调优）和以 NCNN 为代表的全手动搜索（i.e. 手工实现每个 case）之间一种新颖的设计思想。它的核心洞察在于，TVM 的自动编译优化，难以匹敌针对硬件特性和算子的手写汇编；同时，模型算子、参数的 case 组合无穷多，无法针对每个 case 进行优化。在最后的「数据论证」部分，我们会用实验数据展示 MNN 相对于全自动搜索（TVM）和全手动搜索（NCNN）的优势。
为了支撑运行时半自动搜索的能力，MNN 提出了一个特殊的处理过程，称为「预推理」。预推理过程中，会提前进行算子的计算策略选择和资源分配。
一般情况下深度学习的应用输入尺寸变动的频率比较小或者可以经过特定的预处理阶段变成相对归一的尺寸。而在输入尺寸确定的情况下，我们可以对模型中每个 Op，计算出它的输出大小以及不同计算策略的消耗以及资源需求量，并以此为依据决定每个 Op 的计算策略，提前进行资源的分配。
计算策略选择
算子的计算策略，包含算法与运行后端的选择。每种算子可以有多种计算策略，不同计算策略适用于不同的输入尺寸，MNN 采用 Cost 计算的方式，去决定计算策略的选取。算法的 Cost 与运行后端的调度 Cost 共同决定了一种计算策略的 Cost。
运行后端的调度 Cost，我们通过在大量实际的机器上测试获得。而需要重点关注的是不同算法实现的 Cost。
算法cost 主要体现在 卷积的不同实现方法的不同复杂度
滑窗/矩阵乘的 Cost ，参数定了，cost固定；Winograd 算法因为可以选择分成不同数量的块进行计算，而cost有多种，块数n 增大时，前后变换耗时增加，中间的乘法数减少，因此总cost会先降后升，需要找最小值。
对于不同的卷积情况，从 滑窗/矩阵乘方法和多种Winograd 算法策略中选择最小cost的方法，利用优化技术（SIMD(c_NEON/asm_NEON) 、OMP、数据重排、指令流水线），实现高效的op。
资源预分配
不采用统计计算大块内存，后分配的策略（不易扩展，不同算法选择），而采用内存池资源管理的办法（tensor引用计数，为0则清理）
NC4HW4 格式数据排列，方便向量化运算，降低cache miss
Winograd 算法创新（内置 Winograd 因子生成器，方便产生所有可能的情况，源变换——重排——矩阵乘——重排——目标变换 ），
Strassen 算法创新
对于大矩阵乘 C=AB 的计算，学界很早就有 Strassen 算法，其思路是把 A, B 等分拆成 4 个小块，进行一系列的加减计算后，进行 7 次小块矩阵乘，再经过一系列加减计算组装成 C。这样，原本需要 8 次小矩阵乘，现在只需要 7 次，就减少了 1 次矩阵乘。
MNN 后端 API 的设计理念的独特性在于两点：
MNN 后端 API 帮助实现异构设备的「混合调度」：TFLite 这样的后端 Delegate，会在遇到不支持的算子的时候，回退到算子的 CPU 实现。可以说，TFLite 后端设计是「被动式」的。与 TFLite 这样的后端 Delegate 不同，MNN 的异构调度是「主动式」的，我们称之为「混合调度」：MNN 在创建推理会话时，可以针对算子配置后端，且配置多于一个后端时，会根据后端实现动态选择对性能最优的后端。同时，会话负责衔接后端间的数据拷贝，单一后端仅需实现到数据缓存区域的读写，而无需感知其他后端的存在。这样，就可以在单会话内或多会话间实现后端的自由组合。在后端不支持或性能不适合实现特定算子时，就可以借助其他后端的实现，完成整个推理过程。
MNN 后端 API 的为算子抽象级别，而非例如 TFLite 的子图抽象级别。也就是说，在 MNN 的后端实现中，每个算子是单独实现的，后端实现不需要考虑子图的拓扑结构与优化。这一点，与前文所提的「半自动搜索」有关：在预处理过程中，整个计算图的图优化已经统一提前完成，所以不需要在后端子图实现。另外，算子级别的后端抽象，也极大的提高了后端实现的可调试性：可以将实现有误的后端算子快速定位。
MNN 通过半自动搜索，卷积算法优化创新和异构设备的混合调度，达到了在绝大多数情况下，领先于业界的性能。我们意识到性能是端侧智能应用非常重要的一环，会在未来持续投入更多创新性的性能优化方案，比如把半自动搜索应用于 MNN 正在建设的动态图训练能力中，让动态搭建的计算图可以选择出最适合当前参数的算子实现。另外，我们还看到端智能应用场景正在往 NLP 和 IOT 方向飞速发展。由于 NLP 的模型普遍较大，IOT 设备相比于移动端算力受限，这些都对模型压缩提出了更高的要求。所以，MNN 在未来除了投资性能优化以外，还会致力于研究更大压缩比、更好性能提升的模型压缩算法，让 MNN 成为端侧推理性能、压缩能力最好的深度学习引擎。
read model-->create Net(Interpreter) --> 配置backend --> create session --> config input and output --> run session -->（Pipeline --> Unit-->op-->Execution(调用不同后端算子)）--> finished
MNN 作为阿里巴巴开源的端侧推理引擎，已经支撑了两届淘宝双十一。我们以轻量级的推理引擎和配套工具，支持 Caffe、TensorFlow、PyTorch 训练框架和端侧 CPU、GPU、NPU 上的高效推理。
手机淘宝中有许多对实时性和精度要求都比较高业务，例如视频流检测、拍立淘等等。在算力有限的情况下，性能和精度往往不可兼得 —— 要么接受更慢的响应速度，保障精度，例如放弃视频流，只支持图片；要么舍弃一部分精度，用更小的模型换取更快的速度。
HiAI 是华为端侧 AI 能力开放平台，通过 HiAI Foundation 芯片能力开放，可以借助异构调度和 NPU 加速， 获得更佳的性能和功耗，有了这样性能和功耗同时得以提升的方案， MNN 就可以在配备了 NPU 的设备上启用那个名场面 —— 我全都要！
那么，究竟要怎么做呢？毕竟NPU是完全不同于CPU和GPU的计算设备。在这里，就需要简单回顾一下 MNN 对计算设备的抽象了。
计算设备在 MNN 中，被抽象为 Backend ，即后端；每一种后端都有三种职责：计算资源的分配、计算任务的调度、数据拷贝（含必要的格式转换）。 MNN 在实现对华为 NPU 支持的时候，就依赖了这种抽象设计。
具体来说，创建会话阶段，我们会在 NPUExecution 的 onCreate 方法中，将 MNN 的 Op 转换为 HiAI 的 OM Op ，逐步构建出 OM 的模型图；资源分配阶段，我们会在 NPUBackend 的 onResizeEnd 方法中，编译 OM 的模型图，生成 NPU 可用的 IR 模型，并预留出输入输出相关的 AI Tensor ；在推理运行阶段，我们会借助 NPUBackend 的 onCopyBuffer 方法，将输入数据从 MNN Tensor 拷贝到 AITensor ，而后利用华为 NPU 执行推理计算，再将结果从 AITensor 拷贝到 MNN Tensor。
整个过程看上去还是非常复杂的，但是 MNN 把绝大部分复杂的工作隐藏在了后端的抽象设计中。用户在使用的时候，只需要将 backend 的 type 设置为 NPU ，就可以实现对 NPU 的调用。同时，如果设备不支持 NPU ，还可以自动将计算回退到 CPU 上来实现。
笔者和 Apple、Arm、华为等公司的工程师都有过交流，大家对 XPU 的未来都一致看好。虽然 APU、TPU、NPU 间的乱战可能还要持续上三五年，但在深度学习应用领域，它们逐步从云端走向终端，逐步替代 CPU、GPU 应当是大势所趋。
端智能行业是一个飞速发展的行业，我们在这样的大环境下，不进则退。在这里，把我们平时做的调研总结一下，说4个趋势：
端上推理的重要性高于训练，但是补齐端上训练能力也有价值。
后摩尔时代到来，XPU 百花齐放。
NLP 逐步走向成熟。
从手机端到AIOT端。
为了满足新模型对算力的要求，出现了许多针对AI特殊加速的“XPU”。比如Google的TPU、Edge TPU，华为的麒麟NPU等。
未来的几年是NLP的广泛应用的几年。目前，最小的ALBERT模型大约47MB。这个大小已经适合在手机端上运行了。
“端智能”中所谓的“端”，不局限于手机端。未来的几年，将属于AIOT (Artificial Intelligence of Things)。未来的几年，全球手机的出货量不会再像往年那样大幅增长，而是平稳甚至下滑，而以智能音箱为代表的AIOT设备的出货量正在处于一个飞速发展的时期。
训练框架上
Caffe 、 TensorFlow 、 PyTorch 、 MXNet 在训练模型时都很常用；
计算设备上
CPU 、 GPU 已是主流， NPU 、 TPU 渐渐成为标配， DSP 、 FPGA 在 IoT上也很常见；
算子层面上
众多参数会形成不同的组合，从而对应出不同的优化方式，轻量化和通用化需要取舍；
一款优秀的端侧推理引擎，就需要在这样碎片化的环境下，利用设备有限的资源，尽可能发挥出设备的性能。为此，也需要在转换、调度、执行上加入相应的优化策略。下文，会就其中的部分展开说明。
在模型优化中，MNN 引入了前端的概念来统一训练框架。不同的前端负责加载不同训练框架的模型，统一转换为 MNN 的模型格式。对于最常用的训练框架 TensorFlow 和 Caffe ，我们提供了独立的前端；其他训练框架，比如 MXNet ，则需要先将模型转换为 ONNX ，再通过 ONNX 前端加载。这里，由于 TensorFlow 的算子颗粒度相比 Caffe 和 ONNX 要更小，我们引入了图优化的模块来对齐算子之间的颗粒度。模型转换之后，会经过优化器优化，包含图优化、算子融合、算子替换、布局调整等等。之后，可以选择对浮点模型执行量化压缩。目前模型压缩的模块还没有开源，我们会在完善之后，将相关代码开源。这些步骤都完成之后，会使用 flatbuffer 来保存部署模型。
这里以 RNN-GRU cell 为例，说明一下图优化。 左图是 RNN-GRU cell 在 TensorBoard 中的可视化描述。它足足包含了 3584 个节点，而每一个节点都代表了一定的数据读写或运算，累积起来的总量非常大。然而，所有这些节点可以打包使用一个大颗粒的算子来替代。这不仅大幅降低了部署模型的大小，还可以在大颗粒算子的实现中聚合大量的计算，避免不必要的数据读写。
以 Convolution、Batchnorm、Scale、ReLU 为例说明优化器中的算子融合。 首先融合 Convolution 和 Batchnorm，Convolution 的 weight 等于 weight 乘 alpha ，而 bias 等于 bias 乘 alpha 再加 beta ；而后融合 Convolution 和 Scale ，融合过程和 Batchnorm 类似；最后融合 Convolution 和 ReLU ，在输出结果前，计算激活函数 ReLU 即可。
这样，四个算子就可以合并成一个算子。融合的过程避免了三次 tensor 读写、两次 tensor 乘加。
模型转换好之后，可以使用 MNN 的量化工具对模型进行压缩。目前，MNN支持 post-training quantization（无训练量化）。后续 MNN 会支持 quantization-aware training（带训练量化），以获得更好的准确率和更低比特的压缩。
MNN的量化方案是自己实现的，它目前有ADMM和KL散度两种方案。也就是说，“源头”的预训练好的模型需要是浮点的。ADMM量化方案，是MNN根据达摩院的Paper “Extremely Low Bit Neural Network: Squeeze the Last Bit Out with ADMM” [3] 实现的。它与KL散度的区别在于：ADMM是基于数学优化的方法，只需要几十个数据点即可，但是计算较慢。而KL散度是基于概率统计的方法，需要较多的数据（500到1000个数据点），计算较快。实际操作上来说，对特征的量化，ADMM和KL散度没有巨大的差距；对权重的量化，推荐使用ADMM。
NLP 应用是未来的一大趋势。而 NLP 的模型普遍大于 CV 模型。在这个时候，大幅度地压缩模型，能够让之前只能在服务器运行的模型放到端上运行。所以未来的 MNN ，会提供更好的模型压缩。
在调度上， MNN 将每一类计算设备抽象为一个后端，将算子在特定后端上的实现抽象为执行器。后端负责特定设备上的资源分配和计算调度，执行器负责具体的实现。后端和算子的添加都通过注册表来实现，这是一个双层注册表结构，拓展起来就相对灵活。
调度时，可以为子图选择相应的后端，再由后端创建出相应的执行器，组成管线；也可以为子图选择后端组，实现混合调度。比如，在 GPU 上不宜实现排序算子时，可以回退到 CPU 来执行。
目前， MNN 在 CPU 上实现了 76 个算子， Metal 上有 55 个， OpenGL 覆盖了基础的 CNN 网络， OpenCL 和 Vulkan 分别有 29 和 31 个。
在创建完执行器之后，子图和管线已经就绪。下来，需要计算出所有tensor的形状，在相应的后端上完成内存的分配。而后，在准备执行器时，再为所有的执行器预先在后端上申请好必要的buffer。运行结束后，返回tensor即可。
由于推理所需的所有内存在准备期就已经申请完毕，在后续推理时，如果输入的形状不变，就可以复用tensor和buffer，从而避免频繁地申请、释放内存；只有输入形状改变的时候，才需要从形状计算开始，调整一次内存分配。同时，由于使用后端统一管理缓存，后端内的执行器之间，缓存就可以充分复用的，这就大大减少了内存的需求量。此外，MNN分配内存时，默认按照32位对齐，内存对齐有利于数据读写。
数据布局对性能影响巨大。（cache相关）
先来看一看在 NCHW 的布局下，怎么利用 SIMD 加速 3x3 的 depth-wise 卷积。
首先，读取数据时，需要一次性读取四个 float 作为第一行的数据，后两行的读取也是相似的；此时，读取出的三行数据已经足够计算两列输出，即，可以复用部分数据；而后，为了提高数据复用，会再读取出第四行数据，一次计算两行两列，即，可以引入循环展开；然而，残留的 525 和 2125 亮度眼边界无法利用 SIMD 计算，只能逐一循环读写完成计算；按照这样的方式，就可以相应完成后几个通道的计算。
但是， NCHW 布局下，无法充分利用 SIMD 进行加速，同时，实现优化分支越多，占用包大小也就越多。
再来看一看 NC/4HW4 布局下，利用 SIMD 加速的情况又是怎样的。 这里的 "C/4" 指的是按照 4 个通道对齐的方式重排数据。重排所有输入和权重数据后，每次 SIMD 读写都天然是 4 个通道的输入数据和 4 个通道的权重数据。这样，不论 kernel、stride、dilation 怎么变化，我们都可以简单地使用 for 循环和 SIMD 的一套通用优化完成卷积计算。既不会有边缘数据无法加速的问题，也不会对包大小造成影响。
对于对于 KxK 卷积，可以使用 Winograd 算法进一步加速。 MNN 中支持 2x2 到 7x7 的 Winograd 实现。 Winograd 计算时，需要把输出拆分成 NxN 的小块，把输入拆分成 (N+K-1)x(N+K-1) 的小块。这样，问题就可以简化为两个小矩阵的卷积。
再套用 Winograd 的公式，将矩阵间的卷积运算转换为矩阵点乘运算。在这个过程中，除了矩阵点乘外，还引入三个矩阵转换，分别是输入矩阵 d 、权重矩阵 g 和结果矩阵 Y’ 的转换。其中，权重转换时， G 矩阵可以利用中国剩余数定理计算， GgGT 就可以在准备执行器时提前计算；输入转换和输出转换时用到的 A 和 B 矩阵需要根据 N 和 K 计算，我们在代码中内置了几种优化后的组合，所以实际计算时，这两个转换并不需要经过复杂的矩阵乘法。
这样，原来矩阵卷积所需要的 9x4 次乘法计算就可以用矩阵点乘的 4x4 次乘法计算代替。只考虑乘法耗时的话，加速了 2.25 倍。示例中， K=3，N=2 ，但实际使用时，可以选择更大的 N 值，获取高的加速倍数，但也要相应消耗更多的内存。
MNN 可能是端侧推理引擎中，第一个应用 Strassen 算法优化矩阵乘法的。
Strassen 在计算矩阵乘法时，首先需要将矩阵平均拆分成四个小矩阵。这里使用 a11 ~ a22、b11 ~ b22、c11 ~ c22 代表四个小矩阵，计算过程一共需要8次小矩阵乘法运算。
这里可以引入中间小矩阵， s1 ~ s4、t1 ~ t4、m1 ~ m7、u1 ~ u7 。其中，只有 m1 ~ m7 包含小矩阵乘法，一共 7 次小矩阵乘法运算。而其他的，只包含小矩阵的加减法。也就是说，通过 4 + 4 + 7 次小矩阵加减法，替代了一次小矩阵乘法。
与原来的矩阵乘法相比， Strassen 的时间复杂度从 n 的 3 次方，降低到 n 的 2.81 次方。在矩阵较大时，矩阵乘法远远慢于矩阵加减法，收益就更明显。
在 MNN 中，我们会递归使用 Strassen 。也就是说，递归拆分矩阵。在矩阵足够大时，继续拆分；在矩阵不够大时，使用普通的矩阵算法。这里使用减免的矩阵乘法开销作为收益，使用小矩阵 s 、小矩阵 t 、小矩阵 u 矩阵的加减法开销之和作为代价，收益大于代价时，就可以考虑使用 Strassen 算法。
链路优化可以举一个 19 年春节淘宝扫年货的例子。在获得手机相机输入后，每一帧的图像首先需要经过一次预处理，将图片缩放到年货检测模型的输入大小上，然而再经过推理，判定图像有没有年货，如果有，就发放相关权益。这个过程中，图片预处理的耗时也不容忽视。降低这个耗时，就可以帮助我们提升帧率，从而改进用户体验。为此，我们引入了一个轻量级的 2D 图片处理库，可以高效地完成色值变化、色彩空间的转换或者仿射变换等。这样， MNN 的用户就不再需要为图片处理引入 libyuv 或者 opencv 了。