图形处理器上CSB+-树索引的并行构建算法*

刘勇 奚建清 黄东平 贾连印 苗德成

(华南理工大学 计算机科学与工程学院，广东 广州 510006)

在数据库系统中，索引是加快检索表中数据的一种直接有效的方法.由于索引项的空间比记录小，因此减少查询读取的数据量，可以提高查询效率.自内存数据库的概念被提出以来［1］，为适应内存数据库及硬件环境的要求，人们除了继续引用一些传统的索引到内存数据库中之外，还提出了多种新的内存索引技术和改进方案.Rao 等［2］在传统B+-树索引的基础上，提出了基于缓存敏感技术的CSS-树索引，具有比传统内存数据库索引(如T-树和B+-树)查找速度更快且空间占用率更小的性能.针对CSS-树无法解决索引数据的有效更新问题，Rao 等［3］提出了CSB+-树索引，它既具有与CSS-树相似的缓存性能，又具有B+-树的更新操作性能.

CSB+-树的结构与传统B+-树的结构类似，区别在于:CSB+-树的每个父节点只保留指向第一个孩子节点的指针，其他孩子节点的地址可通过计算与第一个孩子节点的偏移量得出;在CSB+-树中，一个节点的所有孩子节点按序存储并构成一个逻辑上的节点组.由于只保留一个指向孩子节点的指针，对于同样大小的内部节点，CSB+-树的扇出率比B+-树提高近1 倍，因此在一个缓存行里可存放更多的索引键，从而既提高了缓存的命中率，又节省了存储空间.

目前，基于图形处理器(GPU)的索引技术已有相关的研究，但它们在索引的并行创建和可操作性等方面存在着一定的不足.Fix 等［4］提出了基于GPU 的B+-树并行遍历算法，但因B+树是直接从CPU 上拷入GPU 端而未能利用GPU 的并行处理能力;Christensen 等［5］提出了优化的CSS-树多线程并行构建算法，但仅实现了单个节点内部键值的并行创建，而且在其基于线程块查询的优化算法中，也未考虑线程块出现线程分支的情形，从而影响程序的性能且若采用线程同步命令时还会引起程序出错等问题;Kaczmarski［6］根据传统B+树的批量装载算法，提出了一种基于树层的自底向上并行构建算法，该算法的并行度较文献［5］中算法有所提高，然而其思想是建立在传统CPU 平台上，因此未能充分利用GPU 的并行计算资源.Liu 等［7］在GPU 平台上实现了多维线性动态哈希表的记录批量插入，大大提高了索引的操作性能，但须借助GPU 的原子锁函数才能完成并行处理，因此并行度不高.Kim 等［8］在CPU 和GPU 平台上实现了完全二叉树的快速构建和遍历算法，尽管创建索引树的速度极快，但该算法比较简单，不适用于解决复杂的问题.

近年来，GPU 的通用计算(GPGPU)［9］已经在科学计算和数据库技术等领域中得到广泛的应用.为此，文中在GPU 平台上研究缓存敏感树索引CSB+-树的并行构建和查询的操作性能.

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

1.1 数据结构

目前NVIDIA CUDA 编程模型［10］尚未支持在GPU 上动态分配显存空间，而传统CSB+-树的存储结构可支持索引数据的动态增减.为此，文中采用结构体数组预分配的方式存储CSB+-树数据，数组的每个元素表示CSB+-树的一个节点，并通过两层数据结构［11］实现结构体数组的动态伸缩，其结构如图1所示.

图1 动态数组的数据结构Fig.1 Data structure of dynamic array

在此结构中，将存储CSB+-树数据的动态数组划分成若干大小固定的数据段，每个数据段的首地址保存在目录数组中;当数组需要扩大时，则根据所需的数据量增加新的数据段和相应数量的目录数组存储空间;当数组需要收缩时，则释放多余的数据段和对应的目录数组存储空间.假定每个数据段大小为S，则动态数组第i 个元素的段地址(sa)和段内地址(sia)为

它在数组的地址为directory［sa］.element［sia］.

由此可知，基于GPU 平台的CSB+-树的数据结构由叶子节点结构、内部节点结构和它们相应的段结构构成，其程序代码如下:

在CSBplusStruct 结构中，leaf_dir 和inter_dir 分别为存储叶子节点和内部节点数据的目录数组，leaf_dirlen和inter_dirlen 分别为当前叶子目录数组和内部节点目录数组的长度，leaf_SP 和inter_SP 分别指向各自目录数组中下一个待分配的0 地址.叶子节点和内部节点采用不同的结构，可减少不必要的指针空间浪费.

1.2 CSB +-树的并行构建算法

传统B+-树的批量装载算法是将一组已排序的记录从距根节点最右的路径起逐个插入直至结束.然而，如果按此算法构建CSB+-树，由于同一个节点组内的节点不是按顺序建立，因此需要重新分配内存以构建节点组，其操作代价极大.为此，Rao 等［2］提出了一种效率更高的CSB+-树批量装载算法，该算法可以自底向上、一层层地构建CSB+-树，具体步骤如下:

(1)对待插入的索引记录按关键字排序;

(2)根据记录数分配CSB+-树的叶子节点空间，并将记录依次按序插入叶子节点内，在树的底层建立叶子层;

(3)根据CSB+-树的阶和下层的节点数计算上一层所需的内部节点数，并为上层节点分配连续的存储空间，节点内的键值为其对应下一层节点的最大键值，同时设置每个节点的第一个孩子指针;

(4)返回步骤(3)直至上一层的节点数为1，即该节点为CSB+-树的根节点.

由于在整个构建过程，同一层的所有节点地址都是连续分配的，因此无需进行任何额外的数据复制操作即可构成一个节点组.由此可见，CSB+-树的构建包括叶子节点的构建和内部节点的构建.

1.2.1 叶子节点的并行构建算法

为保证CSB+-树的存储利用率，在初次建树时可通过设置节点的填充因子α 来控制每个节点的记录数.假设M 是每个节点的记录容量，则构建N个数据的CSB+-树所需分配的叶子节点数为

因此，可根据X 在GPU 上为叶子节点分配动态数组空间，然后将已排好序的数据从主机端传输至设备端，再将记录并行插入到CSB+-树的叶子节点中.由于线程的编号顺序与叶子节点的编号顺序相对应，因此创建的CSB+-树的相邻叶子节点要按序存储.

1.2.2 内部节点的并行构建算法

基于树层的B+-树内部节点并行构建算法［6］的思想与CSB+-树的批量装载算法相似，即节点内的每一个键值由独立的线程并行计算，并行的线程数由下一层的节点数决定，并根据树的高度需要多次调用CUDA 核函数.由于每次调用核函数后还需要线程的同步操作且这些操作需要耗费几百个GPU时钟.

为此，文中提出了一种基于键的内部节点并行构建算法，该算法通过计算树中内部节点的每个键与最终叶子节点的对应关系来实现一次性并行构建所有内部节点的键值.首先自下而上、自左向右地对内部节点进行编号，接着计算每个线程所代表的键在索引树中的层节点编号layerNode 以及它在该节点内的键编号nodeKey，然后计算该层的节点与节点之间的叶子偏移量nodeLeafs、节点内部键之间的叶子偏移量keyLeafs，最后计算该键对应的目标叶子节点leaf:

leaf 的最大值为该线程所代表的内部节点的键值.该算法的伪代码如下:

1.3 CSB +-树的并行查询算法

传统CSB+-树的查询算法主要是通过二分查找的方式，从根节点开始搜索，直至目标叶子节点.由于二分查找并不适合并行处理，因此一种比较合理的方法就是在每个节点的内部采用多线程并行查找的算法.为此，Christensen 等［5］提出了一种基于线程块的CSS-树查询算法，按该算法思路设计的基于线程块的CSB+-树内部节点的并行查询算法的伪代码如下:

在上述算法中，为防止数组的越界访问，当线程tid=0 时需要进行特殊处理，从而在线程块中产生一个分支.CUDA 的指令执行模式是SIMT 方式，warp 是CUDA 的最小调度单位，当一个warp 内的线程出现分支时，warp 将沿着每个分支调度串行化指令，直至warp 内所有的线程可执行相同的指令为止［12］.由此可见，当warp 内的线程走向不同的分支时，需要的时间是不同分支的执行时间之和，并且分支影响了并行计算的吞吐量.为避免程序出现分支的情况，文中在CSB+-树每个内部节点的最左边添加一个填充位，新的节点结构如图2 所示.

图2 带左填充位的节点结构Fig.2 Structure of node with left padding bit

每个节点填充位的值可设为所有索引数据的最小值－1，修改节点结构后基于线程块的CSB+-树内部节点的查找(BlockSearchNode)算法的伪代码如下:

2 性能分析

传统缓存敏感技术的思想是利用高速存储器来解决CPU 运算速度快与访存速度慢不匹配的瓶颈问题.在GPU 中常用的CUDA 程序优化方法是利用共享存储器来减少访问全局存储器的次数，从而获得更高的内存带宽，如GPU 上的稀疏矩阵乘法运算等.文中根据建立CUDA 程序计算模型的方法［13-14］来分析GPU 上使用共享存储器加速CSB+-树查询性能的可行性.

假设CSB+-树每个节点的索引键数为m，N 是待并行查询的记录数，GPU 共有NSM个流处理器(SM)，则使用BlockSearchNode 算法并行查询N 个记录的时间t 为

式中:tblock为每个线程块完成一次查询任务的时间，tblock= tglobal+ tsyn+ tcomupter，tglobal为一个线程块内读取全局存储器数据的总时间，tsyn为线程块内线程同步的总时间，tcomputer为计算指令执行的总时间;Nblock为GPU 每次可并行计算的线程块数，Nblock=SSMNBLP，SSM为每个SM 的共享存储器容量，NBLP为每个SM 的活动线程块数，它受GPU 的硬件和核函数使用的资源(共享存储器容量和寄存器数等)的限制，NBLP＜SSM/Sshare，Sshare是CUDA 核函数使用的共享存储器大小.

由此可见，若能减少tglobal或增大NBLP，则可以使t 值变小.如果使用共享存储器的查询方式，则线程块内访存的总时间t'global为

式中，tsg为将CSB+-树部分或全部内部节点的数据从全局存储器拷贝至共享存储器的时间，tsh为线程访问共享存储器的时间，tgl为数据不在共享存储器时线程到全局存储器的访问时间.由式(4)可知:若能减少tblock，则可提高CSB+-树的查询速度;在每个线程块需要处理的数据量不变(即tsyn与tcomputer均不变)的情况下，如果通过利用共享存储器来实现t'global＜tglobal，则一个线程块内的共享存储器必须装入足够多的节点数据，而且还需要有一定的查询量才能摊销tsg的代价.

现假定CSB+-树每个节点的键容量m=128，并且每个键值占4B 的存储空间，SM 的共享存储器容量为16kB，则该共享存储器可装入的最大节点数为32.

这意味着在NBLP取最小值1 的极端情况下，对于一棵较大数据规模的CSB+-树，共享存储器尚不能装满2 层树的节点数据，这显然无法摊销tsg的代价.由此可见，由于GPU 共享存储器架构设计的特殊性，通过高速共享存储器来提高数据读取的速度以提高程序的性能，在CSB+-树的并行查询中并不适用.

3 实验结果与分析

实验硬件平台:GPU 为NVIDIA GTX 550Ti，CPU 为Intel core i5 2.53 GHz;软件环境:操作系统Windows 7，GPU 编程使用CUDA 4.0 的开发包;编译器是Visual Studio 2010.为验证文中提出的并行构建CSB+-树内部节点算法的性能，在GPU 平台上分别进行索引数据规模从500 万至2 500 万的建树实验，其中内部节点的键容量m 为64，并与文献［5-6］中算法的性能进行对比，结果如图3 所示.实验采用NVIDIA 提供的CUDA Profiler 工具统计每个核函数的运行时间.

图3 3 种算法的性能对比Fig.3 Performance comparison of three algorithms

从图3 可以看出，当处理的数据规模为2500 万时，使用文献［5］算法构建树内部节点需要22 ms，而文中算法仅需0.7 ms，相对于其他两种算法，文中算法的加速比分别达到了31.0 和1.4 倍.在CSB+-树只有一个内部节点的情况下，3 种算法使用的时间是相同的.

图4 给出了在GPU 上使用带分支和无分支线程块查询算法的性能对比.由图可知，查询5 ×1 024和25 ×1024 条数据时，带分支线程块查询算法分别需要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”，发现文中算法的分支总数比文献［5］中算法减少近1/3.由此可见，在GPU 的并行计算中，减少线程块内的线程分支数可有效地提高程序的性能.

4 结论

文中在GPU 平台上提出了一种一次性并行创建CSB+-树所有内部节点键值的算法，以充分利用GPU 强大的并行计算吞吐量.对CSB+-树查找算法使用共享存储器进行可行性分析，发现传统的缓存敏感树技术不适用于复杂的GPU 内存框架.文中通过增加节点的填充位来减少GPU 线程块内的线程分支数，有效地提高了CUDA 程序的性能.今后将进一步研究GPU 在数据库技术中的其他高性能并行计算.

［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.