Journal of South China University of Technology(Natural Science) >
Parallel Algorithm to Construct CSB+- Tree Indexing on Graphic Processing Unit
Received date: 2013-04-15
Revised date: 2013-06-12
Online published: 2013-12-01
Supported by
国家自然科学基金资助项目(61103038);云南省教育厅重点项目(2012Z008)
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.
Liu Yong Xi Jian- qing Huang Dong- ping Jia Lian- yin Miao De- cheng . Parallel Algorithm to Construct CSB+- Tree Indexing on Graphic Processing Unit[J]. Journal of South China University of Technology(Natural Science), 2014 , 42(1) : 123 -127,134 . DOI: 10.3969/j.issn.1000-565X.2014.01.021
/
| 〈 |
|
〉 |