级联压缩#

级联压缩是一种通用的压缩方案，非常适合分析工作负载。它使用一系列可以组合使用的底层压缩构建块。由于这些构建块有许多可能的组合，因此级联压缩可以通过多种不同的方式进行配置。以下是每个底层构建块压缩方案的简要概述。

每个算法的更详细描述可在 GTC 2020 演示文稿 “用于分析工作负载的基于软件的压缩” 中找到。

游程编码 (RLE)#

游程编码是一种非常简单的编码方案，它将重复的值压缩成一对：值和游程长度（重复次数）。由于 RLE 仅压缩重复的副本，因此其性能高度依赖于输入数据集。请注意，对输入序列执行 RLE 会产生两个序列：值和游程。因此，如果每个游程的长度为 1（没有重复的连续值），则 RLE 可能会导致输入扩展 2 倍。

示例

3 9 9 4 4 4 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 -> (3,1) (9,2) (4,3) (0,10) (1,6)

对于编码（压缩），nvCOMP 使用 CUB 库中提供的底层 RLE 内核。总体而言，该方法只是识别每个游程的开始并计算其长度。并行地，我们通过让每个线程检查一对连续值是否不同来识别每个游程的开始。然后，我们使用前缀和运算来计算每个游程的长度。

解码（解压缩）是通过首先对游程长度执行前缀和来完成的，以计算每个游程开始的输出索引。然后，我们只需为每个游程写出重复项，注意在写出大型游程时要有足够的并行性。

Delta 编码#

Delta 编码涉及用其相对于序列中前一个值的差分（或 delta）来表示每个值。虽然它本身不直接压缩，但它提供了两个潜在的好处：1) 减小值的范围，允许使用位打包（如下所述）进行进一步压缩，以及 2) 创建更多连续的重复项，这些重复项可以通过后续的 RLE 步骤进行压缩。

示例

15000 15001 15002 15003 15004 15204 15104 15103 15102 15101 15100 -> 15000 1 1 1 1 200 -100 -1 -1 -1 -1

我们可以通过简单地以线程并行的方式计算每对连续值之间的差异，在 GPU 上高效地执行 Delta 编码（压缩）。

解码（解压缩）是通过简单的互斥前缀和运算执行的，我们使用 CUB 库实现来执行此操作。

位打包#

位打包是一种位级操作，旨在减少存储每个值所需的位数。它通过仅使用表示输入数据中找到的值范围所需的位数来实现这一点。如果输入对每个值使用 B 位，并且我们可以将它们打包成每个值 b 位，则实现的压缩率约为 B/b。

示例

15000 15001 15002 15003 15004 15204 15104 15103 15102 15101 15100 -> min:15000, 0 1 2 3 4 204 104 103 102 101 100

结果值都小于 256，因此每个压缩值仅需要 8 位。

位打包压缩算法有两个步骤：1) 查找最小值和最大值，以及 2) 编码输入数据。我们可以通过并行扫描和归约操作有效地找到最小值和最大值。一旦找到最小值和最大值，范围将计算为 max-min，从而得出每个值所需的位数 b。然后，我们将数据集中的每个值编码为 val-min，仅使用 b 位表示。我们将此编码与最小值一起存储为最终压缩的位串。请注意，如果 b 不是机器字大小 (32) 的倍数，则某些符号可能会跨越多个字。我们特别注意处理这些情况，详细信息请参阅 GTC 2020 演示文稿 “用于分析工作负载的基于软件的压缩”。

解包（解压缩）涉及计算每个编码符号的完整值（符号 + 最小值）并使用完整的 B 位将其写出。由于我们知道 B，我们可以轻松计算每个值的输出位置并以线程并行的方式执行此操作。

级联压缩器中唯一取决于指定数据类型是有符号还是无符号的部分是在不使用 delta 编码进行压缩时查找位打包的最小值和最大值，因为对于有符号数据类型，大于最大有符号值的值将被解释为负数，而对于无符号数据类型，它们将被解释为正数。这意味着，如果要压缩的数据表示只能为正的整数，并且不使用 delta 编码，则在某些情况下，指定无符号数据类型（例如 uchar 或 uint）而不是有符号数据类型（例如 char 或 int）可能是有益的。

组合成级联方案#

使用 RLE、Delta 和位打包构建块，我们可以组装各种级联方案。我们通过 RLE、Delta 的数量以及是否启用位打包来定义每个方案。因此，2 2 1 将是一个级联压缩方案，其中包含 2 个 RLE、2 个 Delta，并启用位打包。RLE 和 Delta 层是交错的。然后，构建块压缩方案以下列方式连接在一起：RLE 和 Delta 交错，来自 RLE 的值输出用作 Delta 的输入。一旦所有 RLE 和 Delta 完成，就会对所有结果数据（游程和值）执行位打包。

级联压缩方案可通过 C 和 C++ API 调用获得，并且每个方案都可以通过向 API 调用传递压缩格式来配置。在 C API 中，压缩调用接受指向 CascadedFormatOpts 结构的指针，该结构具有 3 个字段：num_RLEs、num_deltas 和 up_bp。C++ API CascadedCompressor 构造函数将每个值作为参数。

下面的示例说明了一个 2 1 1 (RLE=2, Delta=1, bitpacking=1) 级联方案。