基于GPU的RDF图的Type同构并行匹配算法

摘要

子图匹配作为图论中的一个基本的问题，也是RDF图数据管理中的一种基本查询形式。随着开放链式数据和语义Web运动的发展，不断增长的数据规模以及子图匹配的理论复杂性给RDF图数据管理带来巨大的挑战。受限于传统的CPU体系架构，现有的基于filter-and-refine策略的线性算法效率严重依赖于中央处理器的计算性能。随着新型硬件的发展，GPU已经广泛应用于通用计算领域。相比于CPU，GPU有更高的计算性能，更好的扩展性，更低廉的价格。如何在海量的RDF图上设计高效的并行匹配算法，成为一项挑战性的工作。
　　本文把type同构的概念拓展到RDF图，提出两种基于type同构的RDF图并行匹配方案。在集中式匹配方案中，给出了一种基于RDF图的子图匹配模型，该模型利用了type同构的并行可扩展的特点，支持以细粒度并行的方式加速匹配过程。基于此模型把子图匹配过程做了并行化处理，设计实现了基于GPU的匹配算法和基于GPU的连接算法，并给出完整的RDF图并行匹配算法，开发了一个原型机IRSMG。在单机并行的基础上，给出了分布式并行匹配方案，提出了gmars并行计算架构，把集中式并行匹配算法嵌入到分布式计算节点中，融合任务并行与数据并行两种并行计算模式，主节点分解查询，从节点并行执行，GPU加速数据处理，组装重构子查询结果。本文设计的实验从查询的响应时间上对两种实现方法做了评价，测试了不同的数据规模下算法性能，实验结果表明，相比于串行算法，本文所提算法能够取得3-5倍的效率提高。
　　综上所述，本文提出的两种并行匹配方案适用于RDF图的子图匹配,匹配算法充分利用了新型硬件的大规模并行计算优势，极大地提高了匹配算法的性能。展现了新型硬件在图计算领域良好的应用前景。

目录

声明

第1章 绪论

1.1 研究背景

1.2 研究目标和主要内容

1.3 论文组织结构

第2章 相关工作综述

2.1 一般图的子图匹配

2.2 RDF图的子图匹配

2.3 GPU加速图算法研究现状

第3章 基于GPU的集中式并行匹配算法设计

3.1 并行图查询模型

3.2 并行匹配算法的设计

3.3 并行匹配算法的扩展性分析

3.4 小结

第4章 分布式集群算法设计

4.1 分布式并行计算

4.2 多机计算架构

4.3 小结

第5章 实验结果及评价

5.1 集中式并行匹配实验

5.2 多节点分布式实验

5.3 本章小结

第6章 总结和展望

6.1 总结

6.2 展望

参考文献

发表论文和参加科研情况说明

致谢