随着GPU的发展,将通用的内存索引结构应用到GPU之上成为了一个新的研究方向。目前针对GPU优化的数据结构还比较少,特别地,现在只有很少的完全并发且可动态更新的内存索引结构能够适应GPU,并且没有充分发挥出GPU的并行加速能力。为此,本文将设计实现基于GPU的Hash索引结构。本文的工作内容有三点:1.对内存索引结构进行了综述与性能评估。在Masstree、Cuckoo hash table和Hopscotch hash table三种结构的单线程比较实验中,Masstree的内存使用率最好但性能较差,而Hopscotch hash table不仅内存使用率较好性能也是最优的;在 Masstree、Skip list、Cuckoo hash table 和 Hopscotch hash table 四种结构的并发版本中,Cuckoo hash table的性能最好。2.对一种基于GPU的静态Cuckoo hash table(CUDPP实现)进行了改进,采用warp协同工作共享策略,显著减少了 GPU程序的分支与发散。改进后的实现,在内存使用率较高且插入操作数量较多的情况下,可以获得更快的构建速度。3.提出并实现了基于GPU的完全并发且可动态更新的Hash索引结构一一GLHT(GPU lock-freeHopscotchhashtable)。GLHT 结合 warp 协同工作共享策略和高效的GPU内存合并访问,与现有的CPU Hopscotch hash table相比,具有4-9倍的性能优势;比采取预先分配内存的GPU Chained Hash table更加灵活,并且在写操作较多的工作负载中获得了更好的性能。