【论文阅读笔记】Ristretto：HardwareOrientedApproximationofConvolutionalNeuralNetworks

概念
MAC&＃xff1a;multiplication-accumulation operations

2. Convolutional Neural Networks

2.2.1 Normalization layers
  正则化层(LRN、BN) 需要计算出非常多的中间数(不是参数)。以AlexNet为例&＃xff0c;LRN层的中间数可以达到2¹⁴ &＃xff0c;比任意层的中间数都有多。因为这个原因&＃xff0c;这篇文章假设LRN和BN层用float point计算&＃xff0c;而我们致力于其它层的近似。【本文只集中于近似fc层和conv层】

2.4 Computational Complexity and Memory Requirements

  深度CNN的复杂性可以分为两部分&＃xff1a;

1. 卷积层是计算密集型层&＃xff0c;包含超过90&＃xff05;的算术运算&＃xff1b;
2. 全连接层是资源密集处&＃xff0c;包含超过$90$的参数。全连接层是资源密集处&＃xff0c;包含超过$90$的参数。

2.6 Neural Networks With Limited Numerical Precision

  Most deep learning frameworks use 32-bit or 64-bit floating point for CNN training and inference.(This paper is to describe the process of quantizing a full precision network to limited precision numbers).

2.6.1 Quantization

  如上图所示&＃xff0c;为了简化在硬件上的模拟过程&＃xff0c;我们的框架同时量化layer inputs和weights&＃xff0c;加法计算使用32-bits的floating point进行计算。加法器在大小和功率上都要比乘法器小。

2.6.2 Rounding Schemes

Round nearest even

round(x)&＃61;{⌊x⌋,if⌊x⌋≤x≤x&＃43;ϵ2⌊x⌋&＃43;ϵ,if⌊x⌋&＃43;ϵ2round(x)&＃61;{⌊x⌋,⌊x⌋&＃43;ϵ,​if ⌊x⌋≤x≤x&＃43;2ϵ​if ⌊x⌋&＃43;2ϵ​<x≤x&＃43;ϵ​

  Denoting $ϵ$ as the quantization step size and $\lfloor x\rfloor$ as the largest quantization value less or equal to x.
  As round-nearest-even is deterministic, we chose this rounding scheme for inference

Round stochastic

round(x)&＃61;{⌊x⌋,w.p.1−x−⌊x⌋ϵ⌊x⌋&＃43;ϵ,w.p.x−⌊x⌋ϵround(x) &＃61; \begin{cases} \lfloor x \rfloor, & w.p. \ 1-\frac{x-\lfloor x \rfloor}{\epsilon} \\ \lfloor x \rfloor &＃43; \epsilon , & w.p. \ \frac{x-\lfloor x \rfloor}{\epsilon} \end{cases}round(x)&＃61;{⌊x⌋,⌊x⌋&＃43;ϵ,​w.p. 1−ϵx−⌊x⌋​w.p. ϵx−⌊x⌋​​
  随机舍入给量化过程增加了随机性&＃xff0c;在训练过程可以有一个平均的影响&＃xff08;即平均结果一般为0&＃xff09;。
  We chose to use this rounding scheme when quantizing network parameters during fine-tuning.

2.6.3 Optimization in Discrete Parameter Space

  在传统的64-bit浮点数训练上&＃xff0c;优化问题是在平滑的误差表面上进行。而对于量化网络&＃xff0c;误差表面就变成离散的了。
  有如下两种方式训练量化网络&＃xff1a;

1. 从头开始训练量化权重&＃xff08;即没有利用上pre-trained model的权重&＃xff09;
2. 在连续领域训练网络&＃xff0c;然后量化参数&＃xff0c;最后再微调到离散量化空间。

  本文更新权重的方式是第二种&＃xff1a;: full precision shadow weights. Small weight updates ∆w are applied to the full precision weights w, whereas the discrete weights w¹ are sampled from the full precision weights. &＃xff08;在9.3有更多的fine-tune细节而&＃xff09;

3. Related Work

3.1 Network Approximation

3.1.1 Fixed Point Approximation

  方法提出的出发点&＃xff1a;fixed-point计算比floating point计算需要更少的资源&＃xff0c;更快。
  所以有一些从fixed-point上工作的方法。比如&＃xff0c;在CIFAR-10上工作的16-bit网络&＃xff1b;与上一个相同网络架构的7-bit网络&＃xff1b;二元/三元网络等。
但这些方法只证明了fixed-point方案能在small Networks上工作良好&＃xff0c;但在大网络上效果有限&＃xff0c;比如AlexNet。

3.1.2 Network Pruning and Shared Weights

  方法提出的出发点&＃xff1a;在数据密集型应用的能量耗费上&＃xff0c;片外内存&＃xff08;Off-chip&＃xff09;的访问占据了很大一部分。
  所以&＃xff0c;有一个很重要步骤就是压缩网络的参数数量。Han et al.&＃xff08;2016b&＃xff09;解决了这个问题&＃xff0c;其方案分为三个步骤&＃xff1a;

1. 移除网络中不重要的连接&＃xff08;通过阈值判断&＃xff09;。移除后的稀疏网络经过re-trained后重复进行移除连接&＃xff1b;
2. 将剩下来的权重进行聚类&＃xff0c;从而共享参数 。这些共享的权重也经过re-train以发现optimal centroids&＃xff1b;
3. 采用零损失压缩方案(比如&＃xff0c;Huffman Coding) 压缩最后的权重.

4. Fixed Point Approximation

4.2 Fixed Point Format

  fixed point number format&＃xff1a;$[IL.FL]$&＃xff0c;其中$IL和FL$分别表示整数长度和分数长度。即bitwidth&＃61;IL&＃43;FLbit _{width} &＃61; IL &＃43; FLbitwidth​&＃61;IL&＃43;FL
  为了把 floating point 量化成 fixed point&＃xff0c;本文使用round-nearest。使用二进制补码数来表示数字&＃xff0c;所以最大的正数可以表示为&＃xff1a;Xmax&＃61;2IL−1−2−FLX_{max}&＃61;2^{IL-1}-2^{-FL}Xmax​&＃61;2IL−1−2−FL

注意&＃xff0c;以下的实验中&＃xff0c;所有截断的数字都是用共享的固定点格式&＃xff0c;即他们共享使用相同的整数和小数长度

4.3 Dynamic Range of Parameters and Layer Outputs

4.3.1 Dynamic Range in Small CNN

  如上图所示&＃xff0c;平均而言&＃xff0c;参数的大小是要小于layer output的。99%的训练好的网络的参数在 [20&＃xff0c;210][2^0&＃xff0c;2^{10}][20&＃xff0c;210]&＃xff1b;而对于全连接层&＃xff0c;$99\%$的 layer outputs 在 [2−4&＃xff0c;25][2^{-4}&＃xff0c;2^5][2−4&＃xff0c;25]。
  为了把 layer outputs 和网络参数都量化到 8-bit 的 fixed point&＃xff0c;有一部分的参数会饱和&＃xff08;即丢失更多的精度&＃xff0c;截断&＃xff09;。作者在$Q.4.4$的格式下得到了最高的量化结果&＃xff0c;这代表着&＃xff0c;相对而言&＃xff0c;大的layer output比小的参数要更重要&＃xff08;因为这里 activation 和 weight 都固定到一个格式&＃xff0c;其IL 和 FL都是固定的。对activation而言&＃xff0c;需要更大的IL&＃xff1b;对weight而言&＃xff0c;需要更大的FL。这二个结果&＃xff0c;代表了结果向IL偏向&＃xff09;。

4.3.1 Dynamic Range in Large CNN

  如上图所示&＃xff0c;像small networks一样&＃xff0c;参数的大小是要小于layer output的&＃xff0c;而且这两组数的平均值差距更大了。因为这个动态数值范围比 LeNet更大了&＃xff0c;所以需要更多的 bit 来完成 fixed point representations。结果显示&＃xff0c;效果最后的是 16-bit 的 fixed point&＃xff0c;格式为 Q9.7。可以看出&＃xff0c;有相当一部分的参数在这个格式下是饱和的&＃xff0c;这意味着小数的Bit长度不足。而只有很少的 layer output&＃xff08;$0.46\%$的卷积层output&＃xff09;是比这个表示范围大的&＃xff0c;而有$21.23\%$的参数是被截断到$0$的。
  这个图的分析结果&＃xff0c;和LeNet一样&＃xff0c;“大的 layer output 比小的参数更重要”。

  从上一章节可以看出&＃xff0c;如果 weight 和 layer output使用相同的 fixed point格式&＃xff0c;则其中一组数字就会饱和&＃xff0c;从而损失精度。所以&＃xff0c;本章节介绍了一种 dynamic fixed point&＃xff0c;其可以进一步的减小参数size&＃xff0c;同时保持高准确率。

5.1 Mixed Precision Fixed Point

  如上图所示&＃xff0c;activation 和 weights 分别用 m-bits 和 n-bits表示&＃xff0c;在进行了乘法运算后&＃xff0c;经过树形加法运算。在每层加法运算进行的同时&＃xff0c;用 &＃43;1 bit 的空间来存储&＃xff0c;以避免溢出。最后一层加法&＃xff0c;用$m\&＃43;n\&＃43;lg(x)$ bits存储&＃xff0c;其中&＃xff0c;x为乘法运算的个数。

5.2 Dynamic Fixed Point

  Dynamic Fixed Point是为了解决Fixed Point表达能力受限的问题&＃xff0c;Dynamic Fixed Point固定的是bit-width&＃xff0c;而FL由 value group决定&＃xff0c;对于每一层的每一个type的数值&＃xff0c;都有一个常数FL&＃xff08;即其IL和FL是确定的&＃xff09;。
  在Dynamic Fixed Point中&＃xff0c;每个数字都可以表达为如下形式&＃xff1a;(−1)s2−FL∑i&＃61;0B−22ixi(-1)^{s}2^{-FL}\sum_{i&＃61;0}^{B-2}2^ix_i(−1)s2−FLi&＃61;0∑B−2​2ixi​

Choice of Number Format
  在每一层的每一个Type的数值而言&＃xff0c;其Fixed Point的格式为&＃xff1a;IL&＃61;⌈lg2(max(x))&＃43;1⌉IL&＃61;\lceil lg_2(max(x))&＃43;1\rceilIL&＃61;⌈lg2​(max(x))&＃43;1⌉  即保证IL足够让所有的数都包括进来&＃xff0c;而不向上饱和。
注意&＃xff0c;这种计算 IL 的方法&＃xff0c;适用于 layer parameters&＃xff1b;对于 layer outputs&＃xff0c;用这个公式 减去 1 来表达 IL。

5.3 Result

  可以看出&＃xff0c;即使是已经压缩过的模型&＃xff0c;如 SqueezeNet 都能在 ImageNet 上以 8-bit 达到很好的结果。

  上图是没有经过 fine-tune的结果。

  对于硬件加速器来说&＃xff0c;Fixed Point Approximation 是耗时和耗能量最少的。但是&＃xff0c;当bit变小时&＃xff0c;Fixed Point也是表现最差的。&＃xff08;会向上饱和&＃xff09;
  对比minifloat和Fixed Point&＃xff0c;Dynamic Fixed Point是三种近似方案中最好的。动态固定点使其能覆盖很大的动态范围&＃xff08;动态固定点隐式存储&＃xff1a;IL&＃61;⌈lg2(max(x))&＃43;1⌉IL&＃61;\lceil lg_2(max(x))&＃43;1\rceilIL&＃61;⌈lg2​(max(x))&＃43;1⌉&＃xff09;。

9. Ristretto: An Approximation Framework for Deep CNNs

9.2 Quantization Flow

  Ristretto 将网络模型从 32-bit floating 量化到 fixed point&＃xff0c;有如上图的五个阶段&＃xff1a;

1. 统计、分析Weight信息&＃xff0c; 分配足够的bit给实数部分&＃xff1b;(大的数比较重要)
2. 前向传播成千上万的图片&＃xff0c;统计、分析Activation信息&＃xff0c;分配足够的bit给实数部分&＃xff1b;
3. 给每一种类型的array决定bit分配&＃xff0c;用二分查找法寻找最优的bit&＃xff1b;&＃xff08;应该是分别对conv weight、fc weight、layer output分别决定一个bit分配&＃xff0c;即所有的相同类型层共用一个格式&＃xff09;
4. 评估每种bit的分配带来的误差&＃xff1b;&＃xff08;在二分查找一个类型的最优bit时&＃xff0c;其余两种类型保留floating point形式&＃xff09;
5. 找到每个部分的最优bit后&＃xff0c;开始fine-tune

9.3 Fine-tuning

  Fine-Tuning步骤如上图所示&＃xff1a;
  注意&＃xff0c;activation在Fine-Tuning步骤不进行量化&＃xff1b;

1. 利用量化后的离散值 w′w&＃x27;w′ 进行前向传播计算activation/output&＃xff1b;
2. 利用量化后的离散值 w′w&＃x27;w′ 进行反向传播传播计算gradient&＃xff1b;
3. 将gradient应用在floating point的w上进行参数更新&＃xff08;防止更新的范围 △w不足step-size&＃xff09;

  在预测阶段&＃xff0c;activation才进行量化。

  在微调阶段&＃xff0c;为了充分利用per-trained的参数信息&＃xff0c;使用的学习率比上一次全精度训练迭代低一个数量级。

9.5 Ristretto From a User Perspective