A Parallel Huffman Coder on the CUDA Architecture

Rahmani H., TOPAL C., Akinlar C.

IEEE Visual Communications and Image Processing Conference, Valletta, Malta, 7 - 10 Aralık 2014, ss.311-314 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: Valletta
  • Basıldığı Ülke: Malta
  • Sayfa Sayıları: ss.311-314
  • Anahtar Kelimeler: Huffman coding, variable length coding, CUDA, GPGPU, parallel computing, JPEG
  • Anadolu Üniversitesi Adresli: Evet

Özet

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 22x speedups compared to the serial CPU implementation without any constraint on the maximum codeword length or data entropy.