了解更多开源请访问：51CTO开源基础软件社区https://ost.51cto.com【技术】DNA】【智能场景】*****************************************************************************************************************************************************************************************************************************************************************************************************************************************************************************场景自动驾驶/AR语音信号流视频GPU渲染科学，云计算内存缩减科学应用医学图像数据库服务器人工智能图像文本传输GAN媒体压缩图像压缩文件同步数据库系统通用数据技术点云压缩稀疏快速傅里叶变换有损视频压缩网格压缩动态选择离子压缩算法框架无损压缩分层数据压缩医学图像压缩无损通用压缩人工智能图像压缩短字符串压缩GAN压缩在线多粒度蒸馏图像压缩文件传输压缩快速随机访问字符串压缩高吞吐量并行无损压缩开源项目Draco/基于深度学习算法/PCL/OctNetSFFTAV1/H.266编码/H.266解码/VP9MeshOpt/Draco战神LZ4HCompressDICOMBrotliRAISRAIMCSOMGDOpenJPEGrsyncFSSTndzip简介无损数据压缩是一种很有前途的软件方法，可以在不引入近似误差的情况下降低科学应用程序对加速器集群的带宽要求。合适的压缩器必须能够有效地压缩浮点数据，同时使系统互连饱和，以避免引入不必要的延迟。在通往百亿亿次级的道路上，能效正成为高性能计算(HPC)创新的主要驱动力。节点内并行性的快速增长，包括GPU作为通用加速器的出现，大大降低了计算密集型应用程序的能源成本。为了证明数据压缩在加速节点间通信方面的可行性，本文探讨了GPU压缩如何提供必要的性能。基于ndzip，我们提出了ndzip-gpu，这是一种用于ndzip的高效GPU并行化方案，一种先进的无损浮点压缩器。并行无损数据压缩的背景挑战由于可变编码器/解码器状态和可变长度输出流编码的必要性，传统的无损压缩器倾向于支持串行实现。通过为输入数据构建概率模型并将较短的表示分配给可能的输入，将较长的表示分配给不太可能的输入减少（例如霍夫曼编码），可变编码器/解码器状态通常在数据量方面是无损的。解码器必须知道编码器的概率模型才能反转此映射。由于模型通常既不是提前已知的，也不是整个数据流的静态模型，因此单通道压缩器显式交换它变得不可行。编码器和解码器都将根据先前观察到的未压缩符号构建并不断更新相同的模型。高度并行的压缩器必须能够打破这种依赖链，以避免由同步共享状态主导的运行时行为。具有大状态的压缩器（例如字典编码器）在精细细分其输入空间时效率会??大大降低。局部去相关方案在这方面更加稳健。压缩可变长度编码的分块数据流是一个输入并行问题，因为压缩的分块长度是事先不知道的。并行压缩器的线程必须同步以确定各个块在输出流中的位置。有两种基本方法可以避免围绕这种依赖性进行序列化：在快速暂存内存中的k个并行线程中压缩k个块，在屏障之后导出输出位置，最后让每个线程将写入提交到输出流。将整个流压缩到足够大的中间缓冲区中，使用前缀和计算所有块的输出位置，并使用单独的压缩步骤最终确定输出流。专用浮点压缩器浮点二进制表示具有比面向字节的通用压缩器假设的字长更大的字长。此外，来自实际应用程序的浮点数据具有许多相同重复值的位，很容易进行重复数据删除。因此，传统的字典编码器方法对这类数据并不是特别有效。来自物理模拟或传感器阵列的密集网格数据通常表现出低频成分，使得从邻近值进行局部预测变得可行。网格的维数越高，由于每个值的相邻单元格数量越多，预期的局部相关性就越高。因此，专门的浮点压缩器的构造通常由以下三个部分组成：预测器通过字典、哈希表或邻居值从先前编码的点估计数据。差分运算符以可逆方式计算值与其预测值之间的残差，例如使用XOR运算或整数差分。残差编码器使用有利于小幅度值的可变长度代码表示残差。算法通常旨在通过游程编码（RLE）或算术编码（Arithmeticcoding）等表示来消除前导零位。除了ndzip算法之外，还有几个著名的基于CPU的无损浮点压缩器。fpzip使用Lorenzo预测器来利用一维网格内点的直接邻域的平滑度，使用范围编码器压缩残差。该方案表现出很高的压缩效率，尤其是对于单精度值，但仅限于单线程操作。FPC使用一对基于哈希表的值预测器来压缩非结构化双精度数据流。线程并行pFPC变体允许通过按块处理输入数据来进一步确定压缩吞吐量的优先级。ZFP是一种固定速率有损压缩器，它使用频率变换对多维网格中的浮点值进行去相关。GPU上的数据压缩适用于浮点数据的GPU公开可用的无损数据压缩器很少。作者在文章中列举了几个：UniversalCompressor。nvCOMP3是用于NVIDIAGPU的无损数据压缩框架。它包括著名的LZ4压缩器的高吞吐量实现和非常适合整数数据的可配置级联压缩管道。cudppCompress是一种通用的面向字节的GPU压缩器。它并行化了著名的bzip2压缩器的三个阶段，与类似时代的硬件CPU实现相比实现了可测量的加速。相应的并行解压缩器未实现。在一些工作中，GPU已成功用作协处理器来加速Burrows-Wheeler变换。LZW和LZSS压缩器也存在并行实现，并且有用于GPU熵编码的快速霍夫曼和非对称数系统(ANS)编码器。专用浮点压缩器。MPC是一种GPU压缩方案，用于单精度或双精度浮点数据的非结构化多变量流。两步1D值预测与垂直位打包相结合，这是一种很好地映射到目标硬件的编码方案。GFC是用于非结构化双精度数据的超快GPU压缩器。来自1D预测器的残差通过运行长度编码前导零位进行压缩。与评估的所有其他压缩器不同，GFC会产生碎片化的压缩输出，这些输出在传输回主机时会被压缩。NDZIPndzip是用于单精度或双精度浮点数据的1D到3D网格的高级块压缩器。它使用整数洛伦佐变换来近似洛伦佐预测器，这是一种用于多维块的局部去相关的可分离就地操作。使用先前在MPC中发现的垂直位打包方案对残差进行编码，该方案消除了相邻残差位位置的零游程。通过完全在整数域中操作，该算法保证了压缩操作的可逆性和可移植性。与已建立的通用压缩器（如Deflate）和专用算法（如fpzip或FPC）相比，ndzip已被证明可以在CPU上提供出色的吞吐量，并且其实现利用了线程和SIMD并行性。而ndzip-gpu压缩器完全再现了ndzip的压缩格式。关于ndzip的更多信息，可以阅读之前发表的文章OpenHarmony吃论文俱乐部-数据高通量无损压缩方案，文中详细介绍了ndzip算法，并附有该算法的使用教程。在并行化方案的这一部分，我们描述了并行化方案ndzip-gpu如何在多达768个线程之间有效地分配转换和残差编码，同时将分支发散和序列化保持在最低限度。我们的目标是在设备上的全局内存缓冲区之间进行压缩和解压缩。压缩管道概述并行压缩的输出偏差问题可以通过完全设备同步或在每个块中启动多个内核以及通过中间全局暂存缓冲区进行往返来解决。ndzip-gpu采用第二种方法，期望全局障碍部分抵消计算量大的残差编码器中短路评估的好处。图1三级压缩流水线上图详述了三级压缩流程。核心1从全局加载一个未压缩的块到共享内存，将浮点值转换为其整数表示。然后，n维整数洛伦佐变换计算就地传递的n块数据中的残差。残差被分组为32个单精度值或64个双精度值的序列，并通过垂直位打包进行编码，从而产生一个标头和可变数量的非零列。分配一个全局暂存缓冲区，为不可压缩的情况提供足够的空间。索引空间被细分为块，每个块为所有标题字保留一个块，然后为每个位压缩列序列保留一个较小的块。暂存缓冲区中的所有块偏移量都是从输入网格的维度先验已知的。编码后，每个线程块将各自的块写入暂存内存，并将块长度写入单独的缓冲区。内核2在长度缓冲区上计算并行前缀和，以获得紧凑输出流中所有块的偏移量。最后，使用偏移缓冲区，内核3从零内存加载块并将它们存储在输出流中的最终位置。每个块中第一个块的输出偏移量收集在流头中。图2中可视化的流布局有意将固定大小的元信息（块偏移量和块标头）与可变长度压缩列编码分开。这允许解码器并行计算压缩列的绝对偏移量，而无需同步或多次通过流。Figure2CompressedstreamlayoutDecompressionpipelineoverview由于可以从流头中检索压缩缓冲区中每个块的偏移量，因此解压是并行输出的，不需要块之间的同步。单个内核启动足以解码整个流或块的任意子集。图3详细描述了单个块的解压过程。内核首先从第一个块中加载所有的头，计算设置的位以获得每个序列的非零列的数量，最后执行前缀求和以在共享内存中生成偏移表。然后可以并行反转所有块的位打包，扩展到剩余的共享内存块。然后通过逆整数Lorenzo变换恢复未压缩值的整数表示。最后，通过反转整数映射恢复浮点位模式，并将块写入全局输出网格缓冲区。图3.单级解压流水线共享内存布局必须仔细选择多通道转换步骤的中间结果的共享内存布局，以避免所有必需的访问模式之间发生库冲突。硬件会将冲突的加载或存储拆分为尽可能多的无冲突访问，这可以显着增加共享内存访问绑定的函数的运行时间，例如整数Lorenzo变换。这个问题没有明显的通用解决方案。相反，索引空间转换必须专门用于1D、2D和3D情况，以及分别用于单精度和双精度数据。填充。为了确保沿所有轴访问超立方体的连续索引可以映射到非重叠组，插入了填充词。由于每个内存块都是32位宽，并且64位加载和存储是作为两个连续的32位访问执行的，因此双精度情况下的填充必须仍然是32位宽。这需要故意不对齐访问64位值。定向访问顺序。在转换步骤的每个维度中，通道项上的迭代可以建模为具有固定步幅的循环。但是，由于每个活动warp（SM的基本执行单元）同时处理32个通道，因此必须显式计算每个通道中第一项的内存偏移量。同样，必须仔细划分一组通道以避免存储库冲突。ParallelIntegerLorenzoTransformn维整数洛伦佐变换，包括正向和逆向，由n个通道组成。在每个有向通道中，可以并行处理L个数据；这些通道分布在线程块的线程中。正向变换。正向变换在每车道4096次迭代中构造残差，表示为其前身的整数差替换值。Precursor值在寄存器中进行跟踪，因此该方案只需在共享内存中对每个数据点执行一次加载和一次存储。逆变换。为了重建值表示，每个逆变换过程都必须将解码前导添加到每个残差中。由于这引入了一个大小等于块边长的依赖链，因此最多可以有4096^{1-1/n}个独立通道（1维1个，2维64个，3维256个）。由于每个通道的逆变换形成一个前缀和，因此可以通过采用并行扫描来避免序列化。在实践中，我们通过在连续块内存上使用快速并行前缀和来反转1D变换，并通过对每个通道执行顺序求和来接受2D和3D情况下的有限占用。WarpCooperativeVerticalBitPacking固定宽度整数序列的垂直位打包已经在数据库系统中得到应用。这种压缩长度不能被处理器的最小可寻址单元分割的位模式的方法在并行硬件（例如支持SIMD的处理器）上被有效地矢量化。它可以很容易地适应压缩输入位位置的任意子集，而不是对整数中的连续位进行操作，再次允许在SIMD架构上高效实现。在这种形式下，它以前作为MPC压缩器的一部分用于GPU浮点压缩。在下文中，我们将未压缩的单词称为行，将未压缩序列中相同位置的位称为列。ndzip-gpu的新颖打包方案通过缩短评估全零块而没有线程发散的昂贵转置步骤，显着提高了现代GPU上超越MPC方法的性能。通过避免阻塞允许独立的前进进程——在打包期间完全同步。通过将压缩块写入全局暂存缓冲区并在解包期间使用单独的压缩内核。避免围绕输出流位置序列化，避免通过从流头读取粗粒度块偏移量并计算块内的细粒度块偏移量作为并行前缀和来围绕输入流位置序列化。包裹。在ndzip-gpu编码器中，32个线程协作打包32条32位或64条64位线。图4显示了更简单的32位情况的机制，其中一个字对应一个线程。图4协同垂直位打包和解包。对于32位情况，解码阶段使用与图5所示类似的线程分配。首先，每个打包块的长度由其标头中的位数(popcount)决定。根据这些长度，使用线程块并行前缀并计算打包流的偏移量。图5Cooperativeverticalbitunpackingparameteradjustment由于ndzip格式需要固定的块大小，因此最重要的可调参数是每个块的线程数。这个数字可以独立于实现的其余部分进行选择，并允许交易缓存局部性以获得更高的占用率，从而提高隐藏指令延迟的能力。评估评估方法将数据集的压缩率定义为压缩后的大小除以未压缩的大小（以字节为单位），比率越低表示压缩越好。该定义允许使用未加权的算术平均值从一组观察值中对预期压缩比进行有意义的分析。压缩机性能是通过测量从第一个内核开始到最后一个内核结束的设备执行时间来评估的。缓冲区分配和主机设备内存传输不包括在测量中。我们以每秒未压缩的字节数报告吞吐量，这转化为压缩的输入和解压缩的输出带宽。对每个算法-数据集对重复测量，直到总运行时间超过一秒，但至少五次。所有CPU算法都通过测量执行时间进行基准测试，不包括所有可以提前执行的内存分配。结果图6展示了ndzip-gpu提供的吞吐量和压缩比之间的出色权衡。在评估的测试数据上，并行化方案同时提供了所有测试压缩器中单精度的最佳平均压缩比和最高吞吐量。对于双精度，GFC和nvCOMP级联方案在RTX2070SUPER和A100GPU上超过了ndzip-gpu的速度，但压缩比更差。与GFC和MPC不同，ndzip-gpu显示压缩和解压缩速度之间存在显着差异。这可以用压缩器的多级架构来解释，压缩器需要完整的全局内存往返。图6平均压缩率与TeslaV100上压缩器/解压缩器吞吐量的比较表1TeslaV100上每个GPU压缩器实现的每个数据集的压缩率和吞吐量每个数据集的压缩效率。上表列出了每个压缩器在每个数据集上实现的压缩率和吞吐量。虽然ndzip-gpu实现了最佳的数据缩减和最高的平均吞吐量，但某些数据集可以通过竞争算法更有效或更快地压缩。对于大多数输入，ndzip和MPC的比率非常接近，因为这两种算法共享相同的残差编码算法。了解更多开源信息，请访问：51CTO开源基础软件社区https://ost.51cto.com。
