Dan Alcantara Inadequately caffeinated
>> Real-time Parallel Hashing on the GPU
Overview of our construction using a voxelized Lucy model, colored by mapping x, y, and z coordinates to red, green, and blue respectively (far left). The 3.5 million voxels (left) are inputted as 32-bit keys into our hash table. Keys are placed into buckets of ≤ 512 keys (center), averaging 409 per bucket. Each bucket then builds a cuckoo hash with three sub-tables and stores them in a larger structure with 5 million entries (right). The close-ups follow the progress of a single bucket, showing the keys allocated to it (center) and each of its completed cuckoo sub-tables (right). Finding any key requires checking only three possible locations.

Abstract

We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself, and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching.

Figures

Timings on random data, comparing hash table construction and retrieval versus radix sort and binary search. Retrievals search the structures for all of the inputted keys in randomized order. These timings were collected using CUDA 2.2.
Geometric hashing application. Although the images differ by a slight rotation, the picture in the upper left is found in the larger picture in the upper right by searching for the best affine transformation.
Boolean operators application. The two models in the center change every frame. As the models intersect, portions of each surface found to be in the opposite model are cut out or highlighted.

Poster

Shown at the NVIDIA GPU Technology Conference, 2009.

Publications

  • Dan A. Alcantara, Andrei Sharf, Fatemeh Abbasinejad, Shubhabrata Sengupta, Michael Mitzenmacher, John D. Owens, and Nina Amenta "Real-time Parallel Hashing on the GPU", ACM Transactions on Graphics (Proceedings of ACM SIGGRAPH Asia 2009)
    [ PDF ] [ MOV ] [ PPTX ]
You've stumbled upon the website of Dan Anthony Alcantara, a Ph.D candidate in the UC Davis Computer Science department. You are likely to be eaten by a grue.