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.