Gpu methods to locate unique IDs

Hi,

I am just looking for some ideas to solve this problem on gpu with matlab.

There is a 2 x N vector. Row 1 has N has Ids which can be duplicate. Row 2 has corresponding numerical values. I need to sum all the values for which there is a unique column ID.

Input : [1 1 1 2 2 3 3; 10 11 12 13 14 15 16] Output : [1 2 3; 33 27 31]

A vectorized solution of this on a GPU I am guessing would be the fastest

Any suggestions would be greatly appreciated.

Thanks

Answer 1

[Jan]

Start with an implementation on the CPU using accumarray.

Then decide, if the index vector is dense, this means if it contains values from 1 to N, which are all positive integers without larger gaps. Then it is much faster to accumulate the values using them as indixes. In this case a C-Mex function might be very efficient.

[EssGee]

Thanks Jan,

As you suggest, a CUDA kernel may be the only fast solution. I am not sure how to do this efficiently with bsxfun or arrayfun.

[Jan]

Please explain, if the IDs are "dense" positive integers. I'm not convinced, that this is most efficient on the GPU. How large is the array?

[EssGee]

Yes the IDs are positive integers, with no gaps. I am also not very sure that this a GPU problem. However most of the calculations leading up to this operations were on the GPU. so transferring the data out of the GPU just for this would be a big overhead.