基于细粒度数据流架构的稀疏神经网络全连接层加速

深度神经网络近几年在飞速发展，它们在人脸识别、智能监控、图像识别、文字识别等领域有着非常出色的表现.特别是在2012年多伦多大学的Alex Krizhevsky团队凭借他们提出的深度神经网络分类模型AlexNet[1]，获得了ImageNet挑战赛冠军.他们把分类误差记录从26%降到了15%.自此之后，大量公司和学者都投入了深度学习的研究中.

目前常用的DNN算法都具有大量的权重，其中全连接层(fully connected layers, FC layers)的权重比例非常高.例如，AlexNet有61×106的权重参数，而这其中全连接层的参数数量有59×106.VGG-16[2]有138×106的权重参数，其中全连接层的参数数量有124×106.为减少DNN算法的权重数量，文献[3]提出了一种使用剪枝(pruning)、权值量化与共享(weight quanti-zation and shared)和哈夫曼编码(Huffman coding)压缩权重的方法.如表1所示，经过剪枝后AlexNet和VGG-16在全连接层的权重数量大量减少.

Table 1 Compression Statistics for FC Layers in AlexNet and VGG-16 After Pruning

虽然压缩DNN可以减少存储权重的空间，然而目前的DNN加速器并不能很好支持这样的算法执行.

近年来涌现出的许多DNN硬件加速器，例如DianNao[4],TPU[5],Eyeriss[6]等，充分利用了DNN的并行性和数据重用的特征，提出了低功耗高性能的DNN硬件加速方法.但是这些专用加速器只能运行稠密的DNN，甚至部分加速器不能支持DNN中一些常见的层，如激活层和局部响应归一化层.只有少量加速器，如EIE[7]和Cambricon-X[8]，可以运行稀疏的神经网络.但是同样地在这些不灵活的硬件上很难实现一些新的算法.

细粒度数据流加速器已经在科学计算领域[9]和大数据领域[10]广泛应用,它在具有高性能的同时也保持着很高的通用性.本文构建的一个细粒度数据流加速器(fine-grained dataflow processing units, FDPU),它可以加速Stencil、FFT和矩阵乘等高性能应用[11-12]，此外文献[13]还证明了DNN在细粒度数据流结构上的实现可以获得非常好的效率和能效比.如图1所示，FDPU(16tiles，8.192Tops)在运行AlexNet各层时，相较于GPU(NVIDIA Tesla K80，8.73TFLOPS)有1.48× ～ 26×的加速.

为了更高效地在细粒度数据流加速器上实现DNN的加速，我们提出了一种在细粒度数据流加速器上加速稀疏的全连接层的方法.这种方法可以减少加速器对内存数据的访问量，并且基本不增加硬件设计，同时对加速器的性能影响也较小.

本文的贡献主要有3个方面：

1) 提出了一种适合细粒度数据流加速器的压缩数据格式，并提出了读取该压缩数据格式的数据流图.

2) 分析了全连接层的特点，为稀疏的神经网络提出了在FDPU上的加速方案.

3) 对比了FDPU与CPU，GPU和专用数据流加速器的实验结果.从实验结果可知，本文提出的加速稀疏的全连接层的方法相较于原有稠密的全连接层运算减少了2.44×～ 6.17×的峰值带宽需求.在输入图像的批次大小(batch size)为64时，FDPU运行稀疏全连接层的计算部件利用率远超过其他硬件平台，平均比CPU,GPU和mGPU分别高了43.15%,34.57%和44.24%.

1 相关工作

1.1 通用细粒度数据流加速器

细粒度数据流架构由Dennis[14]提出，其结构与传统的控制流架构完全不同.细粒度数据流结构具有较好的指令并行性、数据复用性和低功耗等特点.细粒度数据流架构具有3种特性：

1) 数据流结构中的指令只要其操作数准备好了即可被执行，指令的执行不受程序计数器和指令窗口的限制，可以充分挖掘指令级并行和数据级并行；

2) 数据在执行单元(PE)间直接通信，避免了频繁的数据存取，减少访存开销；

3) 执行单元不需要如乱序执行、分支预测、深度流水等复杂的逻辑控制，简化了执行单元的设计.

TRIPS[15]是由德克萨斯大学的Burger等人提出的细粒度数据流体系结构.TRIPS可以同时支持8个程序块(frame)并行运行，用以掩盖指令之间传输操作数的延迟.程序块的指令被映射到4×4执行单元(PE)阵列上，每个PE执行被分配到的部分指令，并将执行结果传递给目的指令.程序块执行完成后，TRIPS调度下一个程序块，将下一个程序块的指令映射到执行阵列上执行.WaveScalar[16]是华盛顿大学的Swanson提出的基于簇(cluster)的可扩展数据流体系结构.每个簇包含4个域(domains)，每个域包含8个PE.数据流程序中的每条指令被映射到PE中.在程序执行期间，WaveScalar不断替换无用指令并将新的未执行指令加载到PE中，就如同波浪一样一波一波地执行指令.2种数据流体系结构都是通用处理器，无法充分利用DNN中的并行性来掩盖操作数传输的延迟，导致功能单元的利用率较低.

1.2 基于数据流思想的专用DNN加速器

相比于功耗较高的通用计算引擎，例如图形处理单元(GPU)，越来越多的研究人员提出了在功耗和性能上更具优势的基于ASIC[17-18]或基于FPGA[19-21]的专用DNN加速器.其中基于脉动阵列的DNN加速器或者是简单的控制数据流入流出的DNN专用加速器都可以视为数据流思想延伸的产物.

纽约大学的Farabet等人在2011年提出了一款面向卷积神经网络的数据流加速器NeuFlow[22]，它是一个运行时可重配置的数据流结构.DianNao[4]是由中国科学院计算技术研究所的陈云霁于2014年提出的深度学习专用加速器.它采用了基于分时复用的加速器设计结构，该结构由神经功能部件(neural functional unit, NFU)和片上存储构成.DianNao可以说开启了专用DNN加速芯片研究的风潮.2016年麻省理工大学的Sze提出了卷积神经网络加速器Eyeriss[6].Eyeriss使用了一种最小化数据传输功耗开销的数据流模型，可以利用DNN具有的所有数据重用类型.TPU[5]是谷歌提出的机器学习专用芯片，它使用了256×256的脉动阵列加速矩阵乘和卷积，实现了非常高的吞吐量和极短的响应时间.FlexFlow[23] 提出了基于多种并行类型互补的卷积实现，提高了计算资源的利用率.此外，它可以为不同的卷积层提供最优的并行混合方案.EIE[7]是2016年斯坦福大学提出的用于加速稀疏的全连接层和RNN等神经网络的专用加速器.Cambricon-X[8]提出了一款既可以加速稠密神经网络，也可以加速稀疏神经网络的硬件加速器.但是这些专用数据流加速器为了获得更高的性能牺牲了硬件的灵活性，有些加速器甚至不能支持DNN的全部层.相较于这些加速器，细粒度数据流体系结构可以提供更高的灵活性和更广的应用范围，针对不同应用自身的特点挖掘其并行性.如本文提出的架构可以用于数据中心[24]加速矩阵乘、FFT、Stencil等高性能应用，同时也能用于加速神经网络等应用.

2 DNN全连接层背景

DNN在各个领域和各种应用中具有不同的形状和尺寸，比较著名的DNN模型有AlexNet[1],VGG-16[2]等，这些模型独特的结构决定了它们能达到的精度和效率.DNN是由一系列层(layer)构成的，主要有卷积层(convolutional layers, CONV)、池化层(pooling layers, POOL)、全连接层(fully connected layers, FC)、激活层(activation layers, ACT)和局部响应归一化层(local response normali-zation layers, LRN)等.DNN的输入是一组需要被网络分析的信息，这些值可以是图像的像素、音频的采样幅度等数值表示.这些输入通过DNN的推断后，就会得到相应的分析结果.DNN的精度还与它各个层中权重的值有关，可以通过训练对网络中的权值进行调整.

全连接层是DNN的重要组成部分，是DNN所有层中参数最多的层.全连接层通过使用滤波器权重从输入数据中提取特征.全连接层的参数如表2所示.

全连接层的输入是由从多张输入图像提取出的一组2-D输入特征图(input feature maps)构成.一张输入图像提取出的一组输入特征图称为一个通道(channel)，每次输入网络的一组图片称为一个批次(batch).所以输入集是一个四维张量，其参数分别是一个batch内的图像个数N、每张图像的输入特征图数量C、输入特征图的行数H、输入特征图的列数W，本文用I∈RNCHW表示.全连接层的权重(filters)也是一个四维张量，其参数分别是每张图像的输入特征图数量C、每张图像的输出特征图(output feature maps)数量K、权重的行数R、权重的列数S，本文中用F∈RKCRS表示.在全连接层中，每一个结点都与上一层的所有结点相连.因此输入特征图与权重大小相同，即H=R, W=S.多个2-D filters会组成一个filter channel，分别与一个channel内对应的2-D输入特征图卷积，所得结果累加获得一个输出特征图.每个输入channel都会和K个filter channel卷积，从而获得输出特征图的四维张量，本文中用O∈RNKPQ表示(其中P是输出特征图的行数，Q是输出特征图的列数，P=Q=1).

可以得到全连接层的计算为

0≤n<N, 0≤k<K, p=q=0.

从式(1)可以看出，全连接层可以看作是输入特征图与权重大小相同的特殊卷积层.根据全连接的运算特点，当N=1时，通常将其转换为矩阵向量乘计算，其形式如图2所示.N>1时，则可以转化为矩阵乘.

N=1时，得到全连接层的公式为

3 FDPU结构

3.1 细粒度数据流体系结构概述

FDPU是面向计算密集型的、具有简单的访存模式和数据重用特征应用的细粒度数据流加速芯片.FDPU是基于ASIC实现的，它支持细粒度数据流指令集，通过最大化数据流指令级并行性提高其性能.FDPU的总体结构如图3所示.FDPU是由执行单元(processing element, PE)、数据缓存(data buffer, Dbuf)、指令缓存(command buffer, Cbuf)、一个微控制器(micro controller, MicC)和一个直接存储器存取(direct memory access, DMA)组成.PE阵列呈二维结构排列.Dbuf和Cbuf是用便签式存储(scratch pad memory, SPM)的存储访问形式实现的.Dbuf分布在PE阵列的周围，Cbuf则位于PE阵列的左侧.MicC用于控制指令在PE上的执行.PE，Dbuf，Cbuf，MicC通过2-D mesh网络相互通信.

1) PE.PE的内部结构如图3的下半部分所示.每个PE包含可流水的执行单元、指令缓冲、操作数缓冲、指令发射控制器和本地寄存器单元.

2) Dbuf.用于存储数据，被所有PE共享.

3) Cbuf.用于存储要映射到PE中的指令和PE的本地寄存器值.

4) MicC.负责控制加速器的运行过程.执行开始时，CPU会向MicC发送请求启动加速器.然后MicC会通过Mesh网络把Cbuf中存储的指令和本地寄存器的值送到PE内.PE初始化完成后，MicC会向PE阵列流水地发送上下文启动指令和上下文ID，并收集PE发来的上下文结束消息.当PE阵列将所有上下文都执行完后，MicC会向CPU发送结束消息.

5) NoC.Router之间采用静态XY(X方向优先)的确定性路由策略.

6) DMA.负责Cbuf、Dbuf和内存的数据交换.

3.2 并行模式

传统细粒度数据流架构(如TRIPS[15])，将应用的程序划分为多个块，程序块之间必须串行执行.只有前一个程序块执行完后，才会载入和运行新的程序块，这造成计算部件的利用率不高.因此，FDPU不只是简单地采用了数据流模式，还采用了循环流水[25]的优化方法提高计算部件的利用率.

数据流模式是一种与传统控制流完全不同的计算模式.在传统控制流处理器中，指令按照程序计数器(program counter, PC)的顺序执行.但是，在数据流模式中，只要指令的操作数准备好了，那么这条指令即可被执行.

在数据流计算中，程序是以数据流图表示的，每条指令的执行结果直接传递到另外一条指令，指令与指令之间通过依赖边来建立依赖关系，从而形成数据流图.数据流图中的每个节点表示一条指令，每条边表示一条指令与另一条指令之间的依赖关系.如图4(a)所示，把数送入数据流图，指令就会依据依赖关系依次被发射.例如当Inst3收到Inst0和Inst1输出的结果后，Inst3就可以执行了.

在PE中，操作数缓冲中的每一个条目是被一条指令私有的，存储属于这条指令的所有操作数.指令发射控制器会监视指令所需的所有操作数是否都已就位.当指令满足发射条件，指令发射控制器会将指令和其操作数送入译码器中.译码完成后，opcode和操作数被送入可流水的计算部件中.最终，指令的计算结果会通过Mesh网络传输到Dbuf中或依赖于这条指令的其他指令的数据缓冲条目中.

数据流图的指令会被映射到PE中，图4(b)给出了图4(a)中的一种可能的映射结果.文献[26]提出了一种在细粒度数据流体系结构中使用的指令映射算法——基于负载均衡(load balance centric, LBC)的指令映射算法.LBC算法按照深度的优先顺序依次映射数据流图中的所有指令，对每条指令分别计算执行单元阵列中所有位置的代价，取最小代价的位置作为最佳映射位置.在本文中，为了获得尽可能更优的性能，数据流图的映射则是采用了手动映射的方法.

2) 循环流水模式

数据流程序可以在加速器上被多次执行，一个数据流程序的一次完整执行称为一个上下文.循环流水的优化方法面向具有可分块和并行性特征的应用，进一步利用上下文间的并行处理特征修改数据流结构中上下文切换逻辑，使每一个上下文的开始不需要等待上一个上下文的结束.这样循环流水化结构上的多个上下文以流水线的方式进入执行阵列，数据流图中的每一条指令在执行一次后会立刻接收到下一个上下文的操作数，使执行单元的利用率得到极大的提高.

如图4(c)所示，多个上下文以流水线的方式流过整个数据图，结果以流的方式从数据流图中流出.Inst5执行完上下文1的数据操作后，立刻接收到上下文2的操作数，可以再次执行运算.用户只需要配置MicC，设置好需要计算的上下文数量.FDPU开始计算后，MicC将上下文流水送入执行阵列，并统计已经完成的上下文数量，确定当前计算是否完成.在上下文之间完全没有数据依赖时，所有上下文可以在加速器上充分流水；若上下文间有数据依赖，可通过MicC中的上下文控制逻辑控制上下文进入执行阵列的时间，维持有数据依赖的上下文之间的顺序.

3.3 数据流指令集

FDPU的指令格式如图5所示.每个指令由指令码、指令依赖的源操作数个数、立即数、结果的目的地址组成.目的地址指向某个PE中的操作数缓冲的地址.FDPU的指令集包含了基础的运算指令、访存指令和循环指令[27]等.表3列出了本文中用到的数据流指令和指令对应的功能.

4 基于稀疏的全连接层加速方案

4.1 细粒度数据流分支指令设计

为了增加数据流程序的控制能力、更好地支持稀疏的全连接层，本文设计了用于细粒度数据流结构的分支指令——SWITCH指令.SWITCH语句会根据上游给它的第2个操作数的值与0比大小的结果判断将数据发送给哪些下游指令.图6是一个使用SWITCH指令的数据流程序例子.图6(a)是这个数据流程序实现功能的伪代码.如果EQ发送给SWITCH0的值大于0，则SWITCH0会沿着点划线发送从LD0接收来的数据，接着会执行IMM1,MUL0指令；如果EQ发送给SWITCH0的值等于0，则SWITCH0会沿着粗实线发送从LD0接收来数据，接着会执行IMM3指令.点划线和粗实线最终都会将数据传输到同一个指令的相同操作数位置，保证不论走哪个分支下游指令均可以发射.

可以看到图6中ADD0指令有一条虚线指向SWITCH0，这条依赖边是为了保证在循环流水模式下，上下文流过SWITCH0的数据顺序与流过ADD0的数据顺序是一致的.如图7(a)所示，在没有ADD0指向SWITCH0的数据依赖边时，当2个上下文的数据在不同的分支流动，后运行的上下文的数据有可能会先于前面的上下文到达后续的指令.这是因为指令执行(数据流指令的发射没有固定的顺序)和数据在片上网络传输的延迟是不确定的，这种情况会造成运算结果的错误.

在汇合指令ADD0增加一条指向SWITCH0的依赖边可以解决这样的问题，这条边被称为反馈依赖边.SWITCH指令被增加了一个源操作数用于接收反馈信号，在执行初始状态下，这个操作数被初始化为已经收到；运行过程中，每次SWITCH执行后都需要等到分支后的某个汇合指令给它发送的操作数，才能进行下一次运算.如图7(b)中，ADD0担任了汇合指令的作用.汇合指令可以是任意种类的指令，但它必须是SWITCH指令的2个分支汇合后的数据流指令.这样的方式可以在不增加硬件开销的情况下保证SWITCH和其后的指令的数据流动顺序一致.

4.2 面向细粒度数据流的稀疏存储格式

常用的稀疏矩阵存储格式有很多，比如坐标格式(coordinate format, COO)、压缩稀疏行格式(compressed sparse row, CSR)等.但是由于数据流程序的控制性较弱，无法灵活地控制循环次数等，在这些格式很难用数据流程序高效解析.比如COO，它用一个三元组表示，分别是(行号，列号，数值).读取到当前数据的行号与列号后，才能知道数据的位置，很难将数据划分为多个上下文并行处理.而CSR格式，虽然其格式可以方便地推算得到每行数据的数量和数据的起始位置，便于划分数据，但是由于每行数据的数量不确定，数据流图无法确定.对于细粒度数据流加速器，需要一种更具有“确定性”的稀疏矩阵存储格式.

本文提出了一种类似于CSR的存储格式，称为面向细粒度数据流的压缩稀疏行格式(fine-grained dataflow CSR, FD-CSR).FD-CSR与CSR相同，也由3部分组成：数值(values)、列号(column indices)以及行偏移(row offsets).数值用于存储数组中所有的非零元素；列号的每一个比特标志了一行数据中每个元素是否为0；行偏移则表示每行的第1个非零元素在value中的偏移位置.通过这样的设计，可以使列号和行偏移都成为固定长度的数组，方便数据流程序进行读取.

如图8所示，一个任意长度的一维数组会被重新排列为每行16个元素的二维数组.这是因为每个列号的数据位宽是16 bit，只能表示最多16个元素的有效位.列号的每一个比特代表其对应的数据是否为0，如第1个列号为6339，其二进制数值为0001100011000011(最低位对应第1行的第1个数据，最高位对应第1行的最后一个数据).该数组压缩后的列号和行偏移的数据个数均为二维数组的行数，数值的数据个数则为数组中非零元素的个数.

这样的稀疏矩阵存储格式的设计可以将列号和行偏移的个数固定.本文设计的数据流图会通过对列号和行偏移的分析，同时使用SWITCH语句，实现对不定个数的数值的解析访问.

4.3 读取稀疏存储格式的数据流图设计

全连接层的计算通常被转化为矩阵向量乘.矩阵向量乘是由大量的向量点积组成的，其操作如图9(a)所示，其中A代表权重的一行，B代表输入特征图，C代表输出特征图的一个元素.A的每个元素与对应的B元素相乘，其结果进行累加，最终得到C.在稠密的矩阵向量乘中，数据流图被写为图9(b)的形式.在稀疏的全连接层中，权重使用了稀疏矩阵存储格式进行存储.为了读取稀疏的权重，本文提出了如图9(c)所示的数据流图.

数据流图首先获取了本行的列号和行偏移.列号被共享给了多条指令，AND0将列号与0x1按位与，获得了本行第1个数是否为非零数的结果.同样AND1,AND2,AND3分别将右移了1位、2位、3位的值与0x1按位与，分别获得了对应的数据是否为非零数的结果.行偏移首先被减一，然后与AND0输出的结果相加.如果AND0输出1，那么ADD0算出的就是本行第1个数在数值向量中的偏移.ADD0的结果会传给下一个ADD，只有AND输出的值为1时，即对应数据是非零数，ADD的输出结果才是对应数据在数值向量中的地址偏移.AND与ADD的结果均会被传给SWITCH指令.当AND输出1时，SWITCH会把ADD算出的偏移传给LD指令，LD指令从对应的存储地址取数并把获取到的数发送给FMUL或FMADD.当AND输出0时，SWITCH则会传输数据给FIMM，FIMM则将0值发送给下游.FMUL指令和FMADD指令会从2条分支中的一条获得向量A中的一个元素，并与从LD指令传输来的向量B的元素相乘.FMADD指令将乘积与上游送来的C的部分和进行累加，最终得到C.

5 实验与结果

在本节中，我们使用本文提出的方法，在FDPU上加速运算了经过剪枝后的AlexNet和VGG-16中的稀疏全连接层.

5.1 度量标准

本文使用了计算部件利用率(computing resource utilization)来评估稀疏神经网络在不同峰值性能的硬件加速器的优化效果.

5.2 实验平台

我们以中国科学院计算技术研究所自主研发的大规模并行模拟框架SimICT[28]为平台，实现了一个C语言的精确于时钟的模拟器.实验环境具体配置如表1所示.FDPU模拟器的结构如图3所示，主要包含ARM处理器、DMA控制器、内存和FDPU等模拟组件.

FDPU加速器由8×8个PE、32个Dbuf、8个Cbuf、1个微控制器(MicC)和1个DMA控制器组成.所有Dbuf的大小均为2 MB，每个PE内的操作数缓冲为6 KB.浮点数据均使用16-bit表示.每个PE有2个32-bit的定点乘加器、用于计算load width=5,height=11,dpi=110

store的地址索引以及16-bit的SIMD4的乘加器.FDPU运行时的频率为1 GHz，其峰值性能为512 Gops.

我们用verilog对FDPU设计进行了实现和rtl级仿真，并对模拟器进行了时钟级的校准.然后用45 nm的工艺进行了综合，最终得到的面积约为44 mm2，功耗约为3.27 W.

实验中的对比基准我们使用了CPU(Intel Core i-7 5930k)，GPU(NVIDIA GeForce GTX Titan X)和Mobile GPU(NVIDIA Tegra K1).其性能数据均来自文献[7].

5.3 数据集

我们选择了AlexNet和VGG-16中稀疏程度差异较大的3个层进行性能对比，这3个层分别是AlexNet-FC6，AlexNet-FC8和VGG16-FC7，它们的稀疏性分别为9%，25%，4%.我们对比了运行稠密的全连接层和稀疏的全连接层的性能.其中稠密的全连接层来自Caffe model zone，稀疏的全连接层使用了文献[3]中剪枝的算法生成.

5.4 实验和结果

图10展示了FDPU在加速稀疏全连接层与稠密全连接层所实现的计算部件利用率.我们可以看出，本文提出的稀疏全连接层的加速方法虽然相较于稠密的全连接层增加了大量的指令，但是仅有少量的性能损失.其中在batch size为1和4时，两者的性能差距最高为1.4%；在batch size为64时，稀疏全连接层的计算部件利用率平均比稠密的低11.7%.其主要原因在于batch size较小时，全连接层的数据复用程度很低，此时不论是稠密的还是稀疏的全连接层数据流图中计算指令的比例较低，访存和计算访存地址的指令比例较高.这使得因读取稀疏矩阵数据所增加的指令在访存指令的占比很低，导致稀疏与稠密的全连接层运行时计算部件的利用率相近.而batch size为64时，因数据在全连接层的复用程度增高，全连接层数据流图中计算指令的比例增加，使得因读取稀疏矩阵数据所增加的指令在访存指令的占比增高，导致了稀疏全连接层的性能较稠密的全连接层有较大的性能下降.

从图10中我们还可以发现本文提出的稀疏全连接层的加速方法在不同的稀疏比例的全连接层中计算部件利用率基本相等.这是因为我们提出的方案为了适应细粒度数据流结构，采取了比较稳定的数据流图设计.对于不同的全连接层，其数据流图的流动方式、执行的指令条数相差不大.对于每个权重，不论其是否为非零值，我们都会计算出其对应的地址索引.因此在不同的稀疏比例的全连接层中，FDPU获得的计算部件利用率非常接近.

图11展示了FDPU运行稀疏全连接层相较于稠密全连接层对带宽需求的减少比.稀疏全连接层相较于稠密全连接层可以减少2.44×～ 6.17×的峰值带宽需求.

表4列出了FDPU与CPU，GPU和mGPU在运行batch size为64的稀疏全连接层时的计算部件利用率对比.可以看到，FDPU的计算部件利用率远超过其他硬件平台，平均比CPU，GPU和mGPU分别高了43.15%，34.57%和44.24%.

表5列出了FDPU与CPU,GPU和mGPU在运行稀疏全连接层时的峰值性能、面积效率和能效等的对比.其中FDPU的面积效率是CPU和GPU的17.9倍和2.7倍，能效是CPU,GPU和mGPU的50倍、9.7倍和7.9倍.

Table 4 Computing Resource Utilization Comparison of FDPU and Other Platforms for Running Sparse FC Layers

6 关于卷积层的讨论

本文提出的方法主要利用了权重的稀疏性.卷积层在FDPU上实现是通过循环展开成矩阵乘的方式实现.因此，卷积层也可以利用这种方法减少存储空间和访存带宽需求.但是在卷积层中权重占输入数据的比重相较于全连接层较小，例如在batch size为64时，AlexNet中的5个卷积层中权重分别占输入数据的0.35%,9.43%,19.35%,19.35%和13.79%.本文提出的方法对于卷积层的存储空间和带宽需求的改善很小，但是会造成一定的性能下降.因此在FDPU上目前卷积层还是用稠密的方式存储权重和计算.未来我们会进一步研究如何避免零值权重的计算，从而提高FDPU加速卷积层和全连接层的性能.

7 总结

为了更高效地在细粒度数据流加速器上实现DNN的加速，我们提出了一种在细粒度数据流加速器上加速稀疏的全连接层的方法.这种方法可以减少加速器对内存数据的访问量，并且基本不增加硬件设计，同时对加速器的性能影响也较小.本文提出的加速稀疏的全连接层的方法相较于原有稠密的全连接层运算减少了2.44×～ 6.17×的峰值带宽需求.在batch size为64时，FDPU运行稀疏全连接层的计算部件利用率远超过其他硬件平台，平均比CPU,GPU和mGPU分别高了43.15%,34.57%和44.24%.但是本文中提出的方法无法利用全连接层的稀疏性减少运行的指令条数.未来工作中，我们会继续研究稀疏全连接层的加速，目标是设计出可以利用权重的稀疏性减少计算的数据流图.

[1]Krizhevsky A, Sutskever I, Hinton G E. ImageNet classification with deep convolutional neural networks[C] //Proc of NIPS 2012. Cambridge, MA: MIT Press, 2012: 1097-1105

[2]Simonyan K, Zisserman A. Very deep convolutional networks for large-scale image recognition[J]. arXiv preprint, arXiv:1409.1556, 2014

[3]Han Song, Mao Huizi, Dally W J. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding[J]. arXiv preprint, arXiv:1510.00149, 2015

[4]Chen Yunji, Chen Tianshi, Du Zidong, et al. DianNao: A small-footprint high-throughput accelerator for ubiquitous machine-learning[C] //Proc of the 19th Int Conf on Architectural Support for Programming Languages and Operating Systems. New York: ACM, 2014: 269-284

[5]Jouppi N P, Young C, Patil N, et al. In-datacenter performance analysis of a tensor processing unit[C] //Proc of the 44th Annual Int Symp on Computer Architecture. New York: ACM, 2017: 1-17

[6]Chen Yu-Hsin, Emer J, Sze V. Eyeriss: A spatial architecture for energy-efficient dataflow for convolutional neural networks[C] //Proc of the 43rd Annual Int Symp on Computer Architecture. New York: ACM, 2016: 367-379

[7]Han Song, Liu Xingyu, Mao Huizi, et al. EIE: Efficient inference engine on compressed deep neural network[C] //Proc of the 43rd Annual Int Symp on Computer Architecture. Piscataway, NJ: IEEE, 2016: 243-254

[8]Zhang Shijin, Du Zidong, Zhang Lei, et al. Cambricon-X: An accelerator for sparse neural networks[C] //Proc of the 49th IEEE/ACM Int Symp on Microarchitecture. Piscataway, NJ: IEEE, 2016: No.20

[9]Verdoscia L, Vaccaro R, Giorgi R. A matrix multiplier case study for an evaluation of a configurable dataflow-machine[C] //Proc of the 12th ACM Int Conf on Computing Frontiers. New York: ACM, 2015: 1-6

[10]Milutinovic M, Salom J, Trifunovic N, et al. Guide to Dataflow Supercomputing[M]. Berlin: Springer, 2015

[11]Shen Xiaowe, Ye Xiaochun, Tan Xu, et al. An efficient network-on-chip router for dataflow architecture[J]. Journal of Computer Science and Technology, 2017, 32(1): 11-25

[12]Tan Xu, Shen Xiaowe, Ye Xiaochun, et al. A non-stop double buffering mechanism for dataflow architecture[J]. Journal of Computer Science and Technology, 2018, 33(1): 145-157

[13]Xiang Taoran, Feng Yujing, Ye Xiaochun, et al. Accelerating CNN algorithm with fine-grained dataflow architectures[C] //Proc of 2018 IEEE 20th Int Conf on High Performance Computing and Communications. Los Alamitos, CA: IEEE Computer Society, 2018: 243-251

[14]Dennis J B. First version of data flow procedure language[C] //Proc of Programming Symp, Proceedings Colloque Sur La Programmation. Berlin: Springer, 1974: 362-376

[15]Govindan M S S, Burger D. TRIPS: A distributed explicit data graph execution (EDGE) microprocessor[C] //Proc of 2007 IEEE Hot Chips 19 Symp (HCS). Piscataway, NJ: IEEE, 2013: 1-13

[16]Swanson S. The WaveScalar Architecture[M]. Saint Louis, Missouri: University of Washington, 2006

[17]Chen Guilin, Ma Sheng, Guo Yang. Survey on accelerating neural network with hardware[J]. Journal of Computer Research and Development, 2019, 56(2): 240-253 (in Chinese)(陈桂林, 马胜, 郭阳. 硬件加速神经网络综述[J]. 计算机研究与发展, 2019, 56(2): 240-253)

[18]Ji Rongrong, Lin Shaohui, Chao Fei, et al. Deep neural network compression and acceleration: A review[J]. Journal of Computer Research and Development, 2018, 55(9): 1871-1888 (in Chinese)(纪荣嵘, 林绍辉, 晁飞, 等. 深度神经网络压缩与加速综述[J]. 计算机研究与发展, 2018, 55(9): 1871-1888)

[19]Lu Liqiang, Liang Yun, Xiao Qingcheng, et al. Evaluating fast algorithms for convolutional neural networks on FPGAs[C] //Proc of 2017 IEEE 25th Annual Int Symp on Field-Programmable Custom Computing Machines (FCCM). Los Alamitos, CA: IEEE Computer Society, 2017: 101-108

[20]Lu Liqiang, Liang Yun. SpWA: An efficient sparse winograd convolutional neural networks accelerator on FPGAs[C] //Proc of 2018 55th ACM/ESDA/IEEE Design Automation Conf (DAC). Piscataway, NJ: IEEE, 2018: 1-6

[21]Lu Liqiang, Liang Yun, Xiao Qingcheng, et al. Evaluating fast algorithms for convolutional neural networks on FPGAs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2019: 1-1

[22]Farabet C, Martini B, Corda B, et al. NeuFlow: A runtime reconfigurable dataflow processor for vision[C] //Proc of 2011 IEEE Computer Society Conf on Computer Vision and Pattern Recognition Workshops (CVPR Workshops 2011). Los Alamitos, CA: IEEE Computer Society, 2011: 109-116

[23]Lu Wenyan, Yan Guihai, Li Jiajun, et al. FlexFlow: A flexible dataflow accelerator architecture for convolutional neural networks[C] //Proc of 2017 IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2017: 553-564

[24]Fan Dongrui, Li Wenming, Ye Xiaochun, et al. SmarCo: An efficient many-core processor for high-throughput applica-tions in datacenters[C] //Proc of 2018 IEEE Int Symp on High Performance Computer Architecture (HPCA). Piscataway, NJ: IEEE, 2018: 596-607

[25]Shen Xiaowei, Ye Xiaochun, Tan Xu, et al. POSTER: An optimization of dataflow architectures for scientific applica-tions[C] //Proc of the 2016 Int Conf on Parallel Architectures & Compilation Techniques (PACT). Piscataway, NJ: IEEE, 2016: 441-442

[26]Shen Xiaowei, Ye Xiaochun, Wang Da, et al. Optimizing dataflow architecture for scientific applications[J]. Chinese Journal of Computers, 2017, 40(9): 223-238 (in Chinese)(申小伟, 叶笑春, 王达, 等. 一种面向科学计算的数据流优化方法[J]. 计算机学报, 2017, 40(9): 223-238)

[27]Tan Xu, Ye Xiaochun, Shen Xiaowei, et al. A pipelining loop optimization method for dataflow architecture[J]. Journal of Computer Science and Technology, 2018, 33(1): 116-130

[28]Ye Xiaochun, Fan Dongrui, Sun Ninghui, et al. SimICT: A fast and flexible framework for performance and power evaluation of large-scale architecture[C] //Proc of IEEE Int Symp on Low Power Electronics & Design. Piscataway, NJ: IEEE, 2013: 273-278