解析卷积的高速计算中的细节，一步步代码带你飞
加入Jishi Professional CV Exchange Group，与来自著名企业和大学的6,000多个视觉开发人员进行互动，例如Tencent，Huawei，Baidu，Baidu，Peking University，Tsinghua University和中国科学院！我有机会与凯·菲（Kai-Fu Lee）老师和其他大牛群互动！
同时，它提供了每月的实时广播共享大知名人士，真正的项目需求对接，干燥信息摘要和行业技术交易所。遵循Jishi平台的官方帐户，回复加入该小组，并立即申请加入该小组〜
介绍
卷积是深度学习的基本操作。那么卷积操作如何如此迅速地加速呢？让我们将其分开，然后将其分解以供您看到。
在我不太破旧的笔记本电脑CPU上开元ky888棋牌官方版，使用TensorFlow之类的库，我可以（最多）在10-100毫秒内运行最常见的CNN型号。在2019年，即使智能手机也可以在不到半秒的时间内运行“重型” CNN（例如Resnet）型号。因此，想象一下，当我定时实现自己的卷积层时，我惊讶地发现单层需要2秒钟！
现代深度学习图书馆对大多数操作都有高度优化的实现，这不足为奇。但是这些图书馆有什么魔术？他们如何将性能提高100次？我们如何“优化”或加速神经网络的操作？在讨论高性能/有效的DNN时，我经常问（经常被问到）这些问题。
在本文中，我将尝试带您了解DNN库中如何实现卷积层。我不仅是模型中最常见，最重的操作，而且我还发现，卷积高性能实施的技术特别具有代表性 - 有点聪明的算法，许多仔细的调整和低级体系结构的开发。
我在这里介绍的大部分内容来自Goto等人的开创性纸：高性能矩阵乘法的解剖结构，这为线性代数库（例如OpenBlas）中使用的算法奠定了基础。
最原始的卷积实施
“过早优化是万事万物的来源” - 唐纳德·诺斯（Donald Knuth）
在优化之前，让我们看一下基线和瓶颈。这是一个天真的numpy/for循环卷积：
'''
Convolve `input` with `kernel` to generate `output`
input.shape = [input_channels, input_height, input_width]
kernel.shape = [num_filters, input_channels, kernel_height, kernel_width]
output.shape = [num_filters, output_height, output_width]
'''
for filter in 0..num_filters
for channel in 0..input_channels
for out_h in 0..output_height
for out_w in 0..output_width
for k_h in 0..kernel_height
for k_w in 0..kernel_width
output[filter, channel, out_h, out_h] +=
kernel[filter, channel, k_h, k_w] *
input[channel, out_h + k_h, out_w + k_w]这是一个6层嵌套的循环（如果您在多个输入批次上迭代）。我们尚未研究大步，扩展或其他参数。如果我在此处输入Mobilenet第一层的大小并在正常C中运行它，那将需要22秒的惊人！使用最具侵略性的编译器优化，例如“ -o3”或“ -ofast”，它减少到2.2秒。但这对于第一层仍然非常慢。
如果我使用Caffe运行同一层怎么办？这台计算机只花了18毫秒。这要比100倍加速！整个网络在我的CPU上运行约100ms。
什么是瓶颈，我们应该从哪里开始优化？
最内向的循环执行两个浮点操作（多个和添加），对于我使用的尺寸，它的执行量约为8516万次，也就是说，该卷积需要1.7亿浮点操作（MFLOPS）。根据英特尔数据，我的CPU的最大性能为每秒800亿次，这意味着从理论上讲，它可以在0.002秒内完成这项工作。显然，我们仍然远离这个目标，很明显，这里的原始处理能力就足够了。
无法达到理论峰的原因（永远不会）是内存访问也需要时间 - 如果无法快速获得数据，则不足以快速处理数据。事实证明，上面的循环的嵌套使数据访问模式非常困难，这使得高速缓存的利用率非常低。
如您所见，在整个讨论中，反复出现的问题之一是我们如何访问正在运行的数据以及该数据如何与其存储方式相关联。
一些先决条件
我们对“性能”或速度的测量是吞吐量，该吞吐量是在每秒浮点点计算的。较大的浮点操作的操作自然会较慢，因此可以更一致的方式比较flop/s速率。
我们还可以使用它来了解我们与CPU最高性能的距离。在我的笔记本电脑CPU上：
它的峰值性能是Gflop/s。这是我CPU的理论峰值。同样，对于单个核心，此数字为80Gflop/s。
虽然我们从逻辑上将矩阵/图像/张量视为多维，但实际上它们存储在线性的一维计算机内存中。我们必须定义一个规定，该约定如何将这些多维数据扩展到线性存储中，反之亦然。
大多数现代的DL库都使用Row-Main订单存储。这意味着同一行的连续元素相互存储。更一般而言，对于多维性，行序列是指在线性扫描内存时，第一个维度会更改最慢。
那么尺寸本身的顺序呢？通常，对于CNN等四维张量，您会听到NCHW，NHWC和其他存储订单。我将在这篇文章中假设NCHW-如果我有n个块HXW图像的C通道，那么所有具有相同n通道的图像都是重叠的，在该块中，同一通道C的所有像素都重叠，依此类推。
这里讨论的许多优化需要在使用神秘的C语法甚至组装的底部进行干预。这不仅使代码难以读取，而且使尝试不同的优化变得困难，因为我们必须重写整个代码。 Halide是C ++中的一种嵌入式语言，可帮助抽象这些概念，旨在帮助编写快速图像处理代码。可以更轻松地使用分解算法（计算内容）和计划（计算方法/何时计算）更容易地实验不同的优化。我们可以保持算法不变并使用不同的策略。
我将使用卤化物来表示这些较低级别的概念，但是您应该能够理解足够直观的函数名称。
从卷积到宝石
我们上面讨论的简单卷积已经非常慢，并且由于参数，例如步长，扩展和填充，更实际的实现只会变得更加复杂。我们可以继续使用基本卷积作为一个工作示例，但是，如您所见，从计算机中提取最大的性能需要许多技巧 - 一种非常详细的调整在多个层次上进行，并利用了现有的计算机体系结构特定的知识。换句话说，如果我们希望解决所有复杂性，那将是一项艰巨的任务。
我们可以将其变成更容易解决的问题吗？也许矩阵乘法？
矩阵乘法，或矩阵或广义的matrixmultiplication（GEMM）是深度学习的核心。它用于完全连接的层，RNN等，也可以用于实施卷积。
毕竟，卷积是带有输入填充的滤波器的点产物。如果将过滤器放入二维矩阵中，请将输入的小贴片放入另一个矩阵中，然后将两个矩阵乘以相同的点产品。与CNN不同，在过去的几十年中，矩阵乘法已进行了广泛的研究和优化，并且在许多科学领域都是关键问题。
将图像块放入矩阵中的上述操作称为IM2COL，用于图像列。我们将图像重新排列到矩阵的列中，以使每个列对应于使用卷积过滤器的贴片。
考虑这个普通的直接3x3卷积：
以下是与矩阵乘法相同的操作。正确的矩阵是IM2COL的结果 - 必须通过在原始图像中复制像素来构造它。左侧的矩阵具有转为权重，它们已经以这种方式存储在内存中。
请注意，矩阵产品可直接给出Conv输出 - 不需要其他“转换”到原始表单。
为了清楚起见，我将在这里分别显示每个补丁。但是，实际上，不同的图像块之间通常存在一定的重叠，因此IM2COL会产生一定的内存重复。生成此IM2COL缓冲区和肿的内存所需的时间必须被GEMM实现的加速度所抵消。
使用IM2Col，我们将卷积操作转换为矩阵乘法。现在，我们可以插入更通用和流行的线性代数库，例如OpenBlas，eigen等，并使用数十年的优化和仔细的调整来有效地计算此MATMUL。
如果我们要证明IM2Col转换带来的额外工作和记忆是合理的，那么我们需要一些非常严重的加速度，因此让我们看看这些库如何实现这一目标。在系统级别进行优化时，这也很好地介绍了一些常见方法。
尽管以前存在不同形式的卷积 - 算法，但Caffe是最早在CPU和GPU上使用这种方法的深度学习库之一，并且显示出更大的加速度。这里：github.com/yangqing//wi一份非常有趣的阅读来自Yanqing Jia本人（Caffe的创始人），介绍了该决定的起源，以及关于“临时”解决方案的想法。
加速宝石
在本文的其余部分中，我认为Gemm被执行为
和以前一样，首先让我们的时间为基本的教科书矩阵乘法：
for i in 0..M:
for j in 0..N:
for k in 0..K:
C[i, j] += A[i, k] * B[k, j]
使用卤化物：
Halide::Buffer C, A, B;
Halide::Var x, y;
C(x,y) += A(k, x) *= B(y, k); // loop bounds, dims, etc. are taken care of automatically
最内向的行执行2个浮点操作（多个和添加），并执行m ∗ n ∗ k次，因此该GEMM的拖鞋为2MNK。
让我们以不同的矩阵大小来衡量其性能：
我们的表现刚刚达到了其峰值的10％！虽然我们将研究更快地进行计算的方法，但反复出现的话题是，如果我们无法快速获取数据，那么快速计算数据是不够的。由于记忆是较大矩阵的越来越大问题，因此性能将逐渐下降。您最终看到的急剧下降意味着，当矩阵变得太大而无法放入缓存中时，吞吐量突然掉落 - 您可以看到系统阻塞。
RAM是一个较大且缓慢的记忆。 CPU缓存速度更快，但要小得多，因此正确使用它们至关重要。但是没有明确的指示说“缓存负载数据”。这是由CPU自动管理的过程。
每次从主内存中检索数据时，CPU都会自动将数据及其相邻内存加载到缓存中，希望利用参考的局部性。
您应该注意的第一件事是访问数据的模式。我们在A上逐行横穿。
它们的存储也是行的主要顺序，因此一旦找到[i，k]，该行中的下一个元素a [i，k+1]已经被缓存。凉爽的。但是看看B发生了什么：
我们需要重新设计循环以利用此缓存功能。如果您正在阅读数据，我们不妨利用它。这是我们要进行的第一个更改：循环重新排序。
让我们从I，J，K到I，K，J：
for i in 0..M:
for k in 0..K:
for j in 0..N:
我们的答案仍然正确，因为乘法/加法的顺序无关紧要。现在的遍历顺序看起来像这样：
这种简单的更改只需重新排序循环，就可以快速加速：
为了进一步改善重新排序，我们还需要考虑一个缓存问题。
对于A的每一行，我们都会循环整个B。在B中的每个步骤中，我们将加载一些新列的列开元ky888棋牌官网版，并从缓存中删除一些旧列。当我们到达A的下一行时，我们从第一列开始。我们反复添加并从缓存中删除相同的数据，这称为抖动。
如果我们所有的数据都可以放入缓存中，则不会有抖动。如果我们使用较小的矩阵，它们可以愉快地生活在一起而不会反复开除。值得庆幸的是，我们可以在子序列上分解矩阵乘法。要计算C中的一个小r×c块，只需要在A中的R行，并且B中的C列C中的C中仅是C中的C。让我们将C分成6x16个块。
C(x, y) += A(k, y) * B(x, k);
C.update()
.tile(x, y, xo, yo, xi, yi, 6, 16)
/*
in pseudocode:
for xo in 0..N/16:
for yo in 0..M/6:
for yi in 6:
for xi in 0..16:
for k in 0..K:
C(...) = ...
*/
我们已经将X和Y的尺寸分解为外部XO和YO以及内部XI和Yi。我们将努力为较小的6x16块（标记为XI，yi）优化微粒，并在所有块上运行该微粒（由XO，YO迭代）。
矢量化和FMA
大多数现代CPU都支持SIMD或单个Instructionmultipledata。顾名思义，SIMD可以在同一CPU周期上同时在多个值（例如添加，乘等）上执行相同的操作/指令。如果我们可以一次在4个数据点上运行SIMD指令，则可以达到4倍加速度。
因此，当我们计算处理器的峰值速度时，我们会“有点”作弊，而是参考此矢量化的性能。这对于诸如向量之类的数据非常有用，我们必须对每个向量元素应用相同的说明。但是我们仍然需要设计内核才能正确利用它。
计算峰故障时使用的第二个“黑客”是FMA-FUSEMULTIPLY-ADD。虽然将乘法和添加算作两个单独的浮点操作，但它们是如此普遍，以至于可以使用专门的硬件单元来“ fuze”它们并作为指令执行它们。使用它通常由编译器处理。
在Intel CPU上，我们可以使用SIMD（称为AVX＆SSE）在一项指令中处理多达8个浮点数。编译器优化通常能够自行确定矢量化的机会，但要确保我们自己做。
C.update()
.tile(x, y, xo, yo, xi, yi, 6, 16)
.reorder(xi, yi, k, xo, yo)
.vectorize(xi, 8)
/*
in pseudocode:
for xo in 0..N/16:
for yo in 0..M/6:
for k in 0..K:
for yi in 6:
for vectorized xi in 0..16:
C(...) = ...
*/
到目前为止，我们只使用了一个CPU核心。我们有多个可用的内核，每个内核都可以同时实际执行多个指令。程序可以将自己分为多个线程，每个线程可以在单独的内核上运行。
C.update()
.tile(x, y, xo, yo, xi, yi, 6, 16)
.reorder(xi, yi, k, xo, yo)
.vectorize(xi, 8)
.parallel(yo)
/*
in pseudocode:
for xo in 0..N/16 in steps of 16:
for parallel yo in steps of 6:
for k in 0..K:
for yi in 6:
for vectorized xi in 0..16 in steps of 8:
C(...) = ...
*/
您可能会注意到，对于很小的尺寸，性能实际上会下降，因为线程的工作时间更少，并且在较小的工作负载下彼此同步的时间越多。线程还有许多其他类似的问题，本身可能需要进一步研究它们。
循环让我们避免一遍又一遍地编写相同的线路的痛苦，同时引入一些额外的工作，例如检查循环终止，更新循环计数器，指针算法等。 ，我们可以减少这个开销。例如，我们可以运行包含4个语句的2个迭代，而不是1个语句的8个迭代。
起初，令我惊讶的是，这种反复无常的，看似微不足道的管理费用实际上很重要。但是，尽管这些循环操作可能“便宜”，但它们肯定不是免费的。如果您记得这里的迭代次数数百万，则每次迭代的另外2-3个说明的成本将很快增加。当周期开销变得相对较小时，益处逐渐下降。
扩展是另一种优化，现在几乎完全由编译器来处理开yun体育官网入口登录app，除非像我们这样的微孔，我们更喜欢控制。
C.update()
.tile(x, y, xo, yo, xi, yi, 6, 16)
.reorder(xi, yi, k, xo, yo)
.vectorize(xi, 8)
.unroll(xi)
.unroll(yi)
/*
in pseudocode:
for xo in 0..N/16:
for parallel yo:
for k in 0..K:
C(xi:xi+8, yi+0)
C(xi:xi+8, yi+1)
...
C(xi:xi+8, yi+5)
C(xi+8:xi+16, yi+0)
C(xi+8:xi+16, yi+1)
...
C(xi+8:xi+16, yi+5)
*/
现在，我们可以达到60gflop/s。
把它们全部放在一起
上述步骤涵盖了一些最常用的转换，以提高性能。它们通常以不同的方式组合，从而产生越来越复杂的策略来计算同一任务。
这是卤化物的更仔细优化的策略。
matrix_mul(x, y) += A(k, y) * B(x, k);
out(x, y) = matrix_mul(x, y);
out.tile(x, y, xi, yi, 24, 32)
.fuse(x, y, xy).parallel(xy)
.split(yi, yi, yii, 4)
.vectorize(xi, 8)
.unroll(xi)
.unroll(yii);
matrix_mul.compute_at(out, yi)
.vectorize(x, 8).unroll(y);
matrix_mul.update(0)
.reorder(x, y, k)
.vectorize(x, 8)
.unroll(x)
.unroll(y)
.unroll(k, 2);
总而言之，它做到了：
最后，我们能够达到以上超过120 glops的速度，即接近160Gflops的峰值性能，并且能够匹配生产级库，例如OpenBlas。使用类似的IM2COL微调代码，其次是GEMM，现在相同的卷积为约20ms。如果您有兴趣研究这一点，可以尝试使用自己的不同策略 - 作为工程师，我总是会听到有关缓存，性能等的信息。看到它们的真实影响可能是有益的，很有趣。
请注意，此IM2Col+GEMM方法是大多数深度学习库中流行的一般方法。但是，自定义是关键 - 对于特定的共同大小，不同的体系结构（GPU）和不同的操作参数（例如腹胀，分组等），这些库可能会再次使用类似的技术或假设来对这些情况进行更新。定制实现。这些微动物是通过反复试验和高度迭代过程来构建的。程序员通常只对应该/不应该奏效的内容和/或必须根据结果考虑解释的直觉。听起来很适合深度学习研究，对吗？
原始英语链接：
