我们有一个用霍夫曼编码编码的数据库。这里的目的是在 GPU 上复制它及其相关的解码器；然后在 GPU 上，解码数据库并在这个解码的数据库上做一些事情，而不是在 CPU 上复制回来。
我远不是霍夫曼专家，但我知道的少数人表明它似乎是一种基本上基于控制结构的算法。有了基础算法，恐怕会出现很多序列化的操作。
我的两个问题是：
我看到了其他限制，但它们并不重要： - GPU 无法非常有效地处理树：二叉树可以存储在经典数组中 - 工作负载可能难以平衡：我们稍后会看到
霍夫曼编码的问题是你不能快进。即：您必须逐位线性解码。
因此，它不适合并行性。
如果您可以决定编码，则可以完美地逐块编码，以便能够独立解码每个块。
是的，您可以并行进行霍夫曼解码，因此您可以在 GPU 中获得优势——只要内存不是问题。
对于下面的讨论，我将讨论霍夫曼树和霍夫曼输出 - 输出是需要在霍夫曼树中查找以进行解码的压缩符号。
霍夫曼算法要求你有一棵用于解码的霍夫曼树——这棵树可能很大。您可以通过使用适合 GPU 中本地内存的小型霍夫曼树来解决此问题 - 但这会影响算法的压缩效率。例如，您可以在 gpu 处理器允许的范围内将树限制为最好的 2^n 个节点。（例如，使用限制为 1024 个节点的树。
如果您不限制霍夫曼树，以便您可以在每个 gpu 的本地存储中放置一个副本，那么您将不会真正获得您期望的并行度，因为所有 gpu 处理器将被阻止访问所有读取同一共享树的内存。
霍夫曼输出的符号被打包在可变数量的位中。如果您从输出中间开始，就无法知道您是否在符号边界上。但是您可以创建自己的界限。例如，在输出中，您可以强制将每个 x 个单词的符号对齐为单词对齐。然后你知道你可以开始解码输出中任意倍数的 x 字，并将该块连同适当的树一起发送到 GPU 处理节点。
您不必只使用一棵树，但每块一棵树也可能是矫枉过正。也就是说，如果每个块都有一棵树，那么如果块很小，那么压缩效率就会大大降低。
因此，您可以尝试查看块的相似性并使用相同的树对相似的块进行编码，并为每个块存储一个树索引。例如，您可能在输出中有 10000 个块，但只有 50 个 1024 节点树。然后将一个块和一棵树发送到每个 GPU 处理节点以并行解码。
使其快速的关键是每个 GPU 处理节点仅在本地内存上工作。
我对这样一个明显的共识感到惊讶，即 Huffman 在 GPU 上是不可能的。
我呼吁格言：“如果它发生，它一定是可能的”。（各种归因于阿加莎克里斯蒂，阿尔伯特爱因斯坦等）
由于 SuperXero 在 GPU 上做 Huffman，我想它一定是可能的。
首次执行后 CPU 霍夫曼压缩更快？（超级Xero）