Parallel Huffman

Huffman coding at extreme performance on modern GPU architectures.

Huffman coding is the lossless stage that follows prediction and quantization in an error-bounded compressor, and on a GPU it is the stage that stubbornly refuses to parallelize: the codebook is built from a tree, and the codewords are variable-length. This work makes both parts run on the device.

The code lives today inside pSZ/cuSZ, as its Huffman codec. A standalone repository is planned. PaperSlidesRepo

What it does

  1. An efficient parallel codebook construction on GPUs that scales with the number of input symbols.
  2. A reduction-based encoding scheme that merges codewords on the device rather than serializing them.
  3. Whole-GPU tuning through state-of-the-art CUDA APIs, including Cooperative Groups.
  4. Evaluation on six real-world application datasets across two GPUs, against a multi-threaded CPU Huffman encoder built for the comparison.
  5. A follow-on decoding path, so post hoc analysis is not left waiting on the stage that compression already made fast (IPDPS '22, below).

Two views of one merge

reduce-merge, shuffle-merge
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 0 1 2 3 0 1
reduce-merge, 8-to-1. Each round pairs neighbouring codewords. The left of a pair keeps its slot and descends; the right, dotted, curves in and is concatenated onto the left's tail. Three rounds fold each group of eight codewords into one, so sixteen inputs leave as two. Redrawn from the IPDPS '21 paper.
1 2 3 two segments two parts of right segment move part 1/2 move part 2/2 t₀ t₁ t₂ t₃ t₄ t₅ t₆ t₇ t₈ t₉ t₁₀ t₁₁ t₁₂ t₁₃ t₁₄ t₁₅ t₀ t₁ t₂ t₃ t₄ t₅ t₆ t₇ t₈ t₉ t₁₀ t₁₁ t₁₂ t₁₃ t₁₄ t₁₅ t₈ t₉ t₁₀ t₁₁ t₁₂ t₈ t₉ t₁₀ t₁₁ t₁₂
shuffle-merge. Two eight-word segments. The left segment's bits end 5.2 words in, not on a word boundary, so concatenating the right segment onto it lands every source word across two destination words: the leading 0.8 in one, the trailing 0.2 in the next. That is why the move takes two passes and not one.

Results

encoding throughput, from the IPDPS '21 paper

  • up to 5.0× on NVIDIA RTX 5000, over the state-of-the-art GPU Huffman encoder

  • up to 6.8× on NVIDIA V100, over the same

  • up to 3.3× over a multi-threaded encoder on two 28-core Xeon Platinum 8280 CPUs

Papers

chronologically ordered

  1. IPDPS '21Revisiting Huffman Coding: Toward Extreme Performance on Modern GPU Architectures Jiannan Tian, Cody Rivera, Jieyang Chen, Dingwen Tao, Sheng Di, and Franck Cappello. IEEE International Parallel & Distributed Processing Symposium, (Virtual Event) Portland, OR, May 17–21, 2021. PaperSlides

  2. IPDPS '22Optimizing Huffman Decoding for Error-Bounded Lossy Compression on GPUs Cody Rivera, Sheng Di, Jiannan Tian, Xiaodong Yu, Dingwen Tao, and Franck Cappello. IEEE International Parallel & Distributed Processing Symposium, Lyon, France, May 30 – June 3, 2022. arXiv