Acceleration of Deflate Encoding and Decoding with GPU implementations

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.