基于图形处理器的数据管理技术研究

摘要

本文研究基于GPU的数据存取、操作与可视化分析的方法，以提高数据管理的性能和效率. 纵览GPU上的通用计算(GPGPU)技术，特别是GPU上的数据库技术，我们发现GPU技术有多个功能层面可被利用，如通用并行计算功能，图形流水线计算功能，交互式可视化功能，等等.本文利用通用并行计算功能来加速数据存取，利用图形流水线计算功能来加速数据操作，并利用GPU所独具的“并行计算”与“图形处理”两重属性来加速和改善数据可视化分析.这三方面工作组成了基于GPU的数据管理(DOG)原型系统. 具体地，在数据存取方面，我们使用通用并行计算方法提出了一个基于GPU的数据存取框架，包括一些存取原则和元语.这些原则充分匹配了GPU的并行硬件特性，这些元语可以组成一般的索引建立和查询方法.我们基于这个存取框架，具体研究了网格文件，四叉树以及R树这三种多维索引方法.通过实验，我们基于GPU的算法一般比多核CPU上的已有算法快数倍，有的高达10倍. 在数据操作方面，我们使用图形流水线计算方法提出了一套基于GPU的数据操作元语，这些元语可以组成一般的数据操作方法.我们使用它们实现了块嵌套循环，索引嵌套循环，排序-归并以及哈希这四种连接方法.通过实验，我们基于GPU的算法性能可达到多核CPU上的已有算法性能的7倍. 我们研究了两个数据可视化分析问题.对于多维数据集之间的关系，我们提出了一种基于GPU的信息可视化方法，平行散点图.它结合了平行坐标与散点图方法，综合了多种信息可视化与图形学手段，能使人更有效地观察与分析多维数据集之间的连接关系.为了降低可视化的视觉杂乱度，我们还提出了一种基于空间填充曲线的聚类算法，并使用GPU将聚类的性能加速了20倍.最后，我们将基于GPU的连接、聚类计算与可视化整合起来，可以对千万级数据进行交互级的连接与聚类计算，同时保证高质量的交互式可视化. 对于联机分析处理(OLAP)中的数据立方技术，我们提出了一种基于GPU的可视化分析方法，交互式三维立方.我们提出了“绘制-聚集一体化”算法，将数据立方的分布式聚集操作映射为图形混合操作.数据立方的计算过程本身即是可视化的过程，充分结合了GPU的“并行计算”与“图形处理”两重属性，提高了可视化分析的整体性能.我们的方法不需要预计算时间或额外存储空间，可在千万级数据集上进行交互级的立方计算和三维OLAP操作，同时保证高质量的交互式可视化. 总之，我们的DOG系统在数据存取、操作与可视化分析等方面与已有方法相比，在计算性能上有大幅的提高，在可视化效果上有显著的改进，在理论上提出新的方法和思路，在实际上具有应用价值.

目录

文摘

英文文摘

论文说明：图表目录

声明

致谢

第1章绪论

1.1研究动机

1.2问题陈述

1.3工作概要

1.4章节组织

第2章GPGPU技术综述

2.1 GPU技术发展概述

2.2 GPGPU技术概述

2.3 GPU上的数据库技术

2.4 GPGPU发展趋势

2.5小结

第3章数据存取：基于GPU的多维存取

3.1引言

3.2相关工作

3.3存取原则

3.4存取元语

3.5存取方法

3.6实验

3.7小结

第4章数据操作：基于GPU的关系连接

4.1引言

4.2相关工作

4.3操作元语

4.4连接方法

4.5实验

4.6小结

第5章数据可视化分析：基于GPU的多维数据集连接

5.1引言

5.2相关工作

5.3平行散点图

5.4实验

5.5小结

第6章数据可视化分析：基于GPU的数据立方

6.1引言

6.2相关工作

6.3交互式三维立方

6.4实验

6.5小结

第7章结论

7.1本文贡献

7.2方法局限

7.3将来工作

参考文献

作者简历