beg*_*ner 4 hardware algorithm parallel-processing processor huffman-code
霍夫曼编码涉及的步骤是相当连续的。所以，我想知道如何在支持并行实现的任何平台（如 GPU、多核处理器等）上实现霍夫曼编码时引入并行性？
多核/多个处理器：
可以使用多核处理器并行化霍夫曼编码。基本思想是将源流分割成块，为每个处理器分配一个块，将块并行编码到单独的中间缓冲区中，然后将中间缓冲区（其长度不同）的编码结果连接到最终输出缓冲区。
一个复杂之处在于，由于霍夫曼编码使用不同位长度的代码，因此每个块很可能不会编码为整数字节长的位流。这意味着在连接结果时，可能需要使用位移来将一个中间缓冲区的输出与前一个中间缓冲区的输出正确对齐。例如，如果缓冲区 A 生成的结果为 150 字节和 3 位长，则在复制缓冲区 B 时，数据将必须移位 3 位，其中一个字节的 5 位和中间缓冲区的下一个字节的 3 位连接在一起使每个字节写入输出缓冲区。
解决此问题的一种方法是利用输出格式的特殊性。例如，如果您对 JPEG 格式的图像数据进行霍夫曼编码，则可以在写入输出缓冲区的每个块的开头输出 JPEG 重新启动标记，以将流与字节边界对齐。根据 JPEG 规范，该标记旨在允许并行解码，但它也使并行编码变得更容易。
螺纹加工
假设您有 100Kb 的源数据流和 4 个处理器。最简单的做法是将其分成每个 25Kb 的块，但这可能会导致最坏的情况，即第一个块是最后完成编码的，因此所有其他处理器都必须等待它，因为第二个块在知道第一个块的长度之前，无法将块写入输出缓冲区。为了避免这种情况，请将输入流分成更小的块，按照先到先服务的原则将数据分配给可用的处理器，每个处理器在完成后立即将其中间缓冲区的内容写入输出缓冲区并且所有较早的块已完成编码（以便知道输出缓冲区中要写入的索引），然后被分配输入流中的下一个可用块。
您需要同步对输入缓冲区的读取索引和输出缓冲区的写入索引的访问，但不要同步对输出缓冲区本身的访问。例如，一旦处理器完成，它可以（使用线程同步）读取输出缓冲区索引以知道从哪里开始写入，然后（仍然使用线程同步）根据要写入的数据的大小更新索引，然后（不再使用同步）开始写入。这样，多个处理器可以同时写入输出缓冲区。类似的方案可用于输入缓冲区。
GPU 和硬件加速
我不知道有任何使用 GPU 进行霍夫曼编码的简单方案。一般来说，GPU 非常擅长从不均匀间隔的内存位置读取数据并写入恒定间隔的内存位置，但反之则不然（例如，这就是位移映射如此困难的原因）。由于霍夫曼编码是后者的一个示例，因此它不太适合基于 GPU 的加速。然而，有针对该问题的定制硬件解决方案，例如许多移动电话中使用的硬件加速视频编码器。