Optimizing Lempel-Ziv Factorization for the GPU Architecture

<p>Lossless data compression is used to reduce storage requirements, allowing for the relief of I/O channels and better utilization of bandwidth. The Lempel-Ziv lossless compression algorithms form the basis for many of the most commonly used compression schemes. General purpose computing on graphic processing units (GPGPUs) allows us to take advantage of the massively parallel nature of GPUs for computations other that their original purpose of rendering graphics. Our work targets the use of GPUs for general lossless data compression. Specifically, we developed and ported an algorithm that constructs the Lempel-Ziv factorization directly on the GPU. Our implementation bypasses the sequential nature of the LZ factorization and attempts to compute the factorization in parallel. By breaking down the LZ factorization into what we call the PLZ, we are able to outperform the fastest serial CPU implementations by up to 24x and perform comparatively to a parallel multicore CPU implementation. To achieve these speeds, our implementation outputted LZ factorizations that were on average only 0.01 percent greater than the optimal solution that what could be computed sequentially.</p> <p>We are also able to reevaluate the fastest GPU suffix array construction algorithm, which is needed to compute the LZ factorization. We are able to find speedups of up to 5x over the fastest CPU implementations.</p>

Name thesis:degree_name

MS in Computer Science

Discipline thesis:degree_discipline

Computer Science

Year dc:date.available

2014

Author dc:creator

• Ching, Bryan

Contributors dc:contributor

• Chris Lupo

• GPU
• CUDA
• Parallelism
• Compression
• LZ77
• Lempel-Ziv
• Computer and Systems Architecture

Identifier

10.15368/theses.2014.83

OAI identifier oai:identifier

oai:digitalcommons.calpoly.edu:theses-2361