ACCELERATING LOSSLESS DATA COMPRESSION WITHGRAPHICS PROCESSORS

MPhil Thesis Defence


Title: "ACCELERATING LOSSLESS DATA COMPRESSION WITHGRAPHICS PROCESSORS"

By

Mr. Ge BAI


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 
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 bzip2 
running on two Intel E5-2650 8-core CPUs on the same machine.


Date:			Tuesday, 29 April 2014

Time:			2:00pm – 4:00pm

Venue:			Room 5507
 			Lifts 25/26

Committee Members:	Dr. Qiong Luo (Supervisor)
 			Dr. Charles Zhang (Chairperson)
 			Dr. Lin Gu


**** ALL are Welcome ****