期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

图形处理器上内存数据库索引T-树的研究 被引量：3

T-tree: Main Memory Database Indexing on Graphics Processing Unit
在线阅读 下载PDF
导出
摘要 为进一步提高内存数据库索引结构T-树的操作性能,提出一种基于图形处理器的T-树无锁并行计算方案.该方案通过分析平衡树结构的父子节点间的关系,在图形处理器平台上实现使用m个线程并行创建具有m个节点的T-树索引,从而以最大并行度的方式构建T-树.为验证方案的正确性,提出以堆栈的方式在图形处理器上遍历T-树的算法,对各平台上构建T-树的方案进行性能分析,并通过页锁定内存的方式提高CPU和GPU间的数据传输速率.通过对多个处理器平台上的实验结果的对比发现,提出的方案在并行构建T-树和T-树的批量节点插入上相比于传统CPU平台方案分别获得12倍和8倍以上的加速比. In order to improve the operation performance of T-tree, a main memory database indexing, a lock-free parallel computing scheme for T-tree on the graphics processing unit （GPU） is proposed. By analyzing the parent- child relationship of balanced tree structure, a T-tree with m nodes is constructed with n separate threads in a parallel mode on GPG platform. Thus, a T-tree with the maximum parallelism degree is successfully constructed. Then, in or- der to verify the correctness of the proposed scheme, a T-tree traversal algorithm with stacking on GPU platform is proposed. Moreover, different schemes of constructing T-tree on different platforms are analyzed and the data trans- mission between CPU and GPU is optimized by means of memory pinning. The result of experiments on different plat- forms show that, as compared with the conventional CPU-based schemes, the proposed scheme obtains about 12 times batch creating and 8 times batch inserting of T-tree.
作者 刘勇 奚建清 黄东平 贾连印 苗德成
机构地区 华南理工大学计算机科学与工程学院
出处 《华南理工大学学报（自然科学版）》 EI CAS CSCD 北大核心 2013年第3期22-28,共7页 Journal of South China University of Technology(Natural Science Edition)
基金 广东省科技计划项目(2012A010701011 2011A010801008) 云南省教育厅重点项目(2012Z008)
关键词 图形处理器 T-树 内存数据库 索引结构 并行构建 批量节点插入 graphic processing unit T-tree main memory database index structure parallel creation batch nodeinsertion
分类号 TP393 [自动化与计算机技术—计算机应用技术]
  • 相关文献

参考文献14

  • 1DeWitt D J, Katz R H, Olken F, et al. Implementation techniques for main memory data-base sys-tems [ C ] // Proceedings of the 1984 AC-M SIGMOD International Conference on Management of Data. Boston : ACM, 1984 : 1-8.
  • 2Lehman T J, Michael J. A study of index structures for main memory database management systems [ C ]//Proceedings of the 12th International Conference on Very Large Data Bases. Kyoto : ACM, 1986:294-303.
  • 3郭超,李坤,王永炎,刘胜航,王宏安.多核处理器环境下内存数据库索引性能分析[J].计算机学报,2010,33(8):1512-1522. 被引量：9
  • 4Choi Kong-Rim, Kim Kyung-Chang. T*-tree: a main memory database index structure for reahime applications [ C ] //Proceedings of the Third International Workshop on Real-Time Computing Systems Application. Seoul: IEEE Computer Society, 1996:81-88.
  • 5Lu Hongjun, Ng Yuet Yeung,Tian Zengping. T-Tree or B- Tree:main memory database index structure revisited [ C]// Proceedings of 11th Australasian Database Corfference. Canberra:IEEE Computer Society,2000:65-73.
  • 6Lee Ig-hoon, Shim Junho. CST-Trees: cache sensitive T- Trees [ C] //Proceedings of the 12th International Conference on Database Systems for Advanced Applications. Bangkok : Springer,2007:398-407.
  • 7Fix 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. California: San Jose, CA, 2011 : 1 - 11.
  • 8Kaczmarski Krzysztof. Experimental B +-tree for GPU [ C ] //Proceedings II of the 15th East European Conference on Advances in Databases and Information Systems ( ADBIS 2011 ). Vienna : Springer,2011:232 -241.
  • 9Dion Christensen, Henrik O H, Lasse Juul, et al. Efficient implementation of CSStrees on GPGPUs [ R ]. Aalb-org : Department of Computer Science of Aalb-org University,2010.
  • 10Liao Jiangmiao, Chen Hu, Yuan Yixia, et al. Parallel batch B + -tree insertion on multi-core architectures [ C ]// Proceedings of 5th International Conference on Frontier of Computer Science and Technology. Changchun: IEEE Computer Society, 2010 : 30- 35.

二级参考文献15

  • 1Garcia-Molina H,Salem K.Main-memory database systems:An overview.IEEE Transactions on Knowledge and Data Engineering,1992,4(6):509-516.
  • 2Lehman Tobin J et al.A study of index structures for main memory database management systems//Proceedings of the 12th VLDB Conference.Kyoto,Japan,1986:294-303.
  • 3Rao Jun,Ross Kenneth A.Cache conscious indexing for decision-support in main memory//Proceedings of the 25th VLDB Conference.Edinburgh,Scotland,UK,1999:78-89.
  • 4Rao Jun,Ross Kenneth A.Making B+-trees cache conscious in main memory//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data.Dallas,Texas,USA,2000:475-486.
  • 5Zukowski Marcin.Balancing vectorized query execution with bandwidth-optimized storage[Ph.D.dissertation].Universiteit van Amsterdam,Amsterdam,The Netherlands,1999.
  • 6Bohannon Philip,Mcllroy Peter et al.Main-memory index structures with fixed-size partial keys//Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data.Santa Barbara,California,USA,2001:163-174.
  • 7Cui Bin,Ooi Beng Chin et al.Main memory indexing:The case for BD-tree.IEEE Transactions on Knowledge and Data Engineering,2004,16(7):870-874.
  • 8Hankins Richard A,Patel Jignesh M.Effect of node size on the performance of cache-conscious B+-trees//Proceedings of the 2003 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems.San Diego,CA,USA,2003:283-294.
  • 9Ailamaki Anastassia et al.DBMSs on a modern processor:Where does time go?//Proceedings of the 25th VLDB Conference,Edinburgh,Scotland,UK,1999:266-277.
  • 10Lee Ig-Hoon,Shim Junho et al.CST-trees:Cache sensitive T-trees//Proceedings of the 12th International Conference on Database Systems for Advanced Applications.Bangkok,Thailand,2007:398-409.

共引文献8

同被引文献25

  • 1Yoon Sung-Ho, Park Jun-Sang, Kim Myung-Sup. Signature maintenance for Internet application traffic identification using header signatures [ C ]//Proceedings of 2012 international con- ference on network operations and management. Maui:IEEE, 2012:1151-1158.
  • 2Zhang Wen,Wang Heng. Identification of peer-to-peer traffic based on process fingerprint[ C]//Proceedings of 2011 inter- national conference on mechatronic science, electric engineer- ing and computer. Jilin : IEEE, 2011 : 1559-1562.
  • 3Du Jiang, Long Tao. P2P traffic identification research based on the SVM [ C ]//Proceedings of 2013 intemational confer- ence on wireless and optical communication. Chongqing: IEEE ,2013:683-686.
  • 4Park B, Won Y J, Kim M, et al. Towards automated application signature generation for traffic identification [ C ]//Proc of NOMS 2008. Salvador : IEEE ,2008 : 160-167.
  • 5Lin Guanzhou, Xin Yang, Yang Yixian. An application-level features mining algorithm based on PrefixSpan[ C]//Proceed- ings of 2010 international conference on computer engineering and technology. Chengdu: 1EEE ,2010:461-465.
  • 6Jian Ding, Meng Han. Sequentialpattern mining on highly simi- lar and dense dataset [ C ]//Proceedings of 2013 international conference on computational and information sciences. Shiy- ang: IEEE ,2013:762-765.
  • 7Liu Peiyu, Gong Wei, Jia Xian. An improved PrefixSpan algo- rithm research for sequential pattern mining[ C J//Proceedings of 2011 international conference on IT in medicine and educa- tion. Cuangzhou : IEEE ,2011 : 103-108.
  • 8张建华,张楠.基于混沌的RFID双向认证协议[J].铁道学报,2013(7):85-89.
  • 9赵海,欧阳元新,熊璋.用于RFID中间件的主存数据库索引结构[J].西南民族大学学报(自然科学版),2014,40(4):531-536.
  • 10唐军,卢正新.支持内存数据库索引缓存优化的CST树的设计与实现[J].计算机与数字工程,2010,38(1):173-176. 被引量：3

引证文献3

华南理工大学学报（自然科学版）
2013年 第3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部