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

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

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

1 引言

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

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

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

表1 靜態(tài)哈希與動態(tài)哈希對比

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

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

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

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

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

2 相關(guān)工作

2.1 面向GPU的高性能哈希表

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

2.2 靜態(tài)哈希相關(guān)研究工作

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

2.3 動態(tài)哈希相關(guān)研究工作

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

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

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

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

3 挑戰(zhàn)及應(yīng)對

總結(jié)GPU哈希表設(shè)計面臨的技術(shù)挑戰(zhàn)如下.

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

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

3.2 挑戰(zhàn)2: 無法支持GPU顯存外哈希表索引

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

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

3.3 挑戰(zhàn)3: 可擴展性與性能缺陷

針對當前的動態(tài)哈希和靜態(tài)哈希優(yōu)缺點和高性能的技術(shù)挑戰(zhàn), 本文提出了一種新的基于頁表切分區(qū)域管理的哈希表數(shù)據(jù)結(jié)構(gòu)表示, 以融合兩種哈希表的高性能和高可擴展性優(yōu)勢. 進一步, 本文設(shè)計了哈希表原型系統(tǒng)StarFish以支持上層的高性能哈希應(yīng)用, 支持各類增刪改查的哈希表事務(wù)操作.

4 方案設(shè)計

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

4.1 Starfish架構(gòu)設(shè)計

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

圖1 Starfish 整體架構(gòu)

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

通過如上的架構(gòu)設(shè)計, Starfish構(gòu)建了子表內(nèi)存頁的獨立緩存空間, 通過對大規(guī)模的哈希表結(jié)構(gòu)進行均衡切分和輪轉(zhuǎn)實現(xiàn)局部獨立處理. 此外, Starfish系統(tǒng)支持動態(tài)增減子表的數(shù)目, 不僅能夠為上層的哈希表的索引操作提供靜態(tài)哈希表策略的高性能操作, 而且通過彈性化的GPU顯存控制, 實現(xiàn)了動態(tài)化大規(guī)模哈希表應(yīng)用.

4.2 面向局限GPU顯存空間的哈希表事務(wù)優(yōu)化

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

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

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

圖2 Starfish 哈希表事務(wù) 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)操作放入顯存空間后再進行并行事務(wù)操作更為適合. 以圖3為例, 具體的查找過程如下: (1) Starfish構(gòu)建統(tǒng)一化query查詢數(shù)組對各個查詢事務(wù)進行組合封裝形成查詢集, 歸并后加載至GPU顯存后, 執(zhí)行索引GPU核函數(shù)在GPU哈希緩存頁中進行并行檢索. ChildTable1和ChildTable2內(nèi)存頁為階段性緩存于GPU內(nèi)存頁中,GPU將執(zhí)行檢索(search)核操作對所有輸入的查詢事務(wù)集合并行檢索. 然而, 在檢索過程中, 由于存在哈希索引沖突, 為了進一步降低被重新索引開銷, 我們將成功哈希檢索到的鍵值key在查詢集合(queries)中置空.(4)在對ChildTable1和ChildTable2的操結(jié)束作之后,Starfish將ChildTable1內(nèi)存頁置換到主機內(nèi)存上, 然后將ChildTable3放入顯存, 再在ChildTable3上對查詢集合中還未被成功查找到的queries進行查找.

圖3 Starfish 哈希表事務(wù) search 操作

4.3 基于高并發(fā)的 Starfish 哈希事務(wù)核函數(shù)優(yōu)化

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

插入過程的核函數(shù)的偽代碼如算法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

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

5 實驗和結(jié)果分析

5.1 實驗環(huán)境及數(shù)據(jù)

實驗運行環(huán)境為Ubuntu 16.09, GPU為NVIDIA P100 12 GB, 代碼為C++, 用于測試的數(shù)據(jù)為隨機生成的不重復(fù)key的鍵值對序列. 本節(jié)會將Starfish與經(jīng)典的靜態(tài)哈希—cudpp-Hash以及經(jīng)典的動態(tài)哈?！猄labHash進行對比, 將Starfish中每個ChildTable的容量設(shè)為最高100萬個鍵值對.

5.2 哈希表構(gòu)建性能評估

正常情況下, 哈希表構(gòu)建或者插入的時延應(yīng)該將輸入鍵值對傳入顯存的時間計算在內(nèi), 因此對于Starfish的構(gòu)建性能評估將會包含數(shù)據(jù)傳輸?shù)臅r間.

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

圖4 構(gòu)建性能對比

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

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

圖5 重新構(gòu)建性能對比

5.3 哈希表查找性能評估

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

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

圖6 并發(fā)查找性能對比

5.4 低顯存性能評估

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

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

圖7 顯存使用量對比

6 結(jié)語

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