华南理工大学学报(自然科学版)
華南理工大學學報(自然科學版)
화남리공대학학보(자연과학판)
JOURNAL OF SOUTH CHINA UNIVERSITY OF TECHNOLOGY(NATURAL SCIENCE EDITION)
2014年
1期
123-127,134
,共6页
刘勇%奚建清%黄东平%贾连印%苗德成
劉勇%奚建清%黃東平%賈連印%苗德成
류용%해건청%황동평%가련인%묘덕성
并行算法%图形处理器%CSB +-树索引%动态数组%查询效率
併行算法%圖形處理器%CSB +-樹索引%動態數組%查詢效率
병행산법%도형처리기%CSB +-수색인%동태수조%사순효솔
parallel algorithms%graphic processing unit%CSB +-tree indexing%dynamic array%query efficiency
为提高缓存敏感CSB +-树索引的操作效率,在图形处理器(GPU)上研究CSB +-树的并行构建和查询性能.通过分析索引树内部节点的每一键与对应叶子节点的映射关系,提出了一种一次性并行构建CSB +-树所有内部节点键值的无锁并行算法,以最大并行度来快速构建索引树.该算法通过设计GPU平台上支持CSB +-树的索引数据任意伸缩的动态数组来解决GPU上不能动态分配显存空间的问题,通过在索引内部节点的边界增加填充位来减少线程块的线程分支数,从而提高CSB +-树的查询效率.实验结果表明,文中所提算法的运行时间比基于单个节点和基于树层的并行算法分别提高了31.0和1.4倍.
為提高緩存敏感CSB +-樹索引的操作效率,在圖形處理器(GPU)上研究CSB +-樹的併行構建和查詢性能.通過分析索引樹內部節點的每一鍵與對應葉子節點的映射關繫,提齣瞭一種一次性併行構建CSB +-樹所有內部節點鍵值的無鎖併行算法,以最大併行度來快速構建索引樹.該算法通過設計GPU平檯上支持CSB +-樹的索引數據任意伸縮的動態數組來解決GPU上不能動態分配顯存空間的問題,通過在索引內部節點的邊界增加填充位來減少線程塊的線程分支數,從而提高CSB +-樹的查詢效率.實驗結果錶明,文中所提算法的運行時間比基于單箇節點和基于樹層的併行算法分彆提高瞭31.0和1.4倍.
위제고완존민감CSB +-수색인적조작효솔,재도형처리기(GPU)상연구CSB +-수적병행구건화사순성능.통과분석색인수내부절점적매일건여대응협자절점적영사관계,제출료일충일차성병행구건CSB +-수소유내부절점건치적무쇄병행산법,이최대병행도래쾌속구건색인수.해산법통과설계GPU평태상지지CSB +-수적색인수거임의신축적동태수조래해결GPU상불능동태분배현존공간적문제,통과재색인내부절점적변계증가전충위래감소선정괴적선정분지수,종이제고CSB +-수적사순효솔.실험결과표명,문중소제산법적운행시간비기우단개절점화기우수층적병행산법분별제고료31.0화1.4배.
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).In the investigation,first,the mapping relationship between each key in internal nodes and the corresponding leaf node of the index tree is analyzed,a lock-free parallel algorithm that once for all builds the CSB +-tree internal node keys 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 allocation of memory space on GPU,and padding bits are added to the boundary of the internal nodes to reduce the number of branches,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.