Results 1 to 5 of 5

Thread: Seeking lossless compression algorithm suitable for massively parallel device

  1. #1
    Member
    Join Date
    May 2014
    Location
    Canada
    Posts
    141
    Thanks
    71
    Thanked 21 Times in 12 Posts

    Seeking lossless compression algorithm suitable for massively parallel device

    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!

  2. #2
    Member just a worm's Avatar
    Join Date
    Aug 2013
    Location
    planet "earth"
    Posts
    96
    Thanks
    29
    Thanked 6 Times in 5 Posts
    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:
    Code:
    0000 0000 -> 0
    0000 0001 -> 10
    0000 0010 -> 110
    0000 0011 -> 1110
    ...
    Last edited by just a worm; 1st September 2015 at 20:39.

  3. #3
    Member
    Join Date
    May 2014
    Location
    Canada
    Posts
    141
    Thanks
    71
    Thanked 21 Times in 12 Posts
    Thanks, I need to think about how to characterize the redundancy.

  4. #4
    Member
    Join Date
    Feb 2015
    Location
    United Kingdom
    Posts
    171
    Thanks
    28
    Thanked 73 Times in 43 Posts
    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.
    Last edited by Lucas; 1st September 2015 at 04:15. Reason: included bug notice

  5. #5
    Member
    Join Date
    May 2014
    Location
    Canada
    Posts
    141
    Thanks
    71
    Thanked 21 Times in 12 Posts
    Quote Originally Posted by Lucas View Post
    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.

Similar Threads

  1. Replies: 23
    Last Post: 24th March 2018, 17:57
  2. Looking for parallel algorithm for MQ coder
    By boxerab in forum Data Compression
    Replies: 1
    Last Post: 11th January 2015, 02:50
  3. Replies: 33
    Last Post: 27th August 2011, 05:13
  4. parallel compression with batches
    By evg in forum Data Compression
    Replies: 4
    Last Post: 17th September 2009, 18:14
  5. Best decompression on embedded device
    By ikes in forum Data Compression
    Replies: 7
    Last Post: 16th February 2009, 21:05

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •