Wanted: description of the algorithm (and complexity w.r.t. collisions)

[dumerrill]

This is very cool! I was wondering if you could add a brief description of how the algorithm works to the readme mainpage. There are so many alternatives in the source that are macro-enabled/disabled, it's really hard to tell what's going on. Specifically, I'd really like to hear how you implement the 4x 8b (4-channel RGBA) histogram. Privatized counters in shared memory? Shared memory atomics? Hand-rolled exclusive read-modify-write in shared memory using naming collisions? Some other weird hashing variant?

Thanks!

Duane

[bryancatanzaro]

I second Duane's request - also it'd be great if you could put some benchmark results on the webpage, so people know what kind of performance you provide. For example, you could graph throughput (GB/s histogrammed) versus input size for several data types and histogram types.

[trantalaiho]

Will do,

The implementation of 4-channel RGBA 8bit histogram is a bit embarrassing: The best way to do it (at least at the moment) is to do 4 passes of a 256-bin 8-bit histogram over the data. The reason is that the histogram problem is not actually one big 1024-bin histogram, but can be viewed as four separate problems, due to the fact that we always know the bin-range where the values of each channel will land.

Some benchmark-figures are available in the wiki-page: https://github.com/trantalaiho/Cuda-Histogram/wiki ,
but these are only for Tesla M2070 with ECC on, which I'm told skews the results quite a lot - the machines I'm using won't allow me to switch ECC off for testing purposes.

Short description of the algorithms coming soon though, hence assigning issue to me.

[trantalaiho]

Just updated the readme with requested information - is this enough information for now? The code itself is a tad messy (semi-hobby project), but I'll try to clean it up some time.