A Dynamic Hash Table for the GPU
A Dynamic Hash Table for the GPU
复制标题
DOI：
10.1109/ipdps.2018.00052
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Saman Ashkiani;Martín Farach-Colton;John Douglas Owens
中科院分区：
文献类型：
--
作者：
Saman Ashkiani;Martín Farach-Colton;John Douglas Owens
我们设计并实现了一个完全并发的动态哈希表的GPU具有可比的性能，最先进的静态哈希表。我们提出了一个warp合作的工作共享策略，减少分支分歧，并提供了一个有效的替代传统的方式，每线程（或每warp）的工作分配和处理。通过使用这种策略，我们建立了一个动态的非阻塞并发链表，板列表，支持异步，并发更新（插入和删除），以及搜索查询。我们使用slab list来实现一个带链接的动态哈希表（slab hash）。在NVIDIA Tesla K40 c GPU上，slab hash以高达512 M更新/s的速度执行更新，并以高达937 M查询/s的速度处理搜索查询。我们还设计了一个翘曲同步的动态内存分配器，SlabAlloc，适合的slab哈希的高性能需求。SlabAlloc以600 M分配/s的速率动态分配内存，这比类似场景中的替代方法快37倍。
We design and implement a fully concurrent dynamic hash table for GPUs with comparable performance to the state of the art static hash tables. We propose a warp-cooperative work sharing strategy that reduces branch divergence and provides an efficient alternative to the traditional way of per-thread (or per-warp) work assignment and processing. By using this strategy, we build a dynamic non-blocking concurrent linked list, the slab list, that supports asynchronous, concurrent updates (insertions and deletions) as well as search queries. We use the slab list to implement a dynamic hash table with chaining (the slab hash). On an NVIDIA Tesla K40c GPU, the slab hash performs updates with up to 512 M updates/s and processes search queries with up to 937 M queries/s. We also design a warp-synchronous dynamic memory allocator, SlabAlloc, that suits the high performance needs of the slab hash. SlabAlloc dynamically allocates memory at a rate of 600 M allocations/s, which is up to 37x faster than alternative methods in similar scenarios.