A parallel Huffman coder on the CUDA architecture

Rahmani H., Topal C., AKINLAR C.

2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014, Valletta, Malta, 7 - 10 December 2014, pp.311-314 identifier

  • Publication Type: Conference Paper / Full Text
  • Doi Number: 10.1109/vcip.2014.7051566
  • City: Valletta
  • Country: Malta
  • Page Numbers: pp.311-314
  • Keywords: CUDA, GPGPU, Huffman coding, JPEG, parallel computing, variable length coding
  • Istanbul Technical University Affiliated: Yes

Abstract

We present a parallel implementation of the widely-used entropy encoding algorithm, the Huffman coder, on the NVIDIA CUDA architecture. After constructing the Huffman codeword tree serially, we proceed in parallel by generating a byte stream where each byte represents a single bit of the compressed output stream. The final step is then to combine each consecutive 8 bytes into a single byte in parallel to generate the final compressed output bit stream. Experimental results show that we can achieve up to 22× speedups compared to the serial CPU implementation without any constraint on the maximum codeword length or data entropy.