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

摘要：

为提高缓存敏感CSB ＋-树索引的操作效率，在图形处理器（GPU）上研究CSB ＋-树的并行构建和查询性能．通过分析索引树内部节点的每一键与对应叶子节点的映射关系，提出了一种一次性并行构建CSB ＋-树所有内部节点键值的无锁并行算法，以最大并行度来快速构建索引树．该算法通过设计GPU平台上支持CSB ＋-树的索引数据任意伸缩的动态数组来解决GPU上不能动态分配显存空间的问题，通过在索引内部节点的边界增加填充位来减少线程块的线程分支数，从而提高CSB ＋-树的查询效率．实验结果表明，文中所提算法的运行时间比基于单个节点和基于树层的并行算法分别提高了31.0和1．4倍．

关键词：并行算法、图形处理器、CSB+-树索引、动态数组、查询效率

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金资助项目61103038；云南省教育厅重点项目2012Z008

在线出版日期：2014-04-03（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：123-127,134