Acceleration of Deflate Encoding and Decoding with GPU implementations
Acceleration of Deflate Encoding and Decoding with GPU implementations
复制标题
使用 GPU 实现加速 Deflate 编码和解码
DOI：
10.1109/candarw53999.2021.00036
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Akihiko Kasagi:
中科院分区：
文献类型：
--
作者：
Daisuke Takafuji;Koji Nakano;Yasuaki Ito;Akihiko Kasagi:
Deflate编码是一种非常流行的无损数据压缩方法，用在zlib、GNU zip（gzip）和zip中，它使用Huffman编码执行LZSS压缩算法。然而，Deflate编码尚未应用于GPU计算，因为Deflate编码和解码涉及顺序操作，并且使用GPU加速是相当困难的。本文的主要目的是介绍 Deflate 编码和解码的 GPU 实现。为了高效地 GPU 实现 Deflate 编码，我们使用多个小型哈希表通过多个线程并行在字典中查找匹配子序列，并应用单核软同步（SKSS）技术来充分利用 GPU 计算资源。我们还在霍夫曼编码中生成间隙数组以加速并行霍夫曼解码。我们使用 NVIDIA Tesla V100 GPU 评估了 GPU 实现的性能，并与 Pigz（专为 Intel X86 多核 CPU 设计的并行 Deflate 编码库）的性能进行了比较。我们的 Deflate 编码实验结果表明，我们的 GPU 实现速度比在四个 Intel Xeon E7-8870 CPU (2.10GHz)（每个有 20 个物理核心）上运行的 Pigz 快 1.28 倍。此外，我们对相同 9 个文件的 GPU 解码速度比 Pigz 解码快 36.49 倍。因此，我们的 Deflate 编码 GPU 实现是用于操作大型无损数据的 GPU 计算的有前途的工具。
Deflate coding is a very popular lossless data compression method used in zlib, GNU zip (gzip), and zip, which performs LZSS compression algorithm with Huffman coding. However, Deflate coding has not been used in GPU computing, because Deflate encoding and decoding involve sequential operations and their acceleration using a GPU is quite hard. The main purpose of this paper is to present GPU implementations for encoding and decoding of Deflate coding. For efficient GPU implementations of Deflate coding, we have used multiple small hash tables for finding matching subsequences in the dictionary by multiple threads in parallel and applied the Single Kernel Soft Synchronization (SKSS) technique to fully utilize GPU computing resources. We have also generated gap arrays in Huffman encoding to accelerate parallel Huffman decoding. We have evaluated the performance of our GPU implementations using an NVIDIA Tesla V100 GPU and compared with that of pigz, a library for parallel Deflate coding designed for Intel X86 multicore CPUs. Our experimental results for Deflate encoding show that our GPU implementation is up to 1.28x times faster than pigz running on four Intel Xeon E7-8870 CPUs (2.10GHz) with 20 physical cores each. Further, our GPU decoding for the same 9 files is up to 36.49x times faster than pigz decoding. Thus, our GPU implementations for Deflate coding are promising tools for GPU computations operating large lossless data.