GSST: Parallel string decompression at 191 GB/s on GPU

Robin Vonk; Joost Hoozemans; Zaid Al-Ars

doi:10.1145/3759441.3759450

GSST: Parallel string decompression at 191 GB/s on GPU

Robin Vonk, Joost Hoozemans, Zaid Al-Ars

Computer Engineering

Research output: Contribution to journal › Article › Scientific › peer-review

1 Downloads (Pure)

Abstract

Most of the commonly used compression standards make use of some form of the LZ algorithm. Decompressing this type of data is not a good match for the Single-Instruction, Multiple Thread (SIMT) model of computation used by GPUs, resulting in low throughput and poor utilization of the GPU parallel compute capabilities. In this paper, we introduce GSST, a GPU-optimized version of the FSST compression algorithm, which targets string compression. The optimizations proposed in this paper make the algorithm particularly suitable for GPUs, which allows it to achieve a significantly better tradeoff for decompression throughput vs compression ratio as compared to the state of the art. Our results show that the new algorithm pushes the Pareto curve closer towards the ideal region, completely dominating LZ-based compressors in the nvCOMP library (LZ4, Snappy, GDeflate). GSST provides a compression ratio of 2.7 4x and achieves a throughput of 191 GB/s on an A100 GPu.

Original language	English
Pages (from-to)	55-61
Number of pages	7
Journal	Operating Systems Review (ACM)
Volume	59
Issue number	1
DOIs	https://doi.org/10.1145/3759441.3759450
Publication status	Published - 2025

Bibliographical note

Green Open Access added to TU Delft Institutional Repository as part of the Taverne amendment. More information about this copyright law amendment can be found at https://www.openaccess.nl. Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Access to Document

10.1145/3759441.3759450

3759441.3759450Final published version, 1.67 MB

Cite this

@article{cec4f192a14746a68e8186751728f7f5,

title = "GSST: Parallel string decompression at 191 GB/s on GPU",

abstract = "Most of the commonly used compression standards make use of some form of the LZ algorithm. Decompressing this type of data is not a good match for the Single-Instruction, Multiple Thread (SIMT) model of computation used by GPUs, resulting in low throughput and poor utilization of the GPU parallel compute capabilities. In this paper, we introduce GSST, a GPU-optimized version of the FSST compression algorithm, which targets string compression. The optimizations proposed in this paper make the algorithm particularly suitable for GPUs, which allows it to achieve a significantly better tradeoff for decompression throughput vs compression ratio as compared to the state of the art. Our results show that the new algorithm pushes the Pareto curve closer towards the ideal region, completely dominating LZ-based compressors in the nvCOMP library (LZ4, Snappy, GDeflate). GSST provides a compression ratio of 2.7 4x and achieves a throughput of 191 GB/s on an A100 GPu.",

author = "Robin Vonk and Joost Hoozemans and Zaid Al-Ars",

note = "Green Open Access added to TU Delft Institutional Repository as part of the Taverne amendment. More information about this copyright law amendment can be found at https://www.openaccess.nl. Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public. ",

year = "2025",

doi = "10.1145/3759441.3759450",

language = "English",

volume = "59",

pages = "55--61",

journal = "Operating Systems Review (ACM)",

issn = "0163-5980",

publisher = "Association for Computing Machinery (ACM)",

number = "1",

}

TY - JOUR

T1 - GSST

T2 - Parallel string decompression at 191 GB/s on GPU

AU - Vonk, Robin

AU - Hoozemans, Joost

AU - Al-Ars, Zaid

N1 - Green Open Access added to TU Delft Institutional Repository as part of the Taverne amendment. More information about this copyright law amendment can be found at https://www.openaccess.nl. Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

PY - 2025

Y1 - 2025

N2 - Most of the commonly used compression standards make use of some form of the LZ algorithm. Decompressing this type of data is not a good match for the Single-Instruction, Multiple Thread (SIMT) model of computation used by GPUs, resulting in low throughput and poor utilization of the GPU parallel compute capabilities. In this paper, we introduce GSST, a GPU-optimized version of the FSST compression algorithm, which targets string compression. The optimizations proposed in this paper make the algorithm particularly suitable for GPUs, which allows it to achieve a significantly better tradeoff for decompression throughput vs compression ratio as compared to the state of the art. Our results show that the new algorithm pushes the Pareto curve closer towards the ideal region, completely dominating LZ-based compressors in the nvCOMP library (LZ4, Snappy, GDeflate). GSST provides a compression ratio of 2.7 4x and achieves a throughput of 191 GB/s on an A100 GPu.

AB - Most of the commonly used compression standards make use of some form of the LZ algorithm. Decompressing this type of data is not a good match for the Single-Instruction, Multiple Thread (SIMT) model of computation used by GPUs, resulting in low throughput and poor utilization of the GPU parallel compute capabilities. In this paper, we introduce GSST, a GPU-optimized version of the FSST compression algorithm, which targets string compression. The optimizations proposed in this paper make the algorithm particularly suitable for GPUs, which allows it to achieve a significantly better tradeoff for decompression throughput vs compression ratio as compared to the state of the art. Our results show that the new algorithm pushes the Pareto curve closer towards the ideal region, completely dominating LZ-based compressors in the nvCOMP library (LZ4, Snappy, GDeflate). GSST provides a compression ratio of 2.7 4x and achieves a throughput of 191 GB/s on an A100 GPu.

UR - https://www.scopus.com/pages/publications/105012770455

U2 - 10.1145/3759441.3759450

DO - 10.1145/3759441.3759450

M3 - Article

AN - SCOPUS:105012770455

SN - 0163-5980

VL - 59

SP - 55

EP - 61

JO - Operating Systems Review (ACM)

JF - Operating Systems Review (ACM)

IS - 1

ER -

GSST: Parallel string decompression at 191 GB/s on GPU

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this