logo标签列表

能否在GPU上实现Huffman解码？

algorithmgpuhuffman-code
12
我们有一个用Huffman编码的数据库。目标是将其与相关的解码器一起复制到GPU上，然后在GPU上对数据库进行解码，并对此解码的数据库执行操作而无需将其复制回CPU。
我并不是一个Huffman专家，但我所知道的很少，似乎这是一个基于控制结构的算法。使用基本算法时，恐怕会有很多串行操作。
我的两个问题是：
  • 您是否知道是否存在有效的用于Huffman编码的GPU版本？
  • 如果没有，您是否认为存在一种适用于GPU的Huffman算法（即具有较少的控制结构）？或者您可能知道（并且可以提供参考文献）高效的Huffman解码在GPU上不可行。
我还看到其他约束条件，但它们并不是关键因素： - GPU可能无法处理树：二叉树可以存储在经典数组中 - 工作负载可能难以平衡：之后再看。
我怀疑在GPU上实现这个功能-CUDA或其他方式-不会带来任何真正的好处。 GPU只适用于一些问题的子集，其中存在并行性和对多个数据点的同质操作。 - Paul R
1
据我所知，Huffman 编码完全是串行的。您无法将要解码的代码拆分，因为在处理断点之前，您不知道断点在哪里。 - Justin Peel
iOS Metal上的一个示例实现（链接）表明，同时解码多个块比在CPU上执行逻辑要快得多。必须创建每个块的查找表，因此有一些开销。请参见https://stackoverflow.com/a/47954985/763355。 - MoDJ
3个回答
5
使用Huffman编码的问题在于无法快进。也就是说，您必须逐位线性解码。
因此，它不适合并行处理。
如果您可以决定编码方式，可以完美地将数据分块进行编码，以便能够独立解码每个块。
1
你认为为什么逐位处理不是并行处理的理想选择呢？我觉得单独逐位读取多个编码值并不是问题，问题在于如何同时对这些位进行解码。 - Jérôme
6
对于哈夫曼来说，问题在于您不知道一个符号编码需要多少位。您读取第一个比特，检查它是否是一个符号，读取第二个比特，检查它是否是一个符号，读取第三个比特，发现它是一个符号，好的，我将存储该符号并返回我的状态机。继续进行下去。这是不可并行化的。 - Matthieu M.
2
是的，您可以并行进行哈夫曼解码，因此在GPU中可以获得优势-前提是内存不是问题。
以下讨论将涉及哈夫曼树和哈夫曼输出-输出是需要在哈夫曼树中查找以进行解码的压缩符号。
哈夫曼算法要求您拥有用于解码的哈夫曼树-该树可能很大。您可以通过使用适合于GPU本地存储器的小型哈夫曼树来解决此问题-但这将影响算法的压缩效率。例如，您可以将树限制为最佳2 ^ n个节点，以尽可能多地利用gpu处理器（例如，使用限制为1024个节点的树）。
如果您不限制哈夫曼树，以便每个gpu上都可以容纳一个副本，则您实际上不会获得预期的并行性，因为所有gpu处理器都将被阻止访问内存，所有读取相同的共享树。
哈夫曼输出的符号被打包在可变数量的位中。如果您从输出的中间开始，则无法知道您是否处于符号边界上。但是您可以创建自己的边界。例如，在输出中，您可以强制使每x个字中的符号对齐到字对齐。然后，您知道可以从输出的任何x个字的倍数开始解码，并将该块与适当的树一起发送到GPU处理节点。
您不必仅使用一个树-但每个块一个树可能也过度。也就是说，如果每个块都有一个树，则会严重削减压缩效率，如果块很小。
因此，您可以尝试查看块的相似性，并使用相同的树对相似的块进行编码，并为每个块存储一个树索引。例如，您可能在输出中有10000个块，但只有50个1024节点树。然后，您将一个块和一个树发送到每个GPU处理节点以并行解码。
使其快速的关键是每个GPU处理节点仅在本地存储器上工作。
2
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接