并行连接算法优化研究及实现

发布时间：2017-04-09 21:00

  本文关键词：并行连接算法优化研究及实现，由笔耕文化传播整理发布。

【摘要】：随着集成电路和计算机体系结构的发展,出现了多核/众核处理器微处理器体系机构,Intel基于X86架构的新一代协处理器MIC是其中的代表,在核心数和内存带宽相对于CPU有明显的优势,并可以实现SIMD执行,在高性能计算方面展现了卓越的性能。表连接是数据库的基本操作,是提高查询效率的突破点之一。连接算法的并行化优化,一直是并行数据库中研究热点。本文通过充分发掘MIC并行计算能力,结合MIC中的向量处理单元(VPU)实现向量化,利用多核CPU+MIC同构异步模型,改进原有的并行连接算法,加速数据库的中连接操作。本文在分析了嵌套循环连接、排序归并连接及哈希连接等三种常用连接算法基本思想方法和现有并行优化策略基础上,首先结合多核CPU和MIC的特点,提出了各个算法的对应并行化方法,充分发挥MIC支持超过200个线程的性能优势,然后利用MIC的向量处理单元,实现各个算法的数据级并行,进一步加速,提升算法性能,最后充分发挥CPU和MIC的计算能力,利用MIC提供的协同处理异步计算模型,进行相应的任务划分,实现CPU和MIC协同并行连接的方案。在本论文的实验结果与分析部分,分别列出了三种连接方式在CPU和MIC上实现的测试实验数据,通过横向和纵向比较,说明了利用MIC可以有效提高并行连接算法的性能,而结合两者的计算能力的异步计算模型可以实现最佳性能,三种算法相对串行执行最大加速比分别达到52、18、和35倍。
【关键词】：多核处理器 MIC 连接操作 并行优化
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP332
【目录】：

• 摘要5-6
• Abstract6-10
• 第一章 绪论10-14
• 1.1 研究背景10-11
• 1.2 研究目的和意义11
• 1.3 文本主要工作11-12
• 1.4 本文组织12-13
• 1.5 本章小结13-14
• 第二章 相关知识14-28
• 2.1 MIC特性综述14-20
• 2.1.1 MIC硬件特性14-15
• 2.1.2 MIC软件模型15-16
• 2.1.3 向量处理单元与指令集16-17
• 2.1.4 MIC内存管理与数据传输优化17-19
• 2.1.5 MIC优化方法19-20
• 2.2 连接算法定义和概述20-25
• 2.2.1 连接算法优化21-22
• 2.2.2 嵌套循环连接22-23
• 2.2.3 排序归并连接23-24
• 2.2.4 哈希连接24-25
• 2.3 哈希分区25-26
• 2.4 MIC上的数据结构26-27
• 2.5 本章小结27-28
• 第三章 嵌套循环连接算法优化28-36
• 3.1 CPU并行嵌套循环连接28-29
• 3.2 基于分区的并行嵌套循环连接29-31
• 3.3 基于MIC及向量化优化的嵌套循环连接31-33
• 3.4 CPU+MC异步的嵌套循环连接33-35
• 3.5 本章小结35-36
• 第四章 排序归并连接算法优化36-45
• 4.1 CPU并行排序归并连接36-39
• 4.2 基于分区的并行排序归并连接39-40
• 4.3 基于MIC和向量化优化的排序归并连接40-43
• 4.4 CPU+MIC异步的排序归并连接43-44
• 4.5 本章小结44-45
• 第五章 哈希连接算法优化45-64
• 5.1 引言45
• 5.2 CPU并行哈希连接45-51
• 5.2.1 无分区并行哈希连接45-46
• 5.2.2 分区并行哈希连接46-47
• 5.2.3 Radix-Cluster分区并行哈希连接47-51
• 5.3 基于MIC和向量化优化的哈希连接51-61
• 5.3.1 无分区并行哈希连接向量化实现51-53
• 5.3.2 并行分区并行哈希连接向量化实现（一）53-57
• 5.3.3 并行分区并行哈希连接向量化实现（二）57-61
• 5.4 CPU+MC异步哈希连接61-62
• 5.5 本章小结62-64
• 第六章 实验与分析64-80
• 6.1 测试平台64-65
• 6.2 测试数据65-66
• 6.3 实验结果与分析66-79
• 6.3.1 MIC空间分配与数据传输66-67
• 6.3.2 嵌套循环连接实验67-72
• 6.3.3 排序归并连接实验72-75
• 6.3.4 哈希连接实验75-79
• 6.4 本章小结79-80
• 总结与展望80-82
• 参考文献82-85
• 附录 185-86
• 攻读硕士学位期间取得的研究成果86-87
• 致谢87-88
• 附件88

【参考文献】

中国期刊全文数据库 前3条

1 邓亚丹;景宁;熊伟;;多核处理器中基于Radix-Join的嵌套循环连接优化[J];计算机研究与发展;2010年06期

2 叶常春,杨利,杨树强;基于工作站机群结构的并行数据库连接算法的实现[J];计算机工程与科学;2000年05期

3 孙文隽,李建中;排序合并Join算法的新结果[J];软件学报;1999年03期

  本文关键词：并行连接算法优化研究及实现，由笔耕文化传播整理发布。

，

本文编号：296070