Abstract:

In order to improve the insertion performance of linear Hash table known as an effective index structure,the existing insertion methods are analyzed,and a linear Hash table GBLHT with batch records insertion,which is combined with the CUDA parallel programming model,is designed and implemented. With the help of the atomic function atomicAdd,GBLHT takes full advantage of the high parallel throughput of graphic processing unit ( GPU) to implement the lock-free batch insertion of massive records. Some experiments are then carried out to compare the insertion performances of the traditional serial insertion method,the CPU-based batch insertion method and GBLHT. The results show that,under various parameter conditions,the insertion performance of GBLHT is 7~14 times higher than that of the traditional serial method,and is 3~6 times higher than that of the CPU-based batch insertion method with four threads.

Key words: linear Hash table, graphics processor, general-purpose computing on GPU, lock-free batch insertion, in-memory data index structure, atomic function atomicAdd