我们有一个用霍夫曼编码编码的数据库。这里的目的是在GPU上复制它的相关解码器;然后在GPU上解码数据库，并在这个解码的数据库上做一些事情，而不用将其复制回CPU上。是否有可能在GPU中实现霍夫曼解码？
我很快就成为霍夫曼专家，但我所知道的少数人表明，它似乎是一种基本上基于控制结构的算法。用基本的算法，恐怕会有很多序列化的操作。
我的2个问题是：
我看其他的限制，但它们并不重要： - GPU不能非常有效的处理树：二叉树可以存储在一个传统的阵列 - 工作量可能难以平衡：我们将见
霍夫曼编码的问题是你不能快进。即：你必须线性地逐位解码。
因此，它不是并行的理想选择。
如果您可以决定编码，您可以完美地按块编码块，以便能够独立解码每个块。
为什么您一点一点地认为并行是不理想的？我认为读取几个独立的编码值是不成问题的。问题是并行执行这些位的解码。 – 2010-06-11 10:46:23
霍夫曼的问题是你不知道一个符号被编码了多少位。你读第一个，检查它是否是符号，读第二个，检查它是否是符号，读第三个AH是符号，好，所以我存储了符号并倒回我的状态机。继续。这不是可并行化的。 – 2010-06-11 13:36:03
我对Huffman在GPU上不可能达成的明显共识感到惊讶。
我呼吁格言：“如果发生了，它一定是可能的”。 （不同地归因于阿加莎克里斯蒂，阿尔伯特爱因斯坦等）
因为SuperXero在GPU上做霍夫曼，我想这一定是可能的。
CPU huffman compression faster after first execution?（SuperXero）
是的，你可以做并行Huffman解码，所以你可以在GPU获得优势 - 提供的内存是不是一个问题。
对于下面的讨论，我将讨论huffman树和huffman输出 - 输出是需要在huffman树中查找以解码的压缩符号。
huffman算法要求你有一个霍夫曼树解码 - 该树可以很大。您可以通过使用适合GPU中本地内存的小哈夫曼树来解决此问题 - 但这会影响算法的压缩效率。例如。您可以将树限制为最佳的2^n个节点，就像gpu处理器允许的那样多。 （例如，使用限定的树来表示1024个节点
如果你不限制huffman树，这样你就可以在每个gpu的本地存储器中容纳一个副本，那么你将不会真正得到你期望的并行性，因为所有gpu处理器将被阻塞访问所有读取相同共享树的内存。
huffman输出符号被打包在可变数量的位中。如果你从输出的中间开始，就不知道你是否在符号上。但是你可以创造你自己的界限。例如，在输出中，您可以强制每x个单词对齐符号以进行字对齐。然后你知道你可以开始在输出中的任何多个x字的解码，并将该块连同适当的树一起发送到GPU处理节点。
您不必只使用一棵树，但每块一棵树也可能会矫枉过正。也就是说，如果每块有一棵树，那么如果块很小，则会严格切入压缩效率。
因此，您可以尝试查看块的相似性并使用同一棵树对相似块进行编码，并存储每个块的树索引。例如。输出中可能有10000个块，但只有50个1024个节点的树。然后你发送一个块和一个树到每个GPU处理节点并行解码。
使其更快的关键在于每个GPU处理节点仅在本地内存上工作。
我怀疑你会看到任何真正的好处，通过实施GPU - CUDA或其他。 GPU对于多个数据点具有并行性和均匀操作的问题的子集来说只是非常有用的。 – 2010-06-10 11:09:15
霍夫曼，因为我知道它是完全串行的。你根本不能分解要解码的代码，因为你不知道中断是在哪里进行的，除非你在中断之前处理了所有的代码。 – 2010-06-10 14:36:16
iOS Metal上的一个示例实现（链接）显示，同时解码多个块比执行CPU上的逻辑要快得多。必须创建一个每块查找表，所以会有一些开销。请参阅https://stackoverflow.com/a/47954985/763355 – MoDJ 2017-12-28 01:40:38