有没有办法在硬件上并行实现Huffman编码？

Question

的步骤相当顺序化。因此，我想知道如何在支持并行实现的平台上（如GPU、众核处理器等）实现时引入并行性？

- beginner

---

当你说“在硬件上”时，你是指设计系统/芯片/任何东西的架构，以便它被设计为并行运行Huffman吗？ - Daniel

我是指设计硬件架构，将并行性纳入其中，以在支持并行实现的系统上实现Huffman编码，如GPU、多核处理器等。基本上，我想在Huffman编码的架构中引入并行性，其步骤相当顺序化。 - beginner

我还是很困惑。你在标题中说“在硬件上”，但在评论中说“在支持并行实现的系统上”。那么你是在问：1）在已经能够并行运行事物的计算机上创建Huffman编码的并行实现，还是2）创建一个专门用于并行运行Huffman编码的硬件架构？ - Daniel

抱歉造成困惑。我想要选项1。 - beginner

Answer 1

多核/多处理器:

使用多核处理器可以并行压缩Huffman编码。基本思想是将源流分成块，将每个块分配给一个处理器，在并行地对块进行编码后存储到单独的中间缓冲区中，并将中间缓冲区的编码结果（长度不同）连接成最终输出缓冲区。

其中一个复杂问题是，由于Huffman编码使用不同位数的代码，因此每个块的编码长度很可能不是整数个字节的位流。这意味着在连接结果时，可能需要使用位移来正确对齐前一个中间缓冲区的输出和后一个中间缓冲区的输入。例如，如果缓冲区A生成了一个150字节和3位长的结果，则在复制缓冲区B时，必须将数据向左位移3位，然后将中间缓冲区的5位字节和后面3位字节结合起来，以便每个写入输出缓冲区的字节都能够正确对齐。

对此的一种解决方法是利用输出格式的特定属性。例如，如果您正在为JPEG格式的图像数据进行Huffman编码，则可以在写入输出缓冲区的每个块的开头输出JPEG重启标记，以将流对齐到字节边界。根据JPEG规范，该标记旨在实现并行解码，但它也使并行编码更加容易。

线程

假设您有一个100Kb的源数据流和4个处理器。最简单的方法就是将其分成每个25Kb的块，但这可能会导致最坏情况，即第一个块最后完成压缩，因此其他所有处理器都必须等待它，因为在知道第一个块的长度之前，无法将第二个块写入输出缓冲区。为了避免这种情况，将输入流分成更小的块，并按先到先得的原则将数据分配给可用处理器，每个处理器在完成编码后会立即将其中间缓冲区的内容写入输出缓冲区（以便知道在输出缓冲区中写入的索引），然后被分配下一个可用的块。

您需要同步访问输入缓冲区的读取索引和输出缓冲区的写入索引，但不要同步访问输出缓冲区本身。例如，一旦处理器完成，它可以（使用线程同步）读取输出缓冲区索引以确定从哪里开始写入，然后（仍使用线程同步）根据即将写入的数据的大小更新索引，然后（不再使用同步）开始写入。这样，多个处理器可以同时写入输出缓冲区。输入缓冲区也可以使用类似的方案。

GPU和硬件加速

我不知道有没有简单的方案可以使用GPU进行哈夫曼编码。一般来说，GPU非常擅长读取间隔不均匀的内存位置并写入常量间隔的内存位置的操作，但反之则不然（这就是为什么位移映射很难的原因）。由于哈夫曼编码是后者的一个例子，因此它不适合基于GPU的加速。然而，对于这个问题有一些定制的硬件解决方案，例如在许多手机中找到的硬件加速视频编码器所使用的解决方案。

- samgak

Answer 2

根据快速谷歌搜索，霍夫曼编码的并行化是可能的，相关论文可以追溯到几十年前。

• 在并行构建霍夫曼树
• 使用人类和算术编码的并行无损图像压缩
• http://arxiv.org/pdf/1107.1525.pdf

我没有阅读它们（只是短暂地浏览了一下以理解其相关性）。

这里有一个关于这个主题的小博客文章，其中的人声称：

虽然，如果我们拥有足够多的处理器，并且假设处理器元素之间的通信时间非常短，那么并行霍夫曼解码不应该很难。

- Salvador Dali

---

谢谢。您是正确的，有几种实现哈夫曼解码器的并行方式，但几乎没有论文讨论编码器的并行实现。 - beginner