THESIS
2014
ii leaves, iii-ix, 44 pages : illustrations ; 30 cm
Abstract
Lossless data compression tools, such as bzip2, gzip, and winzip, are widely used in our daily lives
as well as in enterprise settings. With these tools, files can be shrunken several times in size and
thus save storage space and transfer time. Furthermore, the compressed files can be decompressed
back into the original files by the same tool. Since lossless compression and decompression is
time-consuming for large data, we propose to utilize graphics processors, or GPUs to speed up the process.
In this thesis work, we parallelize bzip2, an efficient, representative, and open-source lossless data
compressor, on the GPU. In particular, we redesign the three main steps of bzip2 - Burrow-Wheeler
Transform, Move To Front Coding and Huffman Coding to fit the GPU’s massively parallel a...[
Read more ]
Lossless data compression tools, such as bzip2, gzip, and winzip, are widely used in our daily lives
as well as in enterprise settings. With these tools, files can be shrunken several times in size and
thus save storage space and transfer time. Furthermore, the compressed files can be decompressed
back into the original files by the same tool. Since lossless compression and decompression is
time-consuming for large data, we propose to utilize graphics processors, or GPUs to speed up the process.
In this thesis work, we parallelize bzip2, an efficient, representative, and open-source lossless data
compressor, on the GPU. In particular, we redesign the three main steps of bzip2 - Burrow-Wheeler
Transform, Move To Front Coding and Huffman Coding to fit the GPU’s massively parallel architecture.
Furthermore, we convert sequential data operations into GPU-friendly data-parallel primitives
such as sorting, prefix scan, and others. As a result, our GPU-based implementation on an
NVIDIA M2090 GPU achieves a compression and decompression speed of around 30 MB/s and
100 MB/s respectively, both of which are around 3-5 times faster than the sequential bzip2.
Post a Comment