DRAC：一种基于delta循环神经网络的面向边缘计算的算术编码算法

摘要

本文提出了一种基于德尔塔循环神经网络的算术编码算法DRAC，适用于边缘计算设备。我们的算法在Xilinx Zynq 7000 Soc开发板上实现。我们使用四个数据集对DRAC进行评估，并与最先进的压缩器DeepZip进行比较。实验结果表明，DRAC优于DeepZip，实现了5倍的加速比和20倍的功耗节省。

关键词 算术编码 · 德尔塔循环神经网络 · 边缘计算

引言

由于无处不在的移动电话、物联网（IoT）设备和无线传感器网络，近年来它们收集的数据量和数量呈指数级增长。大数据时代给数据处理和存储带来了诸多挑战，核心问题是如何有效压缩多种类型的数据，e.g., 文本、图像、视频、基因组数据以及3D虚拟现实数据。本文仅考虑无损数据压缩，即重构后的消息与原始消息完全相同。根据香农理论，无损压缩可达到的最小压缩率是信息熵。

在无损压缩范式下，已有许多算法[1]被提出，e.g., 霍夫曼编码和LZ77/78。而算术编码（AC）[2]是当前压缩率方面最先进的熵编码算法。

AC编解码器由两部分组成：一个概率估计器，用于估计每个符号的概率；一个算术编码模型，其中编码器根据符号的累积概率将输入符号序列反复映射到单位区间内的子区间[0,1；解码器则利用代码（位于区间[0,1之间的实数）并基于符号的累积概率输出重建的符号序列。精确的概率估计器是AC编解码器的关键。

近年来，随着深度学习的巨大成功，适用于建模时序动态行为的循环神经网络（RNN）也被引入到与AC相关的算法设计中。[3]结合字符级预测RNN与统计编码技术用于文本压缩。[4]使用RNN作为上下文混合器来融合多个压缩器的意见，并实现了更好的压缩性能。CMIX[5]通过采用长短期记忆（LSTM）上下文混合器来混合总共2,122个独立模型，进一步提升了性能。最近，[4][6]提出了DeepZip，该方法将RNN预测器与算术编码器相结合，无损地压缩多种文本和基因组数据集。DeepZip在真实和合成数据集上的表现优于Gzip。

上述所有算法都应在台式计算机上运行，因此未考虑功耗和内存消耗。近几十年来，物联网的快速发展为计算机科学和通信领域带来了新的挑战。当数十亿个物联网设备相互连接并通信时，数据必须以分布式方式进行处理，这被称为边缘计算范式[7]。边缘计算在互联网边缘、靠近移动设备、传感器和终端用户的位置进行数据处理与分析。这项新技术能够为物联网提供可扩展性和隐私策略执行能力，为移动计算提供高度响应的云服务，并具备缓解瞬时云中断的能力。

当前的边缘计算设备，e.g., NVIDIA Jetson Nano, Google EDGE TPU, Intel Neural Compute Stick 2, 和树莓派，可以为深度神经网络模型提供低延迟、低功耗和有限内存平台。

本文解决的主要问题是，如何在功耗有限且计算复杂度较低的边缘计算平台上有效进行无损数据压缩。由于算术编码（AC）相比其他算法能够实现最佳的压缩率，我们选择AC作为编解码器。受2020,[8] proposed EdgeDRNN: adelta RNN accelerator for edge inference这一工作的启发，我们提出了 DRAC：一种基于delta RNN算法、运行于边缘计算设备上的算术编码模型。我们的主要贡献可总结如下：

• 我们介绍了DRAC：一种基于Delta RNN的用于边缘计算设备的算术编码编解码器。据我们所知，这种灵活、低成本、低延迟且节能的压缩器由我们首次提出。
• 我们在Xilinx Zynq 7000 Soc开发板上实现了DRAC。我们使用该平台来证明我们的DRAC模型适用于边缘设备。
• OurDRAC在实验中优于Deepzip。我们使用文本基因组数据集来评估DRAC、DeepZip和Gzip。实验结果表明，DRAC在压缩率、功耗和运行时间方面均优于Deepzip和Gip。

本文其余部分安排如下：“模型描述”描述了 DRAC的模型。Delta RNN在“Delta循环神经网络”中介绍，实验结果在“实验结果”中展示。“结论”对本文进行总结。

模型描述

我们的DRAC包含两个模块：算术编码算法和概率预测器。设Y={y0, y1,…, yN−1}为数据序列。概率预测器包含一个Delta RNN模型，该模型在Y上多轮训练。训练完成后，编码器和解码器均知晓训练得到的模型权重。当观察到前面的J个符号时（在本模型中J设为1），概率P(yi|yi−1,…,yi−J)由Delta RNN估计，并输入至算术编码编码器以执行编码过程，直到输出最终的代码。对于初始的J个符号，采用均匀分布作为先验。此过程如图1a所示。解码过程与编码过程对称。解码器以代码作为输入，并利用预测器提供的概率反复输出重建后的符号，如图1b所示。我们将在“算术编码算法”部分描述算术编码算法模块，在“概率预测器”部分描述概率预测模块。

算术编码算法

我们给出算术编码的编码过程如下。设 X={x0, x1,…, xM−1}为离散信源的符号集，P={p(x0),p(x1),…,p(xM−1)}为各符号的概率，该概率将由“概率预测器”进行预测。累积概率C={c(x0), c(x1),…,c(xM−1)}定义为

$$
c(xi)= \sum_{k=0}^{i} P(xk),
$$

其中 c(x0) ≡ 0 和 c(M) ≡ 1。算术编码编码器将输入序列中的每个符号递归地映射到当前区间划分出的子区间中。设 Y={y0, y1,…, yN−1} 为输入序列，I0=[L0,H0) 为初始区间。新的子区间 Ij=[Lj,Hj) 的计算方法如下

$$
H_j = L_{j-1}+(H_{j-1} - L_{j-1}) \times c(y_{j+1})
$$

$$
L_j = L_{j-1}+(H_{j-1} - L_{j-1}) \times c(y_j),
$$

其中 c(yj+ 1) 是符号集中 yj 后续符号的累积概率。一旦完成编码过程结束时，最终区间内的任意实数D均可被选为代码。

在解码过程中，设Y={˜y0,˜y1,…,˜yN−1}为AC解码器的输出序列。解码器递归地执行以下步骤：

(1) 根据当前代码ai从C确定符号，并输出˜yj=xi， 即

$$
˜yj={xi: c(xi) \leq Dj \leq c(xi+ 1)},j \in{0, 1,…, N −1}.
$$

(2) 通过更新Dj

$$
D_{j+1}= \frac{D_j - c(xi)}{p(xi)}.
$$

一旦解码过程成功结束，即可获得输出序列。

概率预测器

我们的概率预测器是一个Delta循环神经网络。其架构如图2所示。对于一个符号yi，将其前面的J个符号yi−J, yi−J+1,…, yi−1输入到一个双向 Delta门控循环单元（Delta GRU）中，该单元将在“Delta循环神经网络”部分介绍。在Delta GRU单元的末尾，对从Delta GRU单元获得的隐藏状态应用Softmax层和全连接（FC）层。最后得到概率p(yi)。Softmax层定义为

$$
softmax(z) i= p_i= \frac{e^{z_i}}{\sum {j=1}^{|X|} e^{z_j}},
$$

其中 X 是符号的符号集， | · | 是基数。对于输入 X，全连接层定义为

$$
F= \sigma(X W^T+ B),
$$

其中W是权重矩阵，B是偏置， σ(x)是激活函数。

Delta循环神经网络

门控循环单元（GRU）是一类门控RNN，在自然语言处理领域非常流行。对于RNN，每个GRU单元如图3a所示。设 R为实数集，X={x0,x1,…,xi,xN−1}为长度为N的输入序列。对于具有H个神经元、一维输入 xi和输出hi的GRU单元，其更新方程定义为

$$
r_i= \sigma(W_{xr}x_i+ W_{hr}h_{i−1}+ b_r)
$$

$$
u_i= \sigma(W_{xu}x_i+ W_{hu}h_{i−1}+ b_u)
$$

$$
c_i= \tanh(W_{xc}x_i+ r_i \odot (W_{hc}h_{i−1}+ b_c))
$$

$$
h_i=(1 − u_i)\odot c_i+ u_i \odot h_{i−1},
$$

其中r,u, c ∈ R^H分别为重置门、更新门和单元状态。Wx ∈ R^H、Wh ∈ R^{H×H}为权重矩阵，b ∈ R^H为偏置向量。 σ(x)为激活函数，⊙为向量的逐元素乘法。

为了降低GRU的计算复杂度，[9]提出了Delta循环网络。后来，[8]在边缘设备上应用了Delta‐GRU。受他们思路的启发，我们也在模型中应用了Delta GRU。我们定义以下变量：

$$
\hat{x} i=
\begin{cases}
x_i, & |x_i − \hat{x} {i−1}| \geq \eta_x \
\hat{x} {i−1}, & |x_i − \hat{x} {i−1}| < \eta_x
\end{cases}
$$

$$
\hat{h} i=
\begin{cases}
h_i, & |h_i − \hat{h} {i−1}| \geq \eta_h \
\hat{h} {i−1}, & |h_i − \hat{h} {i−1}| < \eta_h
\end{cases}
$$

$$
\delta x_i=
\begin{cases}
x_i − \hat{x} {i−1}, & |x_i − \hat{x} {i−1}| \geq \eta_x \
0, & |x_i − \hat{x}_{i−1}| < \eta_x
\end{cases}
$$

$$
\delta h_i=
\begin{cases}
h_i − \hat{h} {i−1}, & |h_i − \hat{h} {i−1}| \geq \eta_h \
0, & |h_i − \hat{h}_{i−1}| < \eta_h
\end{cases}
$$

其中， $\hat{x}_i$表示第i个时间步的输入状态记忆，$\hat{h}_i$表示第i个时间步的隐藏状态记忆， $\delta x_i$为增量输入状态， $\delta h_i$为增量隐藏状态。 $\eta_x$和 $\eta_h$分别为相应的阈值。在初始时刻，i.e.,i= 1时， $\hat{x}_0$、$h_0$,以及 $\hat{h}_0$均被初始化为零。Delta GRU 的更新方程定义如下：

$$
M_{r,i}= W_{xr} \delta x_i+ W_{hr} \delta h_{i−1}+ M_{r,i−1}
$$

$$
M_{u,i}= W_{xu} \delta x_i+ W_{hu} \delta h_{i−1}+ M_{u,i−1}
$$

$$
M_{xc,i}= W_{xc} \delta x_i+ M_{xc,i−1}
$$

$$
M_{hc,i}= W_{hc} \delta h_{i−1}+ M_{hc,i−1}
$$

$$
r_i= \sigma(M_{r,i})
$$

$$
u_i= \sigma(M_{u,i})
$$

$$
c_i= \tanh(M_{xc,i}+ r_i \odot M_{hc,i})
$$

$$
h_i=(1 − u_i)\odot c_i+ u_i \odot h_{i−1},
$$

其中Mi=0= br, Mu,i=0= bu, Mxc,i=0= bc, Mhc,i=0=0 为增量记忆向量，且M ∈ R^H。

与GRU操作相比，Delta GRU将剪枝权重并移除导致稀疏权重矩阵的不重要神经元连接。稀疏矩阵可被编码为稀疏矩阵格式。通过仅对非零权重执行乘加（ MAC）操作，可以加速稀疏矩阵‐向量乘法。通过跳过增量向量中的零元素，可以跳过整个矩阵‐向量MAC操作列。在模型经过适当训练后，实验表明，在增量网络中，操作数量可减少5到100倍[8,9]。

实验结果

数据集

在我们的实验中使用了四个数据集，如表1所示。其中，webster[10]和enwiki9[11]是从网络资源下载的文本数据，其符号来自ASCII，符号集大小分别为96和206。而h.chr1[12]和c.e.genome[13]是基因组数据，其符号为{A、C、G、T}，字母表大小为4。这四个数据集均来自真实数据。此外，该模型还在合成数据集上进行了评估，这些合成数据集是由已知熵的合成源生成的人工数据。由于论文篇幅有限，我们将在未来研究中对合成数据集进行实验。

训练过程

为了训练基于 Delta RNN 的模型，我们采用分类交叉熵作为损失函数，其定义为

$$
L= \frac{1}{N} \sum_{n=1}^{N} \sum_{m=1}^{M} p_m \log_2 \frac{1}{\hat{p}_m},
$$

其中 N为序列长度，M为字母表大小，pm为独热编码的真实标签，而 $\hat{p}_m$为预测概率。使用Adam [14]优化器最小化分类交叉熵L。序列被划分为$\left\lceil \frac{N}{K+1} \right\rceil$段，每段的长度为K+1。在每个段中，令前K个符号作为输入，最后一个符号作为输出。我们将K设为64，批量大小设为1024。在优化过程中，最大训练轮数为10，学习率为3e−4。当在10轮之前无进一步改进时，训练终止。在每一轮训练中，如果L相较于之前的最小值有所下降，则模型被更新。该训练过程与[6,8]中介绍的方法类似。

实现

DRAC中的算术编码模块借鉴了一个开源代码：算术编码库 [15]，该库由Python实现。我们仅对其进行了少量修改，以使其能够与预测模块集成。Delta RNN模块使用 PyTorch 1.2.0框架实现。训练过程在一块NVIDIA TITAN V GPU上进行，使用了CUDA 10.0和cuDNN 7.6。

我们的边缘设备是一块基于定制基板的Xilinx Zynq‐7000 SoC，包含双核ARM Cortex‐A9 CPU、Kintex‐7 XC7Z100 FPGA和1 GB DDR3 SDRAM。其操作系统是Xilinx提供的名为PetaLinux的嵌入式Linux操作系统。在DRAC训练完成后，我们使用Python脚本将Python网络模块转换为C++头文件，其中包含Delta RNN的网络参数。该应用程序使用标准交叉编译器进行编译，生成的镜像被下载到开发板的闪存中。

delta阈值

与RNN相比，Delta RNN的主要改进在于引入了 delta阈值 ηx和 ηh。在本节中，我们将通过实验来研究 η(η= ηx= ηh)的影响。Delta RNN使用不同delta阈值 η的数据集进行训练，其范围从0x00到0x80（η采用16位Q8.8格式，Q8.8格式中的0x80对应十进制数0.5）。通过计算预测概率误差来评估准确率。预测概率准确率作为delta阈值的函数如图4所示。

如图4所示。我们发现，在 η较小时，准确率几乎保持在100%。当 η大于0x80时，准确率显著下降。

我们从 webster中取一个长度为10M的样本数据，用于测量预测的计算时间。图4显示，随着 η的增加，计算时间逐渐减少。这是因为较大的delta阈值将允许跳过许多MAC操作，而减少的操作会导致功耗和计算时间的降低。我们在准确率和计算时间之间进行权衡，在后续实验中选择 η= 0x80作为最优值。

性能比较

为了研究我们模型的性能，我们将DRAC与DeepZip在压缩率、运行时间和功耗方面进行了比较。

四个数据集（表1）在实验中被使用。我们选择了两个版本的DeepZip [6], i.e., Deepzip‐b，其神经网络由GRU的双向变体实现，以及Deepzip‐l，其神经网络由多个LSTM单元构成。之所以采用这种设置，是因为Deepzip‐b和Deepzip‐l是当前最先进的无损压缩器。所有DeepZip模型均在配备Intel i7‐6800K CPU和 NVIDIA TITAN V GPU的台式服务器上进行测试。

CPU功耗通过Stress Terminal UI监控工具[16]测量，GPU功耗则使用nvidia‐smi工具进行测量。DRAC模型在Zynq‐7000开发板上运行，总功耗通过墙插式功率计测量。同时测量了运行时间。所有实验结果如表2所示，其中最佳结果以粗体标出。

实验结果表明，在压缩大小方面，DRAC几乎达到了与DeepZip相同的性能，但在运行时间和功耗方面与DeepZip相比，DRAC性能大幅提升。DRAC的加速比接近DeepZip的5倍，功耗节省达到20倍。这一改进得益于Delta RNN的引入。实验表明，DRAC适用于边缘计算框架。

表1 数据集
Name
—
webster
enwiki9
h.chr1
c.e.genome

表2 实验结果
模型
Deepzip‐b
Deepzip‐l
DRAC

结论

我们提出了DRAC：一种基于DeltaRNN的用于无损压缩的AC编解码器，并在Zynq‐7000 SoC板上实现了它。该设置使其适用于边缘计算环境。我们在四个数据集上将DRAC与DeepZip进行了比较，结果表明DRAC优于DeepZip。

本工作存在两个主要局限：delta阈值 η的选择采用启发式方法，且数据集不够丰富。在未来研究中，我们希望提出一种引导搜索算法，通过利用准确率与运行时间之间的动态权衡，快速收敛到最优 η。我们还将评估DRAC在更多真实和合成数据集上的表现。