支持分页显存的高性能哈希表索引系统
支持分页显存的高性能哈希表索引系统
复制标题
DOI：
10.15888/j.cnki.csa.008664
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
武延军
中科院分区：
文献类型：
--
作者：
熊轶翔;蒋筱斌;张珩;武延军
哈希表以访问效率时间复杂度 O(1) 著称, 作为一类可提供大规模数据高效访问的算法和数据结构为各类 大数据应用所采用, 例如, 适用于各类新兴高性能 (HPC) 领域、数据库领域的工作负载和场景. 随着高性能协处理 器 GPU 硬件性能的日益提升, 面向高性能 GPU 环境的哈希表并行优化已逐渐吸引了大量研究工作. 当前的各类 GPU 哈希表优化方法和解决方案集中于利用 GPU 的大规模线程环境和高内存带宽来提升哈希表的事务高并发性 处理和键值对数据快速访问. 然而, 由于现有 GPU 哈希表结构的研究工作普遍忽略了 GPU 资源有效管理, 并没有 以如何充分利用 GPU 线程资源和显存资源. 同时, 由于 GPU 显存空间的大小限制, 用于存储哈希表结构数据的空 间有限, 无法应对更大规模的哈希表结构. 因此, 面向 GPU 环境下的哈希表方法的可扩展性和性能仍存在着技术挑 战. 本文提出并设计了一种面向 GPU 环境的可处理大规模并发事务的哈希表技术, 命名为 Starfish. Starfish 提出了 新的基于异步 GPU 流的“交换层” (swap layer) 技术, 用以支持 GPU 显存外的动态哈希表, 同时也保障了 GPU 哈希 表的索引方法性能. 为了解决 GPU 大规模线程的访问带来的哈希冲突开销, Starfish 设计了一类紧凑型数据结构, 并研究了一种可分页显存的分配方法, 不仅为 GPU 哈希表技术提供了静态哈希方法的高性能, 而且也支持动态哈 希的高可扩展性. 性能评估实验表明, Starfish 显著优于其他 GPU 哈希表技术, 包括 cudpp-Hash, SlabHash.