multi count ?

[Viewon01]

I'm currently trying to implement a multi-count algorithm. So, I
explain :

I have a dataset with 'int' values where the first byte is a key
(1,2,4,8,16 are possibles values).

So, I need to sort the data set but also being able to 'count' the
number of instances for each key.

I'm currently trying, a simple count can be done with a 'local
counting' and then a scan.

But for multi-count (in one scan only) it is more difficult, mainly
due to local memory allocation constraints !

So, if you know a papers/algorithm about this, I'm very interested.

Thx

Krys

BTW: I have commit the 'count' algorithm. It is not tested but
contains 99% of the logic !

[Rick Weber]

Have each work group work on part of the total array. You have a NumThreads * NumKeys block of local memory initialized to zero. Each thread increments their counters based on what they read from global memory. When each thread in a work group has read all the elements they're going to read, reduce the partial results into a single set of counters for that work group. Then, atomically add to global counters.

So long as the size of the array pieces each work group works on is largish, the frequency of atomic global operations is pretty low, so you don't get too much performance loss.

-Rick

[Viewon01]

Thanks a lot Rick,

Finally there is a simple solution.

- Sort the array
- Found the position where the keys are differents

I have implemented it and it works like a charms ;-)

BTW: it is not implemented, maybe I will remove it from CLPP.