Building an Efficient Hash Table on the GPU

摘要: Publisher Summary This chapter describes a straightforward algorithm for parallel hash table construction on the graphical processing unit (GPU). It constructs in global memory and use atomic operations to detect resolve collisions. Construction retrieval performance are limited almost entirely by time required these uncoalesced accesses, which linear total number of accesses; so design goal is minimize average accesses per insertion or lookup. In fact, it guarantees constant worst-case bound Further, one alternative using store data sorted array access via binary search. Sorted arrays can be built very quickly radix sort because pattern localized, allowing GPU coalesce many reduce their cost significantly. However, search, incurs as lg ( N) probes worst case, much less efficient than tables useful interactive graphics applications, where they used sparse spatial data—usually 3D models that voxelized uniform grid. Rather entire voxel grid, mostly empty, hold just occupied voxels.