混合多CPU和GPGPU解析大型XML文档的算法研究

摘要

XML是一种半结构化的语言，XML文档被越来越多地应用在数据传播和存储领域，比如在线数据，日志文件，配置文件，基于内容的数据库以及企业文档。通常处理XML文件时，会顺序扫描整个文件来分析文档的元素和结构。但是当XML文件变得非常大的时候，这种方法将有很大的效率问题，因为从头到尾地分析整个文档将会消耗大量的时间，传统的XML文件处理将会变成灾难。为了解决解析XML的问题，许多基于CPU线程的并行算法已经被提出来，但是仍然没有使用 GPGPU来解析XML的方法出现。
　　在这篇文章中，为了解决处理大型 XML的效率问题,我们提出 Hybrid Parallel XML Processing（HPXP）算法，HPXP算法是一种使用GPGPU集群来处理大型XML文件的算法设计。这个算法将混合使用CPU和GPGPU，形成master-slave的架构来处理文件。处理过程包括两个阶段，结构抽取以及标签解析。结构抽取阶段使用多线程来读取和识别文档结构，标签解析阶段将利用GPGPU来获取每一个标签的名称和属性，这一阶段的工作将基于结构抽取阶段获取到的标签位置信息。
　　文中的算法改进了以前一些并行算法的缺陷，并且验证了使用 GPGPU来处理XML文档的可行性，在测试环节，我们使用4个CPU线程以及1536个GPU线程最终取得了与传统SAX方法相比2.5倍的解析效率。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 本文研究内容

2 算法设计

2.1 问题难点分析

2.2 HPXP算法

2.2.1 HPXP算法提出

2.2.2 算法任务并行化设计

2.2.3 算法数据并行化设计

2.3 算法实现

2.3.1 文档结构抽取阶段实现

2.3.2 标签详细解析阶段实现

2.3.3 负载均衡控制

2.4 本章小结

3 实验与分析

3.1 实验环境

3.2 结构抽取性能测试

3.2.1 不同线程数下结构抽取性能

3.2.2 不同文件大小的抽取结构性能

3.3 完整解析性能测试

3.3.1 不同结构抽取效率下的整体解析性能

3.3.2 不同标签详细解析效率下整体解析性能

3.4 与SAX方法的性能对比

3.5 整体解析的负载均衡情况

3.6 本章小结

4 全文总结

致谢

参考文献