劉勇 奚建清 黃東平 賈連印 苗德成

(華南理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 廣州 510006)

在數(shù)據(jù)庫系統(tǒng)中，索引是加快檢索表中數(shù)據(jù)的一種直接有效的方法.由于索引項(xiàng)的空間比記錄小，因此減少查詢讀取的數(shù)據(jù)量，可以提高查詢效率.自內(nèi)存數(shù)據(jù)庫的概念被提出以來［1］，為適應(yīng)內(nèi)存數(shù)據(jù)庫及硬件環(huán)境的要求，人們除了繼續(xù)引用一些傳統(tǒng)的索引到內(nèi)存數(shù)據(jù)庫中之外，還提出了多種新的內(nèi)存索引技術(shù)和改進(jìn)方案.Rao 等［2］在傳統(tǒng)B+-樹索引的基礎(chǔ)上，提出了基于緩存敏感技術(shù)的CSS-樹索引，具有比傳統(tǒng)內(nèi)存數(shù)據(jù)庫索引(如T-樹和B+-樹)查找速度更快且空間占用率更小的性能.針對CSS-樹無法解決索引數(shù)據(jù)的有效更新問題，Rao 等［3］提出了CSB+-樹索引，它既具有與CSS-樹相似的緩存性能，又具有B+-樹的更新操作性能.

CSB+-樹的結(jié)構(gòu)與傳統(tǒng)B+-樹的結(jié)構(gòu)類似，區(qū)別在于:CSB+-樹的每個父節(jié)點(diǎn)只保留指向第一個孩子節(jié)點(diǎn)的指針，其他孩子節(jié)點(diǎn)的地址可通過計(jì)算與第一個孩子節(jié)點(diǎn)的偏移量得出;在CSB+-樹中，一個節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)按序存儲并構(gòu)成一個邏輯上的節(jié)點(diǎn)組.由于只保留一個指向孩子節(jié)點(diǎn)的指針，對于同樣大小的內(nèi)部節(jié)點(diǎn)，CSB+-樹的扇出率比B+-樹提高近1 倍，因此在一個緩存行里可存放更多的索引鍵，從而既提高了緩存的命中率，又節(jié)省了存儲空間.

目前，基于圖形處理器(GPU)的索引技術(shù)已有相關(guān)的研究，但它們在索引的并行創(chuàng)建和可操作性等方面存在著一定的不足.Fix 等［4］提出了基于GPU 的B+-樹并行遍歷算法，但因B+樹是直接從CPU 上拷入GPU 端而未能利用GPU 的并行處理能力;Christensen 等［5］提出了優(yōu)化的CSS-樹多線程并行構(gòu)建算法，但僅實(shí)現(xiàn)了單個節(jié)點(diǎn)內(nèi)部鍵值的并行創(chuàng)建，而且在其基于線程塊查詢的優(yōu)化算法中，也未考慮線程塊出現(xiàn)線程分支的情形，從而影響程序的性能且若采用線程同步命令時還會引起程序出錯等問題;Kaczmarski［6］根據(jù)傳統(tǒng)B+樹的批量裝載算法，提出了一種基于樹層的自底向上并行構(gòu)建算法，該算法的并行度較文獻(xiàn)［5］中算法有所提高，然而其思想是建立在傳統(tǒng)CPU 平臺上，因此未能充分利用GPU 的并行計(jì)算資源.Liu 等［7］在GPU 平臺上實(shí)現(xiàn)了多維線性動態(tài)哈希表的記錄批量插入，大大提高了索引的操作性能，但須借助GPU 的原子鎖函數(shù)才能完成并行處理，因此并行度不高.Kim 等［8］在CPU 和GPU 平臺上實(shí)現(xiàn)了完全二叉樹的快速構(gòu)建和遍歷算法，盡管創(chuàng)建索引樹的速度極快，但該算法比較簡單，不適用于解決復(fù)雜的問題.

近年來，GPU 的通用計(jì)算(GPGPU)［9］已經(jīng)在科學(xué)計(jì)算和數(shù)據(jù)庫技術(shù)等領(lǐng)域中得到廣泛的應(yīng)用.為此，文中在GPU 平臺上研究緩存敏感樹索引CSB+-樹的并行構(gòu)建和查詢的操作性能.

1 基于GPU 的CSB+-樹并行方案

1.1 數(shù)據(jù)結(jié)構(gòu)

目前NVIDIA CUDA 編程模型［10］尚未支持在GPU 上動態(tài)分配顯存空間，而傳統(tǒng)CSB+-樹的存儲結(jié)構(gòu)可支持索引數(shù)據(jù)的動態(tài)增減.為此，文中采用結(jié)構(gòu)體數(shù)組預(yù)分配的方式存儲CSB+-樹數(shù)據(jù)，數(shù)組的每個元素表示CSB+-樹的一個節(jié)點(diǎn)，并通過兩層數(shù)據(jù)結(jié)構(gòu)［11］實(shí)現(xiàn)結(jié)構(gòu)體數(shù)組的動態(tài)伸縮，其結(jié)構(gòu)如圖1所示.

圖1 動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)Fig.1 Data structure of dynamic array

在此結(jié)構(gòu)中，將存儲CSB+-樹數(shù)據(jù)的動態(tài)數(shù)組劃分成若干大小固定的數(shù)據(jù)段，每個數(shù)據(jù)段的首地址保存在目錄數(shù)組中;當(dāng)數(shù)組需要擴(kuò)大時，則根據(jù)所需的數(shù)據(jù)量增加新的數(shù)據(jù)段和相應(yīng)數(shù)量的目錄數(shù)組存儲空間;當(dāng)數(shù)組需要收縮時，則釋放多余的數(shù)據(jù)段和對應(yīng)的目錄數(shù)組存儲空間.假定每個數(shù)據(jù)段大小為S，則動態(tài)數(shù)組第i 個元素的段地址(sa)和段內(nèi)地址(sia)為

它在數(shù)組的地址為directory［sa］.element［sia］.

由此可知，基于GPU 平臺的CSB+-樹的數(shù)據(jù)結(jié)構(gòu)由葉子節(jié)點(diǎn)結(jié)構(gòu)、內(nèi)部節(jié)點(diǎn)結(jié)構(gòu)和它們相應(yīng)的段結(jié)構(gòu)構(gòu)成，其程序代碼如下:

在CSBplusStruct 結(jié)構(gòu)中，leaf_dir 和inter_dir 分別為存儲葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)數(shù)據(jù)的目錄數(shù)組，leaf_dirlen和inter_dirlen 分別為當(dāng)前葉子目錄數(shù)組和內(nèi)部節(jié)點(diǎn)目錄數(shù)組的長度，leaf_SP 和inter_SP 分別指向各自目錄數(shù)組中下一個待分配的0 地址.葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)采用不同的結(jié)構(gòu)，可減少不必要的指針空間浪費(fèi).

1.2 CSB +-樹的并行構(gòu)建算法

傳統(tǒng)B+-樹的批量裝載算法是將一組已排序的記錄從距根節(jié)點(diǎn)最右的路徑起逐個插入直至結(jié)束.然而，如果按此算法構(gòu)建CSB+-樹，由于同一個節(jié)點(diǎn)組內(nèi)的節(jié)點(diǎn)不是按順序建立，因此需要重新分配內(nèi)存以構(gòu)建節(jié)點(diǎn)組，其操作代價極大.為此，Rao 等［2］提出了一種效率更高的CSB+-樹批量裝載算法，該算法可以自底向上、一層層地構(gòu)建CSB+-樹，具體步驟如下:

(1)對待插入的索引記錄按關(guān)鍵字排序;

(2)根據(jù)記錄數(shù)分配CSB+-樹的葉子節(jié)點(diǎn)空間，并將記錄依次按序插入葉子節(jié)點(diǎn)內(nèi)，在樹的底層建立葉子層;

(3)根據(jù)CSB+-樹的階和下層的節(jié)點(diǎn)數(shù)計(jì)算上一層所需的內(nèi)部節(jié)點(diǎn)數(shù)，并為上層節(jié)點(diǎn)分配連續(xù)的存儲空間，節(jié)點(diǎn)內(nèi)的鍵值為其對應(yīng)下一層節(jié)點(diǎn)的最大鍵值，同時設(shè)置每個節(jié)點(diǎn)的第一個孩子指針;

(4)返回步驟(3)直至上一層的節(jié)點(diǎn)數(shù)為1，即該節(jié)點(diǎn)為CSB+-樹的根節(jié)點(diǎn).

由于在整個構(gòu)建過程，同一層的所有節(jié)點(diǎn)地址都是連續(xù)分配的，因此無需進(jìn)行任何額外的數(shù)據(jù)復(fù)制操作即可構(gòu)成一個節(jié)點(diǎn)組.由此可見，CSB+-樹的構(gòu)建包括葉子節(jié)點(diǎn)的構(gòu)建和內(nèi)部節(jié)點(diǎn)的構(gòu)建.

1.2.1 葉子節(jié)點(diǎn)的并行構(gòu)建算法

為保證CSB+-樹的存儲利用率，在初次建樹時可通過設(shè)置節(jié)點(diǎn)的填充因子α 來控制每個節(jié)點(diǎn)的記錄數(shù).假設(shè)M 是每個節(jié)點(diǎn)的記錄容量，則構(gòu)建N個數(shù)據(jù)的CSB+-樹所需分配的葉子節(jié)點(diǎn)數(shù)為

因此，可根據(jù)X 在GPU 上為葉子節(jié)點(diǎn)分配動態(tài)數(shù)組空間，然后將已排好序的數(shù)據(jù)從主機(jī)端傳輸至設(shè)備端，再將記錄并行插入到CSB+-樹的葉子節(jié)點(diǎn)中.由于線程的編號順序與葉子節(jié)點(diǎn)的編號順序相對應(yīng)，因此創(chuàng)建的CSB+-樹的相鄰葉子節(jié)點(diǎn)要按序存儲.

1.2.2 內(nèi)部節(jié)點(diǎn)的并行構(gòu)建算法

基于樹層的B+-樹內(nèi)部節(jié)點(diǎn)并行構(gòu)建算法［6］的思想與CSB+-樹的批量裝載算法相似，即節(jié)點(diǎn)內(nèi)的每一個鍵值由獨(dú)立的線程并行計(jì)算，并行的線程數(shù)由下一層的節(jié)點(diǎn)數(shù)決定，并根據(jù)樹的高度需要多次調(diào)用CUDA 核函數(shù).由于每次調(diào)用核函數(shù)后還需要線程的同步操作且這些操作需要耗費(fèi)幾百個GPU時鐘.

為此，文中提出了一種基于鍵的內(nèi)部節(jié)點(diǎn)并行構(gòu)建算法，該算法通過計(jì)算樹中內(nèi)部節(jié)點(diǎn)的每個鍵與最終葉子節(jié)點(diǎn)的對應(yīng)關(guān)系來實(shí)現(xiàn)一次性并行構(gòu)建所有內(nèi)部節(jié)點(diǎn)的鍵值.首先自下而上、自左向右地對內(nèi)部節(jié)點(diǎn)進(jìn)行編號，接著計(jì)算每個線程所代表的鍵在索引樹中的層節(jié)點(diǎn)編號layerNode 以及它在該節(jié)點(diǎn)內(nèi)的鍵編號nodeKey，然后計(jì)算該層的節(jié)點(diǎn)與節(jié)點(diǎn)之間的葉子偏移量nodeLeafs、節(jié)點(diǎn)內(nèi)部鍵之間的葉子偏移量keyLeafs，最后計(jì)算該鍵對應(yīng)的目標(biāo)葉子節(jié)點(diǎn)leaf:

leaf 的最大值為該線程所代表的內(nèi)部節(jié)點(diǎn)的鍵值.該算法的偽代碼如下:

1.3 CSB +-樹的并行查詢算法

傳統(tǒng)CSB+-樹的查詢算法主要是通過二分查找的方式，從根節(jié)點(diǎn)開始搜索，直至目標(biāo)葉子節(jié)點(diǎn).由于二分查找并不適合并行處理，因此一種比較合理的方法就是在每個節(jié)點(diǎn)的內(nèi)部采用多線程并行查找的算法.為此，Christensen 等［5］提出了一種基于線程塊的CSS-樹查詢算法，按該算法思路設(shè)計(jì)的基于線程塊的CSB+-樹內(nèi)部節(jié)點(diǎn)的并行查詢算法的偽代碼如下:

在上述算法中，為防止數(shù)組的越界訪問，當(dāng)線程tid=0 時需要進(jìn)行特殊處理，從而在線程塊中產(chǎn)生一個分支.CUDA 的指令執(zhí)行模式是SIMT 方式，warp 是CUDA 的最小調(diào)度單位，當(dāng)一個warp 內(nèi)的線程出現(xiàn)分支時，warp 將沿著每個分支調(diào)度串行化指令，直至warp 內(nèi)所有的線程可執(zhí)行相同的指令為止［12］.由此可見，當(dāng)warp 內(nèi)的線程走向不同的分支時，需要的時間是不同分支的執(zhí)行時間之和，并且分支影響了并行計(jì)算的吞吐量.為避免程序出現(xiàn)分支的情況，文中在CSB+-樹每個內(nèi)部節(jié)點(diǎn)的最左邊添加一個填充位，新的節(jié)點(diǎn)結(jié)構(gòu)如圖2 所示.

圖2 帶左填充位的節(jié)點(diǎn)結(jié)構(gòu)Fig.2 Structure of node with left padding bit

每個節(jié)點(diǎn)填充位的值可設(shè)為所有索引數(shù)據(jù)的最小值－1，修改節(jié)點(diǎn)結(jié)構(gòu)后基于線程塊的CSB+-樹內(nèi)部節(jié)點(diǎn)的查找(BlockSearchNode)算法的偽代碼如下:

2 性能分析

傳統(tǒng)緩存敏感技術(shù)的思想是利用高速存儲器來解決CPU 運(yùn)算速度快與訪存速度慢不匹配的瓶頸問題.在GPU 中常用的CUDA 程序優(yōu)化方法是利用共享存儲器來減少訪問全局存儲器的次數(shù)，從而獲得更高的內(nèi)存帶寬，如GPU 上的稀疏矩陣乘法運(yùn)算等.文中根據(jù)建立CUDA 程序計(jì)算模型的方法［13-14］來分析GPU 上使用共享存儲器加速CSB+-樹查詢性能的可行性.

假設(shè)CSB+-樹每個節(jié)點(diǎn)的索引鍵數(shù)為m，N 是待并行查詢的記錄數(shù)，GPU 共有NSM個流處理器(SM)，則使用BlockSearchNode 算法并行查詢N 個記錄的時間t 為

式中:tblock為每個線程塊完成一次查詢?nèi)蝿?wù)的時間，tblock= tglobal+ tsyn+ tcomupter，tglobal為一個線程塊內(nèi)讀取全局存儲器數(shù)據(jù)的總時間，tsyn為線程塊內(nèi)線程同步的總時間，tcomputer為計(jì)算指令執(zhí)行的總時間;Nblock為GPU 每次可并行計(jì)算的線程塊數(shù)，Nblock=SSMNBLP，SSM為每個SM 的共享存儲器容量，NBLP為每個SM 的活動線程塊數(shù)，它受GPU 的硬件和核函數(shù)使用的資源(共享存儲器容量和寄存器數(shù)等)的限制，NBLP＜SSM/Sshare，Sshare是CUDA 核函數(shù)使用的共享存儲器大小.

由此可見，若能減少tglobal或增大NBLP，則可以使t 值變小.如果使用共享存儲器的查詢方式，則線程塊內(nèi)訪存的總時間t'global為

式中，tsg為將CSB+-樹部分或全部內(nèi)部節(jié)點(diǎn)的數(shù)據(jù)從全局存儲器拷貝至共享存儲器的時間，tsh為線程訪問共享存儲器的時間，tgl為數(shù)據(jù)不在共享存儲器時線程到全局存儲器的訪問時間.由式(4)可知:若能減少tblock，則可提高CSB+-樹的查詢速度;在每個線程塊需要處理的數(shù)據(jù)量不變(即tsyn與tcomputer均不變)的情況下，如果通過利用共享存儲器來實(shí)現(xiàn)t'global＜tglobal，則一個線程塊內(nèi)的共享存儲器必須裝入足夠多的節(jié)點(diǎn)數(shù)據(jù)，而且還需要有一定的查詢量才能攤銷tsg的代價.

現(xiàn)假定CSB+-樹每個節(jié)點(diǎn)的鍵容量m=128，并且每個鍵值占4B 的存儲空間，SM 的共享存儲器容量為16kB，則該共享存儲器可裝入的最大節(jié)點(diǎn)數(shù)為32.

這意味著在NBLP取最小值1 的極端情況下，對于一棵較大數(shù)據(jù)規(guī)模的CSB+-樹，共享存儲器尚不能裝滿2 層樹的節(jié)點(diǎn)數(shù)據(jù)，這顯然無法攤銷tsg的代價.由此可見，由于GPU 共享存儲器架構(gòu)設(shè)計(jì)的特殊性，通過高速共享存儲器來提高數(shù)據(jù)讀取的速度以提高程序的性能，在CSB+-樹的并行查詢中并不適用.

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

實(shí)驗(yàn)硬件平臺:GPU 為NVIDIA GTX 550Ti，CPU 為Intel core i5 2.53 GHz;軟件環(huán)境:操作系統(tǒng)Windows 7，GPU 編程使用CUDA 4.0 的開發(fā)包;編譯器是Visual Studio 2010.為驗(yàn)證文中提出的并行構(gòu)建CSB+-樹內(nèi)部節(jié)點(diǎn)算法的性能，在GPU 平臺上分別進(jìn)行索引數(shù)據(jù)規(guī)模從500 萬至2 500 萬的建樹實(shí)驗(yàn)，其中內(nèi)部節(jié)點(diǎn)的鍵容量m 為64，并與文獻(xiàn)［5-6］中算法的性能進(jìn)行對比，結(jié)果如圖3 所示.實(shí)驗(yàn)采用NVIDIA 提供的CUDA Profiler 工具統(tǒng)計(jì)每個核函數(shù)的運(yùn)行時間.

圖3 3 種算法的性能對比Fig.3 Performance comparison of three algorithms

從圖3 可以看出，當(dāng)處理的數(shù)據(jù)規(guī)模為2500 萬時，使用文獻(xiàn)［5］算法構(gòu)建樹內(nèi)部節(jié)點(diǎn)需要22 ms，而文中算法僅需0.7 ms，相對于其他兩種算法，文中算法的加速比分別達(dá)到了31.0 和1.4 倍.在CSB+-樹只有一個內(nèi)部節(jié)點(diǎn)的情況下，3 種算法使用的時間是相同的.

圖4 給出了在GPU 上使用帶分支和無分支線程塊查詢算法的性能對比.由圖可知，查詢5 ×1 024和25 ×1024 條數(shù)據(jù)時，帶分支線程塊查詢算法分別需要185 和900 μs，而無分支線程塊查詢算法分別只需156 和750 μs.

圖4 帶分支和無分支線程塊查詢算法的性能對比Fig.4 Performance comparison of thread block search algorithms with branch or no-branch

通過CUDA Profiler 工具觀察文獻(xiàn)［5］算法和文中算法的線程分支指標(biāo)“divergent branch”，發(fā)現(xiàn)文中算法的分支總數(shù)比文獻(xiàn)［5］中算法減少近1/3.由此可見，在GPU 的并行計(jì)算中，減少線程塊內(nèi)的線程分支數(shù)可有效地提高程序的性能.

4 結(jié)論

文中在GPU 平臺上提出了一種一次性并行創(chuàng)建CSB+-樹所有內(nèi)部節(jié)點(diǎn)鍵值的算法，以充分利用GPU 強(qiáng)大的并行計(jì)算吞吐量.對CSB+-樹查找算法使用共享存儲器進(jìn)行可行性分析，發(fā)現(xiàn)傳統(tǒng)的緩存敏感樹技術(shù)不適用于復(fù)雜的GPU 內(nèi)存框架.文中通過增加節(jié)點(diǎn)的填充位來減少GPU 線程塊內(nèi)的線程分支數(shù)，有效地提高了CUDA 程序的性能.今后將進(jìn)一步研究GPU 在數(shù)據(jù)庫技術(shù)中的其他高性能并行計(jì)算.

［1］DeWitt David J，Katz Randy H，Olken Frank，et al.Implementation techniques for main memory database systems［C］∥Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data.Boston:ACM，1984:1-8.

［2］Rao J，Ross K A.Cache conscious indexing for decisionsupport in main memory ［C］∥Proceedings of the 25th Conference on Very Large Data Bases.San Francisco:Morgan Kaufmann Publishers Inc，1999:78-89.

［3］Rao J，Ross K A.Making B+-trees cache conscious in main memory［C］∥Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.New York:ACM，2000:475-486.

［4］Fix J，Wilkes A，Skadron K.Accelerating braided B+tree searches on a GPU with CUDA［C］∥Proceedings of the 2nd Workshop on Applications for Multi and Many Core Processors:Analysis，Implementation，and Performance.San Jose:Springer-Verlag，2011:1-11

［5］Christensen D，Hansen H O，Juul L，et al.Efficient implementation of CSS-trees on GPGPUs［R］.Aalborg:Department of Computer Science，Aalborg University，2010.

［6］Kaczmarski K.B+-tree optimized for GPGPU［M］∥On the Move to Meaningful Internet Systems:OTM 2012.Berlin/Heidelberg:Springer-Verlag，2012:843-854.

［7］Liu Yong，Xi Jianqing，Lai Zhengwen，et al.Batch records insertion into multidimensional linear dynamic hashing table on GPU ［J］.Journal of Computational Information Systems，2012，8(10):4293-4301.

［8］Kim Changkyu，Chhugani Jatin，Satish Nadathur，et al.FAST:fast architecture sensitive tree search on modern CPUs and GPUs ［C］∥Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data.New York:ACM，2010:339-350.

［9］Owens J D，Luebke D，Govindaraju N，et al.A survey of general-purpose computation on graphics hardware ［J］.Computer Graphics Forum，2007，26(1):80-113.

［10］NVIDIA.NVIDIA CUDA programming guide［EB/OL］.(2009-09-27)［2012-08-30］.http:∥developer.nvidia.com/object/cuda.html.

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

［12］張舒，褚艷利，趙開勇，等.GPU 高性能運(yùn)算之CUDA［M］.北京:中國水利水電出版社，2009:68-70.

［13］Ryoo S，Rodrigues C I，Stone Sam S，et al.Program optimization space pruning for a multithreaded GPU［C］∥Proceedings of the 6th Annual IEEE/ACM International Symposium on Code Generation and Optimization.New York:ACM，2008:195-204.

［14］袁良，張?jiān)迫垏?，?基于延遲隱藏因子的GPU計(jì)算模型［J］.軟件學(xué)報(bào)，2010，21(12):251-262.Yuan Liang，Zhang Yun-quan，Long Guo-ping，et al.A GPU computational model based on latency hidden factor［J］.Chinese Journal of Software，2010，21(12):251-262.