ndzip，一个用于科学数据的高通量并行无损压缩器

概述

场景应用

分布式计算以及高性能计算在机器学习、大数据学习与高级建模与模拟等新兴技术上都有使用。在航天航空、制造业、金融、医疗等多个领域也有着非常重要的作用。

ndzip介绍

ndzip，是一种新的高吞吐量无损压缩算法，专门为浮点数据的n维网格而设计。

本文贡献

1. 本文提出了一种新的压缩算法-ndzip，它基于一个快速，且并行整数近似的的知名预测器，并结合了对硬件友好的块细分方案；
2. ndzip 的高性能多级并行实现，利用 SIMD 和线程级并行；
3. 对大量具有代表性的 HPC 数据进行深入的性能评估，并与最新水平的专业浮点压缩器和通用压缩方案进行比较。

技术背景

相关算法

FPZIP

FPZIP 使用洛伦兹预测器利用标量 n 维网格内点的直接邻域的平滑性，使用范围编码器压缩小的残值。该方案具有很高的压缩效率，特别是对于单精度值。

FPC

FPC 使用一对基于哈希表的值预测器来压缩非结构化双精度数据流。它提供了一个可调参数，利用压缩效率提高速度。线程并行的 pFPC 变体允许通过以块的形式处理输入数据来进一步确定压缩吞吐量的优先级。

SPDP

SPDP 结合了一维预测和LZ77变体，可以压缩单精度和双精度数据，而不需要对任何一种格式进行专门处理。

MPC

MPC 是一种用于 GPU 的快速压缩方案。将一个简单的一维值预测器与一个位重组方案相结合，可以很好地映射到目标硬件的残差中去零位。

APE 和 ACE

APE 和 ACE 压缩器自适应地从多个值预测器中选择，将 n 维网格中的数据点与其已处理过的邻居解相关。残差使用一种变体的 Golomb 编码进行压缩。

数值预测

数值预测科学浮点数据中的单个数值通常在低阶尾数位表现出较高的熵，尾数也很少出现精确到重复，这降低了传统字典编码器的效率。相反，我们可以使用专门的方法对已经处理过的数据进行预测，只对残差进行编码。

• SPDP 和 MPC 使用简单的固定步长值预测器，通过存储 k 个值，并用最近编码的第 k 个值预测每个点。
• FPC 和 pFPC 使用一对基于哈希表的预测器来维护一个较大的内部状态，以利用值和值增量中的重复模式。
• fpzip 使用浮点洛伦兹预测器来估计 n 维空间中长度为 2 的超立方体的一个角的值。fpzip通过奇数条边可到达的所有其他角加起来，然后减去通过偶数条边可到达的角。当超立方体可用n - 1次隐式多项式表达时，预测精度是精确的。
• APE 和 ACE 扩展了fpzip预测器的思想，通过在每个维度上使用高维多项式，以更大的计算成本为代价提高了预测精度。

差分运算

在无损压缩环境中，浮点减法不适合用来计算预测残差。小幅度的浮点值通常不会以简短的、可压缩的位的形式出现，而且浮点数的有限精度使浮点减法成为一种非双射的运算。因此，所有研究的算法都明确地计算位表示的残差。

• FPC和pFPC 使用逐位异或差，而 SPDP和MPC 将操作数位重新解释为整数，并对整数减法的结果进行编码。
• APE和ACE 提供了两种变体。
• fpzip 也使用整数减法，但是它根据符号位对操作数进行反运算，以提高映射的连续性。

残差编码

精确的预测会产生具有许多相同前导位的小幅度残差，即异或运算符为零以及二进制补码的整数减法的冗余符号位。对这些前导位进行有效编码是大多数研究方案中所采用的数据简化机制。

• fpzip 使用一个范围编码器来压缩前导冗余位的数量，紧接着复制剩余位。距离编码器能够产生的接近最佳的位串使得其非常节省空间。然而，所需的位粒度寻址难的问题难以有效解决。
• APE 和 ACE 使用与fpzip类似的方法，但使用符号排序的 Golomb 代码来编码冗余位的数量。
• FPC 和 pFPC 通过计算双精度残差中前导零字节的数量，使用固定映射对运行长度和4 bit中的预测部分进行编码。剩余部分将从第一个非零字节开始逐字输出。这种方法是无状态的，在不可压缩的情况下有可接受的1/16开销，代价是由于粒度较低而浪费比特。
• MPC 将剩余流分成 32 个单精度（或 64 个双精度）值的块，发出 32（64）个最高有效位，然后是 32（64）个第二最高有效位，依此类推。零字将从输出流中删除，并在每个编码所有非零字位置的块上替换为32或64位掩码。这种方法在不可压缩的情况下有非常低的开销，仅仅为1/32（1/64），由于字符粒度寻址，该方法在 GPU 上得到了有效的实现，但需要块内所有的残差具有相似的位宽才能实现。
• SPDP 从一个类似于 MPC 的重组策略开始，但是SPDP是在字节级别上的重组策略。SPDP接着使用字节粒度整数减差运算，并使用 lz77 系列编码器对结果流进行编码。这可以消除除前导零之外的重复模式，并使 SPDP 也能处理非浮点数据。

算法分析

ndzip 的算法主要分为块细分、整数洛伦兹变换以及残差编码三个部分。

大体流程：下图展示了ndzip压缩管道的所有步骤，首先它将输入的数据划分为固定大小的超立方体，并使用多维变换在块内对数据进行去相关，从而使其具有更短位表示残差。然后通过位矩阵变换消除公共零位来压缩剩余流。压缩后的数据块存储在报头旁边，报头显示了输出流中压缩数据块的位置。

块细分

ndzip 不是一次性处理输入数据的整个 n 维网格，而是将其细分为独立压缩的小的超立方体，然后依次进行传输。

由于该算法需要多次传递数据，因此可以更好地使用处理器缓存，但会略微损失解相关的效率。块与块之间存在依赖，我们想要消除块之间的所有依赖关系，可以通过附加额外的数据来实现。

这里作者选择了4096个元素，则超立方体的大小可以表示为40961、642或163。对于单精度，这相当于16KB的内存；对于双精度，这相当于32KB的内存。预先确定块的大小能够在之后的步骤生成高度优化的机器码。

当网格范围不是块的大小的倍数时，边框元素将不被压缩地附加到输出中。

整数洛伦兹变换

浮点洛伦兹预测器（Floating-point Lorenzo Predictor） 对于多维数据的预测是非常高效的，但是单独位模式的残差计算需要解码器从已经解码的临近值重建每个预测，从而引入限制并行计算的依赖。

因此，作者使用了整数洛伦兹变换（ Integer Lorenzo Transform） 解决了这个问题。整数洛伦兹变换是一种直接计算整数域内的洛伦兹预测残差的近似的多道运算。下图便说明了这个过程。

残差编码

关于残差编码，ndzip使用了与 MPC 相同的残差编码方案，使其可以在现在的CPU上高效的实现。

大致流程如下：

1. 残差使用了二进制补码进行表示，根据残差的符号，确定了补码第一位是1还是0。之后通过0消去对两者进行编码。
2. 残差首先被转换成符号-数值（sign-magnitude）表示，只要残差为负，就对除了第一个比特外的所有比特进行翻转。

1. 然后将残差流分成32个单精度或者64个双精度的值，对每个块进行 32x32（64x64） 的位矩阵变换

1. 将来自相同位置的比特分组成单词，从输出中消去可以消去的0词

1. 在每个块前面加上一个32位（64位）的头，将非0字的位置编码为位图。

使用教程

上面的原理看的有点头秃，还是来讲讲如何快速上手ndzip吧！

点击进入 ndzip 的地址，git 下项目到本地。

环境搭建

环境需求

运行 ndzip 需要以下环境，Catch2 可根据自己是否需要来选择是否安装。

• CMake >= 3.15
• Clang >= 10.0.0
• Linux (我这里用的Ubuntu20)
• Boost >= 1.66
• Catch2 >= 2.13.3 (可选，用于单元测试和微基准测试)

CMake安装

CMake 在Ubuntu软件源中，安装非常简单，执行以下命令即可：

sudo apt install cmake

版本检查（CMake >= 3.1.5）：

cmake --version

看到 CMake 版本大于3.1.5即可。

Clang 安装

Clang 也存在 Ubuntu软件源中，步骤和CMake差不多，命令如下：

sudo apt install clang

版本检查（Clang >= 10.0.0）：

clang --version

可以看到 Clang 版本为 10.0.0,符合要求

Boost 安装

Boostr 也存在 Ubuntu软件源中，命令如下：

sudo apt-get install libboost-all-dev

版本检查（Boost >= 1.66）：

dpkg -S /usr/include/boost/version.hpp

Catch2 添加

Catch2需要去github上下载编译，命令如下：

git clone https://github.com/catchorg/Catch2.git
cd Catch2
cmake -Bbuild -H. -DBUILD_TESTING=OFF
sudo cmake --build build/ --target install

等待编译添加完即可。

构建

使用 CUDA + NVCC 构建 ndzip

使用 cuda，安装 CUDA Toolkit：

sudo apt-key del 7fa2af80 # 删除旧的GPG密钥，之前装过的要删掉

wget https://developer.download.nvidia.com/compute/cuda/repos/wsl-ubuntu/x86_64/cuda-wsl-ubuntu.pin
sudo mv cuda-wsl-ubuntu.pin /etc/apt/preferences.d/cuda-repository-pin-600
wget https://developer.download.nvidia.com/compute/cuda/11.7.0/local_installers/cuda-repo-wsl-ubuntu-11-7-local_11.7.0-1_amd64.deb
sudo dpkg -i cuda-repo-wsl-ubuntu-11-7-local_11.7.0-1_amd64.deb
sudo apt-get update
sudo apt-get -y install cuda

使用 CUDA + NVCC 构建 ndzip（自己使用SYCL构建ndzip没跑出来。。。）

cmake -B build -DCMAKE_CUDA_ARCHITECTURES=75 -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS="-march=native"
cmake --build build -j

完成构建

测试

测试可用

随便压缩个什么，压缩成功。