An Improved Dynamic Hash Table on GPU with Configurable on-Chip Memory

Hash tables are crucial data structures used for efficient storage and retrieval of data, finding wide applications in various domains such as computer graphics, machine learning, traffic tracking, and database queries. The main objective of this paper is to implement a dynamic hash table that achieves high throughput and operates in parallel. We propose a technique for data-parallel hashing using graphics processing units (GPU) and improve upon the dynamic hash table by leveraging the configurable on-chip memory on GPU. This approach enables high-throughput data insertion, search, and deletion while adhering to the real-world 80/20 rule. We utilize the programming techniques provided by NVIDIA CUDA, minimizing memory access through well-designed data structures. Atomic operations ensure the absence of race conditions, and cooperative groups maximize the utilization of GPU threads, achieving optimal parallel computation. The GPU executes hash table operations in parallel by employing the SIMT (Single Instruction, Multiple Threads) mechanism. Furthermore, we enhance existing data-parallel hashing techniques on GPU to address the challenge of decreasing throughput when the same keys are frequently updated in the hash table. Our architecture significantly improves upon this issue and efficiently handles scenarios in which 20% of elements occupy 80% of the frequency in the real world, even in cases of frequent duplicate key insertions or updates. Additionally, we adopt the LRU (Least Recently Used) approach to keep frequently queried data in the configurable on-chip memory, ensuring that important and frequently requested information is readily accessible. According to the experimental results, our proposed method, under the real-world 80/20 rule, achieves an 82.64 times improvement in insertion throughput compared to the state-of-the-art parallel hashing techniques on GPU. Also, the search throughput is increased by 5 to 8%.