GBLHT:一種GPU加速的批量插入線性哈希表*

黃玉龍 奚建清 張平健 方曉霖 劉勇

(1.華南理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，廣東廣州510006;2.華南理工大學(xué)軟件學(xué)院，廣東廣州510006)

近年來，利用GPU強(qiáng)大的并行計算吞吐量加速通用計算［1］已成為并行計算領(lǐng)域的發(fā)展趨勢.與CPU相比，GPU無論在計算性能還是存儲器帶寬方面都具有明顯優(yōu)勢［2］，從而成為大規(guī)模并行應(yīng)用的首選.CUDA［3］是NVIDIA開發(fā)的一種編程架構(gòu)，它允許編程人員方便地開發(fā)基于GPU的并行程序.目前，在數(shù)據(jù)庫領(lǐng)域，越來越多的研究人員利用GPU加速排序、聚集、關(guān)系連接等操作［1］，取得了很好的效果.

隨著大規(guī)模數(shù)據(jù)駐留在內(nèi)存，使用GPU加速內(nèi)存數(shù)據(jù)檢索受到了越來越多的關(guān)注［4］.在傳統(tǒng)內(nèi)存索引結(jié)構(gòu)中，線性哈希表是一種非常有效的結(jié)構(gòu)［5-7］，它在實(shí)現(xiàn)快速存取以及檢索的同時，可以優(yōu)雅地擴(kuò)展存儲空間.為改善其操作性能，Ellis［8］、陳虎等［9-10］分別提出了基于加鎖協(xié)議的并發(fā)方法以及基于多核CPU的批量插入方法.然而，這些方法都沒有利用當(dāng)前GPU強(qiáng)大的并行計算吞吐量，且需要通過加鎖來避免互斥.Jason以及Alcantara等［11-12］研究了如何利用GPU來快速構(gòu)建靜態(tài)哈希表，但是這些方法都不支持記錄的增量插入.為此，文中在原有批量插入方法的基礎(chǔ)上，使用atomicAdd［3］函數(shù)設(shè)計了一種基于 GPU的無鎖批量插入線性哈希表GBLHT，從而可以充分利用GPU強(qiáng)大的并行計算吞吐量來加速線性哈希表的記錄插入過程.

1 相關(guān)研究工作

1.1 傳統(tǒng)的串行插入方法

線性哈希是由Litwin［5］在1980年提出的，其插入過程的主要思想為:隨著不斷地將索引記錄插入線性哈希表，如分裂條件滿足，則按預(yù)定的順序分裂桶，從而實(shí)現(xiàn)存儲空間的優(yōu)雅擴(kuò)充.詳細(xì)的插入過程描述為:設(shè)線性哈希表初始由N個桶組成，對應(yīng)的地址分別為0，1，…，N-1;在此，使用地址空間C來表示線性哈希表的桶地址.給定鍵值為c的記錄，使用哈希函數(shù)h0(c)將記錄插入線性哈希表;當(dāng)分裂條件滿足時，首先創(chuàng)建一個地址為N的桶并且將該桶添加到線性哈希表的末尾.然后，使用哈希函數(shù)h1(c)將第0號桶中記錄重新分配到第0號桶以及第N號桶;在此過程中，約有一半記錄遷移到新桶.下次分裂時，使用上述過程將第1號桶的記錄分裂到第1號桶以及第N+1號桶;依此類推，直到第N-1號桶也完成分裂為止.自此，線性哈希表實(shí)現(xiàn)了一次完整擴(kuò)展，即地址空間C從［0，N-1］擴(kuò)充為［0，2N-1］.下一輪分裂時，使用2N代替N、h1替代h0、h2替代h1，重復(fù)上述過程.插入過程中，如果記錄溢出，則使用拉鏈法處理，相關(guān)桶之間就形成了一條桶鏈.插入過程使用的哈希函數(shù)定義如下:

為了實(shí)現(xiàn)上述過程，需使用分裂層次變量Level以及指向待分裂桶的指針變量p(0＜=p＜N·2Level)來追蹤線性哈希表的當(dāng)前狀態(tài).當(dāng)線性哈希表分裂一個桶時，這些變量更新如下:

給定一個鍵值為c的記錄，當(dāng)前插入地址的計算方法如下:

目前，線性哈希表的分裂主要有非受控以及受控兩種控制模式.在受控模式中，只有裝填因子K超過給定閾值時才需要進(jìn)行分裂.裝填因子K的計算公式為

其中，x是線性哈希表存儲的記錄數(shù)，b為桶的容量，M為當(dāng)前的主桶數(shù)量.文中設(shè)計的方案主要是基于受控模式.

1.2 現(xiàn)有的并行處理方法

為增強(qiáng)線性哈希的操作性能，Ellis提出了一種并發(fā)處理方法［8］.通過添加封鎖協(xié)議以及擴(kuò)展相關(guān)數(shù)據(jù)結(jié)構(gòu)，該方法可以對線性哈希表的插入、查詢以及刪除等操作進(jìn)行并發(fā)處理.然而，該方法沒有利用多核CPU的強(qiáng)大性能，不能對記錄進(jìn)行批量處理.為此，陳虎等［9-10］提出了一種并行化批量插入方法，主要思想為:與傳統(tǒng)串行插入方法相比，不是立刻將單條記錄插入線性哈希文件，而是在內(nèi)存中開辟一塊緩沖區(qū)保存待插入記錄，直到記錄的數(shù)量達(dá)到設(shè)定的閾值，才批量插入線性哈希文件.在此，為了解決插入過程中產(chǎn)生的互斥問題，需要對緩沖區(qū)加鎖.相比傳統(tǒng)串行方法，該方法具有一定的優(yōu)勢，但也存在如下不足:(1)分裂過程使用單線程執(zhí)行，沒有充分利用多核CPU的強(qiáng)大性能;(2)緩沖區(qū)管理復(fù)雜;(3)沒有利用GPU強(qiáng)大的并行吞吐量.為了利用當(dāng)前GPU強(qiáng)大的并行吞吐量，Jason以及Alcantara等［11-12］研究了如何利用GPU來快速構(gòu)建靜態(tài)哈希表，然而，由于這些方法不支持記錄的增量插入，不能用于索引記錄規(guī)模未知的情形.

2 GBLHT:GPU加速的批量線性哈希表

由于CUDA編程架構(gòu)與CPU編程架構(gòu)存在一定差異，在此，首先設(shè)計了GBLHT的存儲結(jié)構(gòu)，在此基礎(chǔ)上，提出了一種新的無鎖批量插入方法.

2.1 GBLHT的存儲結(jié)構(gòu)

傳統(tǒng)線性哈希表是一個可以動態(tài)伸縮的哈希桶數(shù)組.然而，CUDA-C等編程語言不支持?jǐn)?shù)組的動態(tài)伸縮.如果在GPU中采用原有結(jié)構(gòu)，將會極大浪費(fèi)顯存空間.為此，一種簡單的實(shí)現(xiàn)方法就是使用兩層結(jié)構(gòu)來實(shí)現(xiàn)線性哈希表的動態(tài)收縮［7］，具體結(jié)構(gòu)如圖1所示.

圖1 支持動態(tài)擴(kuò)展的線性哈希表Fig.1 Linear Hash table supporting dynamic extension

在此結(jié)構(gòu)中，線性哈希表被劃分為大小相等的多個片段(segment)，且使用list數(shù)組保存每個segment的起始地址.在此，唯一需要使用傳統(tǒng)靜態(tài)方法進(jìn)行擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)為list數(shù)組.然而，由于list數(shù)組占用的存儲空間很小，這樣的擴(kuò)展不會大量浪費(fèi)存儲空間.使用該結(jié)構(gòu)，擴(kuò)展存儲空間需3個步驟才能完成:(1)創(chuàng)建一個新的segment;(2)擴(kuò)展list數(shù)組一個存儲位;(3)使用list數(shù)組的擴(kuò)展存儲位保存新創(chuàng)建的segment的首地址.基于GPU的線性哈希表結(jié)構(gòu)GBLHT的詳細(xì)定義如下所示.

由以上定義可以看出，GBLHT結(jié)構(gòu)主要由5大部分構(gòu)成:一個指針數(shù)組list、兩個狀態(tài)變量p和Level、一個溢出桶數(shù)組SPBuckets、兩個溢出桶數(shù)組管理變量 SPInsert和SP_len、溢出記錄統(tǒng)計數(shù)組count_SP;其中，變量p和Level的定義同上，list為指向segment的指針數(shù)組.在計算能力2.0以下的設(shè)備中，由于不支持在 device端動態(tài)分配存儲空間［3］，為此需使用cudaMalloc函數(shù)預(yù)分配一個溢出桶數(shù)組SPBuckets來保存溢出記錄.在批量插入過程中，如果溢出桶數(shù)組空間不夠，則使用傳統(tǒng)靜態(tài)方法擴(kuò)展.為了便于管理溢出桶數(shù)組，在此使用變量SPInsert以及SP_len來統(tǒng)計溢出桶數(shù)組的使用情況.其中，SPInsert指示溢出桶數(shù)組中下一個待使用的空桶，SP_len表示當(dāng)前溢出桶數(shù)組長度.count_SP數(shù)組為擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，主要用于統(tǒng)計每次批量插入需增加的溢出桶數(shù)量.

在上述結(jié)構(gòu)中，segment包含了一個bucket(哈希桶)數(shù)組以及一個BListNum數(shù)組，它們的規(guī)模均為N.每個bucket由一個容量為b的鍵值數(shù)組key、兩個變量insertLoc和next構(gòu)成.其中，insertLoc指示bucket中下一個插入位置，next指向下一個溢出桶. BListNum數(shù)組為擴(kuò)展數(shù)據(jù)結(jié)構(gòu)，主要是用于統(tǒng)計哈希表中每一條桶鏈中保存的記錄數(shù)量.

2.2 GBLHT的無鎖批量插入方法

為了利用GPU強(qiáng)大的并行吞吐量來加速線性哈希表的記錄插入過程，在現(xiàn)有并行方法的基礎(chǔ)上，設(shè)計了一種基于GPU的批量插入方法，主要思想為:在內(nèi)存中開辟一塊緩沖區(qū)保存待插入記錄.待記錄數(shù)量達(dá)到某個給定的閾值后，將記錄批量插入到全局內(nèi)存中的線性哈希表.與原有方案相比，基于GPU的批量插入方法改進(jìn)如下:(1)借助原子函數(shù)atomicAdd以及相關(guān)擴(kuò)展數(shù)據(jù)結(jié)構(gòu)解決了批量插入過程中產(chǎn)生的互斥問題，實(shí)現(xiàn)了記錄的無鎖批量插入.(2)在分裂過程中，使用多個線程并行分裂線性哈希表;(3)簡化了緩沖區(qū)管理.基于GPU的批量插入方法詳細(xì)流程如圖2所示.

圖2 基于GPU的批量插入方案流程圖Fig.2 Flow chart of GPU-based batch insertion method

初始，計算需要分裂的主桶數(shù)量split_num，計算公式為:split_num=-M;其中，ori_num為當(dāng)前存儲的記錄數(shù)，T為每次批量插入的記錄數(shù)，σ為給定的裝填因子閾值，M和b的定義同1.1節(jié);如果split_num＞0，則需要擴(kuò)展線性哈希表存儲空間.在此過程中，由于分裂會造成溢出桶數(shù)組出現(xiàn)大量存儲碎片，為此，在分裂的同時還需壓縮溢出桶數(shù)組.壓縮的具體過程如下:(1)創(chuàng)建一個長度等于SP_len的溢出桶數(shù)組n_SPBuckets; (2)將所有分裂過程中產(chǎn)生的溢出記錄保存到新創(chuàng)建的n_SPBuckets數(shù)組;(3)拷貝未分裂桶鏈中的溢出記錄到n_SPBuckets數(shù)組;(4)將線性哈希表的溢出桶數(shù)組指針指向n_SPBuckets數(shù)組.為加快分裂進(jìn)程，在此，使用多線程并行處理.線性哈希表的擴(kuò)展算法如下所示:

初始時，分配一個規(guī)模與segment數(shù)組相等的溢出桶數(shù)組.隨著不斷將記錄插入溢出桶數(shù)組，可能造成溢出桶數(shù)組空間不足，從而無法完成記錄的批量插入.為此，在每次批量插入前，均需判斷溢出桶數(shù)組空余存儲空間是否足夠完成本次批量記錄插入，詳細(xì)的算法如下所示:創(chuàng)建一個長度為SP_len+add_num的溢出桶數(shù)組，使用暴力方法并行拷貝當(dāng)前表中的溢出記錄到新創(chuàng)建的溢出桶數(shù)組并且修改相關(guān)桶的next指針，最后釋放當(dāng)前表的溢出桶數(shù)組并且修改溢出桶數(shù)組指針.

文中設(shè)計的方法最大創(chuàng)新之處在于提出了一種無鎖的批量記錄插入算法，該算法的主要思想為:首先為當(dāng)前批量插入的記錄預(yù)分配溢出空間，然后使用atomicAdd函數(shù)計算記錄在桶鏈中的具體插入位置，最后將記錄批量插入線性哈希表.為了更好地闡述該算法，在此給出了兩個關(guān)鍵定義:設(shè)β為一條長度為q的桶鏈，每個桶有b個槽位，此時β總共擁有qb個槽位.在此，將所有槽位從0開始順序編號，則稱這樣的編號為桶鏈β的槽位索引號.將β中所有桶從0開始順序編號，則稱該編號為桶鏈β的桶索引號.

批量插入算法中，記錄的具體插入位置計算過程如下:(1)計算記錄插入地址(l_index，s_index); (2)使用atomicAdd函數(shù)將輔助數(shù)組的對應(yīng)位置list［l_index］-＞BListNum［s_index］加1，從而獲取記錄在桶鏈中的槽位索引號;(3)根據(jù)槽位索引號獲取桶索引號并且計算出具體存儲位置.詳細(xì)的批量記錄插入過程描述如下:

由上述可知，GBLHT借助原子函數(shù)atomicAdd以及相關(guān)擴(kuò)展數(shù)據(jù)結(jié)構(gòu)有效地解決了批量插入過程中產(chǎn)生的互斥問題，實(shí)現(xiàn)了無鎖的批量記錄插入.由于不需要對緩沖區(qū)進(jìn)行加鎖，該方法的緩沖區(qū)管理非常簡單，這樣就大大減少了Host端與Device端之間的數(shù)據(jù)傳輸次數(shù).同時，該方法使用多線程并行分裂線性哈希表，從而可以充分利用GPU強(qiáng)大的并行吞吐量來提升線性哈希表的插入性能.

2.3 GBLHT性能分析

主要分析在充分利用GPU并行吞吐量的情況下，GBLHT無鎖批量插入方法的時間以及空間開銷.設(shè)b為哈希桶容量，未分裂桶鏈的最大長度為Ln，分裂桶鏈的最大長度為Ls，初始線性哈希表長度為Lh，初始溢出桶數(shù)組長度為sp_leno;批量插入過程中，插入同一地址的鍵值最多為mk個，list數(shù)組平均需要擴(kuò)展l_len，溢出桶數(shù)組平均需要擴(kuò)展o_len.在分裂過程中，平均每個桶要遷移的記錄所占比例為η.

2.3.1 時間開銷

由圖2可知，GBLHT執(zhí)行一次批量插入的平均時間開銷主要由算法A、B、C這3部分開銷組成.為便于分析，在此使用操作符的執(zhí)行次數(shù)進(jìn)行描述.下面分別對上述算法的平均時間開銷進(jìn)行分析.

算法A的開銷由host以及device端組成.除核函數(shù)split_table和copy_table外，算法其余部分均在host端執(zhí)行.host端的主要操作為cudaMalloc，平均執(zhí)行次數(shù)Th=(l_len+3).函數(shù)split_table的平均開銷Ts=(1+η)·Ls·b.函數(shù)copy_table的時間開銷Tc=(Ln-1)·b;從而可以得出A的平均開TA= (1+η)·Ls·b+(Ln-1)·b+(l_len+3);由前面的描述可知，算法B的開銷為TB=mk+max(Ls， Ln)+logLn;算法C的開銷主要由預(yù)分配空間及批量記錄插入部分這兩部分組成，它們的開銷分別為max(Ls，Ln)+max((count_sp［i］-m)/b)，(Ln+ b)/2.因此，算法 C的開銷 TC=max(Ls，Ln)+ max((count_sp［i］-m)/b)+(Ln+b)/2.

由上面分析可得，GBLHT執(zhí)行一次批量插入的平均時間開銷T=TA+TB+TC=(1+η)·Ls·b+ (Ln-1)·b+(l_len+3)+mk+2·max(Ls，Ln)+ Lh+max((count_sp［i］-m)/b)+(Ln+b)/2.

2.3.2 空間開銷

由于GBLHT存儲結(jié)構(gòu)大部分位于GPU的全局內(nèi)存，在此，對σ次批量插入后GBLHT的全局內(nèi)存使用情況進(jìn)行分析.由圖2可知，GBLHT的空間開銷主要由4部分組成:list數(shù)組、SPBuckets數(shù)組、count_SP數(shù)組以及 segment結(jié)構(gòu)體.list為指向segment指針數(shù)組，經(jīng)過σ次擴(kuò)展后的平均開銷為Slist=4·(σ·l_len+Lh/N)個字節(jié);segment由規(guī)模均為N的bucket以及BListNum數(shù)組構(gòu)成，它們的開銷分別為Sb=(b+2)·4·N以及Sbln=4N個字節(jié).因此，segment開銷為Sseg=4·(b+3)·N個字節(jié);經(jīng)過σ次擴(kuò)展后SPBuckets數(shù)組的平均開銷Ssp=4·(sp_leno+σ·o_len)·(b+2)個字節(jié);同時，擴(kuò)展溢出數(shù)組過程中產(chǎn)生的臨時存儲開銷為Sext=Ssp+Sb個字節(jié);count_SP數(shù)組的開銷為Scsp= (N·2Level+p)·4個字節(jié);

由此可得，經(jīng)過σ次擴(kuò)展后，GBLHT的全局內(nèi)存平均開銷Sg=［2·((sp_leno+σ·o_len)+N)· (b+2)+(σ·l_len+Lh/N)·((b+3)·N+1)+ (N·2Level+p)］·4個字節(jié).與傳統(tǒng)方法比較，GBLHT新增開銷為Sga=Sext+Scsp+σ·Sbln.

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)平臺

CPU為 Intel Core i7，4核，每個核的主頻為2.66GHz;內(nèi)存為 DDR3，6 GB;GPU為 NVIDIA GeForce GTX570，每個核的頻率為780 MHz，顯存為GDDR5，1.25GB;操作系統(tǒng)為WindowsXP Professional sp3.軟件開發(fā)工具包為CUDA3.2，集成開發(fā)環(huán)境為VisioStudio2008.

3.2 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

實(shí)驗(yàn)中，每條記錄均由一個鍵值組成.在此，使用隨機(jī)函數(shù)產(chǎn)生規(guī)模為8、16、32、64以及80M的鍵值集合作為測試數(shù)據(jù)集.實(shí)驗(yàn)中涉及的主要參數(shù)為:哈希桶容量b，初始的主桶數(shù)量N、批量插入的記錄數(shù)量batch_num以及裝填因子閾值α，其中α=0.8，其他參數(shù)的設(shè)置如表1所示.

表1 實(shí)驗(yàn)過程的參數(shù)設(shè)置Table 1 Parameter setting in experiment

3.3 實(shí)驗(yàn)設(shè)計及結(jié)果分析

為了驗(yàn)證文中設(shè)計方法的有效性，選取了3個對比方法:內(nèi)存線性哈希表插入方法［7］(方法1);文中提出的無鎖批量插入方法GBLHT(方法2);基于多核CPU的內(nèi)存線性哈希表批量插入方法(方法3).其中，方法3是由文獻(xiàn)［9-10］中的方法修改而來.由于原有方法是基于哈希文件設(shè)計的，在此，為便于性能比較，文中進(jìn)行了如下修改:(1)數(shù)據(jù)結(jié)構(gòu)從外存文件改為內(nèi)存線性哈希表［7］;(2)使用多線程并行分裂;(3)使用OpenMP相關(guān)API在記錄批量插入過程進(jìn)行加鎖來解決互斥問題，從而不需要對緩沖區(qū)加鎖.

實(shí)驗(yàn)中，為了比較方法3中不同線程數(shù)量對插入性能的影響，分別使用2線程和4線程進(jìn)行實(shí)驗(yàn)，它們分別標(biāo)識為OpenMPTwo、OpenMPFour.實(shí)驗(yàn)的具體過程描述為:根據(jù)表1的參數(shù)設(shè)置，分別使用上述插入方法對測試數(shù)據(jù)集進(jìn)行循環(huán)批量插入，從而獲得5組不同方案的插入性能數(shù)據(jù).由于篇幅所限，在此僅給出了第2以及第5種參數(shù)設(shè)置時不同方法的插入性能，分別如圖3和4所示.

GBLHT運(yùn)行時間包含了內(nèi)存和顯存之間的數(shù)據(jù)傳輸時間以及記錄的插入時間.經(jīng)過分析，在GPU運(yùn)行時間中，數(shù)據(jù)傳輸時間所占的比例約為15%.

圖3 第2種參數(shù)設(shè)置下不同方案的插入性能Fig.3 Performance of different methods with the second parameter setting scheme

圖4 第5種參數(shù)設(shè)置下不同方案的插入性能Fig.4 Performance of different methods with the fifth parameter setting scheme

從圖3中可以看出，當(dāng)batch_num值較小時，相對于傳統(tǒng)串行方法，OpenMPTwo、OpenMPFour方法的性能分別提升了1.6倍以及2.4倍，而GBLHT的性能提升了7倍.由圖4可知，當(dāng)batch_num值較大時，OpenMPTwo、OpenMPFour的性能分別提升了1.6倍和2.5倍，而GBLHT的插入性能則提升了14倍.由此可知，與現(xiàn)有插入方法相比，GBLHT的性能優(yōu)勢較為明顯.此外，通過對比分析圖3和4可知，不同的batch_num設(shè)置對GBLHT的插入性能影響較大.

為了更好地分析batch_num對加速比［2］產(chǎn)生的影響，實(shí)驗(yàn)中，將測試數(shù)據(jù)集的規(guī)模固定為64 M.在此情況下，分別測試不同batch_num設(shè)置時上述3種方法的加速比，詳細(xì)描述如圖5所示.

從圖5中可以看出，隨著batch_num不斷增加，2線程CPU批量插入方法OpenMPTwo以及4線程CPU批量插入方法OPenMPFour的加速比基本持平，基于GPU的批量插入方法GBLHT的加速比則快速增長.這充分說明，基于GPU的批量插入方法GBLHT非常適合較大規(guī)模記錄的批量插入.

圖5 不同batch_num對加速比的影響Fig.5 Impact of different batch_num settings on speedup

4 結(jié)語

線性哈希表是一種非常有效的內(nèi)存索引結(jié)構(gòu)，為提高其插入性能，研究人員提出了多種不同的并行方案，然而這些方法都沒有利用GPU強(qiáng)大的并行性能.為此，文中利用原子函數(shù)atomicAdd的特性設(shè)計了一種基于GPU的批量插入方法GBLHT，給出了相關(guān)數(shù)據(jù)結(jié)構(gòu)，并通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性.結(jié)果表明，GBLHT在批量插入大規(guī)模記錄時，性能優(yōu)勢較為明顯.文中當(dāng)前僅僅研究了基于GPU的線性哈希表批量插入方法，下一步工作主要是研究基于GPU的線性哈希表批量查詢以及刪除方法;同時，由于GPU的存儲容量有限，為了構(gòu)建規(guī)模龐大的線性哈希表，還要研究如何將線性哈希表擴(kuò)展到頁鎖定內(nèi)存;最后，打算將GBLHT集成到相關(guān)系統(tǒng)來提升系統(tǒng)的檢索性能.

［1］ 楊珂，羅瓊，石教英.圖形處理器在數(shù)據(jù)庫技術(shù)中的應(yīng)用［J］.浙江大學(xué)學(xué)報:工學(xué)版，2009，43(8):1349-1360. Yang Ke，Luo Qiong，Shi Jiao-ying.Application of graphics processors to database technologies［J］.Journal of Zhejiang University:Engineering Science，2009，43(8):1349-1360.

［2］ 周偉明.多核計算與程序設(shè)計［M］.武漢:華中科技大學(xué)出版社，2009:19-25.

［3］ NVIDIA Corporation.NVIDIA CUDA programming guide，version 2.3.1［EB/OL］.(2009-07-15)［2011-08-27］. www.cs.unc.edu/…/NVID IA_CUDA_Programming_ Guide_2.3.pdf.

［4］ Changkyu Kim，Jatin Chhugani，Nadathur Satish，et al. FAST:fast architecture sensitive tree search on modern CPUs and GPUs［C］∥Proceedings of the ACM SIGMOD.Indianapolis:Association for Computing Machinery，2010:339-350.

［5］ Litwin W.Linear hashing:a new tool for file and table addressing［C］∥International Conference on Very Large Databases.Montreal:IEEE Computer Society，1980:212-223.

［6］ Ashok Rathi，Huizhu Lu，Hearidz G E.Performance comparison of extendible hashing and linear hashing technologies［C］∥Proceedings of ACM SIGSMALL/PC Symposium on Small Systems.Crystal City:Association for Computing Machinery，1990:19-25.

［7］ Per-Ake Larson.Dynamic hash tables［J］.Communications of the ACM，1988，31(4):446-457.

［8］ Ellis Carla Schlatter.Concurrency in linear hashing［J］. ACM Transactions on Database Systems，1987，12(2):195-217.

［9］ Tang Hai-Hao，Chen Hu，Peng Jiang-Feng.Multithreaded linear hashing with diskbuffer［C］∥First International Workshop on Database Technology.Wuhan:IEEE Computer Society，2009:435-439.

［10］ 陳虎，唐海浩，廖江苗，等.面向批量插入優(yōu)化的并行存儲引擎MTPower［J］.計算機(jī)學(xué)報，2010，33(8): 1492-1499. Chen Hu，Tang Hai-hao，Liao Jiang-miao，et al.MTPower:a parallel database storage engine for batch insertion［J］.Chinese Journal of Computers，2010，33(8):1492-1499.

［11］ Jason Sanders，Edward Kandrot.CUDA by example［M］.Ann Arbor:Pearson Education，2010:258-276

［12］ Alcantara Dan A，Sharf Andrei，Abbasinejad Fatemeh，et al.Real-time parallel hashing on the GPU［J］.ACM Transactions on Graphics，2009，28(5):1-9.