摘要
CNN 的流行普及和 CPU 的大规模使用部署，使得如果我们能够提高 CPU 上进行 CNN 模型推演的性能，这将意义重大；
为了提高 CPU 上面的 CNN 推理性能，现有的方法比如： 在 MXNet 和 Intel OpenVINO，通常把模型视为一个计算图，然后使用高性能的库比如 Intel MKL-DNN 来实现图的优化操作；
尽管通过这些现有的库可以提高性能，但是由于 Local operation-level / 局部操作级别 的优化已经被预先定义，所以很难在图级别进行优化；
因此，整体上进行端对端的推理优化很受限制；
这篇文章介绍了 NeoCPU, 一种对 CPU 进行 CNN 模型推断的综合方法，采用了全栈式的系统优化方案；
NeoCPU 无需借助于第三方的库将操作优化为模板，通过操作和图像级别的联合进一步进行性能优化；
实验表明针对于 CNN 模型推理，相比于其他实现方法， NeoCPU 能够达到 3.45x 更低延迟；
1 介绍
CNN 模型在计算机视觉领域大规模使用，使得模型架构优化成为关键；
相似的，大规模在服务器端，客户端，边缘端部署 CPU，也使得 CPU 上进行优化意义重大；
所以如何在 CPU 上进行 CNN 模型推演的优化成为很多用户研究的重点；
CPU 上 CNN 模型性能的推演还有很大提升空间；
CNN 模型推演本质上就是进行执行 a computation graph consisting of operations / 一张由一系列操作构成的计算图；
在实际应用时，大家经常高性能的 kernel 库（比如 Intel MKL-DNN 和 OpenBlas）来提高 CNN 操作性能；
这些库一般输入目标数据形状（比如 2D 卷积），然后进行常规调用操作，但是这些库大多数情况下只关注于（大多数情况下是卷积）操作，而错过了在图级别进行进一步端对端模型推理的优化机会；
图级别的优化往往是交给深度学习框架，比如 TensorFlow 和 MXNet；
然而，图级别的优化，比如 operation fusion / 操作融合 和 data layout planning / 数据布局规划，往往因为已经在第三方库中被预先定义而被限制；
因此框架中的优化工作和 kernel 库中的优化相冲突，这使得有性能提升空间但是没有被发掘；
此外，不同的 CPU 架构会依赖不同的高性能库，把库和深度学习框架整合很容易出错，而且很耗费开发时间；
而且尽管这些库被高度优化过，它们是作为第三方的 plug-ins，这使得可能会和框架中其他的库引起冲突；
比如说 TensorFlow 原本使用 Eigen 库来处理 CPU 的计算，后来引入 MKL-DNN，所以运行 MKL-DNN 线程会和 Eigen 的线程导致资源争用，引起冲突；
所以这种 framwork-specific / 依赖框架 的方法，用于 CPU 上进行 CNN 模型推算是不灵活，麻烦而且效果不好的；
由于框架的限制，如何不引入框架（比如 framework-agnostic / 框架无关 method），来进行 CNN 模型推理性能的优化成为了很多人想要解决的问题；
最近，Intel 发布了一款通用的 CNN 模型推理引擎，称之为 OpenVINO 开发套件；
这款开发套件在 x86 平台的 CPU 进行计算机视觉任务的 CNN 模型优化，而且相比于单独使用深度学习框架，能够获得更好的性能；
由于 OpenVINO 也是基于 MKL-DNN 来进行调用操作，所以只能提供有限的 Graph-level / 图级别 的优化（比如 ngraph 中的操作融合）；
因此 OpenVINO 进行优化对于大多数 CNN 模型意义不大；
基于之前的研究观察，我们得出这样的结论——“flexible end-to-end optimization / 灵活的端对端优化” 是进一步提高 CNN 模型推理能力的关键；
这篇文章中，我们建议使用 NeoCPU 方式进行 CPU 上 CNN 模型的优化；
NeoCPU 是全栈的和系统性的，其中包括操作界别和图像级别的联合优化，而不是依靠第三方高性能库；
在操作级别，我们利用成熟的技术来优化计算量最大的操作，比如模板中的卷积操作，适用于在不同 CPU 架构上跑不同负载，而且让我们可以在图级别灵活操作；
在图级别，除了常规的比如操作融合和推理简化，我们通过操纵数据布局流程来协调各个操作的优化，贯穿整个模型以获得最佳的性能表现；
总而言之，NeoCPU 通过一种灵活和高效的方式，进行端到端的优化，而现有的其他方式往往依赖于第三方库，需要进行性能调优；
NeoCPU 基于深度学习编译栈 TVM 进行一系列改进；TVM 让我们可以进行操作级别的优化，而不是依赖于第三方库，这使得我们很灵活的可以进行 operation-level / 操作级别 和 graph-level / 图级别 的整合；
然而，在 ARM CPU 上，只有一种对于特定类型数据，进行定制化的 operation-level / 操作级别 的优化；
在此之前，TVM 没有提供 operation-level / 操作级别 和 graph-level / 图级别 的联合优化功能；
除此之外，一些其他深度学习编译器比如 Tensor Comprehensions 和 Glow，它们都不是专注于在 CPU 上进行优化，或者对于 CPU 上优化的性能提升没有那么显著；
比如基于文章描述以及我们自己的实验，Glow 仅仅优化 CPU 中的单核性能，因此我们不建议采用这种方式；
这篇文章会介绍以下几点：
- 提供一种在不同主流 CPU （Intel, AMD 和 ARM）上的 operation- and graph-level joint optimization scheme / 操作级别和图级别的联合优化方案 来获取高性能的 CNN 模型推演性能，表现要好过目前的其他方案；
- 构建一种模板可以进行高效率的卷积，通过这种方式，可以灵活的在不同架构 CPU （x86 和 ARM）上进行卷积操作的优化，而不需要依赖于第三方高性能内核库；
- 设计一种全局的方案，在一个 CNN 模型中的不同操作组合中，寻找最优布局方式，在保证高性能的同时，减少操作之间数据布局转换带来的开销；
值得注意的是，本文主要考虑 direct convolution computation / 直接卷积运算，NeoCPU 也兼容在其他计算密集型内核上的优化工作，比如通过 Winograd 和 FFT 进行卷积；
用 15 种主流的神经网络进行测试，我们在 x86 和 ARM 架构的 CPU 上进行了 NeoCPU 的评估，NeoCPU 的表现出色：
- 在 Intel Skylake CPU 上，15 种中 13 种最优；
- 在 AMD EYPC CPU 上，15 种中 14 种最优；
- 在 ARM Cortex A72 CPU 上，15 种中 15 种最优；
值得注意的是，在 x86 CPU 上，Intel 利用 Intel MKL-DNN 进行调优，而对于 AMD 的 CPU 优化程度很低；
选择 framework-specific / 指定框架（比如 MXNet 和 TensorFlow）和 framework-agnostic / 框架无关（OpenVINO）的解决方案，往往在某一种情况下表现突出，而在另一种情况下表现较差；
而 NeoCPU 在不同架构的 CPU 上的表现十分的均衡高效；
除此之外，NeoCPU 提供一个小尺寸的独立模块，不依赖于框架或者高性能内核库，可以在不同平台上轻松部署；
NeoCPU 在 Amazon 的 SageMaker Neo Service 上部署使用，使得模型开发者可以在基于 CPU 的云端服务器和边缘端设备进行推算优化；
已经有很多应用开发者在借助 NeoCPU 在不同平台上进行 CNN 模型的部署推算优化；
所有的源码都在 TVM 的开源项目中进行发布；
这篇文章剩下部分介绍如下内容：
- 第二章介绍了现代 CPU 的背景和典型的 CNN 模型；
- 第三章介绍了我们提出的优化思路以及如何实施；
- 第四章介绍了对于该方案的评估；
- 第五章介绍了相关工作；
- 第六章总结；
2 背景
2.1 现代 CPU
尽管加速器比如 GPU 和 TPU 在深度学习中表示出色，但是很多深度学习的计算工作，尤其是 model Inference / 模型推理，是在 CPU 上进行的；
如今，大多数 CPU 都是 Intel 或者 AMD 的 x86 架构，与此同时 ARM 的 ARM CPU 占据了嵌入式和移动设备市场；
制程工艺的提升，晶体管尺寸不断变小，使得我们可以制造出更大规模和更复杂的处理器，借此 CPU 通过增加核心数来实现和提高并行计算能力；
在一个多核处理器上，要避免不同线程之间的干扰至关重要，最小化线程间的 synchronization cost / 同步损耗；
在处理器内部，一个单个物理核通过 SIMD (single-instruction-multiple-data，单指令多数据流) 技术来达到最高性能；
SIMD 将多个值加载到 wide vector registers / 宽向量寄存器，然后一起处理；
(* SIMD 是一种采用一个控制器来控制多个处理器，同时对一组数据（数据向量）中的每一个分别执行相同的操作，从而实现空间上的并行性的技术；)
比如 Intel 提出了 512-bit Advanced Vector Extension instrcution set （AVX-512），在每个 CPU 循环周期，处理 16 个 32 位单精度浮点数（总共 512 位）；
AVX2 在 256 位的寄存器中处理数据；
除此之外，这些指令集利用 Fused-Multiply-Add (FMA) 技术来执行向量化的乘法，然后在同一个 CPU 循环周期中，将累加结果存储到另一个向量寄存器中；
类似于 SIMD 的技术也被集成在 ARM CPU 和 NEON 上；
我们希望能够找到一种在 x86 和 ARM 的架构 CPU 上通用的优化方式；
除此之外，值得注意的是，如今大多数服务器端的 CPU 通过 simultaneous multi-threading (SMT) 技术，支持 hyper-threading / 超线程 技术；
这样的话在一个物理核上可以有两个虚拟核，用来提高系统吞吐量；
然而超线程对于性能的提升取决于应用程序；
在我们的案例中，我们不使用超线程，因为一个线程会占用对应物理核心的资源，如果在同一个物理核上再开一个线程，会造成性能下降；
我们还会通过共享内存模式 （典型 CNN 模型推理中的系统设置）来限制我们的优化在处理器内；
Non-Uniformed Memory Access (NUMA) / 非统一内存访问 不在本文讨论范围之内；
2.2 Convolutional neural networks / 卷积神经网络
Convolutional neural networks （CNNs）/ 卷积神经网络 在计算机视觉任务中大规模使用；一个 CNN 模型经常被抽形成一个 computation graph / 计算图；
本质上计算图就是 Directed Acyclic Graph (DAG) / 有向无环图 ，一个节点代表一个操作，一个从 X 连到 Y 的线表示操作 X 输出，然后输入到操作 Y）；
执行一个模型推理实际上就是在计算图中输入数据，然后得到输出；
进行图的优化（比如 prune unnecessary nodes and edges / 删除多余节点，pre-compute values independent to input data / 预计算值独立于输入数据）可以提高模型推算性能；
CNN 模型推理中的中的绝大多数计算工作，是在 convolutions (CONVs) / 卷积；
这些操作本质上完全可以利用 CPU 中的并行化，矢量化和 FMA 特性；
已有的研究表明，通过对数据布局的优化调整，完全可以在 CPU 上进行卷积操作的优化；
剩下的挑战就是如何有效的管理数据流程，来让 CNN 模型推理获的高性能；
CNN 其余工作大多数都是卷积中和内存相关的操作（比如 batch normalization / 批量归一化，pooling / 池化，activation / 激活，element-wise addition / 逐元素添加 等等）；
常规做法是将它们融入卷积操作，提高整体的算法复杂度，来提高性能；
CNN 模型的计算图训练本质上和推理没有区别，仅仅更大规模（加入了 backwards 运算）和一些计算上的琐碎运算（比如损失函数）；
因此针对于 CNN 模型推理时的优化工作也可以用于训练；
3 Optimizations / 优化
这章我们会介绍我们的优化思路以及如何实现；
这篇文章中介绍的 CNN 模型推算优化方法是针对于 end-to-end / 端对端 情况；
我们的给出的方案，适用于大多数常见的 CNN 模型；
基本思路是把优化视为一个端对端的问题，然后寻找全局的最佳优化，也就是说，我们不关注于对于单个操作的优化；
为此，我们首先介绍如何利用可配置的模板，来进行 low-level computationally intensive convolution operations / 低层密集型卷积运算 的优化；
通过选择运算间适当的数据布局，来减少不必要开销，使得在一个特定 CPU 架构上，针对一个特定的卷积任务，找到最优实现方式更加灵活；
我们基于 TVM stack，在 compiling pass / 编译过程， operation scheduling / 操作调度 和 runtime components / 运行组件 加入了一些新特性来实现优化；
原生的 TVM stack 已经实现了一些图级别的优化（包括 operation fusion / 运算融合，pre-computing / 预运算 和 simplifying interfence for batch-norm and dropout / 归一化和丢弃的简化），这些在我们的项目中也进行了采用，但是在此不会去介绍；
3.1 Operation optimization / 运算优化
卷积运算的优化对于整个 CNN 任务性能的提升至关重要，因为卷积运算占据了整个运算过程中的大多数；
这是一个已经深入研究过的问题，但是以往的解决方法往往是在汇编代码层面去研究；
在这一节，我们会利用利用 CPU 的特性（SIMD，FMA，并行化等等）来针对单个 CONV 进行优化，而无需考虑繁琐的汇编代码和 C++ 代码；
通过全局的管理实现，会很容易的把我们的优化方式从单个运算拓展到整个计算图；
3.1.1 Single thread optimization / 单个线程优化
我们首先在一个线程中进行 CONV 优化；
CONV 操作计算量大，需要多次遍历操作数来进行运算； 因此管理输入到 CONV 的数据布局至关重要，是减少内存访问开销的关键；
我们首先回归到 CONV 运算本身来说明内存管理机制；
CNN 中一个 2D 的 CONV 输入 一个 3D 特征（高度 x 宽度 x 通道数）和 多个 3D 卷积核（通常比高度和宽度小，但是和通道数一样），输出另一个 3D 的 tensor / 张量；
计算过程在图 1 中进行说明（六个参数：in_channel, kernel_height, kernel_width, out_channel, out_height 和 out_width）：
卷积核在输入特征图上滑动，对应位置相乘求和，产生输出特征图中相应的元素，可以利用到 FMA；
卷积核的数目构成了 out_channel；
注意 in_channel，kernel_height 和 kernel_width 相互约束，不能被 embarrassingly parallelized / 高度并行化处理 ；
我们使用传统的输入方式 NCHW （输入和输出是 4D 的张量，N：批次大小， C：通道数，H：特征图高度，W：特征图宽度）来描述我们默认的数据布局；
相关的卷积核是 KCRS（K：输出通道，C：输入通道，R：核高度，S：核宽度）；
根据经验，我们将特征图的格式设置为 NHCW[x]c （c 是通道数 C 拆分出来的子维度，x 是子维度的分割大小）；
比如 sizeof(c) = x，通道数 C = sizeof(C)x sizeof(c) 大小；
输出和输入一样格式： NCHW[y]c，这里分割因子可以不同；
对应地，卷积核是 KCRS[x]c[y]k，分割尺寸为 x 的 c 和分割尺寸为 y 的 k，是输入通道 C 和 输出通道 K 的子维度；
值得注意的是为了得到理想的布局，需要有大量数据转换的资源开销；
除了尺寸地重新排序，为了更好利用最新的向量指令集（比如 AVX-512，AVX2，NEON 等等），我们借助算数因子 reg_n 把 out_width 分成了 ow_outer 和 ow_inner，然后把 ow_inner 的循环移动到 register blocking 内部；
比如在一块支持 AVX-512 的 CPU 上，我们可以利用 32 x 512 位宽度的寄存器 ZMM- ZMM；
我们保持这样的循环机制：一个 ZMM 寄存器存储 kernel 数据的同时，其他的寄存器存储特征图；
通过 AVX-512F 指令集，一个 ZMM 寄存器 中存储的 kernel 值（最高 512 bits，float32 x 16 个输出通道）被用来和 多个 DRAM 中连续不断的输入特征图 相乘，这些结果之后又会被累加存储到别的 ZMM 寄存器中；
图 1 说明了这种方法思路；
针对于其他向量化的指令，我们也可以用这种思路，但是需要改变 out_width （比如 reg_n）的 split factor / 分割因子；
算法 1 总结了我们在单线程中 CONV 的优化方式，本质上是：
- Dimension ordering for friendly memory locality / 优化布局格式来优化内存访问
- Register blocking for good vectorization instruction utilization / 寄存器阻塞以实现良好的矢量化指令利用率
然而不同于其他方式，我们在高级编程语言中，我们定义了一个 template，其中 block 尺寸（x,y），使用寄存器的数目（reg_n），和 loop-unroll strategy（unroll_key）很容易就可以配置；
所以根据不同的 CPU 架构（缓存大小，向量宽度等等）或者不同的任务（特征图大小，卷积核大小等等），我们可以进行计算逻辑的调整；
这样的话很灵活，也使得我们下一步进行图级别的优化成为可能；
算法1 ：通过 FMA 实现 CONV 操作算法
3.1.2 Thread-level parallelization / 线程级别并行化
通常我们把 CONV 任务分割成几块，然后在 CPU 不同核上进行并行运行；
内核库比如 Intel 的 MKL-DNN 经常使用现成的多线程方案，比如 OpenMP；
然而我们发现利用这种现成并行方案的可拓展性并不理想；
因此我们定制化了一个 thread pool / 线程池 来高效的处理这种尴尬的并行问题；
在一个有 N 个物理核心的系统中，我们将操作的的最外层循环分成 N 份，然后分给 N 个线程；
然后我们在并发期间，通过 C++ 11 atomics 来协调线程，然后在调度程序和每个工作线程之间，通过 an single-producer-single-consumer / 单生产者单消费者模式 的 lock-free queue / 无锁队列 ；
活跃的线程在不同的物理核上运行，来保证最小化的硬件冲突，正如之前所提到，我们没有打开超线程；
对于可以被多个线程访问的全局数据结构（比如 lock-free queues / 无锁队列），我们根据需要来插入缓存进行填充，来避免线程之间的错误共享；
总而言之，这个定制化的线程池，通过这种机制，来减少资源争夺冲突，并减少线程启动开销，这使得这种方式的性能要好于 OpenMP；
3.2 Layout transformation elimination / 布局转换（开销）消除
在这一节，我们把 CNN 模型中的 单个操作优化 拓展到 整个计算图的优化；
主要的思路来源于 3.1 节介绍的从图级别减少数据布局转化开销；
之前的操作关注于单步的操作优化，而没有考虑高度优化的操作之间，数据布局转换要带来的开销；
在 CNN 模型计算中，大多数的工作量是 CONVs，而输入一般都是 NCHW[x]c ，所以我们应该确保每个 CONV 都在布局里面执行；
然而，有些 CONVs 之间的操作可能只和默认布局兼容，导致每一个 CONV 在计算之前需要将输入数据布局（NCHW 或者 NHWC）转换成 NCHW[x]c，并在最后将其转换回去；
这种转换会带来明显的性能开销；
幸运的是，从图级别去看，我们可以把 CONV 之外的布局视为一个独立的节点，仅在必要的时候去插入；
也就是说，我们消除了 CONV 计算时候发生的转换，并尽可能地通过图保持转换后的布局流程；
为了判断一个数据转换是否有必要，我们首先根据操作和数据的接触方式来分为三类：
1. Layout-oblivious operations / 布局无关操作：
这些操作不需要考虑 layout，可以在任意布局中处理数据，比如 ReLU，Softmax 等等；
2. Layout-tolerant operations / 布局半依赖操作：
这些操作需要知道处理的 data layout，比如 CONV，对于我们来说，要处理 NCHW，NHWC 和NCHW[x]c 布局； 还有其他一些操作比如 Batch_Norm， Pooling 等等；
3. Layout-dependent operations / 布局依赖操作：
这些操作只在特定 layout 里面进行，它们不接受数据转换，因此在进行这种操作之前，要事先转换好特定格式；比如 Flatten， Reshape 等等；
典型 CNN 模型中 CONVs 之间操作是布局无关的（比如 ReLU，SoftMax， Concat 和 ElemwiseAdd）或者 layout-tolerant （比如 Batch_Norm 和 Pooling）类型的，使得数据格式可以保持 NCHW[x]c 来跨越卷积层；
从 NCHW 到 NCHW[x]c 的格式转换发生在第一次 CONV 之前；CONVs 之间的的数据布局可以维持相同格式而不进行转换（比如 NCHW[x]c 的 x 值相同）；
只有依赖布局的操作，比如 Flatten ，数据布局要从 NCHW[x]c 转换回 NCHW；
实际操作中，我们首先遍历我们的计算图，来推断所有节点的数据格式，正如图 2 左边的流程图所示，然后我们将 CONVs 的布局从默认转换为 NCHW[x]c 来获得更好性能表现；
注意到为了避免进一步转换，我们把 x 定义为 a constant number / 常量；
然而为了优化性能， x 的值在不同的 CONVs 层可能不一样，所以需要进行布局转换；我们将会在 3.3 节进一步说明；
最后，将 LayoutTransform 节点相应地插入到计算图中；
因此我们仍然具有网络的 NCHW 输入输出，但是 CONV 层之间内部布局，是以优化过的 NCHW[x]c 格式存在的，正如图 2 右边所示；
值得注意的是，模型参数的布局（比如卷积核权重 ，Batch_Norm 的均值和方差）是不变的，所以可以在编译期间进行预先转换；
我们通过向 TVM stack 引入多个图级别的优化过程来实现这个方法；
通过尽可能保持 CONV 层之间，转换后的格式布局不变，和编译时候对卷积核权重的预转换，我们进一步提高了 CNN 模型推理的端到端性能；
3.3 Optimization Scheme search / 优化方案搜索
我们提出了上述的优化方案，尤其根据硬件的特点，比如 cache-size, vectorization unit width, memory access pattern 等等，对数据进行布局；
然而手动尝试所有可能的优化方式既繁琐又不切实际；
所以 3.2 节 假设通道分离出来的参数比如 NCHW[x]c 中的 x，在整个网络中不变，虽然在不同 CONVs 选取不同的 x 值会带来更好的性能；
除此之外，分离出来 output width 的参数比如 reg_n，也需要针对不同的矢量化指令集进行调整；
因此自动的最优方案寻找来进一步提升性能；
我们应该让领域专家来帮忙构建一个搜索空间（在最短的时间内，针对某种平台设备找到最佳方案）；
搜索分为两步，第一步局部搜索，找到各个计算密集型操作的优化方案，然后是全局搜索，选取组合各个方案以获得最佳的端到端性能；
在 3.1 节中提出的优化模板，证明了这种方式是可行的；
3.3.1 Local Search / 局部搜索
第一步为每个 computationally-intensive operations / 计算密集型操作（比如 CNN 模型中的 CONVs）找出优化方式；
我们用一个 tuple / 组 ：（ic_bn, oc_bn, reg_n, unroll_ker）来代表一个卷积过程，这些参数来代表在不同架构 CPU上进行不同卷积任务；
前两个参数 ic_bn 和 oc_bn 代表输入和输出通道分离出来的参数（比如 NCHW[x]c 中的 x），针对于某种 CPU，和 cache size / 缓存大小 有关；
第三个参数 reg_n 代表 Innder Loop 中要使用的 SIMD 寄存器数目，和 CPU 架构和代数有关；我们也观察到，在一个线程中使用所有的 SIMD 寄存器往往并不能带来最佳性能表现；
最后一个参数 unroll_ker 是一个布尔值 ，用来来决定是否展开对卷积核计算的循环（算法 1 中 12 行），因为有时候展开循环会通过减少 branch penaltiles / 分支转移损失 来提高性能；
局部搜索使用 3.1.1 节提到的 template 来找出这些值的最佳组合方式，来最小化 CONV 执行时间；
按照以下步骤进行局部搜索：
- 定义 ic_bn 和 oc_bn 的候选列表；为了尝试出所有的可能，我们列出通道数的所有参数；比如，如果通道数是 64，我们选取 [32, 16, 8, 4, 2, 1] 作为备选；
- 定义 reg_n 的候选列表，实际操作中，我们从 [32, 16, 8, 4, 2] 选取 reg_n 的值；
- 定义 unroll_ker 的候选列表：[True, False]；
- 遍历定义的空间来获得所有组合的执行时间，每个组合运行多次以获取平均时间；最终会生成一个按照执行时间升序排列的列表；
值得注意的是，我们通过这种配置的方法来设计这样一个 tuple，意味着我们可以根据需要去修改这个 tuple（比如加减参数，修改值）；
根据经验，在一台机器上进行一次 CNN 模型的局部搜索，需要花费几个小时，这是可以接收的；
比如在一台 18 核 Intel Skylake 处理器机器上，需要花费 6 个小时来进行 ResNet-50 中 20 个不同 CONV 任务搜索；
除此之外，我们维护了一个数据库，里面存储着每种 CPU 上每种卷积工作量（由特征图核卷积核尺寸定义）的结果，以防止在不同模型中重复搜索；
局部搜索针对于每个单独的操作的优化效果都很好，而且确实是比手动搜索更高效的方法；
然而对每个操作进行局部最优搜索，可能导致并不是全局最优；
比如两个连续 CONV 操作 conv_0 和 conv_1，如果 conv_0 的 输出分割因子（oc_bn）和 conv_1 的 输入分割因子（ic_bn）不同，我们需要进行额外的布局转换工作；
这个额外的转换带来的开销要大于局部搜索所带来的性能提高，尤其网络很大的时候；
换句话说，如果我们在整个网络中选取一个常量作为分割因子（正如 3.2 节所述），我们会在有些 CONVs 没有进行优化；
因此，我们接下来会用全局搜索来做权衡；
3.3.2 Global search / 全局搜索
在这一节，我们会将优化搜索拓展到整个计算图中；
想法是允许每个 CONV 自由的选择分割因子 x (即 ic_bn 和 oc_bn)，并考虑相应的数据布局转换所带来的时间开销；
根据 3.2 节所述，CONVs 之间的操作要么是 layout-oblivious 要么是 layout-tolerant，所以它们可以使用 CONV 操作所决定的 x 值；
我们在以图 3 中模型举例来说明我们的想法；从图中可以看到每个 CONV 有一些候选的方案（由不同的 ic_bn 和 oc_bn 组合指定）；
通过局部搜索可以得到每个组合的最短执行时间；
由于 ic_bn 和 oc_bn 的选择经常小于 10，所以组合总数一般小于 100；
选择不同的方案会带来不同的数据转化开销（CONVs 之间虚线框表示）或者不需要转换（如果某个 CONV 的 oc_bn 等于后续 CONV 的 ic_bn）；
为了简化起见，我们在图中省略了一些不影响全局搜索的操作（比如两个 CONVs 之间的 ReLu，Batch_Norm）;
但是，例如 Elementwis_Add 这种操作不能被省略，因为它需要它的两个输入操作数（CONVj 和 CONVk 的 输出）的格式是一样的；
也就是说，一个 有着 n 个 CONVs （每个 CONV 由 k 个可选方案，总数是 kx kx .. x k）的 CNN 模型，随着层数 n 增大，很容易变得很难处理；
幸运的是实际上我们可以使用一个 dynamic programming（DP）algorithm / 动态规划算法 来有效的解决这个问题；
为一个 CONV 选择方案的时候，只要记住目前的全局最优方案，考虑它自己和它的直接前向连接的 data layout / 数据布局 ，而不需要任何其他前向的 CONV；
算法 2 中介绍了这种方法；
实际上许多 CNN 模型结构很简单，可以简化成一个列表（列表中每个 CONV 只有一个前向处理）；
这种情况下，一个 CONV 完成之后，可以安全的删除掉前面处理所产生的中间状态；
对于更复杂点的结构，比如使用 Elementwise_Add 来将两个 CONV 的输出输入到下一个 CONV 就会很棘手，因为一个 CONV 的 schemes 可能需要保存下来，以后还要使用（比如图 3 中通过 Elementwise_Add 方式，CONV需要 CONV 的 schemes）
算法 2 全局搜索算法
以拓扑结构将计算图中节点进行排序；
使用候选方案的执行时间
然而，如果模型结构过于复杂，CONV 之间存在很多数据依赖关系，那么 DP 算法也会变得不好用；
比如，由于很多 concatenation blocks / 级联块 的出现，SSD 中目标检测模型的状态数可以达到万亿数量级；
这种情况下，我们介绍相似的解决方法来加速搜索；
我们将全局搜索问题，简化成编译器领域中，稍加修改的寄存器分配问题；
将寄存器分配问题模型化，每一个 node 有一个候选列表（包含所有可能寄存器选项），每个 edge 和一个 cost matrix / 开销矩阵 关联，这个矩阵描述了两个 node 之间寄存器的可用情况；
和我们全局搜索中类似，每个 CONV 有一系列的备选方案，每个 edge 和 两个 CONVs 的方案列表，所生成的 layout transformation cost matrix / 布局转换开销矩阵 相关联；
对于别的 non-CONV 的节点，比如 Elementwise_Add，会要求所有的输入必须是相同格式，我们需要把一个输入格式进行修改，然后其他的输入格式都转换过去；
因此，我们定义 non-CONV 的节点的候选列表定义为和第一个 CONV 的输入相同，并且将这两个节点之间的 cost martix 定义为相同，因为对角元素都为0，所以其他元素都无穷大；
由于我们本质上没有对网络进行更改，所以模型输出结果不变；
为了验证，我们将 NeoCPU 结果和其他结果（图像分类模型预测精度和目标检测模型预测准确度）进行比较；
4.1 Overall Performance / 整体性能表现
表 2 中，我们在不同的 CPU 平台上，测试不同优化方式对 15 种主流的 CNN 模型的性能提升影响；
1000 次采样来获取平均执行时间，每次进行一张图像推理（batch_size=1）；
总体来说，在不同的 CPU 平台使用不同的模型，NeoCPU 方法的性能表现要比其他方法好（忽略 OpenVINO 中的一些异常结果，NeoCPU 最高可以带来 11x 性能提升）；
和每个模型的最佳基准结果比较，NeoCPU的表现如下：
- 在 Intel Skylake CPU 上得到 0.94-1.15x 性能提升；
- 在 AMD EYPC CPU 上得到 0.92-1.72 性能提升；
- 在 ARM Cortex A72 CPU 上得到 2.05-3.45 性能提升；
对于 Framework-specific / 依赖框架 的方案，MXNet 和 TensorFlow 并不是在 CPU 上进行 CNN 模型推理的最佳选择；
因为缺少在 graph-level / 图级别 进行优化（比如灵活数据布局管理）的灵活性；
MXNet 支持 Intel MKL-DNN，所以在 x86 CPU 上面性能不错；
但是 MXNet 在 ARM 上比 TensorFlow 性能差，因为 Scalability Issue / 扩展性问题（图 4c 所示）；
TensorFlow 在 SSD 模型表现明显不行，因为 SSD 进行推理的时候要进行 Dynamic Decisions / 动态决策；
相比之下，OpenVINO 中框架无关的方案希望通过移除框架限制来加速性能，然而 OpenVINO 在各个模型中的性能测试结果都不稳定；
尽管一些场景下性能不错，但是有时候在一些特定的模型很慢（比 NeoCPU 在 AMD CPU 上优化 ResNet-152 慢了 45 倍）；
在进行结果分析的时候，我们没有考虑这些异常情况；
值得注意的是 OpenVINO 测量 SSD 的执行时间时候，没有把很多操作（比如 multibox detection）时间算进去；
由于 OpenVINO 不是开源的，所以无法进行内部修改来获取 SSD 模型的真实执行时间；
因为 OpenVINO 依赖于 MKL-DNN（针对于 x86 架构），所以不适用于 ARM CPU；
NeoCPU 方案的性能表现突出，因为基于我们第三章所提出的高性能优化技术；
除此之外，所有的基准优化方式很大程度依赖于第三方库（MKL-DNN，OpenBlas，Eigen）；
NeoCPU 不依赖于这些库，所以有很大的性能提升空间；
4.2 Optimization Implications / 优化意义
这一节我们会将详细介绍第三节描述的优化方案；
为了方便起见，我们在每一个 network family 分别只选取一个网络作比较；
相同 network family 的其他网络优化思路类似；
在 4.2.1 - 4.2.3 节，我们只讨论在 Intel CPU 的性能表现（优化效果也适用于 AMD 和 ARM CPU 上）；
4.2.1 节介绍 operation-level 优化，4.2.2 和 4.2.3 节介绍了 operation-level and graph-level joint optimization / 联合优化；
4.2.1 Layout optimization of CONV /
首先，我们比较了表 3 第二行中的 CONV 操作，在有无 organizing the data in a memory access / 内存访问 和 vectorized instruction utilization 向量化指令利用布局组织数据；
这是 4.1 节中大量使用的 Operation-level 优化，
我们将其复制到一个模板，然后在不更改汇编代码或者内部代码的前提下，使用 TVM 调度机制来在不同 CPU 平台上进行 CNN 模型优化；
从表 3 第二行我们可以看到，与默认数据布局（NCHW）比较有着显著提升；
两种实现方式都配置正确的矢量化，和线程级别的并行化，
也有 TVM stack 中介绍的基本图级别优化方法，比如 operation fusion / 操作融合， pre-computing / 预计算，inference simplification / 推理简化 等等；
4.2.2 Layout transformation elimination / 布局转换评估
其次，我们评估了 3.2 节介绍的，通过消除数据布局转换开销带来的性能提升；
结果如表 3 第三行所示，可以看到减少了布局转换的开销，性能提升了 1.1-1.5x；
NeoCPU 使用系统的方法来消除不必要的数据布局转换，通过推断全局的数据布局，并仅在需要的时候插入格式转换节点；
4.2.3 Optimization scheme search / 优化机制搜索
接下来，我们比较我们搜索算法产生的优化机制，和手动筛选结果的性能表现；
根据表 3 中的第三和第四行，我们可以看到 3.3 节中介绍的算法能够找到数据布局的接近最优组合；
比我们手动找出的结果性能要好 1.1-1.5 倍；
全局搜索加速了 ResNet-50（和它的 variants）获得了加速，因为网络结构更加复杂所以有更多优化空间；
作为对比，VGG-19（和它的 variants）加速效果没那么好，因为结果比较简单；
SSD 利用相似算法，获得了显著的加速效果；
结果验证了自动搜索，可以让我们不需要手动进行调参，还可以获得更好的性能；
据我们所知，NeoCPU 是唯一种目前可以达到这种程度优化的方案；
4.2.4 Multi-thread parallelization / 多线程并行化
最后，我们用 3.1.2 节提到的线程池（通常在 GCC 编译器中通过 OpenMP API 实现）实现的多线程，来进行拓展性的测试；
我们对使用了 Intel MKL-DNN，OpenBlas 和 Eigen（所有通过 OpenMP 实现多线程）的 MXNet，TensorFlow 和 OpenVINO 的结果进行对比；
我们通过环境变量来配置 OpenMP，来确保线程的分配（每个线程会在一个互不相干的核心上运行），类似于线程池的操作；
按照一张接一张的顺序（batch size=1）处理，一秒内一个模型能够处理的数目在图 4 中给出；
为了方便展示，图 4 按照 CPU 平台划分成 3 张图（Intel / AMD / ARM）；
图 4 表明我们的线程池的性能，要比 OpenMP 在 NeoCPU 或者其他方案更好；
OpenMP 启动关闭线程的开销要大于我们的线程池，而且拓展性也不好；
此外，我们观察到，有时候在添加线程时，性能表现会有波动甚至下降；
OpenMP 的性能也有可能根据实现方式不同而不同；
总结来说，我们的评估方法适用于我们的场景，但是针对于不同场景最好有自己定制化的线程池；
5 Related Works / 相关工作
深度学习在我们日常生活中应用越来越广泛，但是仍然还有很多的工作要做（在不同的硬件平台上，CPU / GPU / FPGA / 加速器 上去进行加速深度学习过程）；
如今深度学习框架经常要在不同硬件平台上，利用这些优化的实现方式来运行深度学习训练和推理；
对于一些对于推理性能有特殊要求（比如要求 低延迟 / low- latency 或者 small-binary-size ）的硬件平台，我们也需要对其进行优化工作；
NeoCPU 更加的灵活，高效的把 operation-level 和 graph-level 优化相结合；
尽管本文专注于如何在 CPU 平台上进行优化，但是这些思路也可以应用到其他硬件平台上；
NeoCPU 基于 TVM stack（ 启发于 Halide 的一个端到端的框架），TVM stack 中介绍了如何将一个深度学习网络转为 Intermediate Representations (IRs) / 中间文件 ；
也有几种其他类似的深度学习编译器比如 TensorFLow XLA，Tensor Comprehensions，Glow 和 DLVM；
然而，这几种编译器都没有类似于我们这种，在 CPU 推理优化过程的研究结果（比如 Glow 仅仅在 CPU 进行单核优化）；
我们相信我们提出的这种方案可以整合到这些框架中；
我们利用其他高性能库中，成熟的方法来优化计算密集型的 CONV 操作；
除了这些库，对于 convolutions / 卷积操作 和 matrix multiplications / 矩阵乘法 ，在 Intel CPU 上也有一些高度定制的优化；
这些工作大多数关注于单个 operation-level 的优化，根据卷积过程和 CPU 资源来进行微调，而不考虑整个网络；
这种优化可以在目标 CPU 上最大化卷积的性能，但是拓展到其他平台上做联合优化就很不方便；
和其他优化不同，我们有一个可以配置的模板来进行优化配置，这样的话对于不同架构 CPU 就可以进行很灵活的配置，在 operation-level 和 graph-level 进行联合优化也会变得很容易；
我们利用自动搜索来寻找最佳优化方式；
相似的 auto-tuning 思路在其他地方也被介绍过；
然而他们都关注于对于单个操作，进行性能调整，而我们是对于整个 CNN 模型进行全局优化考虑；
最近我们也在关注在 graph-level 进行 DNN 任务的优化，优化任务牺牲一些局部的优化性能来提高整体的优化性能；
这种非贪婪的想法和我们的思路很相似，也运用在我们的方案中；
我们受启发于 Register Allocation Problem 中的 PBQP，利用相似算法来对复杂结构模型（比如 SSD）进行全局搜索；
这篇文章利用已有的方案思路，稍加修改然后运用到新的领域；
6 Conlusion / 总结
这篇文章中，我们提出了一种端到端的解决方案，在 CPU 上用来编译和优化 CNN，来进行高效的模型推理；
实验表明，在不同种类的 CPU 上（Intel Skylake，AMD EPYC 和 ARM Cortex A72），针对 15 种主流的 CNN 模型中，和其他最先进的方案相比，我们能够达到 3.45X 性能提升；
未来我们会关注于：
- 拓展其他卷积计算算法，比如 Winograd 和 FFT；
- 支持处理量化（比如 INT8）模型推理；
- 在别的硬件平台（比如在 Nvidia 的 GPU 上和 TensorRT 比较）拓展我们 operation-level 和 graph-level 联合优化方案；