Massively Parallel LZ77 Compression and Decompression on the GPU
| dc.contributor.advisor | Burtscher, Martin | |
| dc.contributor.author | Wesley, Kayla | |
| dc.contributor.committeeMember | Metsis, Vangelis | |
| dc.contributor.committeeMember | Peng, Wuxu | |
| dc.date.accessioned | 2022-08-31T15:01:14Z | |
| dc.date.available | 2022-08-31T15:01:14Z | |
| dc.date.issued | 2022-08 | |
| dc.description.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. | |
| dc.description.department | Computer Science | |
| dc.format | Text | |
| dc.format.extent | 55 pages | |
| dc.format.medium | 1 file (.pdf) | |
| dc.identifier.citation | Wesley, K. (2022). Massively parallel LZ77 compression and decompression on the GPU (Unpublished thesis). Texas State University, San Marcos, Texas. | |
| dc.identifier.uri | https://hdl.handle.net/10877/16093 | |
| dc.language.iso | en | |
| dc.subject | Parallelized LZ77 | |
| dc.subject | Lossless parallel compression and decompression | |
| dc.title | Massively Parallel LZ77 Compression and Decompression on the GPU | |
| dc.type | Thesis | |
| thesis.degree.department | Computer Science | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.grantor | Texas State University | |
| thesis.degree.level | Masters | |
| thesis.degree.name | Master of Science |