EIE结构与算法映射

算法基础

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

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

Deep Compression压缩

Deep Compression压缩分为剪枝、量化和编码操作。其中剪枝为对所有权值做以下操作:

其中T为剪枝阈值,该步骤将所有小于剪枝阈值T的权值置为0,引入了权值的稀疏性。原文中对于VGG结构的剪枝后,卷积层的非零参数量一般还剩原参数量的30%~60%中,全连接层的非零参数量一般仅剩5%以下,由于全连接层参数占参数的主要部分,因此全网络的非零参数量仅剩下原有的7.5%。考虑VGG是比较容易产生冗余的网络,因此对其他网络的剪枝效果可能差于VGG网络。剪枝阈值T在剪枝过程中为超参数,需要综合考虑剪枝效果和剪枝后网络的性能表现多次试验确定。

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

现在考虑量化对实现的影响。原有的高精度权值张量(取

bit)的非零参数量为M,则需要的存储空间为

bit。量化后权值张量改为标号张量,标号的位数一般远远低于权值数据,取为

,需要存储空间为

;另考虑编码表,编码表需要的bit数为

。则量化后权值需要的存储空间占原有比例为:

一般来说仅有5bit(VGG网络),因此有

,则可以发现将权值的存储空间降低到

,有效的缓解了存储瓶颈。但是权值使用时,需要根据标号张量中的标号从编码表中查询权值,再将其与输入进行运算,比原有矩阵直接运算多一步查询,需要通过硬件查询。

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

CSC稀疏矩阵表示

CSC(compressed sparse column)为一种稀疏矩阵的表示方法,其将一个稀疏矩阵压缩表示为三个向量。首先考虑向量的压缩方法,每个稀疏向量被压缩为两个非稀疏向量,如下所示的向量:

将其压缩为两个长度相等的向量,第一个向量为按顺序排列的所有的非稀疏元素,第二个向量为对应位置的非稀疏元素与前面一个非稀疏元素中间的0数量,上述向量压缩完成如下所示:

u为非零元素,z为两个非零元素之间0的数量。例如

表示第一个非0元素为1,该元素之前有2个零;

表示第二个非0元素为2,该元素之前没有0(原向量中为

)。由于这里的z向量使用的为int4类型数据,因此第三个非零数据3之前的18个零超出了表示范围,因此在v中添加一个0元素,即其中

表示第三个数据为0,之前有15个0。这个数据并不是非零数据,是为了能使用int4表示18而额外补充的数据。之后的

为要表示的数据3,之前有2个零,和前一条一起表示间隔18个零的情况,如下图所示:

随后考虑矩阵的表示方法,CSC稀疏表示将矩阵的每一列视为一个向量进行压缩,每一列都产生一个v向量和一个z向量,第i列产生的向量

向量的长度和其他列均可能不同。将每一列的v向量按列号依次连接,z向量按列号依次连接,获得矩阵的v和z向量,为了区分不同列,额外引入u向量,u向量长度为列数加1,表示每一列的v或z向量在矩阵v和z向量中的位置,即第i列的v和z向量在矩阵的v和z向量的第

个到第

元素之间,u[0]固定为0。如下图所示:

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

EIE结构

PE结构

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

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

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

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

CSC编码器

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

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

算法映射

矩阵-向量乘法

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

矩阵乘法计算的目标为:

上图中,有a=8、b=8。权值矩阵的第i行数据保存在标号为

的PE中并由该PE负责计算。第i个PE的所有权值行向量顺序堆叠组成一个新权值矩阵

,这里新权值矩阵为2行。标号为i的PE中存储的是新权值矩阵

的CSC表示。

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

EIE的PE输入为一个CSC格式压缩的稀疏向量,将每个元素的数据和标号(v和z)依次输入数据队列和标号队列。处理一个数据时,从数据队列中取出数据D并从标号队列中取出标号

,标号

通过标号累加器变为向量的绝对坐标I。以上图中所述第一个数据X0为例,其相z元素为0,即之前没有0,因此X0的绝对位置为0。输入向量CSC格式累加过程如下所示:

随后通过

查询奇数U缓存,

查询偶数缓存。分别从偶数U缓存和奇数U缓存中获取地址各一个:

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

,从偶数缓存中读取的数据为结束地址

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

,从奇数缓存中读取的数据为结束地址

对于X0而言,对应绝对位置为0,读出起始地址为0,结束地址为1;对于X2,读出起始地址为1,结束地址为2;对于X5,读取起始地址为3,读取终止地址为4。对于

的情况,说明该输入数据对应的列无非0数据,可直接跳过该输入数据的处理过程。随后使用

之间的值(不包括

,即

)从V缓存和Z缓存中读取权值。对于X0,读出权值

和相对位置0,对于X2,读取权值

和相对位置0;对于X5,读取权值

和相对位置1。根据这些权值从编码表中查询真实权值。相对位置进行与输入相同的权值累加计算真实权值WI,计算结果分别为0、0和1。

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

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

卷积映射

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

PE的输入为广播输入,因此所有PE的输入数据必须相同,而所有权值均为本地存储,因此权值应当不在PE之间交换,由上推测出卷积的映射方法应当将一个

的卷积变为

卷积实现。上图举出了一种

卷积在EIE上实现的可能方案。每个PE计算一个输出通道为CO+1,输入通道为CI+1的

卷积,所有PE计算完成后,将结果错位相加即可获得

卷积的计算结果,错位相加过程如下所示:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • DianNao系列加速器总结(1)——架构与运算单元简介整体架构运算模块

    月见樽
  • Faster-RCNN阅读笔记系统架构系统训练

    Faster-RCNN是Fast-RCNN的后续版本,主要针对Fast-RCNN速度过慢进行优化。在Fast-RCNN中,速度的瓶颈主要是用于生成候选区域的Se...

    月见樽
  • 数字IC基础知识总结(笔试、面试向)-持续更新

    BCD码为使用4个bit表示一个十进制位数,即123的BCD码为0x123,余3码表示BCD码基础上加3(十进制),例子如下,对于26而言:

    月见樽
  • 基于磁盘的Kafka为什么这么快

    Kafka是大数据领域无处不在的消息中间件,目前广泛使用在企业内部的实时数据管道,并帮助企业构建自己的流计算应用程序。Kafka虽然是基于磁盘做的数据存储,但却...

    用户6070864
  • 机器学习常见的聚类算法(上篇)

    陈浩然,北大在读,个人网站:chrer.com,里面记录了机器学习、深度学习的系统学习笔记,欢迎大家访问,感谢分享!

    double
  • 机器学习(8)——其他聚类层次聚类画出原始数据的图小结

    层次聚类 紧接上章,本章主要是介绍和K-Means算法思想不同而的其他聚类思想形成的聚类算法。 k-means算法却是一种方便好用的聚类算法,但是始终有K值选择...

    DC童生
  • 软件评测师笔记(十一)—— 可靠性测试相关

    小菠萝测试笔记
  • Android开发(4) 闪屏的实现

    闪屏呢,就是SplashScreen,也可以说是启动画面,就是启动的时候,闪(展示)出一个页面,它持续数秒后,自动关闭。

    zhangyunfeiVir
  • 数据标签太长了,怎么办……

    今天给大家讲解在图表中长数据标签的特殊处理方法! ▽ 如果你的图表要求必须添加数据标签的话 最大的困惑就是对于哪些特别长的数据标签 加上之后图表是这样的 ? 看...

    数据小磨坊
  • Vuex-Mutation 原

    更改 Vuex 的 store 中的状态的唯一方法是提交 mutation。Vuex 中的 mutation 非常类似于事件:每个 mutation 都有一个字...

    tianyawhl

扫码关注云+社区

领取腾讯云代金券