Huffman Coding with Gap Arrays for GPU Acceleration
Huffman Coding with Gap Arrays for GPU Acceleration
复制标题
使用间隙数组进行霍夫曼编码以实现 GPU 加速
DOI：
10.1145/3404397.3404429
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
T. Tabaru
中科院分区：
文献类型：
--
作者：
Naoya Yamamoto;K. Nakano;Yasuaki Ito;Daisuke Takafuji;Akihiko Kasagi;T. Tabaru
Huffman编码是一种基本的无损数据压缩方案，用于许多数据压缩文件格式，例如GZIP，ZIP，PNG和JPEG。霍夫曼编码很容易并行，因为所有8位符号都可以独立转换为代码字。另一方面，由于编码的代码字序列没有分离器来识别每个代码字，因此并行化霍夫曼解码是一项更难的任务。这项工作提出了一种新的数据结构，称为GAP数组，该结构将附加到霍夫曼编码的编码编码序列上，以加速并行Huffman解码。此外，它还表明，GPU Huffman编码和解码可以通过（1）单个内核软同步（SKSS），（2）Wordwise Wise Wise Global Memory访问和（3）紧凑型代码书加速。 NVIDIA TESLA V100 GPU上10个文件的实验结果表明，我们的GPU Huffman编码和解码运行2.87x-7.70x次和1.26x-2.63 x倍的速度分别比以前提出的GPU Huffman编码和解码的速度分别快。同样，如果将间隙阵列连接到编码的代码字序列，则霍夫曼解码可以进一步加速1.67x-6450x。由于Huffman编码中GAP数组的大小和计算开销很小，因此我们可以得出结论，应该引入GPU Huffman编码和解码的GPU阵列。
Huffman coding is a fundamental lossless data compression scheme used in many data compression file formats such as gzip, zip, png, and jpeg. Huffman encoding is easily parallelized, because all 8-bit symbols can be converted into codewords independently. On the other hand, since an encoded codeword sequence has no separator to identify each codeword, parallelizing Huffman decoding is a much harder task. This work presents a new data structure called gap array to be attached to an encoded codeword sequence of Huffman coding for accelerating parallel Huffman decoding. In addition, it also shows that GPU Huffman encoding and decoding can be accelerated by several techniques including (1) the Single Kernel Soft Synchronization (SKSS), (2) wordwise global memory access and (3) compact codebooks. The experimental results for 10 files on NVIDIA Tesla V100 GPU show that our GPU Huffman encoding and decoding run 2.87x-7.70x times and 1.26x-2.63x times faster than previously presented GPU Huffman encoding and decoding, respectively. Also, Huffman decoding can be further accelerated by a factor of 1.67x-6450x if a gap array is attached to an encoded codeword sequence. Since the size and computing overhead of gap arrays in Huffman encoding are small, we can conclude that gap arrays should be introduced for GPU Huffman encoding and decoding.