基于GPU的可擴(kuò)展哈希方法*

胡學(xué)萱 奚建清 林妙

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

哈希索引是一種快速的數(shù)據(jù)檢索方法，已廣泛應(yīng)用于文件系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及一些情報(bào)檢索系統(tǒng)中［1］.動(dòng)態(tài)哈希能優(yōu)雅地?cái)U(kuò)展存儲(chǔ)空間，根據(jù)其方法的不同，可分為可擴(kuò)展哈希［2］和線性哈希［3］.如 何擴(kuò)展和收縮哈希表，快速更新索引記錄以便有效地使用哈希索引，一直以來受到人們的廣泛關(guān)注.Ellis［4］提出了一種基于目錄鎖和桶鎖的兩級(jí)鎖模式的可擴(kuò)展并行哈希算法；Hsu 等［5］提出了一種可以并發(fā)插入刪除的可擴(kuò)展哈希算法；Kumar［6］提出的EHCW算法使用了兩階段鎖和事務(wù)回滾的策略，可并發(fā)擴(kuò)展/收縮目錄，分裂/合并數(shù)據(jù)頁；Lea［7］提出了一種基于復(fù)雜鎖模式的Java 并發(fā)包，允許在改變表大小的同時(shí)進(jìn)行并行查詢；Gao 等［8］提出的可擴(kuò)展哈希算法周期性地切換到全局以調(diào)整哈希表大小狀態(tài)，進(jìn)行多進(jìn)程協(xié)作執(zhí)行數(shù)據(jù)項(xiàng)遷移；Shalev 等［9］提出的RSO 算法通過改變桶地址來擴(kuò)展或收縮表；Zhang 等［10］提出了基于線性哈希和RSO算法的LHlf 算法；陳虎等［11］提出了一種利用多核處理器的并行計(jì)算能力提升批量插入線性哈希表性能的算法；黃玉龍等［12］提出了一種圖形處理器（GPU）加速的線性哈希表的批量插入算法GBLHT.

高性能和可擴(kuò)展的哈希表是當(dāng)代大數(shù)據(jù)應(yīng)用的需求，故需要提高哈希表的并發(fā)處理能力.可編程圖形處理器因其眾核和高存儲(chǔ)器帶寬而成為并行計(jì)算的超強(qiáng)工具，統(tǒng)一計(jì)算設(shè)備架構(gòu)（CUDA）這種基于GPU 的計(jì)算架構(gòu)，提供了易用的編程模型和應(yīng)用程序接口（API），使得將GPU 用于通用計(jì)算成為可能［13］.為充分利用GPU 的高并發(fā)計(jì)算能力，提升可擴(kuò)展哈希方法的性能，文中提出了一種基于GPU 的可擴(kuò)展哈希方法gEHT.

1 相關(guān)的哈希方法

1.1 可擴(kuò)展哈希方法

可擴(kuò)展哈希方法分裂和合并桶時(shí)，不像線性哈希方法那樣按順序進(jìn)行，而是按需要進(jìn)行［2］，即當(dāng)向桶內(nèi)插入的數(shù)據(jù)量超過桶的剩余容量時(shí)，就分裂該桶，一次分裂產(chǎn)生的兩個(gè)桶互為對(duì)應(yīng)桶；反之，當(dāng)桶及其對(duì)應(yīng)桶內(nèi)數(shù)據(jù)被刪除后不足一個(gè)桶的容量時(shí)，就合并這兩個(gè)桶.

圖1給出了一個(gè)初始桶經(jīng)過多次分裂形成的分裂樹，其中樹根為初始桶，實(shí)節(jié)點(diǎn)為已分裂產(chǎn)生的桶，稱為實(shí)桶，虛節(jié)點(diǎn)為預(yù)分裂產(chǎn)生的桶，稱為虛桶；實(shí)有向邊為已產(chǎn)生的分裂，虛有向邊為預(yù)產(chǎn)生的分裂.桶分裂一次，產(chǎn)生實(shí)有向邊所指的下一層的兩個(gè)桶，最底層的所有實(shí)桶為現(xiàn)有桶.可見，桶000、001、100、101、10 和11 為現(xiàn)有桶.

圖1 桶的分裂樹Fig.1 Split tree of bucket

由于各桶的層次無序，必然導(dǎo)致有些目錄項(xiàng)所指的桶為虛桶，解決的方法是將這樣的目錄項(xiàng)指向該虛桶的實(shí)上級(jí)桶，即分裂樹上該虛桶到初始桶的分裂路徑上最大深度的實(shí)桶.這樣，在檢索數(shù)據(jù)時(shí)，能一次定位到不同局部深度的桶上，而不用層層探索，加快了檢索速度.

1.2 基于并行技術(shù)的動(dòng)態(tài)哈希

文獻(xiàn)［4-7］中提出基于鎖的算法，具有死鎖、長(zhǎng)時(shí)間延遲和優(yōu)先級(jí)倒置的缺點(diǎn)，當(dāng)進(jìn)行表的擴(kuò)展或收縮時(shí)，這些情況更加嚴(yán)重.文獻(xiàn)［8］算法使用了write-all 算法，時(shí)間復(fù)雜度為常數(shù).RSO 算法［9］使用鏈表來存儲(chǔ)數(shù)據(jù)，故其訪問效率低，僅適用于將關(guān)鍵字的低位作為最高有效位的哈希函數(shù).文獻(xiàn)［10-12］算法使用了溢出桶，降低了檢索效率，并且延遲的分裂使得分裂前溢出桶的數(shù)據(jù)要重新遷移到分裂后的桶中，這種冗余的數(shù)據(jù)遷移必然會(huì)降低插入的效率.

2 可擴(kuò)展哈希方法在GPU 上的實(shí)現(xiàn)

2.1 基于GPU 的存儲(chǔ)結(jié)構(gòu)

為了在GPU 上動(dòng)態(tài)伸縮表并克服可擴(kuò)展哈希表成倍擴(kuò)展的缺陷，文中采用兩層表結(jié)構(gòu)，分別是段表segList 和桶表bucketList，段表存放段地址，桶表存放桶地址.以桶表的伸縮實(shí)現(xiàn)少量的表擴(kuò)展，段表的重構(gòu)實(shí)現(xiàn)大量的表擴(kuò)展［12］.當(dāng)擴(kuò)展的桶集中在少數(shù)的段時(shí)，只需擴(kuò)展少數(shù)的桶表，其他未擴(kuò)展桶表可被重用.另外，段表、桶表和桶內(nèi)數(shù)據(jù)都采用數(shù)組（即便于GPU 并行處理的結(jié)構(gòu)），并且桶內(nèi)數(shù)據(jù)采用數(shù)組的結(jié)構(gòu)體（SOA）結(jié)構(gòu)而非結(jié)構(gòu)體的數(shù)組（AOS），以適應(yīng)GPU 的存儲(chǔ)器的優(yōu)化存取要求.文獻(xiàn)［12］的兩層存儲(chǔ)結(jié)構(gòu)僅用于動(dòng)態(tài)伸縮.文中采用的存儲(chǔ)結(jié)構(gòu)如下：

上述定義中，Gd 為全局深度，bucketNum 為現(xiàn)有桶的數(shù)量，Ld 為桶的局部深度，insertLoc 為桶內(nèi)下一個(gè)空閑地址，數(shù)組is_df 是每條數(shù)據(jù)的刪除標(biāo)記.初始時(shí)有M 段，每段由N 個(gè)桶構(gòu)成，每個(gè)桶的容量為b 條記錄.維護(hù)這種結(jié)構(gòu)的挑戰(zhàn)在于保證桶分裂/合并和表擴(kuò)展/收縮后，目錄項(xiàng)能指向改變后的桶.表及桶的改變分為以下4 種情況：

（1）桶分裂，段表不擴(kuò)展.如果桶b［i］分裂產(chǎn)生新桶b［i+M·N·2b［i］.Ld］，分裂后所有桶的最大局部深度未超過全局深度，則段表不擴(kuò)展.如果沒有第（i+M·N·2b［i］.Ld）/N 段桶表則增加它，修改該桶表第（i+M·N·2b［i］.Ld）%N 項(xiàng)指向新桶，其他項(xiàng)指向相應(yīng)虛桶的實(shí)上級(jí)桶.桶b［i］和b［i+M·N·2b［i］.Ld］的局部深度為b［i］.Ld+1.

（2）桶合并，段表不收縮.若桶b［i］和b［i+M·N·2b［i］.Ld］合并，合并后所有桶的最大局部深度不小于全局深度，則段表不收縮.釋放桶b［i+M·N·2b［i］.Ld］，修改桶表目錄項(xiàng)i+M·N·2b［i］.Ld指向桶b［i］，桶b［i］的局部深度為b［i］.Ld-1.若第（i+M·N·2b［i］.Ld）/N 段桶表所有表項(xiàng)指向的桶的局部深度都小于全局深度，則釋放該段桶表.

（3）段表擴(kuò)展.若分裂后所有桶的最大局部深度大于全局深度，則段表擴(kuò)展.擴(kuò)展后的第（i+M·N·2b［i］.Ld）/N 項(xiàng)指向新增的桶表，其他表項(xiàng)指向其實(shí)上級(jí)桶所在的桶表.

（4）段表收縮.合并后所有桶的最大局部深度小于全局深度，則段表收縮.

圖2為桶分裂/合并和表擴(kuò)展/收縮的一個(gè)例子.圖2（a）所示的桶經(jīng)過收縮和擴(kuò)展，產(chǎn)生圖2（b）、2（c）所示的桶和表.其中，圖2（a）的桶00 和10、01和11 分別合并為圖2（b）的兩個(gè)桶0 和1，則原指向桶00、10 的表項(xiàng)合并后指向其實(shí)上級(jí)桶0，指向01、11 的表項(xiàng)合并后指向其實(shí)上級(jí)桶1，桶的最大局部深度小于合并前的全局深度，段表和桶表收縮為原表的一半.圖2（a）的桶00 擴(kuò)展為圖2（c）的桶000 和100，桶的最大局部深度大于原全局深度，段表擴(kuò)展一倍，桶表擴(kuò)展第2 段，使段表的第2 項(xiàng)指向新增的桶表，第3 項(xiàng)指向第1 段桶表.新增的桶表中，第4 項(xiàng)指向新增的桶100，其他擴(kuò)展的表項(xiàng)5 指向虛桶101 的實(shí)上級(jí)桶01.可見，采用這種目錄結(jié)構(gòu)雖然擴(kuò)展了指向新增桶的桶表，但能尋址倍增的桶（包括虛桶）.

圖2 表的收縮和擴(kuò)展Fig.2 Shrinking and growing of table

2.2 創(chuàng)建哈希表算法

哈希索引的創(chuàng)建包括創(chuàng)建段表、桶表和桶，并使段表和桶表的各項(xiàng)指向新創(chuàng)建的桶表和桶.算法并行創(chuàng)建段內(nèi)的桶，偽代碼如下：

2.3 查詢算法

檢索數(shù)據(jù)先計(jì)算該數(shù)據(jù)的散列值，然后定位到桶中并在桶中搜索該數(shù)據(jù).在GPU 中，可使每個(gè)數(shù)據(jù)用一個(gè)線程處理，高并發(fā)地執(zhí)行.文獻(xiàn)［12］的查詢算法是基于線性哈希的，因而，對(duì)每個(gè)數(shù)據(jù)的查詢，延遲比可擴(kuò)展哈希大.文中查詢算法的偽代碼如下：

2.4 刪除算法

本算法采用延遲刪除的策略，即刪除并不立即執(zhí)行，只對(duì)刪除數(shù)據(jù)做標(biāo)記.在批量插入數(shù)據(jù)時(shí)，用插入數(shù)據(jù)覆蓋有刪除標(biāo)記的數(shù)據(jù).該算法只需要在查詢算法queryEHTable 中加入對(duì)要?jiǎng)h除的索引記錄做標(biāo)記，文中不再贅述.

2.5 插入算法

當(dāng)批量插入的數(shù)據(jù)量大于該桶的剩余容量時(shí)，需要分裂桶，如果分裂后仍不能滿足插入需要，則要繼續(xù)分裂直到滿足需求為止.分裂會(huì)使部分?jǐn)?shù)據(jù)遷移到新桶中，這些中間過程的數(shù)據(jù)遷移是不必要的，會(huì)降低索引更新速度，成為插入過程的性能瓶頸［11］.因此，文中采用預(yù)分裂技術(shù)，先循環(huán)預(yù)測(cè)桶的分裂情況，再分裂桶或擴(kuò)展表并插入數(shù)據(jù)；充分利用GPU的計(jì)算能力，并行處理預(yù)測(cè)過程和實(shí)際插入過程以提高插入效率.

批量插入算法流程如圖3所示，預(yù)測(cè)部分和插入部分的算法主要由子算法A、B、C、D 構(gòu)成.插入算法的步驟如下：

圖3 批量插入算法流程圖Fig.3 Flowchart of batch insertion algorithm

（1）計(jì)算數(shù)據(jù)插入的桶號(hào)insert_bucketNo、各桶插入數(shù)據(jù)量insert_bucketNum、待分裂的桶號(hào)needSMBucketNo、待分裂的段號(hào)needSMSegNo、桶預(yù)計(jì)分裂到的局部深度SMBucketLd、待分裂桶的數(shù)量needSMBucketNum、所有待分裂桶預(yù)計(jì)分裂到的最大局部深度maxOfBucketLd.若待分裂桶的數(shù)量needSMBucketNum＞0，則置待分裂桶標(biāo)記needSMBucketFlag=1，并根據(jù)上輪循環(huán)預(yù)計(jì)的桶分裂到的局部深度SMBucketLd，循環(huán)計(jì)算以上數(shù)據(jù)，直到needSMBucketNum=0，如算法A（countInsert）.

（2）若所有待分裂桶預(yù)計(jì)分裂到的最大局部深度maxOfBucketLd＞Gd，則轉(zhuǎn)步驟（3），否則轉(zhuǎn)步驟（4）.

（3）擴(kuò)展段表和桶表，將擴(kuò)展的段表表項(xiàng)指向新建的桶表，如算法B（growsTable）.

（4）若有需要分裂的桶，即needSMBucketFlag=1，則轉(zhuǎn)步驟（5），否則轉(zhuǎn)步驟（6）.

（5）分裂桶，修改桶表指針，如算法C（splitBucket）.

（6）插入數(shù)據(jù)，如算法D（insertData）.

如2.4 節(jié)所述，插入數(shù)據(jù)將覆蓋有刪除標(biāo)記的數(shù)據(jù)，因此批量插入數(shù)據(jù)除了上述情況外，也會(huì)有合并桶和收縮表的情況.限于篇幅，以下偽代碼僅為分裂桶和擴(kuò)展表的情況：

2.6 算法優(yōu)化

根據(jù)CUDA 的編程模型，將計(jì)算密集的任務(wù)交給GPU 線程網(wǎng)格處理，如核函數(shù)A、B、C、D，而CPU執(zhí)行邏輯復(fù)雜的處理.在GPU 上的并行優(yōu)化主要從以下幾個(gè)方面考慮：

1）任務(wù)粒度劃分.粒度越細(xì)，越能充分利用GPU大量的輕量級(jí)線程，算法的并行度越高.文中的創(chuàng)建算法中，桶間并行執(zhí)行；查詢算法中，各數(shù)據(jù)可并行查詢；插入算法的預(yù)測(cè)部分中，對(duì)各數(shù)據(jù)的插入位置、各桶分裂情況的計(jì)算相互獨(dú)立；在擴(kuò)展表、分裂桶和插入數(shù)據(jù)算法中，段間、桶間和數(shù)據(jù)間的操作相互獨(dú)立，蘊(yùn)含大量并行操作，如For each tid…parallel do 與End for 之間的代碼所示.

2）程序重構(gòu).GPU 的體系結(jié)構(gòu)使其適于進(jìn)行邏輯簡(jiǎn)單和數(shù)據(jù)并行的密集計(jì)算.文中合并多個(gè)循環(huán)以增強(qiáng)計(jì)算密度，隱藏訪存延遲；重構(gòu)分支以避免warp 內(nèi)分支轉(zhuǎn)移造成性能下降；將不同粒度的并行操作合并為一個(gè)核函數(shù)，以增強(qiáng)計(jì)算密度、減少核函數(shù)啟動(dòng)開銷和數(shù)據(jù)傳輸開銷.

計(jì)算每個(gè)桶是否分裂、分裂到的層次等，其迭代空間是所有的桶，因而可合并循環(huán)，如A7-A13 行；計(jì)算每個(gè)數(shù)據(jù)的插入位置與計(jì)算每個(gè)桶是否需要分裂，其任務(wù)粒度不同，故不能合并循環(huán)，但可以合并為一個(gè)核函數(shù)，以便將待插入數(shù)據(jù)eData 放入共享存儲(chǔ)器重用，如算法A.計(jì)算桶是否分裂以及桶的層數(shù)，需要根據(jù)插入數(shù)據(jù)量與桶的剩余容量大小比較進(jìn)行分支選擇，文中重構(gòu)該分支語句，將比較插入數(shù)據(jù)量與桶的剩余容量大小的邏輯值賦給記錄桶是否分裂的數(shù)組needSMBucketNo，并將該數(shù)組作為桶層數(shù)的增量，如A8、A9 行.

3）數(shù)據(jù)的組織與存儲(chǔ)訪問.適合并行處理的數(shù)據(jù)結(jié)構(gòu)、對(duì)GPU 上各存儲(chǔ)器的充分利用以及規(guī)則的訪問模式是存儲(chǔ)優(yōu)化的主要方法.

（1）數(shù)組能體現(xiàn)數(shù)據(jù)的并行性，適于GPU 上的密集計(jì)算.文中對(duì)哈希表結(jié)構(gòu)、算法的輸入數(shù)據(jù)eData、中 間 變 量（如insert_bucketNo、insert_bucket Num、needSMBucketNo、SMBucketLd 等）及輸出結(jié)果qResult 都使用數(shù)組.為了全局存儲(chǔ)器的合并訪問，盡量將數(shù)據(jù)由AOS 轉(zhuǎn)為SOA 結(jié)構(gòu)［14］，如桶內(nèi)數(shù)據(jù)Data 和輸入數(shù)據(jù)eData.文獻(xiàn)［12］采用數(shù)組結(jié)構(gòu)，但沒有將AOS 轉(zhuǎn)為SOA 結(jié)構(gòu).

（2）GPU 的多層次存儲(chǔ)器可滿足不同需求，共享存儲(chǔ)器訪問速度快但容量有限，為塊內(nèi)線程所共有，適合存放重用的局部性數(shù)據(jù)；全局存儲(chǔ)器容量大但速度慢.高效利用片上局部存儲(chǔ)器，可提高計(jì)算全局訪存比CGMA［13］，且采用規(guī)則訪問的模式能顯著改善程序的存儲(chǔ)墻問題.如算法A 中，待插入數(shù)據(jù)eData 循環(huán)重用，宜用共享存儲(chǔ)器存儲(chǔ).從上述算法可以看出，各數(shù)組的訪存模式中，除insert_bucketNum 為隨機(jī)訪存，needSMSegNo 為跳步訪存外，其他都是規(guī)則訪問，使得全局存儲(chǔ)器能合并訪問，不產(chǎn)生局部訪存沖突，而這兩個(gè)數(shù)組的非規(guī)則訪存，并不適宜進(jìn)行循環(huán)重構(gòu)和數(shù)組重構(gòu)［15］來改變其訪存模式.文獻(xiàn)［12］未提到共享存儲(chǔ)器的使用以及數(shù)據(jù)的規(guī)則訪問.

4）使用cuda 提供的原子函數(shù)和并行算法庫以提高代碼的性能，如A5、A11、A12 和D1 行所示.

3 算法性能分析

文中從時(shí)間和空間兩方面討論gEHT 的性能.假設(shè)哈希表初始段數(shù)為M，每段的桶數(shù)為N，每個(gè)桶的容量為b，現(xiàn)有桶的數(shù)量為bucketNum，現(xiàn)有記錄數(shù)為m，批處理的數(shù)據(jù)規(guī)模為batchNum.

3.1 時(shí)間開銷

（1）查詢時(shí)間開銷.由queryEHTable 算法可知，其時(shí)間開銷tq主要由計(jì)算搜索鍵對(duì)應(yīng)散列值的時(shí)間tc、定位包含數(shù)據(jù)的桶以及在桶中檢索目標(biāo)數(shù)據(jù)的時(shí)間ts構(gòu)成.由Q3 和Q4-Q8 行知，tc的復(fù)雜度為O（1），ts的復(fù)雜度為O（b），因此，查詢時(shí)間tq的復(fù)雜度為O（b）+O（1），即為常數(shù)時(shí)間，且數(shù)據(jù)規(guī)模batch-Num 越大，越能充分利用GPU 的并行計(jì)算能力，從而獲得更高的吞吐量.

（2）插入時(shí)間開銷.由insertEHTable 算法可知，其總時(shí)間開銷ti主要由預(yù)測(cè)部分和實(shí)際操作部分各子算法的執(zhí)行時(shí)間tA、tB、tC和tD組成.

子算法A 循環(huán)執(zhí)行，在最好情況下數(shù)據(jù)平均插入所有桶中，循環(huán)次數(shù)為batchNum/（bucketNum·b）；在最壞情況下數(shù)據(jù)都插入同一個(gè)桶中，循環(huán)次數(shù)為batchNum/b，其循環(huán)內(nèi)部的A2-A6、B7-B13 行并行執(zhí)行，時(shí)間開銷為O（1）.算法B、C 中B2-C11、C1-C7行也是并行執(zhí)行，其并行內(nèi)部循環(huán)次數(shù)與預(yù)測(cè)部分的循環(huán)次數(shù)相同，循環(huán)內(nèi)部的時(shí)間開銷為O（1）.算法D 中D1 行的時(shí)間代價(jià)為O（logrbatchNum）［14］（r 為基數(shù)），D2-D4 行并行執(zhí)行的時(shí)間開銷為O（1）.因此，總時(shí)間開銷ti在最好情況下為O（batchNum/（bucketNum·b）+ logrbatchNum），在最壞情況下為O（batchNum/b+logrbatchNum））.

3.2 空間開銷

文中從總空間開銷和表擴(kuò)展的開銷兩個(gè)方面來分析.

1）總空間開銷.在GPU 上建立的哈希索引，如2.1 節(jié)所述，其顯存的開銷S 主要包括段表空間SsegList、桶表空間SbucketList和桶空間Sbucket.

若m 條記錄占有桶數(shù)L（m）≈m/（bln 2）［16］，則占有空間Sbucket=bL（m）≈m/ln2，桶表所需空間SbucketList為O（m（1+1/b）/b）［17］，段表空間SsegList為O（m（1+1/b）/（Nb）），總空間S 為O（m/ln2+m（1+1/b）/b+m（1+1/b）/（Nb））.

2）表擴(kuò)展的開銷.假設(shè)分裂桶產(chǎn)生a 個(gè)桶段的擴(kuò)展，0≤a≤M（M 為擴(kuò)展前桶的段數(shù)，即段表長(zhǎng)度），則段表增加M 項(xiàng)，桶表增加aN 項(xiàng)（N 為每段桶表的長(zhǎng)度），共擴(kuò)展M+aN 項(xiàng).若無段表僅有桶表，則表項(xiàng)要增加MN 項(xiàng).

（1）當(dāng)數(shù)據(jù)傾斜，分裂的桶不多，即a?M 時(shí)，雙層表結(jié)構(gòu)中表的擴(kuò)展是線性的，而單層表結(jié)構(gòu)中表的擴(kuò)展是二次的，更加劇烈；

（2）當(dāng)數(shù)據(jù)均勻分布，每段都有桶分裂，即a≈M時(shí)，雙層結(jié)構(gòu)表的擴(kuò)展接近M+MN 項(xiàng)，單層結(jié)構(gòu)表的擴(kuò)展接近MN 項(xiàng)，而M?MN，因此這種情況下，雙層結(jié)構(gòu)比單層結(jié)構(gòu)多的表項(xiàng)也是有限的.

4 實(shí)驗(yàn)

實(shí)驗(yàn)在CPU+GPU 的異構(gòu)平臺(tái)上進(jìn)行，CPU 為Intel Core i7-4770k，四核3.50 GHz 主頻，GPU 為NVIDIA GeForce GTX 770，1536 CUDA Cores，每個(gè)核的頻率為1.19 GHz，顯存容量為4 GB.集成開發(fā)環(huán)境為VisioStudio2010，GPU 開發(fā)工具包為CUDA5.5.

文中設(shè)計(jì)兩部分實(shí)驗(yàn)，分別從時(shí)間和空間兩個(gè)方面檢驗(yàn)gEHT 算法的有效性.測(cè)試數(shù)據(jù)集是隨機(jī)產(chǎn)生的鍵值對(duì)構(gòu)成的記錄，每條記錄平均長(zhǎng)度為10B，每桶的記錄容量b 為64 條，初始桶的總數(shù)M×N 為8×1024.

實(shí)驗(yàn)1對(duì)比Lea 算法、RSO 算法、GBLHT 算法和gEHT 算法在數(shù)據(jù)操作上的時(shí)間性能，其中Lea算法和RSO 算法均采用4 線程.

在包含90%的查詢數(shù)據(jù)、6%的插入數(shù)據(jù)和4%的刪除數(shù)據(jù)的負(fù)載下，4 種算法的吞吐量如圖4所示.在4 線程算法中，鎖沖突對(duì)Lea 算法帶來的影響不大，其性能略高于RSO 算法.RSO 算法和gEHT算法的性能都會(huì)隨著數(shù)據(jù)量的增加而有所波動(dòng)，這是因?yàn)楸硎湛s或擴(kuò)展的時(shí)間損耗使其吞吐量下降.GBLHT 算法采用的線性哈希及前述優(yōu)化問題，使其性能略低于gEHT 算法.總的來說，隨著負(fù)載的增加，GBLHT 和gEHT 算法充分利用了GPU 的計(jì)算能力，顯著地提高了吞吐量.

圖4 不同負(fù)載下4 種算法的吞吐量Fig.4 Throughputs of four algorithms under different loads

實(shí)驗(yàn)2測(cè)試Fagin 的EH(Extendible Hashing)算法和gEHT 算法隨著數(shù)據(jù)的插入表擴(kuò)展所占用的空間情況.

圖5 表的大小與插入數(shù)據(jù)量的關(guān)系Fig.5 Directory size versus number of insertions

如圖5所示，EH 算法在擴(kuò)展表時(shí)，表長(zhǎng)成倍增長(zhǎng)，而gEHT 算法接近線性的增長(zhǎng),并且隨著插入數(shù)據(jù)的增加，表空間擴(kuò)展的速度放緩，甚至小于EH 算法的表空間大小.這是因?yàn)殡S著表空間的擴(kuò)大，更多的段表項(xiàng)指向相同的桶表,越來越多的桶表被重用，以致盡管gEHT 算法比EH 算法多出段表，其總的表空間大小也不會(huì)超過EH 算法.

5 結(jié)論

可擴(kuò)展哈希是一種具有最快檢索速度的動(dòng)態(tài)哈希，文中利用GPU 實(shí)現(xiàn)了可擴(kuò)展哈希算法gEHT.首先利用GPU 的計(jì)算能力和CUDA 的編程模型，設(shè)計(jì)并實(shí)現(xiàn)了哈希表的創(chuàng)建、索引的更新以及數(shù)據(jù)檢索的高并發(fā)算法；為了克服表長(zhǎng)增長(zhǎng)劇烈的缺陷，文中采用二級(jí)表結(jié)構(gòu)，使得段表能重用部分桶表，大大地節(jié)省了表結(jié)構(gòu)對(duì)空間的需求.最后，通過實(shí)驗(yàn)驗(yàn)證了gEHT 算法的性能.

顯存空間十分有限，文中討論的算法都是在待處理數(shù)據(jù)能夠全部放在顯存中的前提下進(jìn)行處理的.大數(shù)據(jù)的特征使得批量處理的數(shù)據(jù)量更大，當(dāng)其大于顯存容量時(shí)，又應(yīng)該如何在GPU 上使用哈希索引，是下一步要考慮的問題.

［1］Du H C，Ghanta S，Maly K J，et al.An efficient file structure for document retrieval in the automated office environment ［J］.IEEE Transactions on Knowledge and Data Engineering，1989，1(2)：258-273.

［2］Fagin Ronald，Nievergelt Jurg，Pippenger Nicholas，et al.Extendible hashing：a fast access method for dynamic files［J］.ACM Transactions on Database Systems，1979，4(3)：315-344.

［3］Lirwzn W.linear hashing：a new tool for files and table addressing ［C］//Proceedings of the 6th Conference on VLDB.Montreal：VLDB Endowment，1980：212-223.

［4］Ellis C S.Concurrency in linear hashing ［J］.ACM Transactions on Database Systems，1987，12(2)：195-217.

［5］Hsu M，Yang W.Concurrent operations in extendible hashing［C］//Proceedings of the 12th Conference on VLDB.Kyoto：Morgan Kaufmann Publishers Inc，1986：241-247.

［6］Kumar Vijay.Concurrent operations on extendible hashing and its performance ［J］.Communications of the ACM，1990，33(6)：681-694.

［7］Lea D.Hash table util.con current.concurrent hash map，revision 1.25，in JSR-166，the proposed Java Concurrency package ［EB/OL］.(2013-12-01)［2014-03-10］.http：//gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/.

［8］Gao H，Groote J F，Hesselink W H.Almost wait-free resizable hashtables［C］//Proceedings of the 18th International Parallel and Distributed Processing Symposium.Santa Fe：IEEE，2004：681-689.

［9］Shalev Ori，Shavit Nir.Split-ordered lists：lock-free extensiblehash tables (poster paper) ［J］.Journal of the ACM，2006，53(3)：379-405.

［10］Zhang D，Larson P-A.LHlf：lock-free linear hashing［C］//Proceedings of the 17th ACM SIGPLAN Symposium on Principles＆Practice of Parallel Programming.New York：ACM，2012：307-308.

［11］陳虎，唐海浩，廖江苗，等.面向批量插入優(yōu)化的并行存儲(chǔ)引擎MTPower ［J］.計(jì)算機(jī)學(xué)報(bào)，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.

［12］黃玉龍，奚建清，張平健，等.GBLHT：一種GPU 加速的批量插入線性哈希表［J］.華南理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2012，40(4)：49-56.Huang Yu-long，Xi Jian-qing，Zhang Ping-jian，et al.GBLHT：a GPU-accelerated linear Hash table with batch insertion ［J］.Journal of South China University of Technology：Natural Science Edition，2012，40(4)：49-56.

［13］NVIDIA Corporation.NVIDIA CUDA programming guide version 4.2［EB/OL］.(2012-04-16)［2014-03-10］.http：//docs.nvidia.com/cuda/cuda-c-programming-guide/index.html#ixzz3I5UFqJtq.

［14］Bell N，Hoberock J.Thrust：a productivity-oriented library for CUDA［EB/OL］.(2012-12-10)［2014-03-10］.http：//cloud.github.com/downloads/thrust/thrust/Thrust% 3A%20A% 20Productivity-Oriented% 20Library% 20for%20CUDA.pdf.

［15］Leung S-T.Array restructuring for cache locality ［R］.Seattle：Department of Computer Science and Engineering，University of Washington，1996.

［16］Enbody R J，Du H C.Dynamic hashing schemes ［J］.ACM Computing Surveys，1988，20(2)：85-113.

［17］Gonnct G H.算法和數(shù)據(jù)結(jié)構(gòu)手冊(cè)［M］.張子讓，周曉東，譯，北京：人民郵電出版社，1988.