DACHash: A Dynamic, Cache-Aware and Concurrent Hash Table on GPUs

• Hao Zhou University of Mississippi
• David Troendle University of Mississippi
• Byunghyun Jang University of Mississippi

Resumo

GPU acceleration of hash tables in high-volume transaction applications such as computational geometry and bio-informatics are emerging. Recently, several hash table designs have been proposed on GPUs, but our analysis shows that they still do not adequately factor in several important aspects of a GPU's execution environment, leaving large room for further optimization. To that end, we present a dynamic, cache-aware, concurrent hash table named DACHash. It is specifically designed to improve memory efficiency and reduce thread divergence on GPUs. We propose several novel techniques including a GPU-friendly data structure & sizing, a reorder algorithm, and dynamic thread-data mapping schemes that make the operations of hash table more amendable to GPU architecture. Testing DACHash on an NVIDIA GTX 3090 achieves a peak performance of 8.65 billion queries/second in static searching and 5.54 billion operations/second in concurrent operation execution. It outperforms the state-of-the-art SlabHash by 41.53% and 19.92% respectively. We also verify that our proposed technique improves L2 cache bandwidth and L2 cache hit rate by 9.18× and 2.68× respectively.

Palavras-chave: Computational geometry, Visualization, Heuristic algorithms, Instruction sets, Memory management, Graphics processing units, Bandwidth, hash table, GPGPU, concurrent data structure