是否有可能在GPU中实现霍夫曼解码？

Question

我们有一个用霍夫曼编码编码的数据库.这里的目的是在GPU上复制它与相关的解码器; 然后在GPU上解码数据库,并在这个解码的数据库上执行操作,而无需将其复制回CPU上.

我远远不是霍夫曼专家,但我知道的少数人表明它似乎是一种基本上基于控制结构的算法.使用基本算法,恐怕会有很多序列化操作.

我的两个问题是:

• 你知道是否存在任何有效的霍夫曼编码GPU版本
• 如果没有,你认为存在一个适用于GPU的霍夫曼算法(即控制结构较少).或许您知道(并且您可以提供参考)有效的霍夫曼解码在GPU上无法有效.

我看到其他约束,但它们并不重要: - GPU处理树的效率不高:二叉树可以存储在经典数组中 - 工作量很难平衡:我们会看到

Answer 1

霍夫曼编码的问题在于你不能快进.即:你必须线性地逐位解码.

因此,并行性并不理想.

如果你可以决定编码,你可以完美地按块编码块,以便能够独立解码每个块.