Lock-free Concurrent Hash Tables and Parallel Dynamic Programming on the GPU

We study how to best make use of the a GPU to implement lock-free concurrent hash tables, and on top of that highly parallel dynamic programming. We show that the right hash table can be remarkably effectively parallelized when implemented on a GPU wth a $55\times$ speedup over a single thread on the same GPU. More importantly the GPU implementation is around $7.0\times$ better than on a competitive multi-core CPU, showing that we can take advantage of the massive parallelism of the GPU even with its much slower thread computation. We also examine the use of the hash table for a dynamic programming application. Here the GPU is not as advantageous over the CPU but by adding more speculative computation the GPU becomes the superior choice.