A parallel Huffman coder on the CUDA architecture

Habibelahi Rahmani; Cihan Topal; Cuneyt Akinlar

doi:10.1109/VCIP.2014.7051566

A parallel Huffman coder on the CUDA architecture

Habibelahi Rahmani, Cihan Topal, Cuneyt Akinlar

Anadolu University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Citations (Scopus)

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.

Original language	English
Title of host publication	2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	311-314
Number of pages	4
ISBN (Electronic)	9781479961399
DOIs	https://doi.org/10.1109/VCIP.2014.7051566
Publication status	Published - 27 Feb 2015
Externally published	Yes
Event	2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014 - Valletta, Malta Duration: 7 Dec 2014 → 10 Dec 2014

Publication series

Name	2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014

Conference

Conference	2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014
Country/Territory	Malta
City	Valletta
Period	7/12/14 → 10/12/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

CUDA
GPGPU
Huffman coding
JPEG
parallel computing
variable length coding

Access to Document

10.1109/VCIP.2014.7051566

Cite this

Rahmani, H., Topal, C., & Akinlar, C. (2015). A parallel Huffman coder on the CUDA architecture. In 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014 (pp. 311-314). Article 7051566 (2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/VCIP.2014.7051566

@inproceedings{65ca5ce9994942b8957775bce970b280,

title = "A parallel Huffman coder on the CUDA architecture",

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.",

keywords = "CUDA, GPGPU, Huffman coding, JPEG, parallel computing, variable length coding",

author = "Habibelahi Rahmani and Cihan Topal and Cuneyt Akinlar",

note = "Publisher Copyright: {\textcopyright} 2014 IEEE.; 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014 ; Conference date: 07-12-2014 Through 10-12-2014",

year = "2015",

month = feb,

day = "27",

doi = "10.1109/VCIP.2014.7051566",

language = "English",

series = "2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "311--314",

booktitle = "2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014",

address = "United States",

}

Rahmani, H, Topal, C & Akinlar, C 2015, A parallel Huffman coder on the CUDA architecture. in 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014., 7051566, 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014, Institute of Electrical and Electronics Engineers Inc., pp. 311-314, 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014, Valletta, Malta, 7/12/14. https://doi.org/10.1109/VCIP.2014.7051566

A parallel Huffman coder on the CUDA architecture. / Rahmani, Habibelahi; Topal, Cihan; Akinlar, Cuneyt.
2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014. Institute of Electrical and Electronics Engineers Inc., 2015. p. 311-314 7051566 (2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A parallel Huffman coder on the CUDA architecture

AU - Rahmani, Habibelahi

AU - Topal, Cihan

AU - Akinlar, Cuneyt

PY - 2015/2/27

Y1 - 2015/2/27

N2 - 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.

AB - 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.

KW - CUDA

KW - GPGPU

KW - Huffman coding

KW - JPEG

KW - parallel computing

KW - variable length coding

UR - http://www.scopus.com/inward/record.url?scp=84925438696&partnerID=8YFLogxK

U2 - 10.1109/VCIP.2014.7051566

DO - 10.1109/VCIP.2014.7051566

M3 - Conference contribution

AN - SCOPUS:84925438696

T3 - 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014

SP - 311

EP - 314

BT - 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2014 IEEE Visual Communications and Image Processing Conference, VCIP 2014

Y2 - 7 December 2014 through 10 December 2014

ER -

A parallel Huffman coder on the CUDA architecture

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this