CUDA/OpenCL compressing/decompressing algorithm execution about zstd

[Cyan4973]

You're very welcomed Artyom.

There are limits to what can be done in parallel.

Basically, compressing / decompressing a block involves 2 parts :

• Match Copy
• Entropy Coding

For the time being, entropy coding is completely independent within each block (this could change in the future). That means it's possible to encode / decode this stage within multiple blocks in parallel, store the result, and make it available to the next stage.

Unfortunately, Match Copy is not so kind. Especially during the decompression stage, decompressing a block requires access to previous blocks, which must therefore be already decoded. Serial in nature.

Going around this limitation would require independent blocks.
This is a valid use case btw : in many data structures, random access is important, so blocks are independent and tiny.

Small independent blocks hurt compression badly though. A mitigation solution is to use a shared dictionary, a kind of "static prefix" which is going to be used for all blocks. All block operations remain independent, and thus can be parallelized.

As one can guess, it's a pretty advanced topic. I believe a bit more work is required to get there.

In the meantime, if you are interested in challenging your CUDA skills, I can only invite you to try compressing / decompressing small independent blocks. It's going to be pretty difficult already, and will require you to get a good understanding of zstd internals.

[tomByrer]

When I was doing audio DSP programming, I found CUDA only helped in some scenarios, when processing savings was worth the data transfer costs. Usually I found SSE optimizations easier & less friction.

[Cyan4973]

Should we keep this issue opened ?
Any new item in the foreseeable future ?

[mailagentrus]

Close this issue, please. It is impossible to integrate cuda support for the foreseeable future...