Design And Implementation Of Hash Index Structure Based On GPU

With the development of GPU,applying common in-memory index structures to GPU has become a new research direction.At present,the number of data structures for GPU optimization is still relatively small.In particular,only a few fully concurrent and dynamically updatable in-memory index structures are'now adaptable to GPU and do not give full play to the GPU's parallel acceleration capabilities.To this end,this article will be designed to achieve a new Hash index structure based on GPU.The work of this article has three points:1.Summarized the in-memory index structures and carried out performance evaluations on them.In the single-thread experiments of Masstree,Cuckoo hash table and Hopscotch hash table,Masstree has the best memory usage but poor performance;Hopscotch hash table not only has good memory usage but also best performance.Cuckoo hash table has the best performance among the concurrent versions of Masstree,Skip list,Cuckoo hash table and Hopscotch hash table.2.Improved a GPU-based static Cuckoo hash table(CUDPP implementation).The improved implementation uses warp-cooperative work sharing strategy which significantly reduced the branching and divergence of GPU programs.It allows for faster build rate under the situation of higher memory usage and larger number of insert operations.3.Implemented GPU-based fully concurrent and dynamically updatable Hash index structure-GLHT(GPU lock-free Hopscotch hash table).GLHT combines warp-cooperative work sharing strategy and efficient coalesced access of GPU memory.GLHT has a 4-9x performance advantage over the existing CPU Hopscotch hash table.GLHT is more flexible than GPU Chained Hash table with pre-allocated memory and has better performance in write-weighted workloads.