CUDA LZSS

[Piotr Tarsa]

I've just stumbled upon a rather interesting project: http://homes.soic.indiana.edu/aozsoy/compression.html
I don't have a CUDA-enabled card unfortunately and I cannot access the GitHub repos (well, I think that they're hosted on private GitHub Enterprise instance).

Can somebody assess whether their results are impressive or not? Bulat?

They are talking also about decompression on GPGPU which makes it even more interesting.

[JangoFatXL]

Would be nice if that worked with OpenCL, so that ATI/AMD users were not excluded.

[encode]

I'm really skeptical about CUDA enabled LZSS. However, can somebody provide me that CUDA-LZSS executable to test it on my GTX 780 OC?

[Piotr Tarsa]

Skeptical about what? From what I understood, they are doing LZSS with either 128, 256 or 512 bytes sliding windows and entire input is divided into chunks so that each CUDA thread has its own chunk. So it definitely can work.

Problem is that it does have poor performance, I think. On page 177 (actually 8.) on http://homes.soic.indiana.edu/aozsoy...CS-journal.pdf there's table with performance summaries. CULZSS loses badly to GZIP when it comes to compression ratio. I wonder how CULZSS would compare to LZ4 on fastest setting. I think LZ4 would be both much faster and much stronger. And it's somewhat suspicious they're providing speed in Mbps instead of MBps.

[encode]

Skeptical about 512 byte window and some other aspects. Even jurassic LZSS' use 2..4 KB window. These days, 8..16 KB is essential minimum in my opinion. And of course I'm really confident with 32..128 KB window.
I believe CUDA is for BWT or tricky CM - computationally intense stuff.
Well, since LZSS bottlenecked mostly by memory access, fast DDR5 of GPU looks pretty attractive to me.
I hope Intel will add 128 MB of L4 cache with its Broadwell CPUs, according to specs, L4 can be accessed not only by iGPU, but by CPU as well. Such cache may hugely improve compression speed of existing compressors!

[nburns]

Parallel processing seems to work better when data flows are predictable. Lossless compression is obligated to be opportunistic and unpredictable. I could see it being efficient to produce some kind of 1:1 transform. I'm not sure if the BWT is a good example.

It probably shouldn't take as much memory to compute the BWT as it does now. It becomes compressible as you are sorting, so there should be a way to compress and sort at the same time (and still be fast).

[Kennon Conrad]

Parallel processing seems to work better when data flows are predictable. Lossless compression is obligated to be opportunistic and unpredictable. I could see it being efficient to produce some kind of 1:1 transform. I'm not sure if the BWT is a good example.

It probably shouldn't take as much memory to compute the BWT as it does now. It becomes compressible as you are sorting, so there should be a way to compress and sort at the same time (and still be fast).

Why the 1:1 limitation on the transformation?

[Piotr Tarsa]

I wonder why they say Huffman coding isn't well parallelizable. Firstly you do prefix sum on code lengths and then you have both offsets and codes so the problem becomes embarassingly parallel - at least for encoding.

For entropy coding to be parallelized on decoding you need to somehow find out some code length boundaries before actual decoding so you can start decoding from them. You can store the boundaries in some helper vector together with the compressed stream but that negates some or all of the space savings. There are, however, some self-synchronizing codes eg Fibonacci code.

[nburns]

I wonder why they say Huffman coding isn't well parallelizable. Firstly you do prefix sum on code lengths and then you have both offsets and codes so the problem becomes embarassingly parallel - at least for encoding.

How would you get the prefix sums without actually translating the symbols? By then, you'd have already done most of the work.

However, if you encoded blocks without respect to offsets, the most you'd have to do is shift by a few bits and copy the block into place. But, Huffman isn't exactly compute-intensive to begin with, so maybe the copying is most of the work.

[nburns]

Why the 1:1 limitation on the transformation?

I think you'd want the length of the output to be predictable based on only the length of the input, not its contents. If processor #2 needs too much information from processor #1, the parallelism is lost. 1:1 wouldn't be an absolute requirement for parallelism in general. For lossless compression, the transform could not guarantee to take any less than equal space.

[Piotr Tarsa]

What do you mean by "translating"? Assuming you have a table which maps a symbol to code length it's trivial to map symbol to its code length After that mapping you do prefix sum.

However, if you encoded blocks without respect to offsets, the most you'd have to do is shift by a few bits and copy the block into place. But, Huffman isn't exactly compute-intensive to begin with, so maybe the copying is most of the work.

Even if you first split by blocks, you need to compute prefix sum on blocks sizes.


Most of work in Huffman encoding is IMO computing the actual codes (not only code lengths), shifting them and inserting into bitstream.

[nburns]

What do you mean by "translating"? Assuming you have a table which maps a symbol to code length it's trivial to map symbol to its code length After that mapping you do prefix sum.


Even if you first split by blocks, you need to compute prefix sum on blocks sizes.

You don't just need to map symbols to code lengths, you also have to know exactly which symbols are in a particular prefix. By the time you add that up, maybe you've already blown the speedup?

Most of work in Huffman encoding is IMO computing the actual codes (not only code lengths), shifting them and inserting into bitstream.

Isn't that all of the work? What else is there?

[Kennon Conrad]

I think you'd want the length of the output to be predictable based on only the length of the input, not its contents. If processor #2 needs too much information from processor #1, the parallelism is lost. 1:1 wouldn't be an absolute requirement for parallelism in general. For lossless compression, the transform could not guarantee to take any less than equal space.

Yes, but if you want the length of output to be predictable based on only the length of the input, how can compression be performed in parallel with sorting since it is not possible to always predict an output that is shorter than the input?

I think Piotr's point is that the computation of the sum of the code lengths for a block of data takes much less time than generating the bitstream. If this is done in advance, the bitstreams can be processed in parallel, which would save more time than the pre-calculation of the output size of each block costs. Piotr didn't mention it, but the sizes of the blocks could also be calculated in parallel.

[nburns]

Yes, but if you want the length of output to be predictable based on only the length of the input, how can compression be performed in parallel with sorting since it is not possible to always predict an output that is shorter than the input?

I meant that compressing while sorting could make it faster on a regular CPU. You don't have to resort to parallel processing unless you're out of ideas for major improvements serially.

I think Piotr's point is that the computation of the sum of the code lengths for a block of data takes much less time than generating the bitstream.

Does it?

If this is done in advance, the bitstreams can be processed in parallel, which would save more time than the pre-calculation of the output size of each block costs. Piotr didn't mention it, but the sizes of the blocks could also be calculated in parallel.

[Piotr Tarsa]

Prefix sum on code lengths shouldn't be much slower than eg prefix sum on symbols values (ie verbatim input). After all, it's just one LUT access, and whole LUT can reside in fast caches.

Prefix sum algorithms are now highly tuned and known to run crazy fast on GPUs. Look:
- http://http.developer.nvidia.com/GPU...ems3_ch39.html (20x speedup, 8800 GTX vs single core of Core 2 Duo Extreme),
- http://nvlabs.github.io/cub/ (prefix scan -> tens of bilions of elements per second for prefix scan),
- http://nvlabs.github.io/moderngpu/scan.html (prefix scan with throughput of hundreds of gigabytes),

[nburns]

Piotr: maybe Huffman can be sped up on a GPU. You said it couldn't. I was just speculating on why.

[Piotr Tarsa]

Did I?

I wonder why they say Huffman coding isn't well parallelizable. Firstly you do prefix sum on code lengths and then you have both offsets and codes so the problem becomes embarassingly parallel - at least for encoding.

I think it's clear enough, unless my English is bad.

[Kennon Conrad]

I meant that compressing while sorting could make it faster on a regular CPU. You don't have to resort to parallel processing unless you're out of ideas for major improvements serially.

Then you have me confused. I do not know how you can compress while sorting and maintain a 1:1 input to output size ratio.

Personally, I am more interested in using multiple processors serially and on locally parallelizable processes. For instance, one to get the code lengths and another to generate the codes from the code lengths, or to run multiple processors to update context maps. I think you could do some pretty amazing things with FPGAs.

Does it?

In my experience, yes. YMMV.

[nburns]

Did I?

I think it's clear enough, unless my English is bad.

I was speculating on why "they" say Huffman coding isn't parallelizable.

[nburns]

Then you have me confused. I do not know how you can compress while sorting and maintain a 1:1 input to output size ratio.

They're two different scenarios. 1:1 is if you are using a GPU. Compressing while sorting is if you are using a regular single-threaded CPU.

[Kennon Conrad]

They're two different scenarios. 1:1 is if you are using a GPU. Compressing while sorting is if you are using a regular single-threaded CPU.

Ok. That's not nearly as interesting to me as a multi threaded sort and compress.