导　　师： 奚建清

学科专业： 081203

授予学位： 博士

作　　者： ;

机构地区： 华南理工大学

摘　　要： 由于内存数据库具有比基于磁盘的数据库更高的查询响应速度和并发度，其被广泛应用于银行、证券交易所和在线购物等数据量庞大并且实时性要求高的商业领域。索引能够有效降低数据的搜索空间、提高内存数据库的查询效率，然而当前它却受到性能和效率的挑战。 基于图形处理器的通用计算（GPGPU）在多个领域具有重要的研究价值和应用前景，也是当前研究的热点。目前图形处理器（GPU）上索引技术的研究已有一定的相关成果，然而这些研究成果存在着诸如：并行算法未充分利用硬件的资源、并行度不高，算法缺乏可扩展性且不能解决索引数据的更新等问题。因此，本文以如何充分利用GPU的硬件资源、最大限度地提高内存数据库索引的操作性能为主要研究内容，在相关研究的基础上，本文主要做了以下工作： 1.对目前内存数据库索引技术的研究成果进行总结归纳，并且对GPU的硬件特点和编程技术做了相关综述。 2.提出一种基于GPU T-树索引的并行计算方案，该方案通过分析T-树的节点间的父子关系，在GPU上实现对T-树的最大并行度构建。设计在GPU上T-树索引数据可任意伸缩的动态数组，解决GPU上尚无动态分配显存空间的问题；通过对各种构建T-树方案的理论和实验分析，提出的并行建树方案较传统的建树方案，在操作效率和空间利用率上均有明显的性能优势。为解决CUDA程序数据传输的瓶颈问题，通过页锁定内存的方式提高CPU和GPU间的数据传输速率；为适应未来硬件发展的需求，对算法的可扩展性进行相关研究；为验证方案的正确性，提出基于GPU T-树的遍历算法；为验证提出的并行方案的有效性，进行相关的实验论证。 3.为加速多维数据的操作性能，提出一种基于GPU多维线性哈希索引的并行处理方案。该方案通过对传统哈希索引数据结构的扩展，利用2层的数据结构可实现哈希表在GPU上的任意收缩，从而解决多维数据在GPU上无法有效更新的问题。在哈希表的记录并行批量插入算法中，采用并行分裂哈希桶的方式可加速哈希表分裂的处理速度，从而提高了插入的效率；设计一个灵活的溢出桶管理机制，可提高多维哈希索引在GPU上的存储空间利用率；对提出的记录并行批量插入方案进行算法时间和空间复杂度的分析，并与传统的CPU算法进行相关对比；在各种硬件平台上对多维线性哈希索引记录的并行批量插入、批量删除和查询的操作性能进行相关的实验论证。 4.提出一种基于GPU缓存敏感CSB~+-树索引的无锁并行处理方案，该方案通过对传统的CSB~+-树的结构改进，可实现CSB~+-树的索引数据在GPU上动态更新。在GPU上提出基于树层和基于节点索引键CSB~+-树两种并行构建算法，其中后者可实现对CSB~+-树的最大并行度构建；通过在CSB~+-树的内部节点添加填充位的方式，可减少GPU线程块里的线程分支数，从而提高CSB~+-树的查询性能；通过对CSB~+-树的查询算法使用共享存储器的可行性分析，指出传统的缓存敏感技术的思想在复杂的GPU内存框架中并不适合使用。为验证提出的并行方案的有效性，在多个硬件平台上进行相关的实验论证。 5.在GPU平台上提出一种BD-树索引的并行计算方案，该方案通过修改传统BD-树的哈希函数，可实现对BD-树索引的并行处理。通过对传统BD-树的数据结构改进，可实现BD-树索引数据在GPU上的更新操作；通过分析BD-树的树形结构，可实现基于内部节点键的并行度方式构建BD-树；通过增加额外的空间开销，减少GPU原子函数的调用次数，可显著提高BD-树哈希表的数据插入效率；对BD-树并行构建算法进行空间复杂度的分析，与传统的构建算法相比，提出算法的空间利用率明显得到提高。同样，为验证提出方案的有效性，进行相关的实验论证。 As memory database is more efficient than disk-based database at query speed andconcurrency, the main memory database /(MMDB/) has been applied in amounts of financialfields such as bank, on-line shopping, and stock exchange and so on, which all contain vastvolume of data and need high availability of real-time operations.The indexing can effectivelyreduce the search space of the data, and improve the query efficiency of MMDB, however itfaces the challenges of performance and efficiency. General purposed computing on graphics processing unit /(GPGPU/), which is also a hotarea of research, has significant research value and prospect for application.. Indexing ongraphics processing unit /(GPU/) has got several related scientific research achievements, yetthere are many problems to deal with such as: underutilization of hardware resources, the lowparallel degree of the algorithm, lack of scalability and not effectively addressing index dataupdate and so on. Therefore, how to take full use of GPU hardware resources and maximizememory database index operation performance are the main research contents. Above all, onthe basis of the relevant research, the main works of this paper are as follows: 1. The current studies of indexing technology of MMDB have been summarized. Thehardware characteristic and the programming technology of GPU have been reviewed. 2. A parallel processing solution of T-tree based on GPU has been proposed, whichcreates the maximized T-tree parallelism on GPU platform by analyzing the father-sonrelationship among the internal nodes of T-tree. The dynamic array has been designed so thatthe T-tree indexing can be expanded and contracted on GPU platform to solve the problemthat the display memory on GPU space cannot be dynamically allocated. Through analyzingdifferent T-tree building programs theoretically and empirically, the proposed solution has anobvious advantage of operational efficiency and space utilization over traditional T-treebuilding program. In order to eliminate the bottleneck of GPU program data transmission, themethod of page locking has been used to promote the data transfer rate between CPU andGPU. To meet the needs of hardware development in the future, the scalability of thealgorithm has been studied. The T-tree traversal algorithm based on GPU T-tree has beenproposed to verify the solution. To verify the validity of the parallel program, the empiricalstudy has been done. 3. In order to speed up the performance of multi-dimensional data manipulation, a multi-dimensional linear hashing processing solution has been proposed based on GPU. Thesolution expands the traditional data structure of hash table and uses two-layer data structure to scale arbitrarily on GPU, and solve the problem that multi-dimensional data cannot updateefficiently. In the hash table with the algorithm of bulk insertion of records, processing speedcan be accelerated by parallel splitting hash table and promote the efficiency of insertion. Aflexible overflow bucket management mechanism has been designed to improve the hashindex storage space utilization on GPU. Bulk records insertion program has been analyzed atalgorithm time and space complexity. To verify performance of the bulk record insertionmultidimensional linear hash index on a variety of hardware platforms, bulk deletion andparallel query operating, the related empirical study has been done. 4. Cache sensitive CSB~+-tree index unlock parallel program based on GPU has beenproposed, and it fulfills the CSB~+-tree structure automatic update on GPU by improvingtraditional CSB~+-tree structure. Parallel unlock algorithm based on the tree layer and node keyhave been proposed and the latter can realize the maximum parallel degree construct. Byadding stuffing bits to CSB~+-tree internal nodes to reduce the branch thread of GPU threadblock, and thus improve the CSB~+-tree query performance. By analyzing the feasibility ofCSB~+-tree query algorithm with shared memory, it is pointed out that the thought oftraditional cache sensitive tree technology is not suitable in complex GPU memory frame. Toverify the feasibility of proposed program, the related empirical study has been done ondifferent platforms. 5. BD-tree index parallel computing program on GPU fulfills the parallel processing byimproving traditional hash function and fulfills the update of BD-tree index data on GPU byimproving traditional BD-tree structure. By analyzing the tree structure of BD-tree, it canparallel build the internal structure of BD-tree based on node key. By increasing the spaceoverhead to reduce the GPU atomic number of function calls and improve the BD-tree datainsertion efficiency of the hash table significantly. By analyzing the spatial complexity of BD-tree parallel building algorithm, the space utilization of proposed algorithm is significantlyimproved compared with traditional algorithm. To verify the effectiveness of proposedprogram, the related empirical study has been done.

关 键 词： 图形处理器 内存数据库索引 树 多维线性哈希 树 树

分 类 号： [TP311.13]

领　　域： [自动化与计算机技术] [自动化与计算机技术]