DNN 加速器设计——NPU数据流优化

上一篇文章讨论了DNN处理如何进行计算转换，以利用优化的库或减少运算数量，特别是乘法运算，从而在CPU和GPU等现成的通用处理器上实现更高的性能（即更高的吞吐量和/或更低的延迟）。在本章中，我们将直接通过设计专用硬件来优化DNN的处理。

John Hennessy和Dave Patterson在2018年图灵奖的演讲中描述了设计专用硬件的主要动机[11]。在那个讲座中，他们认为随着摩尔定律[140]的终结，有必要在计算系统中采用特定领域的硬件/软件协同设计(例如，特定领域的语言，如TensorFlow)，以继续提高重要计算领域的性能和能源效率。

Leiserson等人[141]概述了设计此类专门系统的架构配方。这篇文章描述了如何通过以下方式来提高性能或能源效率：(1)确定工作负载中可以显著提高并行性和数据局部性的机会；(2)设计一种利用并行性和数据局部性的硬件架构；(3)简化硬件以最大限度地提高效率，可以通过硬件-软件以及硬件-算法协同设计。在这里，我们区分这两种形式的协同设计：硬件-软件协同设计是指开发新的软件和语言，以提高易用性；此外，编译器可以更好地将此类工作负载映射到特定于领域的硬件，从而提高性能和能源效率。硬件-算法协同设计指的是修改算法及其工作负载，将其与硬件结合起来，以提高性能和能源效率，这是每种方法都无法单独实现的。我们主要关注硬件算法协同设计。

深度神经网络加速领域完全符合刚才描述的范式。首先，计算领域很重要，并允许相当大的并行性和数据局部性(即重用机会)。因此，目标是设计专门的深度神经网络硬件，以进一步提高关键指标，如性能和能源效率，而不是在广泛的深度神经网络计算领域的通用处理器。因此，第二，我们将探索(在本章中)可以利用DNN计算中的并行性和数据局部性来实现这些目标的硬件组织。第三，在第7章、第8章和第9章中，我们将探讨如何共同设计硬件和深度神经网络算法，以进一步提高效率。

在考虑深度神经网络加速的硬件组织时，专门的深度神经网络硬件的设计空间相当大。这是因为在DNN层中，MAC操作的执行顺序没有限制。因此，在某些给定的资源约束(例如，计算数据路径的数量和存储容量的数量)下，硬件设计人员可以非常灵活地选择操作的执行顺序并针对目标指标优化硬件。

为了在大的设计空间中接近硬件设计，我们将讨论几个关键的设计决策以及它们如何影响性能和能源效率，然后展示如何使用loop nest来正式描述这些设计决策，这通常用于描述DNN的处理。然后，我们将讨论在使用循环巢的DNN加速的实际架构中常用的几种设计模式。在本章的最后几节中，将讨论通过灵活的片上网络(NoC)实现高效灵活的数据存储和数据移动的设计模式。

5.1 评估指标和设计目标

正如第三章所讨论的，能耗和性能是设计专用硬件的两个主要驱动指标。在现代计算系统中，能量消耗通常由数据移动主导，特别是内存访问[121]。这是因为从内存访问数据，特别是像DRAM这样的片外存储，可能比实际计算操作数(例如MAC)消耗更多的能量。即使对于片上存储器，从较大的存储器(例如，缓存)访问数据也比从较小的存储器(例如，寄存器)访问数据消耗更多的能量。因此，为了减少能耗，一个目标是设计硬件，通过以下方式减少数据移动：

减少从具有高能量成本的位置(如DRAM或大型片上缓冲区)搬运value的次数；
减少移动每个value的成本。例如将在第7章中讨论的减少数据位宽的方法；

另一方面，吞吐量和延迟方面的性能在很大程度上取决于处理元素(PE)的数量，更具体地说，是可以并行操作的乘数。因此，设计硬件的另一个目标是:

将工作分配给尽可能多的PE，以便它们可以并行操作；
确保有足够的内存带宽来交付需要处理的数据，并最大限度地减少并行PE之间的工作负载不平衡，最大限度地减少每个PE的空闲周期数

只设计并执行必要操作的硬件还可以改进能耗和性能；例如，当数据稀疏时，硬件应该只对非零数据执行MAC，并且也可以利用一些表示稀疏的方法来节省存储空间和数据移动。利用稀疏性将在第8章讨论。能源消耗和性能可能会通过新技术得到改善，这是在第10章中描述。

5.2 DNN要利用的关键属性

DNN有几个属性可以被硬件利用来优化5.1节中讨论的设计目标，从而提高硬件性能和能源效率。如前所述，DNN的关键计算涉及许多MAC，这些MAC在一层内的执行顺序没有限制。因此，尽管DNN每层需要大量的MAC，但通过利用高计算并行性，硬件仍然可以实现更高的吞吐量和更低的延迟。然而，减少将数据移动到并行PE的能耗的挑战仍然存在。

值得庆幸的是，数据移动成本可以通过DNN的另一个重要属性来解决，即相同的数据块通常用于多个MAC操作。这个属性导致了三种形式的数据重用，如图5.1所示。

图5.1: Data reuse opportunities in a CONV or FC layers of DNNs.

Input Fmap Reuse: 对相同的输入特征图应用不同的filter(维度M)，以生成多个输出特征图；因此，每个输入激活被重用M次。
Filter Reuse: 当处理一批（大小为N）输入特征图时，将相同的filter应用于该批中的所有输入；因此，每个filter weight被重复使用N次。
Conv Reuse: 对于卷积层，filter的大小(RxS)小于输入特征映射的大小(HxW)，并且滤波器在输入特征映射中的不同位置(通常相互重叠)滑动以生成输出特征映射。因此，每个权重和输入激活分别被重用PxQ和RxS次，以产生不同的输出激活。

通过从大型但昂贵（就能源成本而言）的存储器中一次性读取数据，数据重用可以转化为降低数据移动的能耗，或者:

将数据存储在相对较小但廉价的存储器中，并（暂时）在该廉价存储器中多次重用该数据；
向多个PE发送相同的数据，并（在空间上）使用这些不同PE处的数据。

这两种方法都节省了对昂贵内存的访问，从而降低了总体能源成本。虽然DNN层的最大数据重用量是由其形状和大小(例如，channel数量，filter大小等)定义的，但相应的能源成本节约是由专用硬件通过这些方法实际利用的数据重用量决定的。将在第5.4节和第5.5节讨论如何在硬件中应用这些方法。

除了利用输入激活和filter weight的数据重用之外，专用硬件还可以通过适当地编排partial sum的移动(partial sum是乘法的中间结果)来减少数据移动的能量成本。如果partial sum可以暂时累积在一个小的缓冲区中(例如，寄存器)，则能耗比从一个较大的缓冲区读取和更新值要少。或者，通过加法树在同一循环中累积partial sum (即作为空间和)可以减少所需的存储容量[135,142]。在最好的情况下，每个输出激活的所有CRS partial sum可以在一个周期内累积，因此partial sum不需要存储在内存中。

与单个two-input加法器实现的相同功能相比，采用spatial sum还可以减少能量和延迟[143]；具体来说，不是在每次加法之后执行进位传播，而是为加法器树使用冗余二进制表示，允许将进位传播延迟到树底部的单个加法器。spatial sum相对于temporal sum的收益大小取决于缩减因子[144]。

尽管每种数据类型的数据移动成本可以单独最小化，但不可能同时最小化所有三种数据类型(即输入激活、权重和partial sum)。这是因为不同的MAC一次最多只能重用一种数据类型的数据。例如，重用相同权重的MAC需要不同的输入激活，并且生成的partial sum不能进一步累积在一起。因此，上述方法一次只能用于减少一种数据类型的能量成本，而会增加其他两种数据类型的数据移动成本。因此，为了最小化总体能耗，重要的是通过优化过程平衡所有三种数据类型的数据移动成本，而不是仅仅最小化其中任何一种数据类型。

除了硬件约束外，优化过程还取决于深度神经网络层的特定形状和尺寸。然而，虽然硬件约束保持固定，但DNN层的形状和大小可以在不同的DNN之间以及DNN内部的不同层之间发生巨大变化。因此，数据移动的优化必须分别对每个DNN层进行，并且硬件需要能够根据优化结果支持不同的数据移动配置。这种灵活性要求提出了几个对专用DNN硬件设计至关重要的考虑因素，将在下一节中讨论。

5.3 DNN硬件加速器设计注意事项

设计专用深度神经网络硬件的挑战包括设计一个灵活的架构，然后找到配置架构的最佳方法，以获得不同深度神经网络层的最佳硬件性能和能源效率。这两个方面是紧密相关的，因为找到最佳配置的机会取决于硬件的灵活性，而更高的灵活性通常也需要额外的硬件，也就意味着效率的损失。因此，通常需要一个迭代过程来提炼出最佳设计。这与第4章中采用的方法形成对比，在第4章中，硬件架构已经固定，重点是调整计算形式以适应硬件的计算范式。

给定特定的DNN模型，在保证性能需求的基础上，找到可以最小化总体能耗的硬件配置。这个过程包括找到一个最优映射，其中映射定义：(1) MAC操作的执行顺序，包括时间上的(即同一PE上的串行顺序)和空间上的(即跨多个并行PE)；(2) 如何在内存层次结构的不同层次上tiling和移动数据，以按照该执行顺序执行计算。对于给定的DNN层，通常存在大量可能的映射。因此，能够找到所需指标的最佳映射是非常重要的。在第5.4节将展示不同映射的示例，并讨论它们对硬件性能的影响。第6章扩展了这个讨论，详细介绍了映射优化过程。

考虑到深度神经网络层的MAC操作可能的时空顺序的绝对数量，硬件架构通常不太可能支持所有这些顺序的执行。因此，实际的硬件将支持更严格的排序集，从而减少合法映射的数量。因此，DNN硬件的一个非常关键的设计考虑是选择要支持的映射子集。换句话说，硬件架构必须建立规则来缩小优化中考虑的映射的范围。确定受支持映射子集的一组重要规则称为数据流。数据流是定义DNN硬件架构的最重要的属性之一，因为所支持映射的子集直接影响优化的质量。在第5.6节中，我们将使用基于循环嵌套的表示法正式定义数据流和映射。

另一个设计考虑因素是，如第2章所述，DNN层的形状和大小可以在不同的DNN之间以及DNN内的不同层之间发生巨大变化。此外，在新兴DNN中发现的层数继续增长。因此，考虑到这个快速增长和变化的领域，设计足够灵活和可扩展的深度神经网络硬件以满足这些不同的需求变得越来越重要。具体来说，硬件应避免对层的形状和大小进行假设；例如，由于深度神经网络的大小不断增长，不能假设整个模型总是可以存储在芯片上。为了有效地支持各种深度神经网络，硬件所需的灵活性已经成为深度神经网络加速器设计的主要挑战之一。总之，专门的深度神经网络硬件的设计和使用涉及多个步骤。

设计时：体系结构是用一组属性指定的。这些属性包括：(1) 支持的数据流；(2) PE的数量以及每个PE乘法器、加法器的数量；(3) 存储器层次结构，包括存储层的数目和每一层的存储容量；(4) NoC在存储器层次结构内以及存储器和PE之间允许的数据传输模式。注意，这些属性对体系结构的合法映射设置了一定的限制。例如，内存层次结构的每个级别上的存储容量会影响硬件中可以利用的数据重用量，从而限制了支持的映射集。将在5.5节中讨论这些限制；
映射时：给定DNN模型，从加速器支持的所有映射中选择一个优化所需操作指标的映射。在第6章将讨论为DNN加速器寻找最优映射的过程；
配置时：将从所选映射导出的配置加载到加速器中；
运行时：加载所需的DNN输入数据，并根据加载的配置进行处理。然而，根据加速器的功能(例如，每个配置可以处理多少层)，它可能需要在配置步骤和运行步骤之间多次迭代。

在下一节将探讨如何利用数据重用。

5.4 利用数据重用的体系结构技术

正如第5.2节，可以利用时间重用和空间重用两种数据重用方法来减少数据移动的能量成本。在本节中将正式定义它们，并描述如何在硬件中应用这些技术。

5.4.1 时间重用

当相同的数据值被同一个计算单元(例如，PE)多次使用时，就会发生临时重用。它可以通过向硬件的内存层次结构添加中间内存层来利用，其中中间内存层具有比作为数据的原始来源的级别更小的存储容量，如图5.2d所示。由于访问较小的存储器比访问较大的存储器消耗更少的能量，因此数据值只从源级(即较大的存储器)传输一次到中间级(即较小的存储器)，并在中间级多次使用，从而降低了总体能源成本。

由于中间内存层的存储容量较小，因此无法同时容纳来自源层的所有数据。因此，中间级别的数据可能会被源级别的新数据所取代，从而失去进一步利用临时重用的机会。中间层的数据是否被替换取决于重用距离。为了利用临时重用，重用距离被定义为使用者在访问同一数据值之间所需的数据访问次数，这是操作顺序的函数。图5.2显示了一个示例来说明这种现象。对于图5.2a所示的示例1-d卷积工作负载，图5.2b和5.2c显示了两种不同的操作顺序：前者的权重的时间重用距离为4，而后者的权重的时间重用距离为1。在图5.2d所示的内存层次结构中，我们只显示了分配给权重的内存空间，并且它在分配给权重的中间内存层(L1)中只有1个slot，图5.2b中的排序不断交换L1中的权重，而图5.2c中的排序可以将每个权重从source Mem读入L1 Mem 1次并重复使用4次。因此，如果某个数据类型的重用距离小于或等于中间内存级别的存储容量，则可以对该数据类型的所有值进行临时重用。然而，如果重用距离较大，那么在重用机会被充分利用之前，存储在中间级别的部分或全部数据值将被替换。换句话说，中间内存层的存储容量限制了可以利用临时重用的最大重用距离。

图5.2: 要运行(a)中的示例1-d卷积，(b)和(c)显示了两种可能的操作顺序。(b)的权重重用距离为4，而(c)的重用距离为1。对于(d)所示的内存层次结构，在中间内存中只有1个slot分配给权重，(c)中的排序可以充分利用时间重用，而(b)中的排序则不能，因为它的重用距离大于中间内存的存储容量。

注意，这里显示的数字是每个数据向量中值的索引。

降低一种数据类型的重用距离通常是以增加其他数据类型的重用距离为代价的，这一点需要同时考虑。虽然在较大的重用距离上可以通过增加中间存储层的存储容量来实现暂时的重用，但这样做的副作用是每次内存访问的能量开销也会增加，从而增加了所有重用距离下数据移动的平均能量开销。另一种解决方案是通过改变MAC的处理顺序来减小重用距离，同时可以保持较小的内存空间。5.5节将讨论各种减少重用距离的技术。

可以在存储层次的多个层次上利用时间重用。通过将中间内存级别视为来自source Mem级别的数据的新消耗单元，可以添加额外的内存级别以进一步利用时间重用。然而，增加存储层需要更多的存储面积，导致不同存储层之间的能耗比率降低，降低了利用时态重用的有效性。类似CPU里的多级cache，不过在NPU设计中，通常不会分那么多层次。

5.4.2 空间重用

当同一个数据值被多个计算单元(例如，一组PE)在硬件的不同空间位置使用时，就会发生空间重用。它可以通过从源内存级别读取一次数据并将其多播给所有使用者来利用。利用空间重用的好处是：(1) 减少对源存储层的访问次数，从而降低整体能耗；(2) 减少对源存储层的带宽需求，有助于使PEs保持忙碌，从而提高性能。

如果一组计算单元没有存储能力，那么空间重用只能由与数据组播处理周期相同的计算单元子集来实现；如果另一部分计算单元需要相同的数据值，但不能在同一个周期内处理，则需要由源内存级别再次发送数据。相反，如果组中的每个计算单元都有一定的存储容量，那么在利用多播进行空间重用时，可以容忍在某个特定的时间跨度(由存储容量决定)内多个计算单元处理相同的数据值。也就是说，使用相同数据值的群体中的计算单元是否能够进行空间重用也取决于重用距离。为了利用空间重用，重用距离被定义为访问同一数据值的任意消费者对之间的最大数据访问次数，它又是一个操作顺序的函数。

图5.3给出了一个示例。对于图5.2中相同的1-D卷积工作负载，我们在一个新的架构上运行它，该架构的内存层次如图5.3a所示，它有四个计算单元，C0到C3。每个计算单元也有1个本地存储权重的slot。图5.3b、5.3c和5.3d显示了三种不同的操作顺序(为简单起见，这里只显示了权重)。除了时间轴，排序还有空间轴，表示在每个并行计算单元上的书序。对于图5.3b、5.3c和5.3d中的排序，权重的空间重用距离分别为0、1和3。由于图5.3b和5.3c中顺序的重用距离小于或等于consumer层的存储容量，因此每个权重只需要从源存储器到所有consumer进行一次组播即可。然而，对于图5.3d中的排序，每个权重需要从源内存中多次读取，因为重用距离大于消费者的存储容量。

图5.3: 要在(a)所示的内存层次上运行相同的1-d卷积，如图5.2a所示，有三种可能的操作顺序如图(b)、(c)和(d)所示，它们的空间重用距离分别为0、1和3。图中红框之间的距离表示重用距离。

由于(b)和(c)中的本地存储中有1个slot用于存储权重，因此(b)和(c)中的重用距离小于或等于consumer的存储容量，可以充分利用权重的空间重用，而(d)中的排序需要多次从源存储器级读取每个权重。

除了复用距离外，由于空间复用涉及到将数据路由到硬件中的多个目的地，因此分布数据的NoC在实现空间复用中也起着重要作用。具体来说，NoC必须支持来自操作顺序的数据分布模式。如图5.4所示，如果使用一个数据值所有consumer在同一周期(图5.3b)，但L1 Mem的每个bank只连接到consumer的一个子集，那么空间重用需要首先从L2更高的memory级别，利用多播数据从L1与L2所有bank每个bank作为一个consumer，然后再多播的L1 bank所有的consumer。在更高层次的存储层次上利用空间重用会在硬件中创建更多重复的数据，这是我们不希望看到的。然而，在单个层次上大规模地为所有consumer提供组播服务的代价也是昂贵的。因此，确定在哪里以及如何利用硬件的空间重用是一种设计权衡。5.9节中讨论用于DNN加速器的片上网络设计。

图5.4: 片上网络L1 Mem与consumer之间的物理连通性限制了L1中任意存储单元向所有consumer进行组播。因此，数据需要首先从L2存储器组播到L1存储器中的所有bank，然后每个L1 bank再进一步组播到相关的consumer。在这种情况下，数据在L1中复制了两次

5.5 减少重用距离的技术

正如上一节所讨论的，操作的顺序决定了重用距离，从而影响时间重用或空间重用的有效性。在本节中，我们将讨论操纵操作顺序以减少重用距离的各种方法。

首先，由于不可能像5.2节中描述的那样同时最小化所有数据类型的重用距离，因此操作的顺序必须优先减少某一数据类型的重用距离。图5.2b和5.2c是两个操作排序的例子，它们分别减小了partial sum和weight的重用距离，以实现时间重用。优先级数据类型的每个数据值在操作序列中似乎都是固定不变的(即，同一个值从内存中连续被访问多次)。稍后在5.6节讨论循环嵌套时，会说明不同数据类型的平稳性是由嵌套循环的顺序控制的，它决定了它们在减少重用距离时的优先级。

数据tiling，也称为分块，是一种常用来减少重用距离的技术，如4.2节中介绍的CPU或GPU分块。数据被划分为更小的分块，一次处理过程只关注一个分块。有很多方法可以tile数据进行处理。除了每个分块的大小之外，沿着哪些维度进行分块也是需要设计决策的(DNN中每种数据类型为4-D)。目标是平铺数据，缩小重用的距离。例如在图5.2c的操作排序中，权重是的优先级高(即每个权重在多个周期中保持不变)，partial sum的时间重用距离很大，并且与整个输出激活向量的长度相同，在本例中为4。如图5.5所示，通过一次只处理一半的输出激活，分块可以减少partial sum的重用距离，从而将partial sum的重用距离缩短两倍，达到2。然而，这也增加了权重的平均重用距离，尽管仍然是最优先的数据类型。

图5.5: 图5.2c操作顺序的时间tiling版本

分块技术既可以利用时间重用，也可以利用空间重用。用于时态重用的分块(Tiling for temporal reuse，简称temporal Tiling)旨在缩小特定数据类型的重用距离，使其小于内存层次中某一内存层的存储容量。例如，假设图5.2d中的中间存储层L1的总存储容量为3个数据值，图5.2c中的未分块排序只能利用权重的时间重用，因为partial sum的时间重用距离太大，必须从更高的存储层存储和获取。然而，使用图5.5中的分块排序，一个权重值和两个partial sum值组成的分块可以放入L1中，以利用时间重用。但要注意，在这种情况下，写入L1的每个权重值只能利用时间重用两次，并且需要从较高的内存层读取两次到L1，而不像未分块排序那样需要读取一次。

另一方面，面向空间重用的数据分块(spatial tiling)侧重于：(1) 相同的数据值被尽可能多的consumer复用；(2) 在给定每个consumer的存储容量的情况下，减小复用距离，使一组播可以服务尽可能多的consumer。例如，图5.6a、5.6b、5.6c展示了三种不同空间分块的影响，它们导致了不同空间重用程度的操作顺序。图5.6a中的排序没有权重的空间重用，因为每个权重只被一个consumer使用。图5.6c中的排序具有最高的空间重用度，因为每个权重都被所有consumer使用。空间分块有效地提高了空间重用量，节省了从源内存读取的次数。

图5.6: 内存层次中不同空间重用程度的操作顺序

时间分块和空间分块的目标都是在一定的内存级别上，使数据类型的重用距离与可用存储容量精确匹配，以最大限度地利用该级别上的数据重用。过度减小复用距离并不会带来额外的好处，反而会增加其他数据类型的复用距离。然而，由于不同层次和不同深度神经网络的数据形状和大小不同，而硬件存储容量是固定的，因此将重用距离与存储容量精确匹配并不总是可行的。这将导致映射碎片，在这种情况下，工作负载无法平均分配到硬件上运行，因此将导致硬件利用率不足。

此外，对于空间分块，我们希望在利用空间重用的同时充分利用所有PE以实现最大性能，但通常这是不可能的，因为可能没有足够的空间重用来利用。例如，图5.7展示了一种在PE之间分配数据以利用并行性的常用方法：不同输出通道(M)的数据垂直发送到不同的PE，而不同输入通道(C)的数据水平发送到不同的PE。因此，每个PE都有一个唯一的权重，每个输入激活在一列具有不同输出通道权重的PE中被空间重用。然而，如果M小于某一列的PE数量，C小于某一行的PE数量，那么只有一部分PE被使用(图5.7中那些有颜色的PE)。为了提高这种情况下的利用率，可以同时运行多个数据分块，同时不会得到更多的空间重用，就像5.7.4节讨论的那样。然而，这种技术只有在数据传输有足够的灵活性和NoC提供足够的带宽时才可行。

图5.7: 如果空间重用不足，空间分块可能导致并行性得不到充分利用。如果输出通道(M)或输入通道(C)的数量分别小于一列/行中的PE数量，则这里将只有一部分用于处理的PE (例如，着色的那些)。

数据优先级排序和分块可以在存储层次的每个层次上独立应用。不同的数据类型可以在存储层次的不同层次上进行优先级划分，这有助于平衡访问所有类型数据的能耗开销。例如，对于从内存级别L1到PE的访问，可以对权重进行优先排序，而对于从L2到L1的访问，可以对partial sum进行优先排序。此外，存储层次的每个层次都可以执行时间或空间分块，或同时执行两者。在空间和时间的分块决策之间没有直接的交互；相反，它们可以在存储层次的不同级别上交叉使用。例如，在图5.4中，时间分块和空间分块同时应用于存储层次的L1和L2层。最后一层的使用者可以拥有本地存储来进行临时分块；但是，如果最后一层的使用者没有本地存储，它们将像第4章中提到的基于向量的体系结构那样运行。请注意，与许多向量体系结构不同，consumers可以相互通信数据，这通常用于跨PE进行部分和的空间累加。

在进行操作重排序或数据分块时，除了考虑重用距离外，还应考虑带宽需求。具体来说，即使平均带宽相同，某些操作顺序的峰值带宽需求可能比其他操作更高，这通常发生在计算的上升或下降过程中。例如，当并行PE在同一个周期内产生多个输出激活时，将它们立即存储到内存将需要较高的峰值带宽。此外，如果使用双缓冲(ping pong buffer)等技术来预取数据并隐藏数据访问延迟，则在总存储容量固定的预算下，内存级别的有效存储容量会变小，在计算所需重用距离时应考虑到这一点。

虽然本节介绍的技术有许多不同的应用方式，但就如何在现有设计中应用而言，有一些常见的方法，即数据流的分类。在下一节中，我们将通过正式介绍基于循环嵌套的数据流表示来详细介绍这些数据流。

5.6 数据流和循环网络

使用第2章中的张量索引表示法，CONV层(with unit stride)的计算如下:

这种计算可以作为预期计算的规范，它没有对单个计算施加顺序或并行概念，但这些特征对在硬件上运行时的计算性能和效率很重要。指定排序方式以及并行计算被称为数据流(dataflow)。

数据流定义了一些控制加速器活动的特定规则。这些问题包括操作的顺序，以及如何在内存层次结构和计算数据路径之间在时间和空间上对数据的使用和传输确定优先级。它还规定了哪些映射是合法的，并直接影响DNN加速器的性能和能效。因此，能够准确地描述数据流是非常关键的。本节正式介绍用于此目的的强大工具——循环嵌套。

循环嵌套是一种简洁的方式，可以描述给定DNN加速器设计的各种属性，特别是它的数据流。图5.8a展示了可以表示图5.2c示例1-D卷积的操作顺序的循环嵌套。包含变量s的循环被放置在最外层，用于索引滤波器权重。该循环遍历开放范围[0, S)，其中S是滤波器权重的数量，定义为卷积形状的一部分；卷积形状的另一个组成部分是Q(partial sum的数量)，它在开放范围上遍历[0, Q)；形状的最后一个分量是W(输入激活数)，它通过对变量s和q的简单计算来遍历。关于这种计算的更多讨论，请参见6.3节。

图5.8: 图5.2a中用于1-D卷积工作负载的三个un-tiled loop nest。在这种情况下，W=6, S=4和Q=4。(a)为weight stationary数据流，生成图5.2c中的排序；(b) 为output stationary数据流，生成图5.2b中的排序。(c)是input stationary的数据流。

在图5.8a中，权重是在最外层的循环中遍历的，对活动的优先级排序的目的是减少filter权重的重用距离。我们将以这种方式构建的数据流称为weight stationary(WS)数据流。我们用一个一维的例子来说明这个想法时，但是也可以推广到更高维度的数据：只要经过不同weight的循环被放置在所有其他循环之上，它就是一个WS数据流。

使用图5.9中的时空图，我们可以看到每个cycle(即loop nest的执行)中对每个数据数组的引用活动。在该图中，我们可以清楚地看到绿色点s的水平序列，它表示在处理移动到新权重之前多次重用相同的filter权重。在很长一段时间间隔后重复访问partial sum，并以大滑动窗口模式访问输入激活。在这两种情况下，重用间隔都是Q。

通过对循环重新排序可以创建不同的数据流，因为卷积没有施加排序约束。因此，我们还可以创建一个output-stationary (OS)数据流，如图5.8b所示。在这种情况下，遍历不同partial sum的循环被放置在最外层循环。

图5.9: 图5.8a中的一维权重平稳卷积数据流的部分和(红色)、输入激活(蓝色)和filter权重(绿色)的时空图，其工作负载形状为S=4、Q=9和W=12。在每个图中，x轴上的每一步都是一个周期(时间)，y轴表示到相应数据数组(空间)的偏移量。因此，点(x, y) = (20, 1) 表示在第20个周期中对元素1的访问。

图5.10a显示了该数据流的时空图。输出的引用模式显示，每个partial sum被连续引用多次，并且在处理移动到下一个partial sum之前完成partial sum。filter权重的参考模式显示，所有权重在运行过程中都以重用距离S重复使用。图5.10b中输入激活的参考模式放大说明了通过输入激活的大小为S的滑动窗口引用。

图5.10: 图5.8b中具有工作负载形状S=4、Q=9和W=12的1-D输出静态卷积数据流的部分和（红色）、输入激活（蓝色）和filter权重（绿色）的时空图。

也可以创建input stationary(IS)数据流；但是必须使用w和s作为循环变量，并计算索引变量q，如图5.8c所示。这些数据流的特征和相关的体系结构设计将在5.7节中讨论。

到目前为止，我们介绍的loop nest不是tile的(即，这些loop nest中的循环遍历数据的整个维度)。tile特定数据类型的数据涉及选择相应数据类型的特定维度并将其分解为多个循环。图5.11显示了图5.5中tile排序的循环嵌套示例。原先经过维度Q的循环现在被分成两个循环，新的循环边界是Q1和Q0。内部边界Q0定义了tile的大小，而外部边界Q1定义了tile的数量。可以重复相同的过程以将其分解为更多的循环，从而创建可以放入内存层次结构中不同存储级别的多级块。通过分解不同维度的循环，tile也可以同时应用于多个数据维度。

图5.11: 图5.8a中weight stationary数据流的tile loop nest，通过设置Q0=2和Q1=2，可以生成如图5.5所示的排序。

除了传统的for循环之外，并行处理还可以通过引入并行for循环来描述loop nest。然后，在并行for循环中迭代的不同操作将在并行PE上运行。例如，我们可以通过在图5.8a的循环嵌套的过滤器权重平铺版本中使变量s0的循环成为并行的，来生成并行权重静态数据流。新的循环嵌套如图5.12所示。

图5.12: 图5.8a中weight stationary数据流的loop nest，并行处理filter权重(数据维度S0)。

平行weight stationary数据流的时空图如图5.13所示。这里我们看到两个权重被重复使用——每个PE一个权重。此外，两个PE访问相同的partial sum，从而为空间和提供了机会(参见第5.2节)。关于输入激活，两个PE在连续的周期中使用相同的输入激活，如果PE缓冲区可以容纳多个输入激活，则提供PE间通信或组播的机会(即，数据将到达标记为“·”的PE，并等待一个周期直到它被使用)。

图5.13: 图5.12中具有两个平行PE的一维权重平稳卷积数据流的partial sum (红色)、输入激活(蓝色)和filter权重(绿色)的时空图。一种PE活动用“·”标记，另一种用“x”标记。工作负载形状为S=4, Q=9, W=12, S被tile成S1=2, S0=2。

图5.13还说明了平铺对参考模式的影响。因为S维度被tile为S1=2和S0=2，所以权重被分成两个权重的tile。在这种情况下，第一个tile用于前9 (Q)个循环，第二个tile用于后9 (Q)个循环。两个tile也会产生相同的partial sum，因此partial sum与tile相关的重用距离为9个周期(Q)。最后，大部分输入激活都被两个tile使用，因此它们的重用距离也很长，为Q-1个周期。

表5.1: 按数据流对一些工作进行分类

数据流仅定义循环嵌套的以下方面：(1) 循环的特定顺序，以确定数据类型的优先级；(2) 用于描述所述tile的每个数据维度的循环的数目；(3)每个循环是时间(for)还是空间(parallel-for)。每个数据维度可以具有的最大循环数由特定数据类型可以利用的层次结构中的存储级别数来限制。

循环嵌套中的特定循环边界，例如图5.11中的S0和S1，不是由数据流定义的。然而，每个环路边界的最大值可能受到多种因素的限制，包括：时间环路的存储容量、通过空间环路的多播网络可到达的consumer数量（即并行）或数据维度的大小。用于特定工作负载的循环边界的特定值的确定由找到最佳映射的优化过程来确定，这将在第6章中更深入地讨论。

5.7 数据流分类

在第5.4节和第5.5节中，我们介绍了几种利用数据重用的技术。虽然有很多方法可以应用这些技术，但有几种常用的设计模式可以归类为数据流分类法：weight stationary（WS）、output stationary（OS）、input stationary（IS）和row stationary（RS）。这些数据流可以在最近的许多DNN加速器设计工作中看到，如表5.1所示。在本节中，我们将使用通用架构来描述这些数据流在最近的工作中是如何使用的。如图5.14所示，该体系结构由PE阵列组成，每个PE都有一些称为register file（RF）的本地存储，PE阵列共享一个称为global buffer的公共存储级别。

图5.14: 一种通用的DNN加速器体系结构

5.7.1 Weight stationary (WS)

Weight stationary数据流旨在通过最大限度地重用每个PE的register file（RF）中的weight，最大限度地降低读取weight的能耗（图5.15a）。weight重用距离最小；因此，每个weight被从DRAM读取到每个PE的RF中，并且保持静止以用于进一步的访问。当weight存在于RF中时，处理运行尽可能多的使用相同weight的MAC；它使weight的卷积和filter重用最大化。输入和partial sum必须通过空间数组和全局缓冲区。输入特征图激活被广播到所有PE，然后partial sum在PE阵列上被空间累积。

图5.15: 常见数据流分类。Act表示着输入激活。颜色梯度用于标记相同数据类型的不同值

实现Weight stationary数据流的工作的一个例子是nn-X(也称为neuFlow)[146]，它使用8个二维卷积引擎，每个引擎都能够处理大小达10 10的二维filter。每个引擎有100个MAC单元(即PE)，每个PE都有一个固定的权重以用于处理。图5.16展示了一个可以处理3 3 filter的二维卷积引擎，这是一个简化的例子。输入的特征图激活被广播到所有MAC单元，并在MAC单元之间累积partial sum。为了正确地累积partial sum，需要额外的延迟存储单元，这些延迟存储单元被计算到本地存储所需的大小中。

图5.16: nn-X(neuFlow)中的WS数据流[146]

实现Weight stationary数据流的另一个示例是Nvidia的深度学习加速器（NVDLA）[135]，如图5.17所示。虽然权重在每个PE中保持固定，但通过PE数组编排输入激活和partial sum的方式与nn-X示例不同，并且与图5.7中所示的示例相同。注意沿PE列垂直进行空间总和（如第5.2节所述）的机会。 NVDLA简化版本的循环嵌套表示如图5.18所示，它说明了输入和输出通道的并行性以及权重的平稳性。

图5.17: NVDLA实现的WS数据流的简化版本，每个周期处理三个输入通道(c)和八个输出通道(m)中每个通道的权重。该图显示了计算的第一个时间步。随后的时间步将增加输出激活的索引值（p和q），然后增加当前权重（r和s）。

图5.18: NVDLA中实现的WS数据流简化变体的循环嵌套。为了处理大量输入通道(C)或输出通道 (M)，需要添加额外的时间for循环。还可以添加额外的并行性，例如权重索引（r和s）。

谷歌的TPU是另一种具有Weight stationary数据流的设计[145]。TPU和NVDLA之间的主要区别在于，TPU利用脉动阵列来共享输入激活并在PE上累积partial sum。其他Weight stationary的例子可以在[147-151]中找到。

5.7.2 Output stationary (OS)

Output stationary的数据流旨在最大限度地减少读取和写入partial sum的能耗(图5.15b)。通过最小化partial sum的重用距离，使相同输出激活值的partial sum的累加保持在RF的局部。为了保持RF中partial sum的累积是稳定的，一种常见的实现方法是在PE阵列中流式输入激活值，并从全局缓存广播权重到阵列中的所有PE。

图5.19显示了一个实现ShiDianNao [156]提出的Output stationary数据流的示例，其中每个PE通过从相邻PE获取相应的输入激活来处理每个输出激活值。PE阵列实现专用NoC以水平和垂直地传递数据。每个PE还具有数据延迟寄存器，以将数据保持在所需数量的周期内。在系统级，全局缓冲器将输入激活流式传输并将权重广播到PE阵列中。partial sum在每个PE内累积，然后被流传输回全局缓冲区。另一个例子可以从Moons等人的工作中看到[155]。如图5.20所示，每个输入激活在同一列中的所有PE之间重用，而每个权重在同一行中的所有PE之间重用。OS的其他示例见[157, 158]。

图5.19: ShiDianNao中的OS数据流。

图5.20: Moons等人实现的OS数据流[155]

如图5.21所示，Output stationary有多种可能的变体，因为同时处理的输出激活可能来自不同的维度。例如，变体OSA以CONV层处理为目标，因此集中一次处理来自相同通道的输出激活，以便最大化卷积数据重用机会。变体OSC以FC层处理为目标，并且集中于从所有不同通道生成输出激活，因为每个通道仅具有一个输出激活。变体OSB是介于OSA和OSC之间的东西。变体OSA、OSB和OSC的实例分别是[156]、[155]和[158]。

图5.21: OS数据流变种[142]

5.7.3 Input stationary (IS)

与前两个数据流类似，Input stationary数据流的设计目标是最小化读取输入激活的能耗(图5.15c)。在最小化重用距离的情况下，从DRAM读取每个输入激活并将其放入每个PE的RF中，并且保持静止以供进一步访问。然后，它在PE中运行尽可能多的MAC以重用相同的输入激活。它最大化了输入激活的卷积和输入特征图重用。虽然每个输入激活在RF中保持不变，但在每个周期，唯一的filter权重被单投到PEs中，而partial sum在PEs中进行空间累积，以产生最终的输出激活。

实现输入平稳数据流的一个例子是SCNN[159]，其中每个PE(如图5.22所示)可以并行处理4个平稳输入激活，每个输入激活由宽度为4的SIMD通道处理。因此，每个PE具有16个MAC的并行性。SCNN利用了笛卡尔积:HxW特征映射平面上的任何输入激活(即单个输入通道)都可以在RxSxM filter weight上重用，反之亦然。因此，PE首先从大小为HxW的输入特征图中获取4个输入激活，在每个循环中遍历4个RxSxM权重，直到所有权重都循环遍历，然后切换到下4个输入激活。每个循环PE接受4个输入激活值和4个权重，处理16个MAC。每个输出激活的部分和在每个周期中被空间累积4次，并被放入一个partial sum RF中，在各个周期中进一步累积。SCNN还支持稀疏数据的处理，这将在第8章讨论。

图5.22: SCNN中的IS数据流[159]

5.7.4 Row stationary (RS)

在[142]中提出了一种行固定数据流，其旨在最大化RF级别的所有类型的数据（权重，输入激活和partial sum）的重用和累积，以实现整体能效。这与WS、OS或IS的数据流不同，这些数据流仅分别针对减少访问权重、partial sum或输入激活的能量进行优化。

RS数据流将一维行卷积的处理分配给每个PE进行处理，如图5.23所示。它使filter权重行在PE的RF内保持静止，然后将输入激活流传输到PE中。PE一次为每个滑动窗口执行MAC，这仅使用一个存储器空间来累积partial sum。由于在不同的滑动窗口之间存在输入激活的重叠，因此输入激活可以被保持在RF中并且被重新使用。通过遍历该行中的所有滑动窗口，它完成了1-D卷积，并最大限度地提高了该行中数据的重用和局部累积。

图5.23: 用于RS数据流的PE内的1-D卷积重用[142]

每个PE处理一个一维卷积，多个PE可以聚合完成二维卷积，如图5.24所示。例如，为了利用具有三行的filter生成第一行输出激活，需要三个1-D卷积。因此，它可以在一列中使用三个PE，每个PE运行三个1-D卷积中的一个。跨三个PE进一步垂直地累加partial sum以产生第一输出行。为了生成第二行输出，它使用另一列PE，其中三行输入激活向下移位一行，并且使用相同的filter行来执行三个1D卷积。添加附加的PE列，直到输出的所有行都完成（即，PE列的数量等于输出行的数量）。

图5.24: RS数据流的空间阵列内的2-D卷积重用[142]。

PE的该2-D阵列实现了其他形式的重用以减少对更昂贵的全局缓冲器的访问。例如，每个滤波器行跨多个PE水平地重用。每行输入激活在多个PE上对角地重复使用。并且每行部分和进一步垂直地跨PE累加。因此，在2-D PE阵列内最大化2-D卷积数据重用和累积。

这个2-D的PEs数组实现了其他形式的重用，以减少对全局缓存的访问。例如，每个filter行在多个PE上水平重用。每一行的输入激活在多个PE上对角重用。每一行的partial sum在PE上进一步累加。因此，在二维PE阵列内部最大化地实现了二维卷积数据的复用和积累。

图5.25: 多行不同的输入特征图、filter和通道被映射到阵列内的相同PE，以便在RS数据流中进行额外的重用[142]

为了解决CONV层的高维卷积（即多个特征映射、filter和通道），可以将多行映射到同一个PE上，如图5.25a所示。2-D卷积被映射到一组PE，并且通过交织或级联附加数据来处理附加维度。对于PE内的filter重用，不同行的特征图被连接并通过相同的PE作为1-D卷积（图5.25b）。为了在PE内重复使用输入特征图，不同的filter行被交织并通过相同的PE作为1-D卷积（图5.25c）。最后，为了增加PE内的局部partial sum累积，来自不同通道的filter行和特征图行被交织，并且作为1-D卷积运行通过相同的PE。来自不同通道的partial sum自然地在PE内部累积（图5.25d）。

可同时处理的filter、通道和特征映射的数量是可编程的，并且存在一个最优映射以获得最佳的能效，这取决于DNN的层形状以及所提供的硬件资源，例如PE的数量和存储层次空间的大小。由于所有变量在运行时之前都是已知的，因此可以构建一个编译器(即第6章描述的mapper)来离线执行此优化，为不同DNN的RS数据流的不同映射配置硬件，如图5.26所示。这类似于编译器针对特定的CPU或GPU体系结构优化二进制文件的方式(第6.2节)。在6.4节和6.5节中，我们将介绍用于优化的能效和性能分析框架。

图5.26: 映射优化采用硬件和DNN形状约束来确定最佳能量数据流[142]

实现RS数据流的一个示例是Eyeriss [160]。它由一个14x12 PE数组、一个108KB全局缓冲区、ReLU和特征图压缩单元组成，如图5.27所示。芯片与片外DRAM通信，使用64位双向数据总线将数据取入全局缓冲区。然后，全局缓冲区将数据流式传输到PE阵列中以进行处理。

图5.27: Eyeriss DNN accelerator [160]

为了支持行平稳数据流，在硬件设计中需要解决两个问题。首先，固定大小的PE阵列如何适应不同的层形状？其次，虽然数据将以非常特定的模式传递，但它仍然会随着不同的形状配置而变化。固定设计如何以不同的模式传递数据？

如图5 - 28所示，可以使用两种映射策略来解决第一个问题。首先，复制可用于映射不使用整个PE阵列的形状。比如，在AlexNet的第三层到第五层中，每个2-D卷积仅使用13x3 PE阵列，其中3是它们的filter高度（R），而13是输出特征图高度（P）。然后将此结构复制四次，并在每次复制中运行不同的通道和/或filter。第二种策略称为折叠。例如，在AlexNet的第二层中，它需要一个27x5 PE阵列来完成2-D卷积。为了将其装入14x12物理PE阵列，将其折叠成14x5和13x5两部分，并且每个部分垂直映射到物理PE阵列中。由于并非所有PE都被映射使用，因此未使用的PE可以被时钟门控以保存能量消耗。

图5.28: 映射使用复制和折叠来最大化PE阵列的利用率[160]

第二个问题与灵活的数据传输有关，采用自定义组播网络来解决。将数据传递到多个目的地的最简单方法是将数据广播给所有PE，然后让每个PE决定是否处理这些数据。然而，当PE阵列规模较大时，该算法的能量效率不高。相反，使用多播网络只将数据发送到需要它的地方。这是通过在NoC路径上使用多播控制器来实现的，该控制器仅在有目的地需要下行数据时才传递数据。为了确定哪些数据要通过每个控制器，每个数据都带有标记值从全局缓冲区发送到NoC。每个组播控制器也配置一个离线ID。然后，控制器检查标签是否与其本地ID匹配，以确定是否传递了数据。

5.7.5 其他数据流

引入的数据流分类通常作为构建块来创建新的数据流。由于数据流的平稳性仅与存储器层次结构的特定级别相关，因此可以在存储器层次结构的每个级别处使用不同的平稳性。例如，数据流可以在RF存储级别处作为WS，但在全局缓冲存储级别处OS。从循环嵌套的角度来看，它涉及将各种数据类型平铺到多个级别，然后在不同级别重新排序循环以优先考虑不同的数据类型。例如，如果存在K个存储器层级，则图5.8a的循环嵌套中的维度Q和S都可以被进一步划分成K个循环（即，对于开放范围[Q0，QK）和[S0到SK）），然后从循环级别0到级别K-1对循环进行独立的重排。同样的重排序策略可以应用于每个存储层；换句话说，设计是分形的。这也意味着较小的DNN加速器设计可以进一步与新级别的存储器组合在一起以形成较大的加速器。

除了为加速器管理一个数据流之外，最近还有一些工作探索在单个灵活的硬件中支持多个数据流，包括FlexFlow [162]，DNA [163]和Maeri [164]。这些设计的关键是提出灵活的NoC和支持各种存储器访问模式，以便执行具有不同数量的循环级别和循环嵌套中的循环排序的不同数据流。

虽然有无限的可能性创建新的数据流和优化这些数据流的硬件架构，以及数据流和硬件架构的组合，但是如何找到最佳的性能和能源效率仍然是一个开放的研究问题，因为它在很大程度上取决于工作任务的大小，技术和硬件资源的量。因此，能够系统有效地分析不同的设计决策至关重要。在第6章中，我们将介绍几种可以帮助进行此类分析的工具。

5.7.6 跨层处理的数据流

到目前为止，我们一直在研究数据流和相关的架构，这些架构专注于一次处理一层。多个层的处理必须被顺序地调度，这可能涉及硬件的重新配置以适应不同层的不同形状和大小，并且可能在层之间将激活移动到DRAM和从DRAM搬运激活。这些设计是基于这样的假设，即加速器不可能一次适合整个层进行处理；因此考虑同时处理多个层没有多大意义。

然而，随着更多的硬件资源被用于DNN加速，并且DNN模型的计算和存储变得更加高效，可以实现各种应用精度，这种情况下一次处理多个层的数据流和硬件可能是有益的。具体地，来自一个层的输出激活通常直接用作下一层的输入激活。通过将激活保持在本地存储器中以用于跨层处理，它可以保存更高级别（诸如DRAM）的附加存储器访问。然而，这通常是以需要来自不同层的权重的更多存储为代价的，并且一次只能处理每个层中的较小的激活tile。

几个以前的设计已经提出了跨层处理的数据流和架构。例如，Fused-layer[165]专注于保存激活的内存访问，以跨DNN中的多个卷积层进行处理，而Shortcut Mining[166]则针对残差网络中shortcut连接的数据重用。BRein [167]通过在同一硬件上一次运行13层来利用类似的想法，这要归功于DNN使用二进制/三进制权重来保持存储需求较小。Brainwave [168]将一次处理许多层的想法发挥到了极致，通过聚合许多FPGA，每个FPGA一次处理一层，以形成处理结构的流水线链。在这种情况下，每个FPGA可以配置有针对特定层优化的数据流。

多层的流水线计算增加了许多额外的考虑。首先，如果需要处理一系列输入特征图（即，batch size>1），则只能利用层粒度的流水线。否则，只有流水线的一个阶段将是忙碌的，尽管tile级流水线仍然可以提供一些益处。其次，流水线层引入了对激活的级间存储的要求（因为关键动机是避免从层之间的存储中转储和恢复激活）。这必须通过仔细tile和/或选择数据流来管理，这可能在层之间变化。例如，Tangram[169]使用tile来控制级间激活存储，BRein [167]通过将输出静止数据流馈送到输入静止数据流来保存一些层对的中间状态。最后，pipeline的每个阶段中的处理和通信应该平衡以保持高吞吐量，如Simba [123]中所探索的。这些考虑因素增加了设计和映射优化过程的复杂性，并且我们不知道对这些问题全面的评估或解决方案。

虽然数据流是任何DNN加速器的关键设计元素，但其他硬件元素也很重要。在接下来的两节中，我们将回顾用于DNN加速器的缓冲区和片上网络设计的重要考虑因素。

作者：Damon
文章来源：知乎

更多嵌入式AI干货请关注嵌入式AI专栏。欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。