高性能零存储开销直接卷积论文及其理解

论文下载地址:http://proceedings.mlr.press/v80/zhang18d.html

简略翻译

                                                                            高性能零存储开销直接卷积

摘要

计算中的卷积神经网络的深层通常是依赖于高性能的程序时使用额外的贸易空间的内存或任何所需的一部分。用于包装用途的算法来提高性能。这样的方法存在两个问题。首先，这些例程会引起额外的内存开销，从而减少能够适合于具有有限内存容量的嵌入式设备的网络的总体大小。其次，这些高性能例程没有针对执行卷积进行优化，这意味着获得的性能通常低于常规预期。在本文中，我们证明，当正确实现时，直接卷积消除了所有的内存开销，并且产生的性能比传统和嵌入式CPU架构上卷积层的现有高性能实现高10%到400%。我们还表明，当增加线程数量时，高性能直接卷积具有更好的伸缩性能，即性能下降较小。

1 .导言

传统观点认为，通过直接卷积计算深层神经网络中的卷积层不是有效的。因此，在深层神经网络中计算卷积层的许多现有方法(.等人，2014；Cho & Brand，2017)基于在诸如基本线性代数子程序(BLAS)(.arra等人，a)等计算库中发现的高度优化的例程(例如，矩阵矩阵矩阵乘法)。L，1990）。为了利用矩阵-矩阵乘法例程，这些框架重塑并选择性地复制原始输入数据的一部分（统称为打包）。从而为性能带来额外的内存空间。

这种方法存在两个问题：首先，重新整形和复制输入数据的元素的额外工作是一个带宽受限的操作，这会导致额外的操作，和非平凡的时间惩罚对整个系统性能的影响。第二，更重要的是，卷积层产生的矩阵通常具有与传统高性能计算（HPC）应用程序产生的矩阵不同的维度。因此，矩阵矩阵乘法例程在卷积矩阵上的性能通常不如HPC矩阵好。

为了说明现有方法的这些缺点，考虑使用图1所示的AMD Piledriver体系结构在AlexNet中的各种卷积层上获得的4线程性能。在这个图中，我们展示了：1)一个传统的基于矩阵乘法的卷积实现与OpenBLAS1 (OpenBLAS)(蓝色)和2)我们提出的高性能直接卷积实现(黄色)相关联的性能。这两种实现的性能都标准化为仅矩阵-矩阵乘法例程(虚线)的性能。这条虚线是在无填充的情况下矩阵-矩阵乘法所获得的性能。注意，OpenBLAS +填料的性能仅达到矩阵乘法本身性能的不到80%。这意味着包装程序使整体性能下降了20%以上。相比之下，我们的自定义直接卷积实现的性能超过了专家实现的矩阵-矩阵乘法例程，即使打包是免费的。此外，我们在没有任何额外内存开销的情况下实现了性能。

随着基于深度神经网络的机器学习任务越来越多地被放置在边缘设备上，重新研究卷积层的计算方法是及时的(Schuster, 2010;Lee & Verma, 2013)。这些设备往往在计算能力和内存容量方面受到限制(Gokhale et al.， 2014;Dundar等)。这意味着以内存容量换取性能的现有方法不再是这些设备的可行解决方案。提高性能和减少内存开销也能带来更好的能源效率(Zhang et al.， 2014)。虽然许多工作都集中在通过近似(Kim et al.， 2015)、量化(Gong et al.， 2014)或权重的稀疏化(Han et al.， 2016)来减少卷积层的内存占用(memory footprint)，但是很少有工作解决为了使用高性能例程所需要的额外内存需求。

以下是本文的贡献:

高性能直接卷积。我们证明了直接卷积的高性能实现可以在实际性能、并行性和减少内存开销方面胜过基于专家实现的矩阵-矩阵乘法卷积。这说明直接卷积是一种可行的计算卷积层的方法。

输入/输出特征图和内核权重的数据布局。我们提出了新的数据布局，用于存储使用直接卷积算法计算卷积层所需的输入、输出和核权值。这些新的数据布局所需的空间与现有的数据存储方案相同，用于存储输入、输出和内核权重，而不是对元素进行打包或复制。

图1。高性能直接卷积实现比高性能矩阵乘法例程获得更高的性能，而基于矩阵乘法的卷积实现受到封装开销的影响并且受矩阵乘法例程的性能限制。

非直接卷积的无效率

在本节中，我们将重点介绍在许多深度学习框架中使用的现有方法计算卷积的低效性

快速的基于傅立叶变换的实现

基于快速傅立叶变换(FFT)的实现(Vasilache et al.， 2014;Mathieu et al.， 2013)提出了一种在频域计算卷积时减少浮点运算次数的方法。然而,为了使计算进行内核的重量必须填充输入图像的大小,导致内存明显多于必要的,特别当内核本身很小(例如3×3)

人们提出了其他方法来将图像细分为更小的块或块(Dukhan)。然而，这种方法还需要将内核权重填充到方便的大小(通常是2的幂)，以获得性能。即使将内核权重填充到架构寄存器大小的小倍数(例如8或16)，也会导致内存需求增加7到28倍。这种额外的填充和将内核转换为频域可以通过实时执行FFT(卷积层计算的一部分)来最小化。然而，正如我们将在性能部分(第5部分)中展示的那样，这会带来显著的性能开销，尤其是在嵌入式设备上。

矩阵Multiplication-based实现

另一种常见的方法是将输入(图像和内核权重)转换为矩阵，并利用第3级基本线性代数子程序(BLAS) (Dongarra et al.， 1990)中发现的高性能矩阵-矩阵乘法例程进行计算。这种方法有两个主要的低效之处:

额外的内存需求。为了将图像转换成一个矩阵，需要执行一个降低操作将三维图像转换成一个二维矩阵。通常情况下,这是通过一个操作执行传统称为im2col复制图像变成矩阵然后用作输入矩阵*矩阵的乘法中调用。在这个降低过程中，适当的元素也会被复制。所需的额外内存随问题大小呈二次增长(Cho & Brand, 2017)。

Cho和Brand (Cho & Brand, 2017)提出了一种替代的降低机制，即通过减少包装过程中需要的重复数量来提高内存效率。在它们的降低例程中，内存占用比im2col平均减少3.2倍。这是通过消除所需的重复数量，以牺牲额外的矩阵-矩阵乘法调用来实现的。尽管如此，这仍然是一个额外的内存需求，而且它们的计算仍然依赖于矩阵-矩阵乘法，对于由卷积产生的矩阵来说，这种乘法通常不是最优的。

                            （Sub-optimal matrix matrix multiplication.）次优矩阵矩阵乘法。

在大多数BLAS库(如GotoBLAS (Goto &van de Geijn,2008)、OpenBLAS (OpenBLAS)、BLIS (van Zee &van de Geijn, 2015)中，矩阵-矩阵乘法例程在内部维即。两个输入矩阵之间共有的维数，输入矩阵的维数与输出矩阵的总体维数相比很小。这种特殊的矩阵形状集合通常在科学和工程代码中找到，这些代码对这些库进行了优化。然而，这种特殊的形状集只适用于六种矩阵乘法算法中的一种(goto&van de Geijn, 2008)。

记得im2col重塑输入矩阵。这意味着输入矩阵的内部维度通常大于两个维度(参见图2)。因此，矩阵乘法在这组特定输入形状上的性能通常明显低于最佳可实现性能。已经证明，对于与卷积层产生的形状相似的形状，应该寻求计算矩阵乘法的替代算法(gunnel et al.，2001)。

矩阵-矩阵乘法在卷积层中效率低下的另一个原因是，现有BLAS库中的并行性是通过对输入矩阵的行和列进行分区得到的(Smith et al.， 2014)。矩阵的这种划分使矩阵形状偏离矩阵-矩阵乘法例程所期望的形状更远。因此  ，随着线程数量的增加，例程的效率会受到影响。

高性能直接卷积计算

直接卷积（参见算法1）的一个简单实现实质上是围绕计算单个输出元素的乘积计算语句的六个完全嵌套循环。循环排序的任何排列都会产生正确的结果。然而，为了获得直接卷积的高性能实现，必须将这些循环及其顺序适当地映射到给定的体系结构。

将循环映射到体系结构的策略

我们将循环映射到模型架构的策略类似于高性能矩阵矩阵乘法的分析模型（Low等人，2016）。（1）首先介绍了高性能矩阵矩阵乘法的模型结构。（2）接下来，我们确定有效利用可用计算单元的循环。(3)最后，为了改善数据重用，我们识别外部循环的顺序，这反过来将减少引入计算中的性能降低的停顿量。在本讨论中，我们使用算法1中所示的索引变量（i，j，k，l，m，n）来区分循环。

模型架构

我们使用了用于高性能矩阵乘法的分析模型的模型体系结构(Low et al.， 2016)。假定模型体系结构具有以下特征:

向量寄存器。我们假设我们的模型架构使用单个指令多个数据(SIMD)指令集。这意味着每个操作同时对标量输出元素执行其操作。我们还假设是2的幂。当为1时，这意味着只有标量计算可用。此外，所有的逻辑寄存器都是可寻址的。

FMA指令集，我们假设存在可以计算融合多添加指令(FMA)的单元。每个FMA指令计算一个乘法和一个加法。每个单元可以在每个周期(即但是每条FMA指令都有周期的延迟。这意味着周期必须通过，因为FMA指令发出后才能发出后续依赖的FMA指令。

加载/存储体系结构。我们假设该体系结构是一个加载/存储体系结构，在对加载的数据执行操作之前，必须将数据加载到寄存器中。在具有直接从内存计算指令的体系结构上，我们假定这些指令没有使用。

循环饱和计算

当所有单元在每个周期中计算一个FMA时，我们的模型体系结构上的最大性能将得到满足。但是，由于每个FMA指令都有周期的延迟，这意味着至少必须有独立于的FMA指令被发送到每个计算单元。由于每个FMA指令都可以计算输出元素，这意味着：

其中是为了达到最大可达到的性能，每个循环中必须计算的独立输出元素的最小数量。

图2。5×5输入图像与三种不同渠道(用不同的颜色表示)与两个独立的内核卷积得到一个3×3和两个输出通道输出。为了利用高性能的矩阵乘法例程，将三维输入图像(左)转换为二维矩阵(右)。由于As Co and/or (Ho× Wo) are often less than Hf × Wf × Ci,在许多BLAS库中，标准矩阵-矩阵乘法的性能通常不是最优的

在确定在每个周期中必须计算至少个输出元素之后，下一步是确定这些输出元素在卷积层的总体输出内的布置。注意，输出具有三维，其中主要是输入大小的函数，而是卷积层的设计参数。由于必须是的倍数，即2的幂，并且可以选择（在实践中也是这种情况）为2的幂，所以j环被选择为最里面的环。

由于最小数高度依赖于FMA计算单元的数量和能力，我们希望确保有足够的输出元素来完全饱和计算。这样，对输出图像的同一行中的元素进行迭代的k循环被选择为围绕j循环2的循环。

循环以优化数据重用

后续循环的顺序是尽可能有效地将数据引入计算单元。

回想一下，内部两个循环(j和k)在多个输出元素上迭代，以确保能够执行足够的独立FMA操作，以避免计算单元中的停顿。由于我们的模型体系结构是加载/存储体系结构，这意味着这些输出元素已经在寄存器中。因此，我们希望引入数据，使我们能够累积到这些输出元素中。

回想一下,计算单个输出元素,所有权重从输入图像中乘以适当的元素累积到输出元素。这自然意味着接下来的三个循环按顺序从最里面到最外面依次是i、m、n个循环。这个循环的顺序是根据大多数卷积层的输入是另一个卷积层的输出来决定的。这意味着，如果以相同的顺序访问来自输入和输出的数据，将是可取的。因此，我们希望在行(n)之前访问通道(i)中的输入元素，这就给出了循环的i、n、m顺序。在最初的6个循环中决定了5个，这意味着最外层的循环必须是l循环。这个循环通过输出的不同行遍历其余行。原循环顺序如算法1 (i, j, k, l, m, n)所示，转换为(l, n, m, i, k, j)循环顺序如算法2所示。

内存层次结构块

寄存器阻塞。聪明的读者将认识到，我们已经方便地忽略了这样一个事实，即是维持峰值性能所需的最小输出元素的数量，它由寄存器数量上限，如以下不等式所述：

                                       (2)

可用寄存器的数量强加的这个上限意味着最多NregNvec元素可以保存在寄存器中。这意味着，不是对所有元素进行迭代，而是必须将块大小为和的循环阻塞/平铺（Wolfe，1989）应用于两个最内部的循环，以避免会降低性能的寄存器溢出。

对原始j和k循环应用循环阻塞将每个输出通道中的一行分解为更小的输出图像，每个输出图像分别具有行宽度和和的输出通道。由于循环阻塞将整个卷积分解为较小的卷积，因此前面描述的循环排序仍然适用。然而，我们现在需要确定如何在较小的卷积上遍历。

循环j0和k0分别对输出的通道维度和行维度中的块进行迭代。此外，循环JJ和KK与相应的通道和行块迭代。我们对访问同一行中的输入元素的观察将要求我们还访问同一行中的内核权重。这表明循环的排序应该类似于遍历内核权重的循环。这样，K0循环嵌套在l和n循环之间。j0循环被设置为最外面的循环，因为它是促进并行化的并行循环。

缓存块。在具有内存层次结构中更多级别的架构（即具有缓存的架构）上，我们可以进一步将输入数据集划分成更小的分区，以便它们适合于缓存的适当级别。回想一下，围绕jj和kk的循环将中间结果累积到寄存器中存储的输出中。由于和，即内核权重的大小，通常小于，因此我们选择对i循环进行分区，该i循环在输入通道上迭代，用于内存层次结构中的下一级。

高性能直接卷积的最终算法如算法3所示。

并行性

为了识别可能的并行算法，我们首先观察到所有输出元素都可以并行计算。由于输出是一个三维对象,这意味着并行性,可以提炼出至少三个不同的维度。

我们的直接卷积实现提取了输出通道维的并行性。每个线程分配一块来计算输出元素,其中每个块输出元素的大小,是使用线程的数量.

卷积计算友好的数据布局

我们为输入数据和内核数据提出了新的数据布局，以便尽可能以单位步幅访问数据。这改进了数据访问，并避免了从较低内存层次结构访问数据时出现代价高昂的停顿。修改布局的一个关键条件是输出图像和输入图像应该具有相同的数据布局。是因为大多数卷积层的输入是另一个卷积层的输出。保持它们在相同的数据布局将避免卷积层之间代价高昂的数据重塑。但是，为了保证与原始输入图像的兼容性，我们没有将所提出的布局强加于第一个卷积层的输入。

4.1输入/输出布局

我们希望以单元跨度访问输出数据。因此，我们通过考虑如何使用算法3中所示的循环顺序访问元素来确定输出数据布局。在内部循环中访问的数据应该比在外部循环中访问的数据更紧密地排列在内存中。五个循环在输出数据上迭代，这意味着一个五维的数据布局。然而，如果我们要将其用于输入数据，这就不是最优的。这是因为输入行中的元素需要计算一个输出元素。在五维布局中，输入的一行被分成元素的块。这意味着，需要来自两个独立的块的输入元素的输出元素将会产生很大的损失，因为这些输入元素在内存中间隔了很大的距离。因此，我们不根据kk循环布局数据。建议的输入/输出布局如图3(左)所示。输出数据被组织成的顺序块，在每个块中，首先在通道尺寸中布置元素，然后被组织成长度为的铅笔的行-主序矩阵。

4.2.内核配置

类似于输入/输出布局，我们使用循环排序来确定如何将内核权重排序到顺序存储器中。注意，算法3中的循环在单个输出通道中迭代输出的高度和宽度。由于同一输出通道中的所有输出元素共享相同的内核权重，因此这些循环不提供关于应该如何存储内核权重的信息。因此，我们只考虑剩下的六个循环。

剩余的六个循环所提出的内核布局如图3（右）所示。内核布局中最快的尺寸是块的输出通道尺寸，并且由最里面的循环指定。从最快到最慢的其余维度是块输入通道（），接着是内核的列和行、输入通道 以及最后是输出通道。

4.3.向后兼容

鉴于卷积神经网络(CNN)在现场的成功部署，所提出的数据布局的改变将意味着训练好的网络不能直接从我们提出的直接卷积实现中受益。然而，为了使训练后的网络使用我们提出的算法，将核权重重新排列到建议的数据布局中只需要一次的成本.其他网络层，如skip layers （He等人，2015）和激活层是点式操作，在实现中不需要任何重大改变。然而，重新排序用于计算这些层的循环将可能产生更好的性能。

结果

在本节中，我们将针对各种体系结构上的现有卷积方法展示直接CNN实现的性能结果。选择传统的CPU体系结构（Intel和AMD）和在嵌入式设备上发现的嵌入式处理器（ARM）的混合物。

实验装置

平台我们在Intel Core i7-4770K、AMD FX(tm)-8350、ARM Cortex-A57架构上进行了实验。这些平台的架构细节列于表中。

软件。我们使用HPC社区的技术来实现我们的直接卷积（Velas等人，2016）。我们将直接卷积实现的性能与链接到高性能BLAS库的基于矩阵乘法的卷积的性能进行比较。对于基于矩阵乘法的卷积，首先使用Caffe的im2col例程将输入数据打包到适当的矩阵中，然后调用高性能的单精度矩阵乘法(SGEMM)例程。所使用的SGEMM例程依赖于体系结构。关于Intel架构，我们链接到Intel的数学内核库（MKL）（Intel，2015），而OpenBLAS（OpenBLAS）用于其他两个架构。我们还提供了与NNPACK（Dukhan）提供的基于FFT的卷积实现的比较，NNPACK（Dukhan）是一个软件库，它支持Caffe 2（caffe2）中基于FFT的卷积。由于NNPACK提供了多个基于FFT（包括Winograd）的实现，因此我们只报告最佳（最快）实现所获得的性能。我们使用NNPACK提供的基准程序来执行我们的测试.

基准。所有实现都是针对AlexNet(Krizhevsky等人，2012)、GoogLeNet(Szegedy等人，2015)和VGG(Simonyan & Zisserman，2014)中所有的卷积层运行的。这三个CNN中的不同卷积层跨越输入、输出和核权重的大小范围。它们还通常用作演示卷积实现的性能的基准。

Performance

标准化为SGEMM+打包方法的不同实现的相对性能如图4所示。我们的直接卷积实现在所有架构上都比所有基于SGEMM的卷积执行至少10%和400%。即使BLAS库（MKL）对卷积产生的适当矩阵形状进行了优化，我们的直接卷积的性能也优于SGEMM。相对于只对HPC矩阵进行优化的BLAS库（OpenBLAS），我们看到在4个线程上的性能增益至少为1.5倍。

与NNPack提供的基于FFT的实现相比，直接卷积实现在ARM上的所有层上都明显优于基于FFT的实现。由于FFT是内存带宽受限的，我们怀疑FFT可能是较小体系结构（如ARM）的瓶颈，其中可用带宽可能受到限制。在Intel架构上，结果类似于直接卷积优于基于FFT的实现。然而，在这种情况下，只有当数据集“足够大”以摊销执行FFT本身的成本时，基于FFT的实现才能超过基于SGEMM的方法。NNPACK不支持AMD体系结构。

图3。输入/输出（左）和内核权重（右）的卷积友好布局。输出数据被组织成的顺序块，在每个块中，最快的维数是通道维数，其次是输出的列和行维数。将核权组织成块,最快维数是块输出通道,接着是被块的输入通道、内核的宽度和高度、输入通道和输出通道。

并行性能

在图5中，我们通过将实现与越来越多的线程并行化来比较卷积性能的可伸缩性。

在所有体系结构上，我们报告标准化为在一个线程上获得的性能的多线程实现的每核性能。注意，现有基于矩阵乘法的卷积的每个核的性能随着线程数量的增加而显著降低。这表明，随着线程数量的增加，现有基于矩阵乘法的实现对处理器的利用效率降低。我们的直接CNN实现表明，随着线程数量的增加，每个核的性能下降最小。

只有当线程的数量是物理内核数量的两倍时，我们实现的每个内核的性能才会显著下降。这是预期和重要的，因为它表明我们的实现有效地利用了计算单元，并且增加了线程的数量，超过了物理计算单元的数量，从而造成了对计算资源的过度争用，从而导致每个芯片性能急剧下降.

6 .结论

本文证明了直接卷积是一种在计算卷积层时被忽略的计算技术，它与现有的卷积层计算技术具有竞争力。我们证明了一个高性能的直接卷积实现不仅消除了所有额外的内存开销，而且获得了比专家实现的基于矩阵乘法的卷积更高的性能。我们还表明，我们的实现规模更大的处理器数量我们的实现利用了具有最高并行性的内核维度，因此性能不会降低。相比之下，当前基于矩阵乘法的高性能实现不能很好地扩展到更大数量的处理器。

我们的直接卷积实现目前达到了Intel、AMD和ARM体系结构理论峰值的87.5%、58.2%和88.9%，而HPC矩阵上的SGEMM达到相同体系结构89%、54%和92%的峰值。虽然我们已经表明我们的直接卷积实现是有竞争力的（在峰值SGEMM性能的3%以内），但我们相信通过采取自动调优（Bilmes等人，1997；Whaley & .arra，1998）或用于识别不同回路的块参数的分析方法(Yotov等人，2005；Low等人，2016)。这些方法还允许探索并行性的不同组合，以确定合适的并行策略。这是我们在不久的将来要追求的目标。

这项工作产生的另一个可能的方向是使用类似的设计技术来优化反向过程，从而在图像和内核中进行更新。考虑到前向和后向过程的相似性，我们认为只需要对循环排序进行少量更改。

最后，我们相信我们的直接卷积算法可以移植到GPU。我们提议的数据布局类似于StridedBatchedGemm操作所需的布局（Shi等人，2016）。由于这种操作和数据布局目前由使用cuBLAS 8.0（Nvidia，2017）的Nvidia GPU支持，因此这支持了我们的信念，即我们的算法可以很容易地移植到GPU。

图4。针对现有基于FFT和基于SGEMM的高性能卷积实现的直接卷积的性能。所有实现的性能归一化到SGEMM+IM2COL例程的性能。直接卷积是很高的与所有其他实现相比，即使在对卷积层产生的矩阵形状进行优化的BLAS库（Intel MKL）的情况下，性能也提高了10%到400%。

图5。缩放行为随着线程数量的增加。当我们将线程数量从1增加到可用核的数量时，我们的直接卷积实现保持了每核的高GFLOP。这是一个有效的并行化算法的指示器。当线程数量超过内核数量时，过多的争用会导致每个内核的性能显著下降。相反，即使在线程数较低（例如2）时，SGEMM仍具有较差的可扩展性。

确认

这项工作是由NSF通过奖励1116802和DARPA根据协议HRUN111-13-2-007赞助的。本文件的内容、观点和结论不一定反映NSF或DARPA的立场或政策。