支持分頁(yè)顯存的高性能哈希表索引系統(tǒng)①

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

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

2(中國(guó)科學(xué)院大學(xué), 北京 100049)

1 引言

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

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

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

表1 靜態(tài)哈希與動(dòng)態(tài)哈希對(duì)比

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

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

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

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

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

2 相關(guān)工作

2.1 面向GPU的高性能哈希表

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

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

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

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

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

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

2.4 當(dāng)前工作在局限GPU顯存條件下存在的缺陷

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

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

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

3.1 挑戰(zhàn)1: 哈希表鍵值對(duì)在沖突處理的開(kāi)銷(xiāo)過(guò)大

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

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

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

上述的全新哈希表結(jié)構(gòu)設(shè)計(jì)對(duì)于局部性的GPU顯存訪(fǎng)問(wèn)模式來(lái)說(shuō), 不會(huì)因?yàn)閿?shù)據(jù)在主存中而降低讀寫(xiě)速度, 反而會(huì)因?yàn)椴怀Ｓ玫臄?shù)據(jù)不占用顯存空間而節(jié)省空間, 讓同一個(gè)進(jìn)程的其他部分甚至其他CUDA進(jìn)程獲得更多可用的顯存空間.

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

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

4 方案設(shè)計(jì)

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

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

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

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

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

通過(guò)如上的架構(gòu)設(shè)計(jì), Starfish構(gòu)建了子表內(nèi)存頁(yè)的獨(dú)立緩存空間, 通過(guò)對(duì)大規(guī)模的哈希表結(jié)構(gòu)進(jìn)行均衡切分和輪轉(zhuǎn)實(shí)現(xiàn)局部獨(dú)立處理. 此外, Starfish系統(tǒng)支持動(dòng)態(tài)增減子表的數(shù)目, 不僅能夠?yàn)樯蠈拥墓１淼乃饕僮魈峁╈o態(tài)哈希表策略的高性能操作, 而且通過(guò)彈性化的GPU顯存控制, 實(shí)現(xiàn)了動(dòng)態(tài)化大規(guī)模哈希表應(yīng)用.

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

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

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

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

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

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

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

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

插入過(guò)程的核函數(shù)的偽代碼如算法1所示, 在第2-4行中每個(gè)線(xiàn)程從輸入的

算法 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

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

5 實(shí)驗(yàn)和結(jié)果分析

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

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

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

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

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

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

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

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

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

5.3 哈希表查找性能評(píng)估

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

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

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

5.4 低顯存性能評(píng)估

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

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

圖7 顯存使用量對(duì)比

6 結(jié)語(yǔ)

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