GPU上基于Hadoop的高效连接操作算法研究

摘要

现代商业数据库领域中，日益增长的数据为数据查询以及数据存储带来了巨大的压力。越来越多的研究关注于如何有效的在大数据集合上进行查询操作。由于目前中央处理机（CPU）的发展日益缓慢，软件上对算法的优化已经到了瓶颈。越来越多的关注集中在利用图像处理器（GPU）作为协处理器加速数据库操作。GPU具有强大的计算能力以及高并行性，十分适用于处理计算密集型任务。连接操作作为现代数据库系统中最为重要的操作之一，有很多研究关注于利用GPU加速连接操作。
　　现有GPU加速嵌套循环连接操作研究成果并不能够很好的适用于较大数据表的连接操作。基于此，本文主要研究如何利用GPU有效地加速大数据表上的嵌套循环连接操作，本文通过将Hadoop与GPU结合，实现了等值连接中的嵌套循环连接、哈希连接以及非等值连接。在处理等值连接时，通过预过滤仅仅将可连接的元组传递到GPU上进行实际的连接操作。
　　本文是第一个利用Map-Reduce与GPU结合加速非等值连接操作的。同时，通过数据预过滤，本文所提方法比现有GPU加速方法能够处理更大数据表的等值连接操作。本文提出的算法能够在不引入额外的开销情况下，更加准确地估计出结果的个数，为其分配适当的存储空间。
　　经过严密的实验表明，本文提出的方法相比于传统的GPU加速等值连接操作算法，能够获得0.5至1倍的加速效果。同时在人工合成数据集上，本文所提加速连接操作算法的GPU版本相比于CPU版本能获得0.3至1倍的加速效果。

目录

声明

中文摘要

英文摘要

目录

第1章绪论

1.1 课题背景及研究的目的和意义

1.2 连接操作加速的发展概况

1.3本文的主要研究内容

第2章背景知识

2.1 引言

2.2 GPU

2.3 CUDA

2.4 图像处理器加速适用条件

2.5 本章小结

第3章基于GPU的等值连接操作

3.1 引言

3.2数据预过滤

3.3 数据预处理

3.4 GPU加速等值连接操作

3.5 GPU与Map-Reduce的结合

3.6本章小结

第4章基于GPU的非等值连接操作

4.1 引言

4.2数据预处理

4.3本章小结

第5章基于GPU的连接实验

5.1 引言

5.2嵌套循环连接

5.3哈希连接

5.4非等值连接

5.5本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢