Seeking lossless compression algorithm suitable for massively parallel device

[boxerab]

I am working on an OpenCL application that is bandwidth starved. I am looking for ways
of increasing bandwidth, and one of them is to store my data losslessly in memory and
decompress on the fly when I need to access it. On a GPU, typically one can get 30 ALU operations
for each memory access. So, assuming 2:1 lossless compression ratio, if compress/decompress can be done
in less than 60 ALU ops, this is a win for my application.

Can anyone recommend a suitable technique? Thanks!

[just a worm]

A compression algorithm is always made for a specific form of redundancy. For a good advice we probably need to know the redundancy your data has. Maybe your data has even several forms of redundancy. Knowing them would give us the possibility to think about which algorithms are good to remove the redundancy with parallel processing.

For example if your data has a redundancy in the form that certain values occure more often than others and every value can be stored with 1 byte of space, then you could use a variable length encoding. You could make a parallel look up of each byte and replace it with a value of a variable length in bits. Something like this would be suitable if low values occure very often and high values nearly never:

0000 0000 -> 0
0000 0001 -> 10
0000 0010 -> 110
0000 0011 -> 1110
...

[boxerab]

Thanks, I need to think about how to characterize the redundancy.

[Lucas]

Actually I wrote a tool a few months ago that might help you. It does some fancy calculations to determine (a rough estimate of) the maximum compression of a file.
It's got a simple UI, just select the file you want to process. Hope this helps!
https://drive.google.com/file/d/0B8goYrnGwKGCX1hBeWZTQWN2cXc/view?usp=sharing


The only bug with it is that the unique char count is off by 4 when the count is 256 or higher. Not quite sure why. But it is fairly accurate overall.

[boxerab]

Actually I wrote a tool a few months ago that might help you. It does some fancy calculations to determine (a rough estimate of) the maximum compression of a file.
It's got a simple UI, just select the file you want to process. Hope this helps!
https://drive.google.com/file/d/0B8goYrnGwKGCX1hBeWZTQWN2cXc/view?usp=sharing


The only bug with it is that the unique char count is off by 4 when the count is 256 or higher. Not quite sure why. But it is fairly accurate overall.

Thanks for mentioning this. In my case, I should be able to analyze the compress-ability theoretically, based on how I am generating the data.