压缩二进制数组以克服 GPU 内存限制
Compression of binary arrays to overcome GPU memory limitations
我正在 GPU (CUDA) 上进行物理模拟，并为标准显卡上有限的可用内存而苦苦挣扎。
问题如下：
我有一个巨大的二进制掩码（> 30 GByte）用作查找 table。为了评估特定变量的有效性，我从变量属性生成索引并检查查找 table。这是在 GPU 上同时针对数百万个变量并行完成的（只需要读取访问权限）。
为了最小化这个二进制掩码的大小以适应 GPU 内存，我正在寻找仍然允许通过索引底层数据进行快速访问的压缩技术（最好由一个透明容器 class 负责关于一切）。由于掩码本身包含多个重复的单个位，我也希望可以实现高压缩率。
所以我的问题是：
在 nvidia 的 CUDA 实现中是否已经有任何已知的方法或者
有没有其他默认的 c++ 库可以解决这个问题？
Run-Length编码
我不知道有任何图书馆可以为您做这件事，但我可以为您提供如何做这件事的想法。由于您的掩码包含许多相同位的重复，因此 suitable 方法将是 Run-Length 编码 (RLE)。这个想法是，不是对单个字节进行编码，而是对字节及其长度进行编码：
aaabbbababaaaaaaaa -> 3a,3b,1a,1b,1a,1b,6a
在实践中有很多方法可以实现这一点。我正在研究体素模型压缩，最适合我的方法是使用字节 0x00 和 0xff 作为转义序列。所以[0x00, N]编码Nzero-bytes，[0xff, N]编码None-filled-bytes。其余字节保持未压缩状态。或者你可以使用 zlib 使用 DEFLATE 压缩，我相信也有一个 GPU 实现。
获得 O(1) 次随机访问
任何类型的压缩技术的问题在于它会将数据减小到可变大小，从而使随机访问变得不可能。要解决这个问题，您必须将数据压缩为 1024 字节的块。然后，您可以存储 table 个指向每个块开头的指针，从而允许您随机访问。
明显的问题是您一次只能保留一个未压缩的块，并且每次访问不同的块时，您也需要对其进行解压缩。这可能非常昂贵。
解决 O(log n) 随机访问
另一种技术是将数据压缩为八进制树。较高级别的一个字节的八位表示 lower-level 八个字节中哪些存在，哪些不存在。
0 0 1 1 // Higher-level bitmask representing
/ | | \ // which bytes exist.
0000.0000 0000.0000 0010.1111 1111.1111 // Lower-level bytes.
这里，一个1代表一个存在的子树，一个0代表一个缺失的子树。
我们可以将这棵树优化为：
0 0 1 1
| \
0010.1111 1111.1111
较高级别的zero-bit表示较低级别的all-zero数据，因此我们可以优化那些较低级别。通过像这样将我们的数据排列在树中，我们可以随机访问任何位，复杂度为 O(log n)。这种技术的优点是我们有很多相邻的 1 或 0，这些将被优化掉并在更高级别变成单个位。
请注意，我们也可以优化 all-one 的子树。为此，我们在更高级别使用 0x00 的掩码。 0x00 掩码不会自然出现，因为它会在更高级别作为单个 zero-bit 被优化掉。所以我们可以赋予它一些特殊的意义。
我正在 GPU (CUDA) 上进行物理模拟，并为标准显卡上有限的可用内存而苦苦挣扎。
问题如下：
我有一个巨大的二进制掩码（> 30 GByte）用作查找 table。为了评估特定变量的有效性，我从变量属性生成索引并检查查找 table。这是在 GPU 上同时针对数百万个变量并行完成的（只需要读取访问权限）。
为了最小化这个二进制掩码的大小以适应 GPU 内存，我正在寻找仍然允许通过索引底层数据进行快速访问的压缩技术（最好由一个透明容器 class 负责关于一切）。由于掩码本身包含多个重复的单个位，我也希望可以实现高压缩率。
所以我的问题是：
在 nvidia 的 CUDA 实现中是否已经有任何已知的方法或者 有没有其他默认的 c++ 库可以解决这个问题？
Run-Length编码
我不知道有任何图书馆可以为您做这件事，但我可以为您提供如何做这件事的想法。由于您的掩码包含许多相同位的重复，因此 suitable 方法将是 Run-Length 编码 (RLE)。这个想法是，不是对单个字节进行编码，而是对字节及其长度进行编码：
aaabbbababaaaaaaaa -> 3a,3b,1a,1b,1a,1b,6a
在实践中有很多方法可以实现这一点。我正在研究体素模型压缩，最适合我的方法是使用字节 0x00 和 0xff 作为转义序列。所以[0x00, N]编码Nzero-bytes，[0xff, N]编码None-filled-bytes。其余字节保持未压缩状态。或者你可以使用 zlib 使用 DEFLATE 压缩，我相信也有一个 GPU 实现。
获得 O(1) 次随机访问
任何类型的压缩技术的问题在于它会将数据减小到可变大小，从而使随机访问变得不可能。要解决这个问题，您必须将数据压缩为 1024 字节的块。然后，您可以存储 table 个指向每个块开头的指针，从而允许您随机访问。
明显的问题是您一次只能保留一个未压缩的块，并且每次访问不同的块时，您也需要对其进行解压缩。这可能非常昂贵。
解决 O(log n) 随机访问
另一种技术是将数据压缩为八进制树。较高级别的一个字节的八位表示 lower-level 八个字节中哪些存在，哪些不存在。
0 0 1 1 // Higher-level bitmask representing
/ | | \ // which bytes exist.
0000.0000 0000.0000 0010.1111 1111.1111 // Lower-level bytes.
这里，一个1代表一个存在的子树，一个0代表一个缺失的子树。
我们可以将这棵树优化为：
0 0 1 1
| \
0010.1111 1111.1111
较高级别的zero-bit表示较低级别的all-zero数据，因此我们可以优化那些较低级别。通过像这样将我们的数据排列在树中，我们可以随机访问任何位，复杂度为 O(log n)。这种技术的优点是我们有很多相邻的 1 或 0，这些将被优化掉并在更高级别变成单个位。
请注意，我们也可以优化 all-one 的子树。为此，我们在更高级别使用 0x00 的掩码。 0x00 掩码不会自然出现，因为它会在更高级别作为单个 zero-bit 被优化掉。所以我们可以赋予它一些特殊的意义。