了解更多开源请访问：51CTO开源基础软件社区https://ost.51cto.com[Whatto本期看】ndzip应用场景ndzip相关算法残差编码重现SIMD【技术DNA】【智能场景】*********************************************************************************************************************************************************************************************************************************************************************************************************************************************************场景自驾/AR语音信号流视频GPU渲染科学、云计算内存缩减科学应用医学图像数据库服务器人工智能图像文本传输GAN媒体压缩图像压缩文件同步数据库系统技术点云压缩稀疏快四ier变换有损视频压缩网格压缩压缩算法框架动态选择无损压缩分层数据压缩医学图像压缩无损通用压缩人工智能图像压缩短字符串压缩GAN压缩在线多粒度蒸馏图像压缩文件传输压缩快速随机访问字符串压缩开源ProjectDraco/基于深度学习算法/PCL/OctNetSFFTAV1/H.266编码/H.266解码/VP9MeshOpt/Draco战神LZ4HCompressDICOMBrotliRAISRAIMCSOMGDOpenJPEGrsyncFSSTNDZIP——一种用于科学数据的高吞吐量并行无损压缩器概述场景应用分布式计算和高-在机器学习、大数据学习和高级建模和仿真等新兴技术中使用性能计算。在航空航天、制造、金融、医疗等诸多领域也发挥着非常重要的作用。ndzip是一种新的高吞吐量无损压缩算法，专为浮点数据的n维网格设计，有效解决了HPC互联带宽的限制因素。本文介绍了一种新的压缩算法-ndzip，它基于一个众所周知的预测器的快速、并行整数近似，并结合了一种硬件友好的块细分方案；ndzip的高性能多级并行实现，利用SIMD和线程级并行；对大量具有代表性的HPC数据进行深入的性能评估，并与最先进的专用浮点压缩器和通用压缩方案进行比较。技术背景相关算法FPZIPFPZIP使用洛伦兹预测器来利用标量n维网格中点的直接邻域的平滑度，并使用距离编码器压缩小残差。该方案具有较高的压缩效率，尤其是对于单精度值。FPCFPC使用一对基于哈希表的值预测器来压缩非结构化双精度数据流。它提供了一个可调参数，利用压缩效率来提高速度。pFPC的线程并行变体允许通过按块处理输入数据来进一步确定压缩吞吐量的优先级。SPDPSPDP结合一维投影和LZ77变体来压缩单精度和双精度数据，而无需对任何一种格式进行专门处理。MPCMPC是GPU的快速压缩方案。将简单的1D值预测器与位重组方案相结合可以很好地映射到目标硬件上残差中的去空位。APE、ACEAPE和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位。其余部分将从第一个非零字节开始逐字输出。这种方法是无状态的，并且在不可压缩的情况下具有可接受的1/16开销，但由于较低的粒度而导致浪费比特。MPC将剩余的流分成32个单值（或64个双值）的块，发出32（64）个最高有效位，然后是32（64）个第二高有效位，依此类推。零字从输出流中移除，并在每个块上替换为32或64位掩码，对所有非零字位置进行编码。该方法的开销非常低，仅为不可压缩情况下的1/32（1/64），由于字符粒度寻址，在GPU上高效实现，但需要块中的所有残差只能通过相似的位宽来实现.SPDP以类似于MPC的重组策略开始，但SPDP是字节级别的重组策略。SPDP然后使用字节粒度整数减法，并使用lz77系列编码器对结果流进行编码。这消除了除前导零之外的重复模式，并使SPDP也能够处理非浮点数据。算法分析ndzip的算法主要分为块细分、整数洛伦兹变换和残差编码三个部分。大体流程：下图展示了ndzip压缩流水线的所有步骤，首先它将输入数据分成固定大小的超立方体，使用多维变换对块内的数据进行去相关，使其具有更短的位表示残差。然后通过位矩阵变换消除公共零位来压缩剩余的流。压缩块存储在标头旁边，标头显示压缩块在输出流中的位置。ChunkSubdivisionndzip不是一次处理输入数据的整个n维网格，而是将其细分为独立压缩然后顺序传输的小超立方体。由于该算法需要多次遍历数据，因此它可以更好地利用处理器缓存，但代价是去相关效率略有下降。块之间存在依赖关系，我们想要去除块之间的所有依赖关系，这可以通过追加额外的数据来实现。这里作者选择了4096个元素，那么超立方体的大小可以表示为40961、642或163。对于单精度，这相当于16KB的内存；对于双精度，这相当于32KB的内存。预先确定块大小可以在后续步骤中生成高度优化的机器代码。当网格范围不是块大小的倍数时，边框元素将不压缩地附加到输出。IntegerLorentztransformFloating-pointLorenzoPredictor(Floating-pointLorenzoPredictor)对多维数据预测非常有效，但是单个位模式的残差计算需要解码器从已经解码的邻居中重建每个预测，从而引入依赖关系限制并行计算。因此，作者采用了整数洛伦佐变换来解决这个问题。整数洛伦兹变换是一种多通道运算，可直接计算整数域中洛伦兹预测残差的近似值。下图说明了这个过程。残差编码关于残差编码，ndzip使用与MPC相同的残差编码方案，使其在当前CPU上高效。大致过程是：残差用二进制补码表示，根据残差的符号判断补码的第一位是1还是0，然后对两者进行消零编码。残差首先转换为符号幅度表示，只要残差为负，就翻转除第一位以外的所有位。然后将残差流分成32个单精度或64个双精度值，对每个块进行32x32（64x64）位矩阵变换，将相同位置的位分组为词，剔除0个可以剔除的词输出在每个块前添加一个32位（64位）标头，将非零字的位置编码为位图。使用教程上面的原理有点秃头，下面讲解如何快速上手ndzip。点击输入ndzip地址，将项目git到本地。环境搭建环境要求运行ndzip需要以下环境，Catch2可以根据自己的需要选择是否安装。CMake>=3.15Clang>=10.0.0Linux(我这里用的是Ubuntu20)Boost>=1.66Catch2>=2.13.3(optional,forunittestingandmicrobenchmarking)CMakeInstallCMake在Ubuntu软件源中，安装非常简单,只需执行以下命令：sudoaptinstallcmakeversioncheck(CMake>=3.1.5):cmake--version查看CMake版本是否大于3.1.5。Clang安装Ubuntu软件源中也存在Clang，步骤与CMake类似，命令如下：sudoaptinstallclangversioncheck(Clang>=10.0.0):clang--version可以看到Clang版本是10.0.0，符合要求Boost安装Ubuntu软件源中也存在Boostr，命令如下：```undefi`nedsudoapt-getinstalllibboost-all-dev-versioncheck(Boost>=1.66):```undefineddpkg-S/usr/include/boost/version.hppCatch2添加Catch2需要在github上下载编译。命令如下：gitclonehttps://github.com/catchorg/Catch2.gitcdCatch2cmake-Bbuild-H。-DBUILD_TESTING=OFFsudocmake--buildbuild/--targetinstall等待编译加入。BuildusingCUDA+NVCCBuildndzipusingcuda,installCUDAToolkit:sudoapt-keydel7fa2af80#删除旧的GPG密钥，如果你之前安装过，删除wgethttps://developer.download.nvidia.com/compute/cuda/repos/wsl-ubuntu/x86_64/cuda-wsl-ubuntu.pinsudomvcuda-wsl-ubuntu.pin/etc/apt/preferences.d/cuda-repository-pin-600wgethttps://developer.download.nvidia.com/compute/cuda/11.7.0/local_installers/cuda-repo-wsl-ubuntu-11-7-local_11.7.0-1_amd64.debsudodpkg-icuda-repo-wsl-ubuntu-11-7-local_11.7.0-1_amd64.debsudoapt-getupdatesudoapt-get-yinstallcuda使用CUDA+NVCC搭建ndzip（我用SYCL搭建ndzip，没跑出来...）cmake-Bbuild-DCMAKE_CUDA_ARCHITECTURES=75-DCMAKE_BUILD_TYPE=Release-DCMAKE_CXX_FLAGS="-march=native"cmake--buildbuild-jcompletebuildtesttestcommandtestndzipcompressionevaluation解耦多维数据ndzip-gpu在通过transformation解耦多维数据时实现了高资源利用率。提出了一种用于垂直位打包的新颖、高效的扭曲率协作原语，提供高吞吐量数据缩减和扩展步骤，为检查数据提供最佳平均压缩率，同时在双精度情况下表现良好-off在数据缩减和吞吐量之间保持。将数据集的压缩率定义为压缩大小除以未压缩大小（以字节为单位），比率越低表示压缩越强。在需要汇总比率的情况下，返回数据集压缩比率的未加权算术平均值。SIMDSIMD（SingleInstructionMultipleData），单指令多数据流，可以复制多个操作数，打包到一组大寄存器的指令集中。ndzip专为在支持SIMD的现代多核处理器上高效实施而量身定制，能够以接近主内存带宽的速度压缩和解压缩数据，显着优于现有方案。通过测量从系统内存到系统内存压缩和解压缩的时钟时间来评估性能。第三方实现允许在必要时进行内存操作。以每秒未压缩的字节数返回吞吐量，转换为压缩输入和解压缩输出带宽。对每个算法和数据集对重复测量，直到总运行时间超过一秒。在每次迭代之前，输入数据都会从CPU缓存中移除。可以通过使用等效的一维转换来转换高维数据集来衡量利用多维的好处。实验新颖的整数洛伦佐变换(ILT)的有效性为了估计新颖的整数洛伦佐变换(ILT)的有效性，我们用其他预测方法替换了我们实现中的变换步骤，并通过变换高维来比较生成的压缩比使用等效的一维变换缩放数据集。该图显示了具有相同维度的所有数据集的平均压缩率，相对于在各自维度中观察到的最差压缩率进行了缩放。因为这个维度的压缩比相对最差（越小越好），所以对于一维数据集，所有方案都差不多。总体而言，FLP是最好和最差的选择是两个一维预测器，表明基于Lorenzo的组件从更高的维度中受益匪浅，余数运算的选择对于逼近FLP的相关特征至关重要。测试数据的算术平均未压缩吞吐量比较了所检查的压缩器实现的吞吐量和压缩率。按照设计，并非所有算法都可以同时处理单精度值和双精度值。一些算法有一个或多个可调参数表示为连续的行，而ndzip没有可调行为。通用算法可以对浮点数据实现高压缩率，但代价是大量的计算资源。例如，LZMA在双精度值上实现了最高的压缩率，可与最强的单精度压缩器fpzip相媲美，同时压缩我们最大的数据集的成本更高。LZ4实现了比审查过的任何其他单线程算法更高的压缩和解压缩吞吐量，同时还提供了最差的数据缩减。Zstandard提供了一个很好的权衡，在单精度数据上主导Deflate和专门的SPDP。大多数专用算法都能够至少在一个维度上胜过通用方案。而fpzip是最强大的单精度压缩器，只是以中等吞吐量为代价，但在解压缩方面失去了吞吐量比较。所以ndzip是最快的专用压缩器和解压缩器，具有显着的优势（“st”）。对于双精度数据集，稍微差一点。我们的压缩器提供的压缩率低于一些较慢的算法，但在吞吐量方面明显优于其唯一的竞争对手LZ4。结论通过设计一种考虑目标体系结构特性的专用压缩算法，可以实现出色的资源利用以及压缩比和吞吐量之间极具竞争力的折衷。基于我们新颖的小型超立方体数据，利用行整数洛伦佐变换（IntegerLorenzoTransform）和硬件友好的残差编码方案，ndzip压缩器利用SIMD和线程并行性实现超过10GB/s的压缩和解压缩速度，显着减少数据量。了解更多开源信息，请访问：51CTO开源基础软件社区https://ost.51cto.com。
