CNN加速器设计新突破，逼近能效理论极限

2020年4月12日上午，北京智源人工智能研究院和北京大学高能效计算与应用中心联合主办了“AI芯片体系架构和软件专题报告会”，五位学者结合在2020年计算机体系结构顶级会议（ASPLOS和HPCA）中发表的最新研究成果。本文介绍智源青年科学家、中国科学院计算技术研究所副研究员陈晓明的《Communication Lower Bound in Convolution Accelerators》（卷积加速器中的通信下界）。

陈晓明，清华大学博士，研究方向为集成电路设计自动化和计算机体系结构。获得2018年首届阿里巴巴达摩院青橙奖，入选2018年中国科协青年人才托举工程，获得2015年EDAA优秀博士论文奖，已发表专著1本，论文70余篇。现担任DAC、ICCAD、ASP-DAC、GLSVLSI等多个会议的程序委员会委员。

在演讲中，陈晓明带来了发表于HPCA 2020会议的最新成果：针对目前的CNN加速器的能效主要受限于访存的问题，怎么就给定的芯片的片上存储资源，设计最优的卷积数据流使访存最小化，从而能效达到最优。在这个基础上，陈晓明团队还设计出了一个CNN加速器架构，使得加速器能效逼近理论最佳值。

整理：智源社区 赵言、高洛生、常政

一、引言

随着深度学习的发展，CNN结构变得愈发庞大，使得计算量显著增加。如果使用VGG16对一个图像做验证，其运算量接近10的10次方，如此庞大的运算量使用CPU显然是比较费时的。目前的研究针对这个问题提出了各式各样的加速器，如主要依靠多数据并行的GPU加速器，可以做一些定制的自适应运算单元的FPGA，具有更佳效果的专用定制芯片ASIC。

图1：CNN计算量和各类型加速器

在CNN加速器的计算层面，数据访存仍然是较大的瓶颈，陈晓明列举了两个例子（图2）：

①Eyeriss的统计结果，显示能量消耗最大的部分在寄存器，这是因为Eyeriss是一个脉动阵列，片上数据传输非常频繁1。

②陈云霁论文的数据显示片外访存几乎占了所有能耗2，所以现在CNN加速器访存仍然是性能瓶颈。

图2：CNN加速器的访存瓶颈

卷积神经网络的一个基本的运算是有七层循环（图3），包含很多数据重用方式，如权重重用、输出重用，但这里的运算统计不分训练过程和验证过程。访存优化的任务实际为在多层空间中做设计检索，找到一个最优的循环顺序，包括循环展开的跨度Stride的大小。

图3：卷积层及数据重用图示

二、通信访存下界

1.批处理矩阵乘法的访存下界

图4：矩阵乘法运算及其访存量

很显然，在未优化的情况下执行一个矩阵乘法操作产生的访存量Q=2ABC（图4）。

图5：矩阵乘法的访存下界

运算部件实际上在处理计算时是批处理操作，那么每次计算一个xy大小的块时，需要对参与运算的矩阵分块，分块如图5所示。当采用通信优化的方法时，可以计算出来这种方式产生的访存量Q=每块的访存量xC+yC乘以XY分块的数量，由均值不等式可导出对于一个访存下界，即2ABC除以√S，其中S是片上存储的总量。

并且当且仅当x=y=√S时，即由两个输入矩阵中读入相等的数据量时，可以达到通信最优。这种方式得到的矩阵的访存量要比最直接的矩阵乘实现减少√S的量，。对应于实际的计算流程，要把几乎所有的片上存储全部分配给输出部分，用来存储输出中间结果的时候可以达到最小的访存量。

2.卷积抽象为矩阵乘法时的访存下界

上文论述了计算任务为矩阵乘法的访存情况，接下来进入卷积的分析，卷积可以转化为矩阵乘法，下面的抽象过程，是为了便于从逻辑上的推导出理论上的访存下界，但实际上陈晓明具体的优化方案并不是把卷积变成矩阵乘法进行操作。具体的方案，参见下文数据流和架构优化部分。

图6：卷积抽象为矩阵乘法图示

卷积抽象成矩阵乘的过程如图6所示，对于卷积核的抽象，即是把每一个卷积核拉成一列，不同的卷积核拉到不同的列上面，这样就将权重矩阵转化完成；

对于输出结果，每个输出通道变成一列，这样能把不同的输出通道变成不同的列，当一个Batch中有多个输出图像，就上下再堆起来，按照这样的方法输出矩阵就转化完成。再分析输入图像矩阵的元素，一个滑动窗之中所有的元素拉成横向量，然后将卷积窗向右滑动一格，绿色标的部分变成第二行，蓝色的卷积窗变成最后一行，一个Batch中不同的图像也上下堆起来，这样输入转变也可以完成。

卷积可以变换成矩阵层，但这种变换并不等价。可以看到仅对于权重和输出来讲是等价的，这只是对它们的元素做了一下形状的重塑，没有增加或删除元素。但是对输入则不一样，我们将卷积窗展开了。卷积窗中有重叠的元素可以重用，按上面的转变方式这种重用就会消失，所以陈晓明团队定义了一个R表示每一个输入卷积窗可以重用的次数。

图7：卷积窗中的数据重用参数

这样等效完毕后，就会带来一个问题：通信最优的卷积是不是通信最优的矩阵乘法再结合滑动窗重用的过程？

答案是肯定的，这里直接给出结论，推导过程详见论文，简言之即对任何一个卷积操作而言，片外访存的通信访存量Q的下界可以用Ω（）表示一种渐近关系4，这种表示法类似于时间复杂度O（）。

图8：图像卷积的通信访存下界

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

三、逼近通信下界的数据流优化

上文的推导得到了理论上可以达到通信访存最优的数据流经方法，这种方式是在输出的图像里每次取一个很小的块，在一个批处理中有若干图像，因此就需要在若干张图像中提取这些小块，每个图像b中取出x·y·z的块。

那么计算这些块需要多少输入数据？

答案是需要x’·y’·所有输入通道，对于权重而言则需要z个权重的所有通道。按照这种分块方式可以得到五个参数：<b,z,y,x,k>。由于无法一次性地把所有需要的输入数据全部装载到片上存储，因此可以使用分批的方法将输入数据进行装载，k即为每次装载的输入通道的数量。理想化时k=1，此时导致用来装载输入数据的片上存储最小。

图9：数据的分块

把输入数据映射到矩阵乘上，仍然得到一个分块矩阵乘。两个输入矩阵中每次读取一列和一行，然后对两个向量做内积，对输出的块再进行部分和累加。

然而，在实际情况中并不需要完整的读取如此多数据。因为卷积窗的重用，每个元素最多可以被重用R次，使得输入矩阵实际读入的数据就被减少到了最多1/R。

以上推导过程可以得到两条选择分块参数的原则：

1)bxy≈Rz，即从两个矩阵当中读入的量相等；

2)bxyz≈S且k=1，即要把几乎片上所有存储全部分配给输出部分，这样可以以每次最少的输入产生最多的输出，这样做其实和矩阵乘是类似的。实际上，通信优化的实现过程也参考了3中描述的方法。

因为部分和永远驻留在片上，直到计算完成才写回DRAM，所以输出重用是完全的。从输入和权重中读入的量是相等的，所以卷积窗重用充分利用，输入重用和权重重用部分利用，这是以一种平衡的方式利用，这便是本文数据流的特点。

四、逼近通信下界的架构优化

1.任务负载映射

关于片上负载的映射，因为使用的方式类似，在此也仅简要概括而不再赘述。其基本思想类似于俄罗斯套娃，每次计算的一块再以同样的方式细分成更小的块，每个小块分给每个PE。

如图10所示有两块黄色Global Buffer，一块用来存储输入数据，另一块用来存储权重，全局寄存器使用灰色方块表示。数据从Global Buffer读到寄存器中，然后所有的PE再从寄存器读取数据进行计算，最后将部分和存入PE的Local寄存器里面。

卷积窗重用通过全局寄存器实现，即我们无需从DRAM中多次读入可重用的数据。该结构可以进一步优化，对于存储输入量和权重的Global Buffer只需要一行一列即可，通过流水线的方式进行工作，而不再需要把数据全部存在片上且每次只用一部分，这是一种非常浪费的行为。

图10：任务负载映射

总而言之，对于Global Buffer而言其下界和DRAM其实是一样的。每次从DRAM读取的数据存储在Global Buffer中还要被读取一次，也要被写入Global Buffer一次，所以对于读取和写入而言Global Buffer通信量最小值其实与DRAM的通信最小值一样。

对于寄存器而言，其通信量最小值和MAC操作数一样，这个结论的前提是假设PE中加法树层数就是一层，若加法树层数是N层，最后则需要除以N。

2.加速器架构

图11：理想的加速器架构

访存最优的加速器架构如图11所示，理想的加速器架构是不考虑一些实际因素，假设直接根据数据流得出的理想架构。只需要一列片上Buffer存储输入，一行片上Buffer存储权重，所有的PE从这两个片上Buffer读取数据，每次读取一列一行做内积，再对部分和进行累加，所有PE之间不需要传递任何数据。

然而，若所有PE全部共享两个片上存储，实际中会带来连线太长的问题；若在片上加入部分全局寄存器，再把PE分组，每个PE共享一组全局寄存器，这样做能够有效避免片上线太长的问题。除此之外，该架构（如图12所示）和理想架构没有太明显的区别。

图12：加速器架构

还有一个问题值得考虑：不同的卷积层映射到这样的架构上面，带来的分块参数是不一样？加速器架构需要适应不同的分块参数，本文提出的适应方法不是采用复杂的片上网络，而是增加了一个非常简单的多路选择器结构，从而避免了复杂的片上网络。含有多路选择器的加速器结构原理也比较简单，对于存储权重的部分寄存器而言，使用了类似Round Robin的连接方式，如果这部分寄存器没有被完全用满，则只需要控制多路选择器的输入即可，而不会涉及没有使用的部分。

同样，对于存储输入的寄存器，每一行PE使用一组寄存器，只需要控制多路选择器的输入即可，这样做的好处是，如果只使用寄存器的前半部分，控制输入可以保证只选择前半部分而不会选择后面未使用的部分。因此图13所示的含有多路选择器的加速器结构被用来适应不同的分块参数。

图13：含有多路选择器的加速器架构

五、仿真实验结果

实验仿真通过台积电65纳米工艺仿真衡量了五种不同的设计。其中，PE和片上Global Buffer尺寸等都不尽相同。

实验中与很多不同的数据流做了对比，有不同的输出重用方式、不同的权重重用方式、不同的输入重用方式等。图14中蓝色的块表示放在片上供重用。

图14：用于比较的数据流

图15表示了片外访存在5组不同数据流比较的结果。通过比较5组不同的数据流的片外访存证明了陈晓明等人的数据流可基本达到理论下界。

图15：5组不同数据流对比结果

由于陈晓明等人的数据流不使用剪枝算法压缩输入，为了公平起见，图16展示了其数据流与Lower bound、未剪枝压缩Eyeriss和经过剪枝压缩Eyeriss的对比情况，数据参考了1和5中的研究。对比结果显示其数据流比Eyeriss减少了大量片外访存。但仍然存在一个特例，就第一层而言，Eyeriss取得了比下界还小的访存量。这是因为下限Ω像时间复杂度一样，是一种渐进描述，对于小问题可能不是那么准确。

图16：Eyeriss对比

片外访存累加后的量化结果（图17）表明：陈晓明等人的数据流接近300MB，该值低于剪枝压缩后Eyeriss的数据流，更远低于不进行剪枝压缩的Eyeriss数据流。

图17：片外访存累加后的量化结果

图18显示Global Buffer访存的值相比Eyeriss减少了1个数量级，减少超过10倍的Global Buffer访存。

图18：GBuf通信（1）

如图19所示，Global Buffer访存量的理论下界其实和DRAM访存量的理论下界相等，对于权重的下界是则是完全相等。对于输入而言，片上Global Buffer的读入量和写入量都高于DRAM。产生这样结果的原因主要是由于“卷积光晕”现象，即卷积输出大小是x*y，则输入大小要比x*y略大一些，因此需要一些额外的读入和写入，因此实验结果稍大一些。

图19：GBuf通信（2）

图20展示了寄存器的访存量，五种不同的设计只比理论下界多了6%-12%的寄存器的访存量。遗憾的是，由于没有找到任何可对比数据，即便Eyeriss也没有给出寄存器的访存量，因此没有和其它任何方案进行对比实验。

图20：寄存器的访存量

加速器的整体能效如图21所示。对于5种不同的实现，基本上计算部分占据了相当大部分的能耗，因此设计的加速器架构是计算占优而不是访存占优，访存已经降低到了比较小的水平。同时，能效与理论下界的差距在37%-87%，差距的主要原因如图21中黄色部分所示，即Local寄存器，由静态功耗比较高引起。该问题仍然具有优化余地，方法是借助存内计算的思路解决该问题。

图21：能效对比

从图22可以看出，Global Buffer的资源利用率比较低，Global寄存器的资源利用率比较低，这是由于加速器需要额外的资源适应不同的分块尺寸。如果从所有存储资源利用率的角度来看，资源利用率仍然处于较高水平，大约维持在80%-90%之间，PE的利用率高于97%。

图22：资源利用率对比

结语

演讲最后，陈晓明言简意赅地总结了他所做的工作：鉴于当前的卷积加速器访存占的能耗很高，于是设计算法推导出访存理论下界，并以此为基础设计出访存最优的卷积数据流和加速器架构。

Q&A

Q：Convolution转成矩阵乘是通过img2col的方式转的吗？

A：这不是一种真正的转换，只是为了从直观上更好地解释推导过程的方式，就是实现当中我们没有做任何转变。

Q：DRAM Communication Lower Bond和Performance之间有什么关系吗？

A：其实Performance影响因素比较多，比如片上的时钟、处理器核的数量，所以我觉得比较难推导，现在我们能推出来的只有片上存储的大小和访存量的关系，因为这两个是直接相关的，Performance可能难以推出这种很强的关系。

参考文献

1 Y. H. Chen, J. Emer, and V. Sze. Eyeriss: A Spatial Architecturefor Energy-Efficient Dataflow for Convolutional Neural Networks. ACM/IEEE 43rd International Symposium on Computer Architecture(ISCA), June 2016, pp. 367–379.

2 Y. Chen, T. Krishna, J. S. Emer, and V. Sze. Eyeriss: An EnergyEfficient Reconfigurable Accelerator for Deep Convolutional Neural Networks. IEEE Journal of Solid-State Circuits, vol. 52, no. 1, pp. 127–138, Jan 2017.

3 K. Goto and R. Van De Geijn. High-performance Implementation of the Level-3 BLAS. ACM Trans. Math. Softw., vol. 35, no. 1, pp. 4:1–4:14, Jul. 2008.

4 J.-W. Hong and H. T. Kung. I/O Complexity: The Red-blue Pebble Game. Thirteenth ACM Symposium on Theory of Computing, 1981, pp. 326–333.

5 J. Li, G. Yan, W. Lu, S. Jiang, S. Gong, J. Wu, and X. Li. SmartShuttle: Optimizing Off-chip Memory Accesses for Deep Learning Accelerators. Design, Automation Test in Europe Conference Exhibition (DATE), March 2018, pp. 343–348

END