圖形處理器上CSB+-樹索引的并行構建算法*

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

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

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

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

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

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

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

1.1 數(shù)據(jù)結構

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

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

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

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

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

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

1.2 CSB +-樹的并行構建算法

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

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

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

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

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

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

1.2.1 葉子節(jié)點的并行構建算法

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

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

1.2.2 內部節(jié)點的并行構建算法

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

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

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

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

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

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

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

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

2 性能分析

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

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

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

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

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

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

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

3 實驗結果與分析

實驗硬件平臺: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.為驗證文中提出的并行構建CSB+-樹內部節(jié)點算法的性能，在GPU 平臺上分別進行索引數(shù)據(jù)規(guī)模從500 萬至2 500 萬的建樹實驗，其中內部節(jié)點的鍵容量m 為64，并與文獻［5-6］中算法的性能進行對比，結果如圖3 所示.實驗采用NVIDIA 提供的CUDA Profiler 工具統(tǒng)計每個核函數(shù)的運行時間.

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

從圖3 可以看出，當處理的數(shù)據(jù)規(guī)模為2500 萬時，使用文獻［5］算法構建樹內部節(jié)點需要22 ms，而文中算法僅需0.7 ms，相對于其他兩種算法，文中算法的加速比分別達到了31.0 和1.4 倍.在CSB+-樹只有一個內部節(jié)點的情況下，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 工具觀察文獻［5］算法和文中算法的線程分支指標“divergent branch”，發(fā)現(xiàn)文中算法的分支總數(shù)比文獻［5］中算法減少近1/3.由此可見，在GPU 的并行計算中，減少線程塊內的線程分支數(shù)可有效地提高程序的性能.

4 結論

文中在GPU 平臺上提出了一種一次性并行創(chuàng)建CSB+-樹所有內部節(jié)點鍵值的算法，以充分利用GPU 強大的并行計算吞吐量.對CSB+-樹查找算法使用共享存儲器進行可行性分析，發(fā)現(xiàn)傳統(tǒng)的緩存敏感樹技術不適用于復雜的GPU 內存框架.文中通過增加節(jié)點的填充位來減少GPU 線程塊內的線程分支數(shù)，有效地提高了CUDA 程序的性能.今后將進一步研究GPU 在數(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 高性能運算之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］袁良，張云泉，龍國平，等.基于延遲隱藏因子的GPU計算模型［J］.軟件學報，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.