支持分頁顯存的高性能哈希表索引系統①

熊軼翔, 蔣筱斌, 張 珩, 武延軍

1(中國科學院 軟件研究所, 北京 100190)

2(中國科學院大學, 北京 100049)

1 引言

哈希表(hash table), 也稱散列表, 是一種根據關鍵碼值技術(key value)來為大規模數據提供直接訪問操作的數據結構, 其通過將關鍵碼值映射到表中的一個位置來訪問記錄數據, 以O(1)時間復雜度來加快數據查找速度. 哈希表作為一種廣泛采用的基礎數據結構和核心算法, 為程序提供對各類數據(文本、流媒體、結構型數據等)高吞吐、低時延的增刪查改操作. 隨著數據規模的不斷擴大和各類應用對高性能的需求, 哈希表技術在當前數據庫軟件、系統軟件和應用軟件中都得到了大規模采用.

在深度學習框架TensorFlow和PyTorch對稀疏矩陣的處理中, 哈希表的應用大幅度提高存儲效率, 也保證了數據塊的吞吐低延遲; 在大規模數據處理應用(圖處理[1,2])中, 哈希表的高效查詢作用至關重要. 此外, 哈希表作為數據庫系統的核心模塊[3-6], 頻繁地被大規模并發事務的索引、更新、刪除等操作調用. 在游戲應用領域, 對動輒上百萬體素的游戲模型修改和訪問[7],哈希表提供系統的可靠性保障. 由于哈希表作為各類系統的核心數據結構來使用, 因此, 對于哈希表的高性能優化能使整體系統的性能、可擴展性各方面得到大幅度提升[6,8,9]. 如何進一步優化哈希表性能以及在各類新型的并行計算機架構上設計高性能哈希表一直是學術界和工業界重點關注的研究領域. 當前的研究對哈希表的數據結構設計、并行度優化、索引沖突等多方面開展各類工作. 在并行哈希表的優化上, 這類研究工作多基于多核CPU架構開展, 設計了面向非統一內存訪問(NUMA)、對稱多處理(SMP)等高性能服務器架構的哈希表結構優化[10], 并通過融合其他數據結構(如索引樹形、環形緩存隊列等)以提高哈希表的并行處理性能, 降低多線程下的哈希索引沖突. 隨著高性能的體系結構發展, 通用圖形處理器(GPU)作為協處理器的性能得到了大幅度提升. 單塊GPU處理單元提供了萬級以上線程數的高并行計算能力和高于100 GB/s顯存帶寬, 大幅提高高通量工作負載的性能, 例如, 單塊NVIDIA V100 GPU卡提供了多達5 120流處理單元. 高性能哈希表的研究工作開始利用協處理GPU的大規模并行和高性價比的優勢來優化哈希表的大規模并發散列事務操作[7,11], 例如, 英偉達cudpp[12,13]設計靜態哈希操作, 顯著地提高了數據索引性能, 相對比sorted array[14]、cuckoo[15]等各類CPU索引方法性能提升1-3倍[12,16]. 在對于GPU哈希操作的優化中, 相同哈希值的鍵值對無法存放在哈希表中的相同位置導致了GPU大規模線程間哈希沖突(溢出處理)開銷, 因此GPU哈希表工作著重于優化GPU內并行處理來離散線程間訪問, 降低索引沖突. 進而, GPU哈希表研究衍生出動態哈希和靜態哈希兩類工作.

通過前期的調研, 目前主流的GPU哈希操作主要使用cuckoo哈希算法的靜態哈希, 在插入和查找時采用固定大小的GPU顯存預分配, 因而其并行度更為線性, 整體性能高, 然而由于預分配需要占用大量GPU顯存空間, 導致GPU顯存利用率地下, 缺乏可擴展性;而使用“桶”策略的動態哈希表在具備了可擴展性的同時彈性的“桶”緩存分配帶來了一定的顯存操作開銷,其整體性能略遜于靜態哈希策略. 具體地, 表1給出了當前GPU哈希策略方法的優缺點對比.

表1 靜態哈希與動態哈希對比

然而, 高性能哈希表的研究多采用單一設計模式,即選擇性地構建靜態哈?；騽討B哈希, 沒有很好融合這兩類哈希表的優點, 同時, 由于GPU顯存占用率非常高,在顯存不足以存放整張哈希表時整體系統無法正常運行. 綜上, 現有GPU高性能哈希表的研究工作仍然存在如下兩類缺陷: (1)由于GPU全局顯存的局限性(如V100 GPU提供32 GB DDR5全局顯存), 現有工作受限于存放大規模的哈希表結構, 無法支持超過GPU顯存的哈希事務, 整體系統的可擴展性和彈性受到限制;(2)隨著數據量不斷增大, 導致以多核優化的哈希表方法無法滿足高性能的數據索引操作. GPU顯存資源在同一時間會有多個任務同時需要占用, 導致留給高性能哈希表的空間不足以處理更多的并發訪問事務. 當空間不足但是任務所需要處理的數據量較大時, 目前的哈希表設計就略顯不足了. 因此, 對哈希表結構的空間結構的壓縮和數據結構的分布優化顯得至關重要.

本文聚焦于結合靜態哈希和動態哈希各自的優點,借鑒Linux的頁面交換機制, 設計一種兼具高性能和高擴展性且對于顯存空間受限GPU架構的全新高性能哈希表結構和方法. 本文將傳統的哈希表分割為多個子表(文中可能同時稱作子表或ChildTable), 并使用子表來支持GPU優化, 通過stream支持流水線insert操作, 利用GPU多線程機制支持search以及delete, 相對現有工作提升了insert操作性能1.5-2倍. 本文主要貢獻如下:

(1)針對GPU顯存占用過高以及靜態哈希表插入性能缺陷問題, 本文首次提出多子表技術, 即構建層級頁表機制來將結構過大的哈希表分解為多個小結構表來統一管理; 構建局部GPU顯存駐留策略, 以支持同一時刻只需駐留少部分子表的GPU工作流, 大大降低GPU顯存占用率.

(2)進一步, 本文設計了Starfish原型系統, 以支持各類GPU哈希表操作, 不限于select/insert以及update操作, 并優化多子表技術將insert操作流水線化, 在提升并行度的同時大幅度降低插入失敗時重新哈希表結構構建開銷.

(3)實驗結果表明, 在多類現實標準數據集上的測試, Starfish在insert以及重新構建的性能方面, 相對于NVIDIA最新的GPU哈希表工作cudpp-Hash顯著提高了1.5-2倍; 顯存占用量降低為cudpp-Hash的5%-10%以及SlabHash的1%-2%.

2 相關工作

2.1 面向GPU的高性能哈希表

隨著各類高性能協處理器單元(如GPU)的架構性能不斷提升, 當前的學術研究方向開始轉向利用GPU服務器來設計高性能的哈希表操作. 相對比CPU處理器上有限線程的并行計算環境, 通過GPU協處理器上基于單指令多數據流(SIMD)芯片架構特性來構建全新的哈希表并行事務策略的處理性能得到了顯著提升, 提升了若干數量級[12,13,18,19]. 各類并行哈希操作的優化工作利用GPU等大規模并行硬件特性來進行加速, 主要通過如下兩個方面進行: 1) SIMT架構為哈希表的并行操作提供了只讀性事務的大規模并行;2)高內存帶寬為哈希表的數據訪問帶來了大數據量的訪問吞吐提升以及高效的原子性操作. GPU哈希表cudpp-Hash[12,13]利用的cuckoo哈希方法以及公共溢出區策略, 第一次提出了標準的GPU下哈希操作, 被廣泛應用于NVIDIA下的各類算法庫[18,19]. 通常地, 現有GPU哈希工作主要分為兩類: 一類是面向靜態GPU顯存空間分配的靜態哈希表, 另一類是以動態頁表方式提供彈性GPU顯存優化的動態哈希表. 這兩類工作各有所長, 具體如本節接下來所述.

2.2 靜態哈希相關研究工作

面向GPU的靜態哈希表都是基于cuckoo策略[15]來處理哈希沖突, 但也有不使用cuckoo策略的哈希表設計, 例如Khorasani等人提出的stadium hash[20]在解決沖突的時候不會驅逐原有的鍵值對, 而是直接尋找下一個合適的位置. 最經典的GPU靜態哈希表為Alcantara等人提出的cudpp-Hash[12,13,16], 已被Nvidia作為標準哈希庫推出, 其算法策略采用cuckoo實現, 此外還加入了stash的機制來盡量減少插入失敗的頻率. cuckoo的多個備用哈希函數機制會帶來重復探測次數過多而導致的性能下降問題, 因此Breslow等人提出的Horton table[21]使用了一種緊湊的數據結構來存放鍵值對使用的備用哈希函數索引, 以減小重復探測的次數. 除此之外, 與cudpp類似且比較能適應大規模并行的哈希表還有使用羅賓漢哈希方法[22]的 coherent parallel hashing[23], 但是同樣面臨著靜態哈希的常見困境.

2.3 動態哈希相關研究工作

Ashkiani等人提出了一種面向GPU的動態哈希表SlabHash[17], 利用動態哈?！巴啊钡乃枷氡荛_了處理哈希沖突的挑戰, 而是在發生哈希沖突時將鍵值對直接插入目標“桶”中. 在進行事務操作過程中, 以warp為單位并大量使用ballot、shuffle等warp內部通信的API來加速處理. 此外還設計了SlabAlloc機制來以warp為單位動態分配新的slab空間. 這樣的實現在用戶看來是動態的, 且不會像靜態哈希那樣發生插入失敗的問題, 但實際上是以較大的顯存空間浪費為代價的.

作為最新的GPU哈希表研究工作, slab hash[17]和stadium hash[20]基于GPU架構提出了當前性能和可擴展性較好的設計, 其中slab hash是一類典型的動態哈希表, stadium hash是一種靜態的哈希表. 此外, 已廣泛應用于NVIDIA RAPIDS框架[19]的cuDF哈希策略和HashGraph[24]兩種哈希表的實現更加具有可擴展性和靈活性, 然而由于其采用過高顯存頻率操作而造成內存性能瓶頸, 導致了嚴重的性能抖動.

2.4 當前工作在局限GPU顯存條件下存在的缺陷

從目前研究工作來看, GPU哈希表策略大多基于將整個哈希表存放于顯存中來設計的, 但是如果哈希表太大而GPU所剩的顯存空間無法滿足要求時, 這些設計就無法正確運行起來. 因此Khorasani等人提出的stadium hash[20]提出了一種out-of-core的策略, 用戶可以自行選擇將哈希表存放于顯存或者主存, 當存放于主存時, stadium hash使用一種ticket board的機制來減少顯存與主存之間不必要的PCI-E交換, 以此達到降低使用鎖頁內存帶來的性能損耗. 另外同樣使用類似out-of-core方法的哈希表還有Hopscotch hashing[25]和Cache-Oblivious hashing[26].

3 挑戰及應對

總結GPU哈希表設計面臨的技術挑戰如下.

3.1 挑戰1: 哈希表鍵值對在沖突處理的開銷過大

傳統的靜態哈希表在發現某個鍵值對完全無法插入的情況下(failure)則會重建整張表, 當這種事件發生在整個建表的尾期時, 則將會將前期所有完成的工作都丟棄然后進行重新構建(restart), 這樣會造成極大的浪費. 因此本文擬提出一種failure處理機制, 將failure的影響范圍縮小到一個較小的區間, 在這個區間內進行restart, 將整個failure處理的過程都控制在這個區間內, 這樣發生failure之后和進行restart都不至于影響整個哈希表. 發生failure的后果就是影響建表性能,因此本文的設計旨在降低failure對于性能的影響.

3.2 挑戰2: 無法支持GPU顯存外哈希表索引

由于GPU協處理器的顯存資源有限, 因此每個應用程序在占用GPU顯存時所能獲得的資源多采用共享GPU顯存模式, 即各自占用百分比顯存空間, 這將導致在GPU顯存空間受限情況下大規模哈希表結構無法完整緩存于GPU顯存空間, 將導致整體的性能和可擴展性受限. 通過前期調研, 當前GPU哈希表的實現均在顯存可容納整張表或者整張表完全放在pinned memory的前提下開展研究, 然而有限顯存空間無法容納整張哈希表; 若干工作提出利用統一地址空間對GPU顯存擴展[20], 然而這類哈希事務的訪問仍需要利用PCI-E來進行大量的host端和GPU device端的數據交換操作, 導致數據訪問效率低下. 因此, 本文提出了一套全新的GPU核外計算(out-of-GPU-memory)的策略, 將哈希表中暫時不用的子表緩存空間從顯存中交換(swap)到host端主存中, 而當前需要訪問的熱度哈希表部分則駐留在GPU顯存中. 此外, 通過自定義顯存駐留表大小和數目, 本文設計了顯存的占用的彈性伸縮機制, 根據用戶配置項設置顯存空間占用.

上述的全新哈希表結構設計對于局部性的GPU顯存訪問模式來說, 不會因為數據在主存中而降低讀寫速度, 反而會因為不常用的數據不占用顯存空間而節省空間, 讓同一個進程的其他部分甚至其他CUDA進程獲得更多可用的顯存空間.

3.3 挑戰3: 可擴展性與性能缺陷

針對當前的動態哈希和靜態哈希優缺點和高性能的技術挑戰, 本文提出了一種新的基于頁表切分區域管理的哈希表數據結構表示, 以融合兩種哈希表的高性能和高可擴展性優勢. 進一步, 本文設計了哈希表原型系統StarFish以支持上層的高性能哈希應用, 支持各類增刪改查的哈希表事務操作.

4 方案設計

本文聚焦于結合動態哈希表和靜態哈希表各自的優點, 基于分層頁表機制提出了一種全新的GPU動態化顯存頁分配與靜態操作的哈希表——Starfish, 并且具備低顯存的能力.

4.1 Starfish架構設計

面向GPU的哈希表系統Starfish的總體技術架構圖如圖1所示. 頂層架構分為兩個部分: 主控邏輯端(host)的CPU處理器主內存的Daemon模塊(圖1中的①)、事務性哈希表數據I/O模塊②以及協處理器控制邏輯GPU執行部分(kernel計算服務模塊③).

圖1 Starfish 整體架構

其中, Daemon主控邏輯①用于管理整個系統, 記錄了當前的子表數、駐留在GPU中的子表索引, 以及指向主存和顯存中多個子表的指針. 一個頁面(子表)就是一個可以向下兼容的完整的底層哈希表, 可以使用cudpp-Hash、horton table等來作為底層哈希表.具體地, Starfish的數據I/O模塊②通過構建頁表的數據結構(ChildTable, 子表)方式來對動態哈希頁進行統一化管理; 所有的底層哈希表(稱為子表)以固定內存頁(默認情況下64 MB)形式進行構建, 其組成形式以若干

通過如上的架構設計, Starfish構建了子表內存頁的獨立緩存空間, 通過對大規模的哈希表結構進行均衡切分和輪轉實現局部獨立處理. 此外, Starfish系統支持動態增減子表的數目, 不僅能夠為上層的哈希表的索引操作提供靜態哈希表策略的高性能操作, 而且通過彈性化的GPU顯存控制, 實現了動態化大規模哈希表應用.

4.2 面向局限GPU顯存空間的哈希表事務優化

由于GPU顯存空間的局限性, 大規模哈希表事務操作無法完整地利用GPU進行并行操作, 這也帶來了目前各類哈希表的高性能操作的可擴展性局限. 為了解決大規模哈希表結構在CPU-GPU之間的高效吞吐問題, Starfish基于CUDA Streaming對象策略, 在ChildTable數據結構基礎上構建了高效的哈希表內存頁置換策略. 通過設置哈希表數據緩存區大小閾值,Starfish在哈希表數據量只夠部分存放于GPU顯存空間情況下, 自動地啟用CPU與GPU間數據I/O輪轉策略, 將整體的哈希操作進行均衡切分, 存放哈希表的部分于顯存. 下面, 本小節將對Starfish所支持的哈希表操作的插入(insert)、檢索(search)等關鍵操作的實現流程進行詳細闡述.

4.2.1 基于CUDA Streaming異步策略的插入操作

在哈希表插入操作(insert)過程中, 無需把所有的輸入數據和整個哈希表都存放于顯存中. 如圖2所示,在輸入(input)哈希事務為3個事務數據列表時, 每段輸入事務數據列表長度相等且都為默認的100萬個鍵值對, 允許最后一段長度小于其他段. 在顯存上只開辟兩段對應的input事務列表空間以及兩段ChildTable空間. 以圖2為例, Starfish的插入過程: (1)考慮到GPU緩存空間局限, 將只對input1和input2的插入事務列表加載至GPU顯存空間. 進一步據這兩個事務集合構建GPU哈希表內存頁ChildTable1和ChildTable2;進而, input3插入事務集合的執行無法完整地緩存至GPU顯存空間, 因此Starfish將ChildTable1從顯存中傳輸到主機上存放, 并且將input3加載至顯存, 在原有ChildTable1的緩存空間構建ChildTable3顯存頁; 以此操作循環, 直至將所有的插入事務集合處理完成, 并且所有ChildTable數組都傳輸到CPU主存端備份. 由于對多個互相獨立的ChildTable操作獨立化, 因此Starfish在構建插入事務哈希表空間時實現了高性能的并行加載和備份機制. 進一步, 基于CUDA Streaming對象策略, Starfish CUDA通過設置若干個Stream來異步化ChildTable內存頁的CPU-GPU的I/O操作和GPU核函數的并行執行, 通過對不同ChildTable構建任務異步化, 從而能讓不同ChildTable的PCI-E數據傳輸和kernel運行同時進行, 隱藏數據傳輸時間或者kernel運行時間.

圖2 Starfish 哈希表事務 insert 操作

算法 1. Insert偽代碼(1) FUNCTION(Keys, Vals)(2) myKey = Kyes[myId]; myVal = Vals[myId];(3) myKV = makeKV(myKey, myVal);(4) myLocation = hashFunction(constants[0], myKey);(5) FOR I in 1 to maxAttempts do(6) KV = atomicExch(table[location], myKV);(7) IF KV is EMPTY or DELETED THEN break;(8) END IF(9) determine_next_location(KV);(10) END FOR(11) IF KV is not EMPTY THEN(12) IF TryToInsertIntoStash(KV) is successed THEN(13) RETURN true;(14) END IF(15) RETURN false;(16) END IF(17) RETURN true;(18) END FUNCTION

4.2.2 基于順序粒度組合的高效索引(search)操作

如圖3中所示, 在索引(search)過程中, 考慮到各個索引查詢(query)的粒度大小對于整個表的緩存空閑相對較小, 因此將所有查詢集合(queries)操作放入顯存空間后再進行并行事務操作更為適合. 以圖3為例, 具體的查找過程如下: (1) Starfish構建統一化query查詢數組對各個查詢事務進行組合封裝形成查詢集, 歸并后加載至GPU顯存后, 執行索引GPU核函數在GPU哈希緩存頁中進行并行檢索. ChildTable1和ChildTable2內存頁為階段性緩存于GPU內存頁中,GPU將執行檢索(search)核操作對所有輸入的查詢事務集合并行檢索. 然而, 在檢索過程中, 由于存在哈希索引沖突, 為了進一步降低被重新索引開銷, 我們將成功哈希檢索到的鍵值key在查詢集合(queries)中置空.(4)在對ChildTable1和ChildTable2的操結束作之后,Starfish將ChildTable1內存頁置換到主機內存上, 然后將ChildTable3放入顯存, 再在ChildTable3上對查詢集合中還未被成功查找到的queries進行查找.

圖3 Starfish 哈希表事務 search 操作

4.3 基于高并發的 Starfish 哈希事務核函數優化

在GPU的SIMD編程模式下, GPU中的若干個線程可以并行運行相同的代碼, 考慮到Starfish已經具備了動態插入的功能, 因此在核函數的設計中沿用了傳統的cuckoo策略來提高插入/查找的性能. 為了增強子表的容錯性, Starfish在每個子表末尾增加了108個

插入過程的核函數的偽代碼如算法1所示, 在第2-4行中每個線程從輸入的

算法 2. Search偽代碼(1) FUNCTION(Queries, Outputs)(2) myKey = Queries[myId];(3) IF myKey is EMPTY THEN RETURN;(4) END IF(5) FOR j in 0 to numFunc do(6) location = hashFunction(constants[i], myKey);(7) KV = table[location];(8) IF getKey[KV] equals myKey THEN(9) Outputs[myId] = getVal[KV];(10) Queries[myId] = EMPTY; RETURN;(11) END IF(12) END FOR(13) Location = SearchInStash(myKey);(14) IF location is valid THEN(15) Outputs[myId] = stash[location];(16) Queries[myId] = EMPTY;(17) RETURN;(18) END IF(19) RETURN;(20) END FUNCTION

查找過程核函數的偽代碼如算法2所示, 第2行從輸入請求查找數組中取出鍵, 第5-12行按照候選哈希函數的順序對鍵進行單詞或多次探測, 若成功命中則將請求查找數組中當前鍵的位置置空, 以避免接下來在其他子表中對其重復查找.

5 實驗和結果分析

5.1 實驗環境及數據

實驗運行環境為Ubuntu 16.09, GPU為NVIDIA P100 12 GB, 代碼為C++, 用于測試的數據為隨機生成的不重復key的鍵值對序列. 本節會將Starfish與經典的靜態哈?！猚udpp-Hash以及經典的動態哈?！猄labHash進行對比, 將Starfish中每個ChildTable的容量設為最高100萬個鍵值對.

5.2 哈希表構建性能評估

正常情況下, 哈希表構建或者插入的時延應該將輸入鍵值對傳入顯存的時間計算在內, 因此對于Starfish的構建性能評估將會包含數據傳輸的時間.

由圖4可以看出, 在數據量超過500萬個鍵值對時Starfish-x (這里的x代表顯存中開辟的空間可容納x個ChildTable)的性能得到了顯著提升, 達到了cudpp-Hash的2倍. 同時可以發現ChildTable數據量(x)逐步增大時, Starfish的性能表現更為優越, 這是因為Child Table數據量越大時, 通過PCI-E進行緩存空間swap的頻率越低, 而PCI-E傳輸相對事務性并行操作開銷較大.

圖4 構建性能對比

緩存空間(swap)的頻率越低, 而PCI-E傳輸相對事務性并行操作開銷較大. 另外, SlabHash-n (n代表平均鏈表長度)在平均鏈表長度越大時要進行的平均顯存次數也會更大, 所以性能也越低.

靜態哈希表在構建過程中還可能發生插入失敗后重新構建的情況, 因此只需要與cudpp-Hash進行比較.由圖5可以看出, 在數據量超過100萬時, Starfish的重新構建性能均超過了cudpp-Hash, 甚至能達到cudpp-Hash的兩倍, 這是因為cudpp-Hash在插入失敗時需要重新構建整個表, 而Starfish只需要構建當前的ChildTable.

圖5 重新構建性能對比

5.3 哈希表查找性能評估

進一步, 本小節對Starfish的并發查找(search)操作的性能進行了評估. 對比系統包括經典的GPU下hash table靜態哈希表cudpp-Hash和動態哈希表SlabHash(bucket長度設置為2), 用以評估Starfish的查找性能和并發事務處理性能.

如圖6所示, 本文對這兩類哈希表和Starfish分別進行了并發查找性能測試, 每種表均由800萬個不重復的鍵值對進行構建. 在顯存駐留空間設置為2個ChildTable配置的情況下, Starfish-2在并發查找請求平均分布于第一個子表和前兩個子表時, 查找速度顯著優于cudpp-Hash和SlabHash, 達到cudpp-Hash的4.7倍和2.6倍. 這是由于Starfish在并發量滿足GPU計算局部性的情況下, 只需要對駐留于顯存中的子表進行查找, 且在駐留子表中查找所用的開銷會遠低于在整張靜態哈希表(cudpp-Hash)中查找的開銷.同時, 在并發查找請求局部性較差時(圖6中并發事務達到200萬以上), Starfish需要在非駐留子表中進行查找, 因此需要通過PCI-E總線交換子表數據, 在訪存和CPU主存間的數據通信過程帶來了一定的開銷, 因此Starfish的并發事務查找速度略低于cudpp-Hash查找性能一半. 進一步實驗驗證, Starfish-4與Starfish-2在查找性能上表現相似特征. 考慮到真實業務場景中在對哈希表查找事務的并發性要求著重于提供分布式配置優化, 本文擬將本部分大規模并發性查找事務的性能優化留于未來工作.

圖6 并發查找性能對比

5.4 低顯存性能評估

對比現有哈希表的GPU并行化工作, Starfish的性能優勢之一來源于GPU顯存的節約效果顯著以及顯存資源的充分利用. 因此, 本文將Starfish與cudpp-Hash以及SlabHash進行了顯存占用量的對比, 評估中除去了CUDA context的空間, 只關注于哈希表本身.

如圖7所示, 在同等輸入規模下, SlabHash的顯存使用量明顯高于Starfish與cudpp-Hash, 因為SlabHash以預分配GPU顯存空間機制, 在進行哈希事務操作之前提前占用了所有的GPU顯存實現哈希動態化插入策略, 帶來了大量的顯存資源開銷. 而Starfish所占用的顯存空間比cudpp-Hash要明顯降低, 并且Starfish在設置固定的駐留表數目之后的顯存占用量不會隨著輸入規模的增加而增加, 這也顯著地降低了cudpp-Hash以及SlabHash所帶來的GPU顯存開銷. Starfish不僅能夠支持高性能的GPU哈希表操作, 而且提供了相對更為節約的GPU顯存空間利用, 為大規模哈希表操作在GPU上的并行高性能應用提供了支撐.

圖7 顯存使用量對比

6 結語

針對目前GPU靜態哈希表面臨的可擴展性差以及failure處理代價高昂的問題, 提出了子表技術來應對. 對于動態哈希表面臨的性能不佳問題, 提出了在子表技術的基礎上, 將子表布局為靜態哈希表來提高局部性能的思路. 進而, 為了應對當前GPU顯存資源不足的情況, 將子表技術結合頁面交換機制, 在保證性能的前提下極大降低了哈希表所占用的顯存空間, 并且在保證并發查找局部性的前提下顯著提高了查找性能.此外, 具有高可擴展性、高性能以及低顯存占用的Starfish哈希表可用于大型數據庫、高性能計算中超大模型的局部計算等大數據加速任務當中.