How to create Large Bit array in cuda?

Question

I need to keep track of around 10000 elements of an array in my algorithm .So for this I need boolean for each record.If I used char array to keep track of 10000 arrays (as 0/1),it would take up lot of memory.

So Can I create an bit array of 10000 bits in Cuda where each bit represents corresponding array record?

Horizon

Answer 1

As Roger said, the answer is yes, CUDA provides the same bitwise operations (i.e. >>, << and &) as normal C so you can implement your bit array essentially normally (almost, see thread synchronisation issues below).

---

However, for your situation it is almost certainly not a good idea.

There are problems with thread syncronisation. Imagine two of the threads on your GPU are inverting two bits of a single entry of your array. Each thread will read the same value out of memory, and apply their operation to it, but the thread that writes its value back to memory last will overwrite the result of the other thread. (Note: if your bit array is not being modified by the GPU code then this isn't a problem.)

And, unless this is explicitly required, you shouldn't be optimising for memory use, an array with 10K elements does not take much memory at all: even if you were storing each boolean in an 64 bit integer it's only 80 KB. And obviously you can store them in a smaller datatype. (You should only start worrying about compressing the array as much as possible when you are getting upwards of tens of millions, or even hundreds of millions of elements.)

Also, the way GPUs work means that you might get best performance by using a reasonably large data type for each boolean (most likely a 32 bit one) so that, for example, memory coalescing works better. (I haven't tested this assertion, you would need to run some benchmarks to check it.)

Furtek

Actually, the main decision in deciding how to store the booleans should be based on if the task is compute bound or memory bound. If it is memory bound, there can be a tremendous benefit in storing one bit per bit, at least for reads. Writing is tricky though, as you mentioned. At least on Fermi, there is no point in storing more than one byte per bit for a read/write array -- it just requires more memory transactions. For a read-only array, I would store one bit per bit. – Fumarole