Journal of South China University of Technology (Natural Science Edition) ›› 2013, Vol. 41 ›› Issue (3): 22-28.doi: 10.3969/j.issn.1000-565X.2013.03.004

• Computer Science & Technology • Previous Articles     Next Articles

T-tree: Main Memory Database Indexing on Graphics 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:2012-08-15 Revised:2013-01-02 Online:2013-03-25 Published:2013-02-01
  • Contact: 刘勇(1973-)，男，博士生，高级工程师，主要从事数据库与高性能并行计算研究． E-mail:l.yong07@mail.scut.edu.cn
  • About author:刘勇(1973-)，男，博士生，高级工程师，主要从事数据库与高性能并行计算研究．
  • Supported by:

    广东省科技计划项目( 2012A010701011， 2011A010801008) ; 云南省教育厅重点项目( 2012Z008)

PDF

820

Abstract:

In order to improve the operation performance of T-tree,a main memory database indexing,a lock-freeparallel computing scheme for T-tree on the graphics processing unit ( GPU) is proposed.By analyzing the parentchildrelationship of balanced tree structure,a T-tree with m nodes is constructed with n separate threads in a parallelmode on GPG platform.Thus,a T-tree with the maximum parallelism degree is successfully constructed.Then,in orderto verify the correctness of the proposed scheme,a T-tree traversal algorithm with stacking on GPU platform isproposed.Moreover,different schemes of constructing T-tree on different platforms are analyzed and the data transmissionbetween CPU and GPU is optimized by means of memory pinning.The result of experiments on different platformsshow that,as compared with the conventional CPU-based schemes,the proposed scheme obtains about 12 timesbatch creating and 8 times batch inserting of T-tree.

Key words: graphic processing unit, T-tree, main memory database, index structure, parallel creation, batch nodeinsertion