基于CPU-GPU协同并行的XML数据查询优化

发布时间：2018-10-11 14:07

【摘要】：随着信息技术的迅速发展,我们可以通过互联网从世界各地接收和发送信息,然而,信息交互的过程中遇到了一个突出的问题：不同的平台用到的数据格式可能是各种各样的,也就是数据格式的异构性问题。XML的出现为这一问题的解决提供了理论和技术支持。随着Internet技术的不断发展,XML技术的应用也不断扩展。人们不仅可以运用XML技术进行银行间的数据交换、图书馆对馆藏书目的查询检索、企事业单位对文件档案进行管理,还可以用于电子商务、搜索引擎软件等领域。XML技术在IT环境中扮演着越来越重要的角色,己逐渐成为互联网上传递和交换信息的事实标准。由于各个领域的XML数据量以爆炸性的速度增长,以及XML本身的重大改善,以传统的串行方式对XML进行查询已经不能满足人们对查询效率的要求,更高效率、更大吞吐量的XML查询方法的研究显得越发重要和迫切,如何加快XML查询和如何提高查询的吞吐量正在成为XML查询技术的热门研究课题。目前,在XML数据查询优化方面,主要通过三种技术手段：利用成熟的数据库技术优化查询、利用索引优化查询和利用并行技术优化查询。利用数据库来优化查询的方法,主要是在传统的关系型数据库的基础上,增加对XML数据结构的支持,通过把XML数据映射成为关系型数据类型,进而利用目前较为成熟的关系型数据库管理技术对XML数据进行存储、查询和管理。利用索引技术对XML数据的查询进行优化的方法,主要是充分利用XML文档自身的自描述性和半结构化等特性,通过某种分类或者简化的方法把XML数据进行分类和建立索引,以此达到优化管理、查询的目的。这两种方法是目前最流行和通用的方法,其本质都是通过改善查询算法的本身来达到优化的目的。利用并行技术优化查询的方法是指通过当前硬件具有强大的通用计算能力来支持XML并行查询,这种方法的研究目前还很少见到,具有较大的研究价值和发展前景。随着GPU技术的迅速发展,特别是GPU通用计算(GPGPU)的提出和应用,GPU以其高度并行的特性正在高性能计算领域发挥着巨大作用。因此,基于GPU的并行优化技术也逐渐成为研究的热点。鉴于以上两点,本文结合XML查询技术和GPU的并行优化技术这两个热点,主要研究了如何使用GPU强大的通用计算能力来加快XML数据查询的效率问题,提出了基于CPU-GPU协同并行的XML数据查询优化算法。为了实现这个算法,我们需要引入一些公共基础。首先,由于XML的文档结构是一个自上而下的树形结构,节点与节点之间有着密切的关系,鉴于XML的这种特殊的文档结构,我们需要对XML文档节点进行编码。本文采用Dewey编码对XML文档进行编码,一是可以方便地管理和获取节点,二是可以利用节点的编码迅速地将XML文档从CPU端传送到GPU端,并在GPU端快速反序列化,恢复XML文档的树形结构,以方便查询的执行。其次,由于对XML文档的解析是一个非常耗时的工作,因此,为了避免每次查询都要花费过多时间来对XML文档进行解析,本文采用Xerces-C对XML文档进行解析,并将解析后的文档存放到嵌入式数据库BerkeleyDB中,以实现一次解析,永久查询。本文首先对XML和XML查询语言、GPU发展现状和NVIDIA的通用计算架构——CUDA编程模型做了简要介绍。然后提出了基于CPU-GPU协同并行的XML数据查询优化算法。算法首先实现一个代价分析模型,该模型用于估算查询的代价,以初步判断该查询是否需要进行GPU并行执行,如果需要进行并行执行,则算法采用查询路径和查询数据量均衡分配相结合的并行分解策略。最后,采用CUDA架构实现了简化后的XML查询语言XPath,并分析了该算法的性能。为了证明该算法的可行性,本文主要从查询加速比和查询时间两个方面进行了对比实验。实验数据表明,我们的并行模型比基于CPU串行方式进行的XML查询模型有更好的加速比和更高的吞吐量。
[Abstract]:......
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2013
【分类号】：TP311.13

【参考文献】