SIGGRAPH article

The "final version" of our SIGGRAPH Asia paper, Real-Time Parallel Hashing on the GPU, is available here.

I was primarily involved in the "hash table construction" part of the paper. The ideas there are familiar in various works (though I don't know of another parallel implementation of cuckoo hashing); the question is how to put pieces together for performance on this architecture. We end up using a 2-level scheme; first hash the items into (1st-level) buckets, with a limited number (512) of items per bucket. Then (2nd level) for each bucket the items are placed in parallel in a cuckoo hash table, using up to 512 thread (one per item) and fast memory for each bucket. Then everything is copied out to global memory. The comparison point, for applications, is sorting/binary search; sorting has been highly optimized for parallel processors. Generally, we come out about even on the construction times, and much better on the lookup times.

The cool stuff is the applications my co-authors tested with the hash table. They use it to compute real-time intersections of surfaces, and for matching of objects (buildings, etc.) to video frames. The accompanying video explains it all better than I could here (picture, thousand words, all that). Since my co-authors did all the work on the applications end, I think I'm allowed to say I'm impressed with the results -- graphics applications just look really great.

The "structure" of the paper reminds me of networking papers I've been involved with. Here's an algorithm/data structure, and here are 1-3 applications to show you what it can really do. This last part is usually a lot of work, since you have to embed the algorithm/data structure into a real system, with many moving parts beyond the algorithm/data structure you're promoting. Getting things to work is always a challenge (which is why simulation is so popular -- and, in many settings, discouraged).

I'm very excited about continuing to do more in this area, and that's due entirely to the amazing abilities of my co-authors: Dan A. Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, John D. Owens, and Nina Amenta.