论文详解：有关DNN那点儿事

点击上方关注，All in AI中国

这是麻省理工学院机器智能社区（MIC）的“机器学习”系列论文中的一篇。麻省理工学院MIC旨在对整个社区进行进行关于机器学习的教育，使得大家能够更快的进入机器学习这个领域。

深度神经网络（DNN）在越来越广泛的工业应用中提供无与伦比的精度和性能，例如图像识别、自然语言处理和其他复杂问题，如自动驾驶车辆的控制。尽管与旧机器学习算法相比有了巨大的成果改进，但DNN在计算方面要求很高，并且需要大量数据集的训练，同时也需要花费大量时间。因此，已经进行了许多努力来加速训练时间以及推断时间（在给定训练模型的情况下实际进行预测所花费的时间）。

这使我们能够在更短的时间内训练更多的数据，并在移动电话或嵌入式系统等功能较弱的设备上进行更快的推理。在他们的论文“Optimal DNN Primitive Selection with Partitioned Boolean Quadratic Programming (PBQP）”中，Andrew Anderson和David Gregg采用混合方法来优化DNN计算。他们专注于寻找DNN原语选择问题的解决方案，可以将其描述为决定使用哪些算法和库来运行DNN的每一层，下面将详细解释该问题。它们还将问题简化为已知的NP难图问题PBQP，并使用现成的PBQP求解器来解决它。

在评估结果时，特别强调卷积运算，这是一种计算极其密集的运算，并且几乎在所有图像处理DNN中都会使用，这种网络被称为卷积神经网络（CNN）。

DNN原语及其重要性

DNN由层的有向图组成，并且在这些图层之间的有向边上发生数据流。每个层都是处理数据的，它由标准数学运算符组成，如卷积、激活、池化或完全连接的层。一层的输出会馈送到下一层，这可以对应到数据流。这些层实现为一组原始例程，其中每个原语都是这些数学运算的优化实现。层有许多可能的算法和实现，这与说有许多可供使用的原始例程选择相同，包括开源实现和专有库。

例如，Winograd和FFT是两种可用于实现卷积的算法。值得注意的是，这些基元在不同场景中的表现不同，具体取决于图层的规格。目的是为每一层选择最佳的原始例程，以便最小化整个网络的整体运行时间，这个问题被称为最佳DNN原语选择。

什么是卷积层？

尽管所使用的方法是通用的，并且很容易可以针对任何类型的层实施和测试，但评估焦点仅保留在卷积层上。它们通常主导运行时间，并且在许多重要的CNN中用于图像处理。卷积层的输入通常是张量，一般以2-D图像的三维或四维表示。例如，对于典型的彩色2-D图像的三维表示，前两个维度通常编码像素的水平和垂直位置，第三维度通常存储红色、绿色和蓝色的量。像素，卷积层通过在图像上滑动一系列小“滤波器”或“内核”来处理该张量，以执行数学卷积运算。在下图中示出了轮廓，其中尺寸为H×W×C的图像与尺寸为k×k×C的核进行卷积以获得尺寸为H×W的输出图像（称为“特征图”），并且由于存在M个这样的内核，因此输出表示为大小H×W×M的张量。

多个内核是很重要的，因为它们可以使网络“学习”不同的功能和模式。例如，一个内核可能会尝试检测图像中是否存在猫，另一个内核可能会学会检测狗。得到的张量 - 来自所有内核的输出 - 然后可以被送入最大池层，这将检测这些M模式中哪一个最重要，例如负责猫的那个内核是否发现了比狗内核更好的匹配 - 这使得高精度图像分类。

图1:卷积层示出尺寸为H×W的图像，其中C通道经历与大小为k×k×C的M个核的卷积

卷积层中的原始选择和数据格式协议

存在大量用于卷积的不同基元。直接循环方法，im2、kn2、Winograd和FFT（使用快速傅立叶变换算法），都是可用于实现卷积的算法系列。如前所述，每种算法的性能取决于卷积层的参数和规格。例如，直接循环方法在步长卷积上表现良好，其中内核跳过一些输入像素以给出较小的输出图像，并且im2在这种情况下也表现良好。但是，直接循环方法通常较慢，而im2算法非常耗费内存， Winograd非常快，但无法预测。

FFT也是一种性能优势平衡的选择，但对小内核不利;尽管具有较低的渐近复杂度，但它具有较大的开销，因此导致较低的复杂度仅在输入较大时才有益。其他参数，如通道数（即上图中C的值）也会影响基元的最佳选择。

由于在典型的CNN中，每个层的参数变化很大，因此对于每个层具有不同的基元选择是有意义的，以便最小化计算在整个网络上的总运行时间。乍一看，这似乎是一个非常容易解决的问题：在实际运行整个网络之前，我们可以简单地尝试每个层上的每个原语并记下列表中的运行时间（让我们将此列表称为“成本向量”） 。对于此试运行，我们可以使用随机输入值，因为运行时间实际上并不取决于值本身，而是它们的总数。事实上，这实际上是作者的出发点。

在对运行时间进行采样后，我们可以通过查看哪一个在试验中表现最佳来为每一层选择最佳算法，这样，问题解决了！该过程如下所示：

图2：显示3层CNN的图。每层旁边显示的“成本向量”表示每层的基元A、B和C的成本。例如，在层conv1上，基元A的运行成本为8，基元B的成本为6，C的成本为10，其他层也是如此。

这里卷积层表示为节点：conv1、conv2和conv3。三个基元是A、B和C，显示了每个层的原始成本向量（由试运行确定），我们可以看到优化整个网络只是选择最小成本原语。在这种情况下，它对应于conv1的选择算法B，conv2的算法C和conv3的算法B。网络的总成本只是每层成本的总和。

然而，这种天真的解决方案缺少一个关键方面。它没有考虑每个基元对不同数据格式的数据进行操作的事实。例如，一些基元接收并以16位浮点格式生成输出值，而其他基元使用32位浮点。一些基元还需要输入图像的尺寸的特定排列，CHW（通道×高度×宽度）和HWC（高度×宽度×通道）是两种不同的数据格式，并且特定基元可以仅对一种格式进行操作。

另一个例子是，如果对信号进行操作，则数据可以用频域表示或时域表示（这些只是表示相同信号的不同方式），并且不同的基元可能仅支持这些格式中的一种。必须考虑这一点，如上图所示，可能是conv1使用与conv2不同的数据格式，数据需要从conv1的格式转换为conv2格式才能在它们之间传递，这样就会有转换成本产生。因此，我们还需要在优化中考虑数据格式转换的成本。

PBQP

由此产生的优化问题现在不仅考虑了图元的运行时间，还考虑了连续图层中使用的图元之间的数据格式转换时间。作者表明，这相当于已知的NP难问题，即分区布尔二次问题（PBQP）。在PBQP中，我们给出了一个图表，并且必须从表示成本的给定标签集合中为每个节点分配标签。

因此，每个节点都具有所有标签的“成本向量”，这与前一图中的问题类似。为节点选择标签的成本会将相应的成本添加到我们目标的总成本中，这是我们想要最小化的。但除了节点的成本之外，每个边缘还有成本。边缘的成本取决于源节点的标签选择，以及目标节点的标签选择。由于它取决于连接节点的标签，因此可以将其视为矩阵（因为它由两个标签索引）。

如下图所示：

图3：显示3层CNN的图。还示出了与图1类似的基元a、b和c的成本向量。还示出了边缘成本矩阵，其中行表示源节点的标签，列表示目标节点的标签。例如，为conv1选择基元c成本为10，为conv2选择基元b成本为19。但是边缘成本矩阵给出的附加边缘成本也为5。

我们可以在上图中看到，conv1的最低成本原语是原始b，成本为6，而conv2的最低成本原语是原始c，成本为14。但是现在我们还必须考虑边缘成本和使用此赋值通过适当地索引到边缘成本矩阵给出额外的边缘成本5。因此实际上为conv1选择原始c更好，因为它给出的边缘成本为零。那么总成本就是所有节点和边缘成本的总和，这是我们想要最小化的目标。

实施和测试

现在我们有正确的问题需要解决，我们可以实现并测试它。为此，我们首先需要运行基元的成本以及数据格式之间转换的成本。通过为每个层运行实际大小的随机输入来预先计算运行基元的成本，并且这应该是相当准确的，因为层的运行时间取决于输入大小而不是实际值。

数据格式转换成本也通过运行转换和时间采样来预先计算。在不可能直接转换的情况下，使用最低成本转换路径的成本。这意味着如果数据格式A，例如不能转换为数据格式B。但是A可以转换为数据格式C，而数据格式C又可以转换为B，然后使用转换成本的总和（这是建模的）作为All-Pairs-Shortest-Paths问题并轻松解决）。

一旦成本向量和矩阵准备就绪，就可以使用现成的PBQP求解器来获得DNN的最佳基元选择，以便进行基准测试。性能在三个流行的神经网络上进行了测试：AlexNet，VGG Model E和GoogleNet。将运行时与整个使用单个基元以及Caffe（一种流行的深度学习框架）的性能进行比较。还包括英特尔MKL-DNN库的基准测试，这是针对DNN基元的优化JIT编译器。实验在不同的硬件架构上进行，Intel Haswell的速度结果如下所示（越高越好）：

图4.用于运行各种流行DNN的不同算法的Intel Haswell加速

我们可以看到，在Intel Haswell上，PBQP原语赋值在多线程的情况下优于所有其他方法，甚至是英特尔自己的MKL-DNN神经网络编译器。在单线程运行的情况下，MKL-DNN在AlexNet和GoogleNet网络中的性能稍好一些，但PBQP方法非常接近并且仍然优于其他方法。对于VGG，PBQP方法也超过MKL-DNN。

ARM Cortex的性能结果如下所示（越高越好）：

图5.用于运行各种流行DNN的不同算法的ARM Cortex上的加速

在这里，我们还可以看到PBQP分配优于ARM Cortex-A57架构上网络的所有其他实现。

讨论与结论

从实验结果可以清楚地看出，PBQP公式在选择实施DNN的最佳基元方面非常有效。存在其他DNN优化框架，并且可以使用一些类似技术来实现更快的DNN计算。也许最快的例子是NVIDIA的cuDNN，它使用最有可能是给定层最快的实现/原语。这与PBQP解析器形成对比，因为它没有考虑边缘成本，即数据格式转换的时间。Tensorflow XLA是另一个框架，它基本上是DNN的提前编译器。它计算跨层转换和数据格式转换的成本，并尝试合并层以避免这些成本，这与PBQP方法有些并行。

结果表明，PBQP方法改善了DNN运行时间，因此可能非常适合DNN优化框架的改进。作者在2018年代码生成和优化国际研讨会（CGO）上发表了这篇论文，本文采用的方法使我们能够更快地训练DNN，并对越来越多的廉价移动和嵌入式系统进行深度学习和推理。

运营：李佳惠