Abstract
In this paper, we propose a hybrid CPU+GPU data structure, that optimizes search operation for frequently accessed search keys. This is based on the working-set structure due to Badiu et al. [1]. The main idea is to maintain a dynamic set of most frequently accessed keys in the GPU memory and the rest of the keys in the CPU main memory. Further, search queries are processed in batches of size 1K to 16K (K = 210). We measured the query throughput of our data structure using Millions of Queries Processed per Second (MQPS) as a metric, on different key access distributions. On distributions, where some keys are accessed more frequently than others, we achieved 2x higher MQPS when compared to a highly tuned hash map provided by C++ BOOST library, and 1.5x higher MQPS against the B+ tree implementation in the Rodinia GPU benchmark. We further showed the effectiveness of our structure, when it is used to store visited vertices information in breadth-first search traversal of graphs. Here, we achieved 1.2x and 1.5x speedups when compared to the BOOST hash map and the GPU B+ trees respectively.