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

论文摘要

数据库技术是处理数据和管理信息的基本技术,其中有三方面重要的数据管理活动,即对数据的存取、操作以及可视化.目前,这三方面均受到性能和效率上的挑战.图形处理器（GPU）是一类独特的新兴硬件,同时具有较强的存取、计算与可视化的能力,为应对这些挑战带来了机会.因此,本文研究基于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系统在数据存取、操作与可视化分析等方面与已有方法相比,在计算性能上有大幅的提高,在可视化效果上有显著的改进,在理论上提出新的方法和思路,在实际上具有应用价值.

论文目录

• 致谢
• 摘要
• Abstract
• 第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 将来工作
• 参考文献
• 作者简历
• 简介
• 教育经历
• 工作经历
• 攻读学位期间发表的论文和完成的工作