Compression of binary arrays to overcome GPU memory limitations

user_14210056 0
Viewed 192

I'm working on physical simulations on the GPU (CUDA) and struggling with the limited amount of available memory on standard graphic cards.

The problem is as follow:

I have a huge binary mask (> 30 GByte) which serves as a lookup table. To evaluate the validity of a specific variable I generate an index from the variable properties and check against the lookup table. This is done in parallel on the GPU for millions of variables simultaneously (only read access required).

To minimize the size of this binary mask to fit it into GPU memory I'm looking for compression techniques that still allow fast access by indexing the underlying data (best by a transparent container class who takes care about everything). Since the mask itself contains multiple repetitions of single bits, I would also expect that it is possible to achieve a high compression ratio.

So my question is:

Is there any known approach already available in nvidia's CUDA implementation OR is there any other default c++ library which can do the trick?

mask cuda compression binary c++
1 Answers

Run-Length Encoding

I don't know of any library that does this for you, but I can provide you with an idea of how to do this. Since your mask contains many repetitions of the same bit, a suitable approach would be Run-Length Encoding (RLE). The idea is that instead of encoding individual bytes, you encode the byte and its length:

aaabbbababaaaaaaaa -> 3a,3b,1a,1b,1a,1b,6a

There are many ways to implement this in practice. I am working on voxel model compression and the approach that has worked best for me is to use the bytes 0x00 and 0xff as escape sequences. So [0x00, N] encodes N zero-bytes, [0xff, N] encodes N one-filled-bytes. The remaining bytes stay uncompressed. Alternatively you could just use DEFLATE compression using zlib, I am sure there is a GPU implementation of this too.

Obtaining O(1) Random Access

The problem with any kind of compression technique is that it reduces data to a variable size, making random access impossible. To solve this, you would have to compress the data in blocks of say, 1024 bytes. You could then store a table of pointers to the start of each block, allowing you random access.

The obvious issue is that you can only keep one block at a time uncompressed and each time you access a different block, you need to decompress that too. This can be very expensive.

Settling for O(log n) Random Access

Another technique is to compress the data as an octal tree. The eight bits of a byte at a higher level represent which of the lower-level eight bytes exist and which don't.

      0       0         1      1        // Higher-level bitmask representing
     /        |         |       \       // which bytes exist.
0000.0000 0000.0000 0010.1111 1111.1111 // Lower-level bytes.

Here, a 1 represents an existing subtree, a 0 represents a missing subtree. We can optimize this tree down to just:

      0       0         1      1
                        |       \
                     0010.1111 1111.1111

A zero-bit at a higher level represents all-zero data at a lower level, so we can just optimize those lower levels away. By arranging our data in a tree like this, we can access any bit randomly with O(log n) complexity. The advantage of this technique is that we have a lot of neighboring ones or zeros, those will get optimized away and turned into a single bit at some higher level.

Note that we can also optimize subtrees that are all-one as well. For that, we use the mask of 0x00 at a higher level. The 0x00 mask does not naturally occur, because it would have been optimized away as a single zero-bit at a higher level. So we can assign some special meaning to it.

user_57404280
Related