基于GPU加速的RDF查询并行Join算法

摘要

在数据爆炸的今天，起源于语义网（Semantic Web）的资源描述框架（Resource Descript数据传输n Framework，简称RDF）由于其简洁灵便的特点，正越来越多的被其他的领域使用。当前针对RDF的研究工作将RDF作为一个可用的数据表示模型，研究重点主要集中在数据物理存储和压缩以及查询优化方面，针对RDF并行查询处理的研究较少。为了优化加速RDF数据查询处理，本文针对基于GPU的并行Join算法进行了研究。
　　本研究利用GPU来加速基于SPARQL语言的RDF查询处理，RDF并行查询处理系统旨在利用GPU核心众多高度并行的特性，加速RDF查询处理。为加速RDF查询处理，一个两层细粒度的并行查询处理框架被设计出来。外层设计了一个计算流水线，流水线分为数据输入、计算、数据输出三个阶段，提高CPU和GPU工作的并行度，提高查询效率。内层采用细粒度的数据划分方式，设计了一个基于数据块的的细粒度并行Join算法，由于各数据块之间相互隔离彼此独立，可以实现完全并行Join算法。在此基础上，为降低数据传输读写开销、减少数据冗余和有效数据利用率，设计了一种基于数据块的数据配对方法，根据内外两层特性，对内外两层数据进行不同粒度的数据配对。系统充分利用GPU计算高性能高并行度特性，在GPU上进行Join算法的并行处理，有效提高了SPARQL查询处理效率。与经典的GPU上的并行 Join算法相比，计算速度提高了至少20％以上；在 CPU内存和 GPU显存之间传输数据的速度上能提高到37%左右。

目录

声明

1 绪论

1.1 研究背景与意义

1.2 国内外研究现状

1.3 论文的主要研究内容

1.4 论文的组织架构

2 相关技术研究

2.1 RDF数据模型和SPARQL查询语言

2.2 GPU并行计算

2.3 CUDA

2.4 TripleBit系统

2.4 本章小结

3 基于GPU加速的两层次的并行JOIN数据调度处理框架

3.1 概述

3.2 任务流水处理方法

3.3 基于块的两层RDF数据处理方法

3.4 GPU上任务间的同步机制

3.5 本章小结

4 并行JOIN处理算法的设计和实现

4.1 并行Join处理算法模型

4.2 并行JOIN算法

4.3 本章小结

5 系统测试和分析

5.1 测试环境

5.2 测试数据集

5.3 性能测试及评价

5.4 本章小结

6 总结与展望

6.1 全文总结

6.2 未来展望

致谢

参考文献