Journal of South China University of Technology (Natural Science Edition) ›› 2014, Vol. 42 ›› Issue (1): 123-127,134.doi: 10.3969/j.issn.1000-565X.2014.01.021

• Computer Science & Technology • Previous Articles     Next Articles

Parallel Algorithm to Construct CSB+- Tree Indexing on Graphic Processing Unit

Liu Yong Xi Jian- qing Huang Dong- ping Jia Lian- yin Miao De- cheng   

  1. School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China
  • Received:2013-04-15 Revised:2013-06-12 Online:2014-01-25 Published:2013-12-01
  • Contact: 刘勇(1973-)，男，在职博士生，广西民族大学高级工程师，主要从事高性能并行计算研究． E-mail:l.yong07@mail.scut.edu.cn
  • About author:刘勇(1973-)，男，在职博士生，广西民族大学高级工程师，主要从事高性能并行计算研究．
  • Supported by:

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

PDF

754

Abstract:

In order to improve the operation efficiency of cache sensitive B+- tree (CSB+- tree) indexing,this pa-per deals with the parallel construction and query performance of CSB+- tree on graphic processing unit (GPU).Inthe investigation,first,the mapping relationship between each key in internal nodes and the corresponding leafnode of the index tree is analyzed, a lock- free parallel algorithm that once for all builds the CSB+- tree internal nodekeys is proposed,and the index tree is constructed at the maximum parallel speed.Moreover, dynamic arrays su-pporting the arbitrary expansion of CSB+- tree index data on GPU are designed to implement the dynamic allocationof memory space on GPU,and padding bits are added to the boundary of the internal nodes to reduce the number ofbranches,thus improving the query efficiency of CSB+- tree.Experimental results indicate that the proposed algo-rithm is 31. 0 and 1.4 times faster respectively than the parallel algorithms based on single node and tree layer.

Key words: parallel algorithms, graphic processing unit, CSB+- tree indexing, dynamic array, query efficiency

CLC Number: