Massively Parallel LZ77 Compression and Decompression on the GPU
Date
2022-08
Authors
Wesley, Kayla
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Parallelizing data compression algorithms is difficult because algorithms like LZ77 have iterative dependencies that cannot easily be circumvented. Previous computation steps directly impact later steps in the algorithm, and parallelizing those dependent steps can prove difficult. My solution is to express both the encoding and decoding portions of LZ77 in terms of prefix sums, union-find operations, and other parallelizable computations. The results show that this methodology is effective in improving throughput. Compared to codes from the literature, my CUDA implementation is an order of magnitude faster but tends to have a lower compression ratio.
Description
Keywords
Parallelized LZ77, Lossless parallel compression and decompression
Citation
Wesley, K. (2022). Massively parallel LZ77 compression and decompression on the GPU (Unpublished thesis). Texas State University, San Marcos, Texas.