各领域发展的需求,二是 GPU 自身的发展,利用 GPU 快速构建哈希表及查询数据具有必要性,所以本文将讨论实现各类哈希表在 GPU 上的构建并拓展其应用。 1.2 国内外研究现状本节分为两部分:一是简要概述近年来在 GPU 上取得的研究成果以及 GPU 研究方向的转变;二是着重概述利用开地址法、链地址法以及杜鹃哈希法串行和并行构建哈希表的发展,并把工作重心集中于 GPU 上讨论。 GPU 上取得成果及发展方向 2007 年6月,NVIDIA 推出的 CUDA 引发了 GPU 通用计算的革命,这样 GPU 的含义也可能从图形处理器(Graphic Processing Unit )扩展为通用处理器(General Purpose Unit )。近几年利用 GPU 通用计算提升性能取得了广泛应用,例如, Kruger [1]在GPU 上进行了线性代数的运算,实现了矩阵和向量运算; Falcao [2]用 GPU 对LDPC 纠错码进行加速,这个性能的提升使得 LDPC 码的应用不需特定的解码硬件器; Curry [3]利用 GPU 来增强 RAID 系统可靠性,证明了 GPU 可以加速 Reed-Solomon ;Sudipta N.Sinha [4]等人利用 GPU 实现视频 SIFT 特征检测;以及应用于加速图像处理[5]、视频编解码[6]、网络安全[7]、模式识别[8]等领域。但在 GPU 上运用的数据结构,大多数是通过在 CPU 端进行构造,然后通过 GPU 进行加速并行应用,随着 GPU 计算能力增强,近来可以直接在 GPU 上通过并行建造算法建造这些数据结构,如 Zhou [9][10] 在GPU 上快速地构造八叉树并允许交互式曲面的创建和变形,以及在 GPU 上实时建造 KD树,应用于光线跟踪;D.Merrill [11]实现了基于 GPU 的基数排序高度并行。
全文预览
