Lightweight Huffman Coding for Efficient GPU Compression
Open Access
- 21 June 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 99-110
Abstract
Lossy compression is often deployed in scientific applications to reduce data footprint and improve data transfers and I/O performance. Especially for applications requiring on-the-flight compression, it is essential to minimize compression's runtime. In this paper, we design a scheme to improve the performance of cuSZ, a GPU-based lossy compressor. We observe that Huffman coding - used by cuSZ to compress metadata generated during compression - incurs a performance overhead that can be significant, especially for smaller datasets. Our work seeks to reduce the Huffman coding runtime with minimal-to-no impact on cuSZ's compression efficiency. Our contributions are as follows. First, we examine a variety of probability distributions to determine which distributions closely model the input to cuSZ's Huffman coding stage. From these distributions, we create a dictionary of pre-computed codebooks such that during compression, a codebook is selected from the dictionary instead of computing a custom codebook. Second, we explore three codebook selection criteria to be applied at runtime. Finally, we evaluate our scheme on real-world datasets and in the context of two important application use cases, HDF5 and MPI, using an NVIDIA A100 GPU. Our evaluation shows that our method can reduce the Huffman coding penalty by a factor of 78--92×, translating to a total speedup of up to 5× over baseline cuSZ. Smaller HDF5 chunk sizes enjoy over an 8× speedup in compression and MPI messages on the scale of tens of MB have a 1.4--30.5× speedup in communication time.Keywords
This publication has 15 references indexed in Scilit:
- SDRBench: Scientific Data Reduction Benchmark for Lossy Compressors2020
- cuSZ2020
- Adaptive algorithm for quantum circuit simulationPhysical Review A, 2020
- SciPy 1.0: fundamental algorithms for scientific computing in PythonNature Methods, 2020
- Use cases of lossy compression for floating-point data in scientific data setsThe International Journal of High Performance Computing Applications, 2019
- Error-Controlled Lossy Compression Optimized for High Compression Ratios of Scientific Datasets2018
- Parallel lossless data compression on the GPU2012
- FPC: A High-Speed Compressor for Double-Precision Floating-Point DataIEEE Transactions on Computers, 2008
- Generating a canonical prefix encodingCommunications of the ACM, 1964
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952