EIE结构与算法映射

作者: 月见樽 | 来源:发表于2019-07-22 23:25 被阅读23次

    首发于个人博客

    算法基础

    EIE(Efficient Inference Engine)的算法基础是一种被称为Deep Compression的神经网络压缩算法。EIE可以说是为Deep Compression量身定制的硬件,Deep Compression的算法流程如下所示:

    1. 剪枝:将小于某个阈值的权值直接置为0,这一操作引入权值的稀疏性
    2. 量化:这里的量化是一种非线性量化,通过k近邻类聚算法确定量化中心和量化间隔
    3. 编码:原文中使用霍夫曼编码压缩权值的存储,EIE中使用CSC压缩存储方式

    Deep Compression压缩

    Deep Compression压缩分为剪枝、量化和编码操作。其中剪枝为对所有权值做以下操作:
    pruning(x) = \begin{cases}x & x > T \\ 0 & x \leq T\end{cases}
    其中T为剪枝阈值,该步骤将所有小于剪枝阈值T的权值置为0,引入了权值的稀疏性。原文中对于VGG结构的剪枝后,卷积层的非零参数量一般还剩原参数量的30%~60%中,全连接层的非零参数量一般仅剩5%以下,由于全连接层参数占参数的主要部分,因此全网络的非零参数量仅剩下原有的7.5%。考虑VGG是比较容易产生冗余的网络,因此对其他网络的剪枝效果可能差于VGG网络。剪枝阈值T在剪枝过程中为超参数,需要综合考虑剪枝效果和剪枝后网络的性能表现多次试验确定。

    量化操作为对于每个层,使用k-近邻类聚算法类聚。类聚算法产生指定数量的类聚中心,所有属于某一类的权值都被直接赋予类聚中心的值。随后使用修改过的优化算法运行一定轮数的训练,调整类聚中心的值(权值从属关系不改变),具体过程参见Deep Compression论文,这里仅考虑结果,进行完量化后,每一层的权值张量变为一个同形状的标号张量和一个解码表。标号张量标记每个位置的元素属于的类别,一般仅有25bit(即分为432类);解码表标记每个类别的数据,如下图所示:

    quantize.png

    现在考虑量化对实现的影响。原有的高精度权值张量(取D_Hbit)的非零参数量为M,则需要的存储空间为M \times D_Hbit。量化后权值张量改为标号张量,标号的位数一般远远低于权值数据,取为D_L,需要存储空间为M \times D_L;另考虑编码表,编码表需要的bit数为2^{D_L} \times D_H。则量化后权值需要的存储空间占原有比例为:
    R_w = \frac{M \times D_L + 2^{D_L} \times D_H}{M \times D_H} = \frac{D_L}{D_H} + \frac{2^{D_L}}{M}
    D_L一般来说仅有5bit(VGG网络),因此有M >> 2^{D_L},则可以发现将权值的存储空间降低到\frac{5}{32} = 15.625\%,有效的缓解了存储瓶颈。但是权值使用时,需要根据标号张量中的标号从编码表中查询权值,再将其与输入进行运算,比原有矩阵直接运算多一步查询,需要通过硬件查询。

    Deep Compression论文中为了进一步压缩权值的存储,在量化后使用霍夫曼编码压缩矩阵的存储。EIE为了方便的硬件实现,使用CSC方法压缩稀疏权值矩阵。

    CSC稀疏矩阵表示

    CSC(compressed sparse column)为一种稀疏矩阵的表示方法,其将一个稀疏矩阵压缩表示为三个向量。首先考虑向量的压缩方法,每个稀疏向量被压缩为两个非稀疏向量,如下所示的向量:
    [0, 0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3]
    将其压缩为两个长度相等的向量,第一个向量为按顺序排列的所有的非稀疏元素,第二个向量为对应位置的非稀疏元素与前面一个非稀疏元素中间的0数量,上述向量压缩完成如下所示:
    v = [1, 2, 0, 3] \\ z = [2, 0, 15, 2]
    u为非零元素,z为两个非零元素之间0的数量。例如v[0]=1,z[0]=2表示第一个非0元素为1,该元素之前有2个零;v[1]=2,z[1]=0表示第二个非0元素为2,该元素之前没有0(原向量中为[0,0,1,2,...)。由于这里的z向量使用的为int4类型数据,因此第三个非零数据3之前的18个零超出了表示范围,因此在v中添加一个0元素,即其中v[2]=0,z[2]=15表示第三个数据为0,之前有15个0。这个数据并不是非零数据,是为了能使用int4表示18而额外补充的数据。之后的v[3]=3,z[3]=2为要表示的数据3,之前有2个零,和前一条一起表示间隔18个零的情况,如下图所示:

    csc_vector.png

    随后考虑矩阵的表示方法,CSC稀疏表示将矩阵的每一列视为一个向量进行压缩,每一列都产生一个v向量和一个z向量,第i列产生的向量v_iz_i向量的长度和其他列均可能不同。将每一列的v向量按列号依次连接,z向量按列号依次连接,获得矩阵的v和z向量,为了区分不同列,额外引入u向量,u向量长度为列数加1,表示每一列的v或z向量在矩阵v和z向量中的位置,即第i列的v和z向量在矩阵的v和z向量的第u[i]个到第u[i+1] - 1元素之间,u[0]固定为0。如下图所示:

    csc_matrix.png

    最终,一个稀疏矩阵将被压缩到三个向量U、V和Z中,该方式仅保存非零数据(为了表示超过Z限制额外引入的0除外),同时Z和U向量使用的数据类型一般比U小,因此可以有效的压缩稀疏矩阵。

    EIE结构

    PE结构

    EIE(Efficient Inference Engine)作为一种Engine,主要作为加速器系统组件使用,因此论文中并未提出明确的系统架构,而是重点描述了其PE的结构,PE结构图如下:

    eie_structure.png

    PE按功能为以下几个部分:

    • 蓝色底色部分为缓存部分,分布缓存了CSC格式表示矩阵方法下的U、V和Z向量以及Deep Compression产生的解码表和产生的部分和输出数据。
    • 紫色底色部分为标号处理部分,标号累加为一个累加器,通过累加一个向量CSC表示中之前的元素的z部分产生该元素在向量中的实际绝对位置;列地址生成从矩阵从U向量中获取某一列的数据在V和Z向量中的起始和结束位置。
    • 橙色底色部分为算数运算部分,输入数据和解码后的权值相乘并和之前的结构相加,结果保存在输出缓存中,当运算完成时,通过ReLu单元激活后输出。

    该PE如何映射运算将在后续章节[算法映射]中表述。

    CSC编码器

    PE运算产生的结果并不是CSC方法表示。一般来说,在ReLU函数之前的输出数据并不具有稀疏性,但是ReLU函数将所有负数输出置为0,引入了输入\输出数据的稀疏性,因此需要将输出数据进行CSC编码,CSC编码器结构如下所示:

    nzd_structure.png

    论文中PE以4个一组,每个PE输出一个输出数据及其绝对标号,非零数据检测器从PE0的输出数据开始依次检测,若发现非0数据,则通过绝对标号计算CSC格式的相对标号,同时输出器数据和相对标号,实现CSC编码。

    算法映射

    矩阵-向量乘法

    原论文中以4个PE为一组,计算矩阵乘法。输入权值和输入数据以下图为例:

    eie_weight_data.png

    矩阵乘法计算的目标为:
    Y = W \times X,W \in R^{a \times b},X \in R^b
    上图中,有a=8、b=8。权值矩阵的第i行数据保存在标号为i \% 4的PE中并由该PE负责计算。第i个PE的所有权值行向量顺序堆叠组成一个新权值矩阵W_i,W \in R^{(a//4) \times b},这里新权值矩阵为2行。标号为i的PE中存储的是新权值矩阵W_i的CSC表示。

    EIE映射算法的原理如下图所示,综合考虑输入数据和权值的稀疏性,将矩阵-向量乘法分解为多个向量相乘,当且仅当对应位置上的元素均不为0时才进行计算,因此可以减少很多0之间的运算。

    eie_source.png

    EIE的PE输入为一个CSC格式压缩的稀疏向量,将每个元素的数据和标号(v和z)依次输入数据队列和标号队列。处理一个数据时,从数据队列中取出数据D并从标号队列中取出标号I_z,标号I_z通过标号累加器变为向量的绝对坐标I。以上图中所述第一个数据X0为例,其相z元素为0,即之前没有0,因此X0的绝对位置为0。输入向量CSC格式累加过程如下所示:

    eie_index_acc.png

    随后通过I//2查询奇数U缓存,I // 2 + I \%2查询偶数缓存。分别从偶数U缓存和奇数U缓存中获取地址各一个:

    • 若I为奇数,则从奇数缓存中读取的数据为起始地址U_s,从偶数缓存中读取的数据为结束地址U_e
    • 若I为偶数,则从偶数缓存中读取的数据为起始地址U_s,从奇数缓存中读取的数据为结束地址U_e

    对于X0而言,对应绝对位置为0,读出起始地址为0,结束地址为1;对于X2,读出起始地址为1,结束地址为2;对于X5,读取起始地址为3,读取终止地址为4。对于U_s = U_e的情况,说明该输入数据对应的列无非0数据,可直接跳过该输入数据的处理过程。随后使用U_sU_e之间的值(不包括U_e,即[U_s,U_e))从V缓存和Z缓存中读取权值。对于X0,读出权值W_{0,0}和相对位置0,对于X2,读取权值W_{0,2}和相对位置0;对于X5,读取权值W_{4,5}和相对位置1。根据这些权值从编码表中查询真实权值。相对位置进行与输入相同的权值累加计算真实权值WI,计算结果分别为0、0和1。

    随后输入数据与读出的真实权值依次相乘,相乘的结果与输出缓存中位置为WI的数据累加,过程如下所示:

    eie_acc.png

    累加完成后,输出缓存每个地址存储的就是对应绝对位置的输出结果,完成矩阵-向量乘法映射。

    卷积映射

    卷积映射在原论文中没有提到,一下为基于结构对映射卷积方式的猜测,其映射卷积的方式可能为将卷积拆分为多个矩阵乘法实现,如下图所示:

    eie_conv.png

    PE的输入为广播输入,因此所有PE的输入数据必须相同,而所有权值均为本地存储,因此权值应当不在PE之间交换,由上推测出卷积的映射方法应当将一个K \times K的卷积变为K \times K1 \times 1卷积实现。上图举出了一种2 \times 2卷积在EIE上实现的可能方案。每个PE计算一个输出通道为CO+1,输入通道为CI+1的1 \times 1卷积,所有PE计算完成后,将结果错位相加即可获得2 \times 2卷积的计算结果,错位相加过程如下所示:

    eie_conv_add.png

    相关文章

      网友评论

        本文标题:EIE结构与算法映射

        本文链接:https://www.haomeiwen.com/subject/exxnlctx.html