时间戳

首页 > 解决方案 > 压缩二进制数组以克服 GPU 内存限制

c++ - 压缩二进制数组以克服 GPU 内存限制

问题描述

我正在 GPU (CUDA) 上进行物理模拟，并努力解决标准显卡上有限的可用内存量。

问题如下：

我有一个巨大的二进制掩码（> 30 GByte）用作查找表。为了评估特定变量的有效性，我从变量属性生成索引并检查查找表。这是在 GPU 上同时为数百万个变量并行完成的（只需要读取访问权限）。

为了最小化这个二进制掩码的大小以使其适合 GPU 内存，我正在寻找通过索引底层数据仍然允许快速访问的压缩技术（最好由一个负责所有事情的透明容器类）。由于掩码本身包含多个重复的单个位，因此我还希望可以实现高压缩比。

所以我的问题是：

在 nvidia 的 CUDA 实现中是否已经有任何已知的方法可用，或者是否有任何其他默认的 c++ 库可以做到这一点？

标签： c++binarycudacompressionmask

解决方案

游程编码

我不知道有任何图书馆可以为您执行此操作，但我可以为您提供如何执行此操作的想法。由于您的掩码包含相同位的许多重复，因此合适的方法是运行长度编码 (RLE)。这个想法是，不是对单个字节进行编码，而是对字节及其长度进行编码：

aaabbbababaaaaaaaa -> 3a,3b,1a,1b,1a,1b,6a

在实践中有很多方法可以实现这一点。我正在研究体素模型压缩，最适合我的方法是使用字节0x00和0xff作为转义序列。所以[0x00, N]编码 N 个零字节，[0xff, N]编码 N 个填充字节。剩余的字节保持未压缩。或者，您可以使用 zlib 使用 DEFLATE 压缩，我相信这也有 GPU 实现。

获得 O(1) 随机访问

任何类型的压缩技术的问题在于它将数据减少到可变大小，使得随机访问变得不可能。为了解决这个问题，您必须将数据压缩为 1024 字节的块。然后，您可以存储一个指向每个块开头的指针表，允许您随机访问。

显而易见的问题是，您一次只能保留一个块未压缩，并且每次访问不同的块时，您也需要对其进行解压缩。这可能非常昂贵。

解决 O(log n) 随机访问

另一种技术是将数据压缩为八进制树。较高级别的字节的八位代表较低级别的八个字节中的哪些存在，哪些不存在。

      0       0         1      1        // Higher-level bitmask representing
     /        |         |       \       // which bytes exist.
0000.0000 0000.0000 0010.1111 1111.1111 // Lower-level bytes.

这里，a1表示现有的子树，a0表示缺失的子树。我们可以将这棵树优化为：

      0       0         1      1
                        |       \
                     0010.1111 1111.1111

较高级别的零位表示较低级别的全零数据，因此我们可以优化那些较低级别的数据。通过像这样将数据排列在树中，我们可以以 O(log n) 的复杂度随机访问任何位。这种技术的优点是我们有很多相邻的 1 或 0，这些将被优化掉并在更高级别变成单个位。

请注意，我们也可以优化全为一的子树。为此，我们使用0x00更高级别的掩码。0x00掩码不会自然发生，因为它会被优化为更高级别的单个零位。所以我们可以赋予它一些特殊的含义。

推荐阅读