学位论文 > 优秀研究生学位论文题录展示

GPU上并行数据操作技术优化

作　者: 郑超
导　师: 邓倩妮
学　校: 上海交通大学
专　业: 高性能并行计算
关键词: GPU 并行关系连接算法 CMD算法数据偏斜
分类号: TP338.6
类　型: 硕士论文
年　份: 2010年
下　载: 167次
引　用: 0次
阅　读: 论文下载

内容摘要

近年来,随着多核技术与GPU(Graphics Processing Units)技术的发展和成熟,GPU以其强大的并行计算能力越来越成为研究领域中的热点。人们已经开始研究使用GPU对多种数据操作进行加速。其中在数据库操作中最常用最耗时的连接操作成为人们研究的重点。本文研究了三个经典的连接算法(嵌套连接算法,排序-归并算法和哈希算法)的串行实现和并行实现,在GPU平台上实现了它们的并行化算法,并根据它们各自的特点做了一些优化。同时,鉴于GPU平台和多核处理器系统的相似性,本文把应用在计算机集群上的CMD(Coordinate Module Distribution)数据划分算法移至到了GPU平台上,并比较了两个并行连接算法(排序-归并算法和哈希算法)和CMD连接算法的性能。另外,本文也比较了以上算法在处理数据偏斜时的性能。为了和CPU多核进行比较,本文还使用了OpenMP实现了排序-归并和哈希连接算法,并把它们同GPU上的版本进行了比较。本文的贡献在于,在GPU平台上实现了排序-归并和哈希连接算法,并根据各个算法的特点进行了优化,同时把CMD算法移植到了GPU平台。本文比较了这些算法在处理数据偏斜时的性能,实验表明,哈希算法具有很好的表现,CMD连接算法次之,排序-归并算法最差。但是在处理均匀分布的数据表时,CMD连接算法要明显逊色于其它两个算法。而在同OpenMP的版本比较中发现,两个版本的性能不相上下。

全文目录

摘要  3-5
ABSTRACT  5-10
第一章绪论  10-14
  1.1 研究背景  10-12
  1.2 国内外研究现状  12-13
  1.3 本文的组织  13-14
第二章 CUDA 简介  14-30
  2.1 GPU 介绍  14-15
  2.2 CUDA 执行模型  15-17
  2.3 CUDA 中的基本概念  17-19
    2.3.1 核函数（KERNEL 函数）  17-18
    2.3.2 线程结构  18
    2.3.3 WARP  18-19
  2.4 CUDA 执行模型  19
  2.5 CUDA 软件体系  19-23
    2.5.1 CUDA C 语言  20-21
    2.5.2 NVCC 编译器  21-22
    2.5.3 运行时API 与驱动API  22-23
  2.6 CUDA 的存储器模型  23-28
    2.6.1 寄存器  23-24
    2.6.2 局部存储器  24
    2.6.3 共享存储器  24
    2.6.4 全局存储器  24
    2.6.5 常数内存（CONSTANT MEMORY）和纹理内存(TEXTURE MEMORY)  24-25
    2.6.6 共享存储器访问冲突  25-28
  2.7 CUDA 通信机制  28-30
    2.7.1 __SYNCTHREADS()  28
    2.7.2 MEMORY FENCE 函数  28
    2.7.3 核函数间通信  28
    2.7.4 原子操作  28-30
第三章数据库连接（JOIN）操作简介  30-42
  3.1 JOIN 语义  30-31
  3.2 连接操作的串行实现  31-34
    3.2.1 嵌套循环连接（NESTED-LOOP JOIN）  31-32
    3.2.2 排序-合并连接（SORT-MERGE JOIN）  32-33
    3.2.3 哈希连接（HASH JOIN）  33-34
  3.3 连接操作的并行实现  34-37
    3.3.1 并行嵌套循环连接算法  34
    3.3.2 并行的排序归并连接算法  34-36
    3.3.3 并行的哈希连接算法  36-37
  3.4 多维数据分布方法CMD 以及基于CMD 的连接算法  37-42
    3.4.1 多维数据分布方法CMD  37-39
    3.4.2 基于CMD 算法的连接算法  39-42
第四章并行连接算法在GPU 平台上的实现和优化  42-56
  4.1 GPU 架构同多处理机的类比  42-43
  4.2 GPU 平台上的数据操作优化  43-47
    4.2.1 数据分配  43-45
    4.2.2 线程调度  45-47
  4.3 并行连接算法在GPU 上的实现  47-51
    4.3.1 并行排序归并算法  48-49
    4.3.2 并行哈希算法  49-51
  4.4 CMD 算法在GPU 上的实现和优化  51-56
第五章实现环境  56-58
  5.1 机器环境  56
  5.2 实现数据表准备  56-58
第六章实验结果及分析  58-63
第七章总结与展望  63-64
参考文献  64-67
致谢  67-68
攻读学位期间发表的学术论文  68-70

GPU上并行数据操作技术优化

内容摘要

全文目录

相似论文