论文（卷积数据流）-Communication Lower Bound in Convolution Accelerators

目录

• 1. Introduction
• 2. Background
  • 2.1 Convolutional Layers
  • 2.2 Related Work
  • 2.3 Preliminary: Red-blue Pebble Game（红蓝卵石游戏）
• 3.Layer-wise lower bound of off-chip communication
  • 3.1 Relation Between Convolutions and MM
  • 3.2 Theoretical Derivation
• 4. Communication-optimal dataflow
  • 4.1 Dataflow with Minimized Off-Chip Communication
  • 4.2 Workload and Storage Mapping with Minimized On-Chip Communication
• 5. Communication-optimal CNN accelerator architecture
• 总结

1. Introduction

在CNN的计算过程中，各级存储层次（DRAM、on-chip global buffer、Regs）之间的数据传输很复杂，从功耗的观点来看，当前的CNN加速器是通信主导的，最小化通信是提高CNN加速器能效的关键。

最大化数据复用可以减少通信，数据复用依赖于卷积数据流，当前研究设计的数据流基于直觉/启发式的分析，不能保证是最优的。

在给定的硬件资源（On-chip memory）下，搜索出一种数据流和架构最小化通信具有实用意义。

2. Background

2.1 Convolutional Layers

图1和图2展示了卷积的基本计算过程，它是一个7层的循环，包含对多种数据复用方式，如输入复用（InR，一个输入被多个卷积核使用）、卷积窗复用（WndR，一个输入被多个重叠的滑动窗口复用）、权重复用（WtR，一个权重被多个输入使用）、输出复用（OutR，在整个计算过程中，输出驻留在片上）。

2.2 Related Work

许多CNN加速器都是通过精心设计的数据流来优化目标的，他们声称数据流和/或加速器的优势，但没有解释为什么设计本质上是最好的。

不是使用单一的数据流，一些研究已经将多个数据流集成到一个加速器中(增加了硬件成本)，并根据层的大小选择最佳的一个。

为了找到具有特定目标的最优数据流，一种可能的方法是全面考虑所有可能的loop orders和tiling sizes(即循环步长)。这就是DSE（设计空间探索）方法。

2.3 Preliminary: Red-blue Pebble Game（红蓝卵石游戏）

这是一个理论模型，用来估计两层存储器之间数据传输的最小容量。

3.Layer-wise lower bound of off-chip communication

3.1 Relation Between Convolutions and MM

将卷积层转化为矩阵乘的方法：
输入图像：被unfold成输入矩阵，每一行表示一个滑动窗的输入，不同行对应不同的滑动窗。
卷积核：被reshape成权重矩阵，每一列表示一个卷积核的权重，不同列对应不同的卷积核。
输出图像：被reshape成输出矩阵，每一列表示一个输出通道的输出，不同列对应不同的输出通道。

reshap意味着重新组织元素，没有增删元素，因此对于卷积核和输出图像的转化是“等价的”。但是对输入图像的unfold操作其实是有增加元素的，因为它丢弃了卷积窗重用特性，为了表征这种“不等价性”，文中引入了R表征卷积窗的重用次数：

注意，convolution-to-MM转换只是用于推导的一个逻辑操作。在这篇文章的数据流或架构中，它不是一个真正的操作。

3.2 Theoretical Derivation

（1）矩阵乘法（MM）的访存下界

不经优化

逐点计算：计算输出矩阵的每个点需要2C的访存，一共有AB个输出点。

经优化

逐块计算：每次不再是只计算一个输出点，而是计算一个xy大小的块，这样的话输入矩阵中的每个点就被复用了y次，同样权重矩阵中的每个点就被复用了x次。这种方式产生的访存量Q=每块的访存量（xC+yC）乘以输出矩阵分的块数（AB/xy）。由均值不等式可导出一个访存下界，即2ABC除以√S，其中S是片上存储的总量。并且当且仅当x=y=√S时，即由两个输入矩阵中读入相等的数据量时，可以达到通信最优。这种方式得到的矩阵的访存量要比最直接的矩阵乘实现减少√S的量。对应于实际的计算流程，要把几乎所有的片上存储全部分配给输出部分，用来存储输出中间结果的时候可以达到最小的访存量。

（2）卷积层的访存下界

如果从直观上对得到的访存量公式做解释，分子上是一个卷积层的Batch大小、输出图像长宽、通道个数、卷积核大小连乘积，这和矩阵乘法2ABC类似，分母就是√RS，S是片上存储的大小，R是卷积窗重用每个元素最多被重用的次数，与矩阵乘法的通信下界公式相比，这里其实只多了一个√R，所以卷积当中访存下界其实是比访存最优的矩阵乘减少一个√R的倍数，这是卷积滑动窗重用R次的概念

对应到MM：
“A”= WoHoB
“B”= Co
“C”= WkHkCi

4. Communication-optimal dataflow

4.1 Dataflow with Minimized Off-Chip Communication

（1）数据流描述

这种数据流（数据调度）可以描述如下：对batch、output channel、output row、output column 进行tiling，tiling系数分别为b、z、y、x，也就是说每次迭代计算一个大小为bxyz的输出block的Psums（之所以称作Psums，是因为一次迭代只计算了k个input channel的累加和）。为了计算这样一个输出block（绿色部分），需要在input channel维度上进行多次iterations (partial update to the output block)，每次iteration取k个input channel进行计算，那么输入数据就需要：b×（x+Wk-1）×（y+Hk-1）×k=bx'y'k（红色部分），权重数据就需要：Wk×Hk×k×z（红色部分）。

文章提到“For an output sub-matrix, the needed inputs and weights are read from the off-chip DRAM exactly once.” 文章说对于一个输出子矩阵，所需的inputs和weights只需要从片外DRAM中读取一次。但是考虑到输出矩阵由多个这样的子矩阵构成，这时候inputs和weights的读取就不止一次了，具体来说，对于weights而言，因为对于输入通道Ci的循环位于output row、output column和Batch循环的内层(外层进行一次新的循环，内层循环已经完成一轮，也就意味着原来从DRAM导入到Gbuf的数据发生了覆盖)，因此有多少个子矩阵，就会对应多少次weights(CiWkHkCo)的重复读取,即weights被重复读取的次数为：BWoHo/bxy；同样地，对于inputs而言，因为对应于输入通道Ci的循环位于输出通道Co和Batch的循环的内层，因此inputs被重复读取的次数为：BCo/bz ，即输出通道数除以每次迭代计算的输出通道数。以上是根据数据流的伪代码推出的结果，其实这个结论也可以从文章后面给的公式推导出来。

文章还提到的一点是，“For a fixed quadruple {b, z, y, x}, k does not affect the off-chip communication. However, under a given on-chip memory capacity, smaller k results in larger output sub-matrices, and thus, less output sub-matrices. Hence,k should be the smallest value, namely, 1.” 文章说对一个固定的四重组合{b,z,x,y}，k（每次迭代计算的通道数，也就是每次从DRAM导入到GBuf的通道数）这个因子不会影响片外访存，在给定的片上memory容量下，更小的k会得到更大的输出子矩阵（因为可以匀出更多的的容量给Psums），也就相当于更少的子矩阵数目，从上一段的分析来看就是更少的weights重复读取次数(BWoHo/bxy)，所以文中建议k=1.

如下图所示，k的取值（下图用in_ch表示）其实是会影响片外访存，因为当Ci/k大于1时（只要大于1，就存在Gbuf中weights数据的前后覆盖），weights的访存就是固定为WoHo/xy了，而在一般的实际应用中，通道数Ci往往比较大，不适合分配这么大的片上memory去存Ci个通道，也就是说一般情况下Ci/k这个值都是大于1的，所以文章的思路就是既然这样，干脆就让k=1，把更多的片上memory匀给输出子矩阵，这样就相当于xy可以取得更大，也就减少了weights的访存次数：WoHo/xy。在我现在的设计中，我采用的优化思路是去从算法上减少Ci，也就是通过分组卷积让输入通道减为Ci/group，如此一来达到让Ci/k这个值等于1，从而使得weights的访存降低为1次。另一方面，从inputs访存来看，通过分组卷积使得每组卷积的输出通道减为Co/group,这样inputs被重复读取的次数降低为BCo/(group×bz)。

文章对于这种数据流更好的原因做了以下几点归纳：首先，它充分运用到了OutR，因为Psums在整个计算过程中都驻留在片上，直到所有计算（partial update）完成，才会被一次写回到DRAM。其次，它充分运用了WndR，在每个x'×y'区域，每个input被R个滑窗重用。然后，它也考虑到了InR，因为输入被z个卷积核中的权重所复用，但这种复用不是充分的，因为z<Co。最后，也考虑了WtR，因为一个权重被bx'y'个inputs复用，同样地WtR也是不充分的，因为一个权重只能被这一小块输入复用，其他块计算时需要重新导入一遍。总而言之，这种数据流充分运用了OutR和WndR，也以一种平衡但非充分的方式结合了InR和WtR（InR和WtR可以结合下文图8理解，其实就是计算阵列横向和纵向的相互复用）。

（2）验证提出的数据流达到下边界

按照前面的数据流描述，输出图像一共被分为(BWoHoCo)/(bxyz)个blocks，对于每个block，需要WkHkCiz个weights和bx'y'Ci个inputs数据。因此DRAM的访存为：

可以从第二个等式看出，DRAM访存等于：block的数目乘以卷积核的总大小(WkHkCiCo)，再加上对于输出通道的遍历次数(Co/z)乘以输入图像的总大小。也就是说，卷积核被重复访问了（block的数目）次，输入图像被重复访问了（Co/z）次，这与前面的分析是一致的。

然后文章针对上式做了一个近似，近似的条件为R≈WkHk/(D^2),x'≈Dx,y'≈Dy,其中D表示步长，x'和y'是输入子矩阵的大小，x和y是输出子矩阵的大小，文章提到当x>>1和y>>1时后面2个式子成立，原因在于：x=(x'-Wk)/D+1,y=(y'-Hk)/D+1,所以x'=Dx+Wk-D,y'=Dy+Hk-D（卷积光晕现象），例如卷积核尺寸为3，D=1,x=224，那么x'=1*224+3-1=226，两者近似相等。上式近似后的结果如下：

进一步地，写入DRAM的数据量为：BWoHoCo，这一数据量与分块系数{b,z,y,x}无关，因为该数据流的部分和一直都是驻留在片上，直到计算完成才一次写回到DRAM中。由此文章提出了2条最优通信的tiling参数原则：

第一条：为了平衡inputs和weights的loading，令bxy=u≈Rz，也就是bxy/R≈z，其中R是前文提到的卷积窗复用系数。
从后文mapping部分可以看到，之所以让bxy/R≈z,是因为导入的inputs数据(bxy)可以被使用R个pass，而导入的weights(z)在每个pass都需要导入一次。

第二条：uz=bxyz≈S&k=1,即将大部分的片上memory分配给Psums。
bxyz就是输出block的大小

运用第一条原则，并将写DRAM数据量考虑进来，得到下式：

运用第二条原则，uz≈S，并且当WkHkCi/√RS>>1，此时可以忽略写DRAM的部分，则：

这正是3.2中的理论下界。这个结论背后的基本原则是：使用最少的输入产生最多的输出，这意味着数据重用达到了最大化。

4.2 Workload and Storage Mapping with Minimized On-Chip Communication

按照ASPLOS 2017斯坦福的论文TETRIS所说，数据流问题可以分解为2个子问题，第一个是mapping 问题，即如何将一组卷积计算映射到PE阵列（图7伪代码的红色部分），第二个是ordering问题，即如何buffer数据从而最大化片上数据复用（图7伪代码的绿色部分）。前面的讨论其实都是围绕第二个问题，即ordering问题，优化DRAM和on-chip memory之间的通信，下面文章进一步讨论了第一个问题，即mapping问题。

最小化GBuf通信

文章首先提出，优化off-chip通信和on-chip通信之间有很大的区别。当最小化芯片off-chip通信时，由于问题的规模可以是任意的，但是硬件资源（片上memory）是固定的，所以tiling是必要的，并且工作负载是通过一系列连续的iterations完成的。然而，对于一次迭代，由于输出子矩阵大小受on-chip memory容量的限制，因此可以设计PE数组大小和Reg容量，使硬件资源能够一次处理迭代的工作负载。这种差异导致了不同的下界，加载的输入和权重(在GBuf中)可以被正好读取一次。这无疑是最小可能的GBuf通信。

图9给出了一个详细的例子：对2个PE的mapping。对一个PE，需要x_s'y_s'k个inputs（进一步对bx'y'k按照PE阵列一列上的PE数目进行划分）和z_skW_kH_k个weights（进一步对z按照PE阵列一行上PE数目进行划分）。为了在x_s'y_s'运用WndR（卷积窗复用），x_s'y_s'个inputs（对于1个PE）被load到Regs。因为weigts不存在WndR，因此可以只load z_s 个weights（对于一个PE）。在一次迭代中，如果将一次完整的outputs更新操作（x_sy_sz_s这个输出小块的所有点更新一次）称为一次pass（第i次pass计算所有outputs的第i个Psums）,那么在每次pass，1个PE使用x_s'y_s'个inputs和z_s个weights产生x_sy_sz_s个Psums（也就是一次累加）。因为这里1个PE对应一个MAC 单元，一个周期只能完成1次乘累加操作，因此一个pass对应x_sy_sz_s个周期（计算一个输出点的Psums花费1个周期）。载入的inputs数据可以被使用WkHk个pass，因为Ifmap平面的每个数据点其实都会被kernel平面的每个weights扫一遍（除了边界数据点外）。但是载入的weights只能被使用1个pass，因此PE需要在每个pass都导入z_s个weights到Regs。如此，完成一次迭代，即产生完整的x_sy_sz_s累加和，需要kWkHk个pass（即需要这么多次Psum更新操作），其实也就是累加链长。值得注意的是，这个累加和仅仅对于当前迭代来说是完整的，但是对于实际的卷积计算而言还不不是完整的，因为一次迭代只累加了k个通道，一共有Ci个通道数据需要累加。

结合PE阵列考虑，同1行的PE共享载入的inputs数据，一行中每个PE算z_s个输出通道，一行的PE一共计算z个输出通道（输出并行）。同一列的PE共享载入的weights数据，一列中每个PE算x_sy_s个outputs数据，一列的PE一共计算bxy个数据（其实也就是说卷积核在输入图像的不同区域范围x_s'y_s'是共享的，得益于多个x_s'y_s'的并行计算，也就是卷积窗并行）。因此，GBuf中的每个weight正好只被读取了一次，GBuf中的每个input数据平均被读取了(x_s'y_s'/x_sy_s)次，大于1是因为卷积光晕现象。当然也可以设计一种复杂的数据传输网络避免由于卷积光晕现象导致的额外读取，但是会使得硬件复杂、读取模式不规则。这里对GBuf的读取次数分析时基于当前的iteration而言的，如果考虑所有的iterations，那么weights(CoCiWkHk)被读取的次数为：(BWoHo)/(bxy),也就是分的sub-matrix数目，因为计算每个sub-matrix都要再导入一遍weights数据。考虑所有的iterations，那么inputs(BCiWiHi)被读取的次数为：(BCo)/(bz)，因为每次导入到Gbuf中的数据只够b个batch的z个输出通道使用。此处的分析可以结合图7的数据流伪代码考虑

文章中用来存储inputs和weights数据的存储器使用的是global Regs，而不是PE内部的寄存器，例如在图9中，每一行PE共享x_s'y_s'的GRegs.在实际中为了避免大的fanouts和长线，文章对PE阵列进行分组，每组PE共享一批GRegs。文章选择PE的局部寄存器LRegs对Psum进行存储，一共需要bxyz个寄存器，这样做的好处在于：如果将Psums存储在GBuf中，那么每次update都要从Gbuf中读取到Reg中，更新完再写回GBuf，总而造成大量的数据搬运，导致高能耗。而将Psums保留到PE内部，可以最小化Gbuf和Regs间的通信。

如上图所示，每个PE计算z_s个输出通道的x_s×y_s区域，因此一个PE在输出sub-matrix中贡献z_s×x_s×y_s这样一个block，p×q个PE的输出应该覆盖reshape后的输出sub-matrix（bxy×z）。通过采用上述workload和storage的mapping方式，GBuf的容量可以得到减少：每次不需要导入KWkHkz个weights和bx'y'k个inputs，只需要存储一行一列数据即可，即weights存储z个(Reshaped weight sub-matrx的一行)，inputs存储bx'y'个（Reshaped input sub-matrix的一列），其实也就是一次pass所需的数据量。这样其实就是流水线工作，一旦Gbuf中的数据被导入GRegs，GBuf就被用来为接下来的pass预取数据。

最小化Reg通信

Psums存储在PE的LRegs中，因为每个MAC操作对应一次Reg写操作，所以总的Reg写次数为：

将Psums保持在LRegs自然地达到下边界。

文章只对存Psum的LRegs的写次数进行了分析，缺少对于存Inputs和Weights的GRegs的读次数的分析，GRegs的访存跟PE具体如何使用x_s'y_s'个inputs和z_s个weights产生x_sy_sz_s个Psums的具体操作过程有关，按照前文作者对其数据流优越性的描述提到的“More importantly, it also takes into account InR (an input is reused by weights in z kernels)and WtR (a weight is reused by b×x'×y' inputs) at the same time.”推测其计算方式为：例如对于第1个pass，先取1号weight，与1-9号inputs做MAC（9个clock），再接着取2-z_s号weight重复上述运算过程。所以1个pass inputs就被重复读取了z_s次，一共WkHk个pass就被重复读取了WkHkz_s次,而weights就只被读取了一次。

5. Communication-optimal CNN accelerator architecture

文章给出的架构例子具有64KB的Psums，p×q=16×16个PEs。考虑16bit的算术单元，那么就有32768个Psum条目，每个PE具有128个。如前所述，对PE阵列进行分组，每组PE（pg×qg=4×4 PEs）共享一系列的GRegs，所有GReg行存储相同的weights，所有GReg列存储所有的inputs。

GBufs
根据之前的设计原则，bxy≈Rz,bxyz=S=32768,如果R=1（也就是没有WndR），bxy≈z≈181。因为181是z的近似值，因此设置z=256，也就是WGbuf的大小。如果R变大，典型地，考虑最大的R=9（Wk=Hk=3,D=1），最大的bxy=181×3=543.考虑卷积光晕效应(bx'y')，设置IGBuf=1024。

GRegs

为了适应不同的z（每次迭代计算的输出通道数）值，这里采用了一种MUX逻辑，从而避免复杂的片上网络。对于存储权重的部分寄存器而言，使用了类似Round Robin的连接方式，如果这部分寄存器没有被完全用满，则只需要控制多路选择器的输入即可，而不会涉及没有使用的部分。例如，如果z=64（所以zs=64/16=4），那么MUXes的选择信号就从0-3,4×16刚好等于64。

同样，对于存储输入的寄存器，每一行PE使用一组寄存器，每个GReg具有64个条目，每个GReg segment 从IGBuf导入xs'ys'个inputs，每个GReg segment 具有一个64-1的MUX提供输入给一行PE单元，所以这个input MUX的选择信号为从0到xs'ys'-1。这样做的好处是，只需要控制多路选择器的输入即可将相应的滑窗数据分配给PE。

总结

1、文章对卷积加速器的通信下界作了理论推导，并结合MM作了很直观的类比，很有实践指导意义；
2、文章提出了对于卷积的Ordering方法，总体思路是尽量将片上buffer分配给输出进行分块卷积运算（psum驻留PE的LRegs），并以尽可能少的输入（Inputs和Weights）获得尽量多的输出，我目前的架构设计与其比较类似（输出分块、Psums驻留PE的LRegs），但“以尽可能少的输入获得尽量多的输出”这点还考虑不够
3、文章提出的对于一次卷积Iteration的Mapping方法，在PE阵列的横向运用卷积核并行从而达到InR，纵向运用卷积窗并行从而达到WtR，我目前的架构设计因为只有一列PE，只考虑到了卷积核并行运算，后续可以考虑卷积窗并行，这样一方面可以减少Input buffer的大小，另一方面可以增加输出block的大小，也就是“以尽可能少的输入获得尽量多的输出”，并且提高并行度
4、文章的Mapping方法对于Inputs的重复读取次数较多，对Weights的读取次数只有1次，运用在BWN中是不够合理的，后续可以考虑改进