基于GPU的可扩展哈希方法  

Extendible Hashing Method Based on GPU

作　　者：胡学萱[1] 奚建清[2] 林妙[2] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510006 [2]华南理工大学软件学院,广东广州510006

出　　处：《华南理工大学学报（自然科学版）》2015年第1期111-117,共7页Journal of South China University of Technology(Natural Science Edition)

基　　金：广东省战略性新兴产业核心技术攻关项目(2011A010801008;2012A010701011;2012A010701003);广州市科技计划项目(201200000034)~~

摘　　要：为了使用可扩展哈希表进行快速的数据访问,需要高效地更新索引以维护哈希表.文中提出了一种基于GPU的可扩展哈希算法g EHT.该算法充分利用GPU的并行计算能力,并采用表重用、预分裂技术,无锁地扩展和收缩表、插入和删除数据,实现了高并发地创建哈希表、更新索引和检索数据.实验结果表明,该算法的查询数据、维护哈希表和更新索引性能优于其他多核CPU的线性哈希及可扩展哈希算法,尤其是在高负载的情况下.In order to use an extended hash table for fast data accessing, an efficient index updating to maintain the hash table is necessary. Proposed in this his paper is a GPU-based extendible hashing algorithm named gEHT, which takes full advantage of GPU＇s parallel computing power, and adopts list reuse as well as pre-split technology to extend and merge lists and to insert and delete data in a lock-free manner. Thus, high levels of concurrency for hash table creation, index updating and data retrieval are realized. Experimental results show that gEHT is superior to some other linear hashing and extendible hashing algorithms on the basis of multi-core CPU in terms of querying data, maintaining hash table and updating index, especially in the case of heavy load.

关 键 词：可扩展哈希 并行计算 GPU 算法 多核CPU 

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]