基于网格的海量数据并行JOIN算法研究与实现

VIP免费
3.0 陈辉 2024-11-19 4 4 1.31MB 80 页 15积分
侵权投诉
摘 要
随着信息技术的飞速发展和日益普及，海量信息的处理和高性能计算的需求
越来越迫切。并行计算机和并行环境一直是高性能计算研究热点之一，现已出现
许多高性能的专用并行计算机如 IBM SB2、
SGI Power Challenge、
Cray T3d 以及国
内的曙光系列并行机等，但它们都具备难以接受的高昂的价格。网格和数据网格
以其良好的自治性、自相似性、异构性、管理多样性、强大的并行 I/O 能力、非常
高的性能价格比等特性成为高性能计算的最佳解决方案之一。由于网格并行计算
具有复杂性、动态性，而现在基于网格的数据并行型计算的研究才刚刚起步，存
在着动态管理、扩展性和可靠性问题。
本课题研究的是以网格和数据网格并行计算为基本理论依据，由于网格环境
下各个节点的异构性和通信速率的差异性，再加上海量数据的查询给数据库的查
询操作带来了新的问题。针对这种新的结构特点，本文提出一种基于海量数据并
行JOIN 算法，使其充分利用各种并行性和减少传输量来缩短响应时间。并对算法
进行了实现，对主要影响因素和系统的效率进行了验证。其研究内容有以下几个
方面：网格计算系统（DGCS）、网格监控系统（DGMS）、JOIN 算法实现及优化、
容错机制和资源动态管理策略(RDMM)、海量数据的划分与传输。最后利用 Java
语言和 Eclipse 开发工具实现了这一计算模型，并进行了一系列的实验，获得可靠
的和实用的实验数据，为网格并行计算的研究提供技术和实验数据支持。
关键词：网格计算 并行计算 并行连接 海量数据
ABSTRACT
With the development of information technology, the demand of large scale
information settling and high performance computing become urgent, Parallel computer
and parallel environment is one of the fields of high performance computing. Now some
appropriative parallel computers such as IBM SB2、SGI Power Challenge、Cray T3d
appears, but they have high price. Grid and data grid, with well autonomy,
comparability, isomerism, diversity of management, and powerful parallel I/O capability,
is the best solution of high performance computation.
For data grid parallel computation has complexity and dynamic and the research of
data parallel computation based on data grid starts just now, data grid parallel
computation has the problem of dynamic management, expansibility and dependability.
Based on grid and data grid parallel computation idea and theories , Because of the
high heterogeneity of the nodes and the widely different communication rates under the
Grid environment , in addition the massive data , the database query operation
encounters new challenges. This paper presents an algorithm to make it fully to use each
kind of parallelism and relations reduces algorithm to reduce the response time. And has
carried on the realization to the algorithm, has carried on the confirmation to the major
effect factor and the system efficiency .The content include the following：Date Grid
Computing System (DGCS), Date Grid Monitoring System (DGMS), JOIN algorithm
and optimization, fault-tolerant mechanisms and dynamic resource management
strategy (RDMM), and the delineation of massive data transmission . the programm is
implemented by using Java language and Eclipse development tool. A series of
experience is done and dependable and usable experience data is obtained. The chapter
provides the support of technology and experience data to the research of data grid
parallel computing.
Key Words：Grid Computing, parallel Computing, massive data, parallel
JOIN
目 录
摘 要
ABSTRACT
第一章 绪论 .....................................................................................................................1
§1.1 课题背景与研究意义 .........................................................................................1
§1.2 国内外研究现状及发展 .....................................................................................2
§1.3 本文的研究内容及实施方案 .............................................................................3
第二章 网格计算理论概述 .............................................................................................4
§2.1 网格概述 ............................................................................................................ 5
§2.2 网格计算体系结构 ............................................................................................ 5
§2.3 网格计算系统的关键技术 ................................................................................ 7
§2.4 网格计算系统的应用 ........................................................................................ 8
第三章 海量数据存储方式与并行计算理论 .................................................................8
§3.1 海量数据的划分原则 ........................................................................................ 8
§3.2 数据划分方法 .................................................................................................... 9
§3.3 并行计算概述 .................................................................................................. 11
§3.4 并行计算模型 .................................................................................................. 12
§3.4.1 理想计算模型的特征 .............................................................................13
§3.4.2 典型的同构并行计算模型 .....................................................................14
§3.4.3 异构并行计算模型 .................................................................................17
§3.5 并行算法简介 .................................................................................................. 17
§3.6 并行算法的研究内容 ...................................................................................... 18
§3.7 并行程序设计语言 .......................................................................................... 18
§3.8 并行程序设计目前面临的困难和发展 .......................................................... 19
第四章 并行 JOIN 算法的研究 ....................................................................................21
§4.1 并行 JOIN 的相关算法 ................................................................................... 21
§4.2 基于数据划分的并行连接算法 ...................................................................... 21
§4.2.1 并行嵌套循环连接算法 .........................................................................21
§4.2.2 改进的并行嵌套循环连接算法 .............................................................22
§4.2.3 并行排序合并连接算法 .........................................................................23
§4.2.4 使用索引的并行连接算法 .....................................................................24
§4.2.5 并行哈希连接算法 .................................................................................25
§4.2.6 简单并行 hash 连接算法 ....................................................................... 26
§4.2.7 多趟简单并行哈希连接算法 .................................................................27
§4.2.8 并行 Grace 哈希连接算法 ..................................................................... 27
§4.2.9 并行 Hybrid 哈希连接算法 ................................................................... 28
§4.3 基本并行连接算法比较 ................................................................................ 31
第五章 网格环境管理 ...................................................................................................32
§5.1 基本定义 ........................................................................................................ 32
§5.2 网格监控系统 ................................................................................................ 35
§5.3 任务管理 ........................................................................................................ 38
§5.3.1 任务分解原则 .........................................................................................38
§5.3.2 任务分解策略 .........................................................................................38
§5.3.3 任务协同 .................................................................................................39
§5.3.4 任务冗余分配策略 .................................................................................39
§5.3.5 任务和数据分配 .....................................................................................40
§5.3.6 任务调度策略 .........................................................................................41
§5.3.7 任务和数据访问策略 .............................................................................43
§5.4 资源管理 ........................................................................................................ 44
第六章 网格环境下的 JOIN 算法 ................................................................................47
§6.1 研究的问题及算法描述 ................................................................................ 47
§6.1.1 初始条件及问题描述 .............................................................................47
§6.1.2 参数定义 .................................................................................................47
§6.1.3 查询处理过程 .........................................................................................48
§6.1.4 查询任务 .................................................................................................48
§6.1.5 优化策略 .................................................................................................49
§6.1.6 数据传输策略 .........................................................................................50
§6.1.7 算法处理模型 .........................................................................................50
§6.1.8 算法描述 .................................................................................................52
§6.2 算法时空复杂度分析 .................................................................................... 54
§6.2.1 算法时空复杂度理论分析 .....................................................................54
§6.2.2 本算法连接代价估算 .............................................................................56
第七章 实验模拟与性能分析 .......................................................................................58
§7.1 实验模拟 ........................................................................................................ 58
§7.1.1 环境搭建 .................................................................................................58
§7.1.2 海量数据的产生 .....................................................................................58
§7.1.3 程序核心代码实现 .................................................................................58
§7.1.4 数据划分与存储方式 .............................................................................70
§7.2 实验性能分析 ................................................................................................ 70
§7.2.1 加速比 .....................................................................................................70
§7.2.2 主要影响因素 .........................................................................................71
第八章 结论和展望 .......................................................................................................72
参考文献 .........................................................................................................................73
在读期间公开发表的论文和承担科研项目及取得成果 .............................................76
致谢 .................................................................................................................................77
错误！未定义样式。
1
第一章 绪论
§1.1 课题背景与研究意义
科学技术的发展和金融、电信、交通、信息安全等众多行业信息化需求的不
断增加，在系统业务功能逐步增强的同时,系统的数据量也不断增大,数据量高达
几百 GB 甚至于 TB 级的海量数据库应用已经出现。与此同时,人们对高性能联机
事务处理和复杂查询操作能力的需求也在不断提高，特别针对一些跨国大公司和
国家的公共服务行业，这些地理上分布的海量数据，而用户希望能够访问，使用
这些庞大的分布数据。这种结合海量数据集合，地理上分布的用户和资源，以及
计算密集型的分析处理应用促使了处理海量数据能力的数据库系统的出现，为此,
人们提出了各种不同的并行处理方法： 由 SMP 到集群技术[1-3],再到现在的网格技
术,要求参与并行处理的处理机在地域上的分布越来越分散,从一个计算机内到基
本分布在同一建筑之内的集群,最终到现在遍布全球的网格。网格计算[4-7]的目标是
支持在分布式的异构环境中动态地形成虚拟计算机,方便用户合作完成大型任务。
因为这个虚拟计算机是由分布在各地的计算机形成的,它们之间的协作必定要涉及
到数据的传输问题,尤其是涉及到数据库操作时。数据库在网格环境下的应用,必定
带来数据的大量传输和某些数据操作只能在特定节点执行的问题,还有网格环境本
身固有的高度异构性都给数据库查询任务的并行化带来了新的问题，在海量并行
数据库应用系统中,由于系统具有海量性、高速性、连续性等特点[8-11]，从而对 JOIN
查询的执行效率以及查询性能提出了更高的要求。随着数据源的数量和查询条件
的数量的增加, JOIN 查询所要做的数据传输量也将迅速的增加,系统需要大量的
网络和磁盘 I/O 开销,以至于在海量并行数据库环境下,即使是很简单的查询统计
也变得很难实现,全球各大主流数据库厂商在新产品中无一例外地宣称提供了对海
量数据库 VLDB(Very Large Database) 的支持,众多数据库支持的数据量已达到
TB 级。事实上,对VLDB 的支持并不仅仅指的是数据库系统的数据量,而是更多
地体现在对数据库系统的管理能力,包括日常管理、数据加载、数据查询、索引建
立、运行性能等,同时还需要支持大量的用户连接和大的工作负荷。 只有在此基
础上保持良好运行性能的数据库系统才能构成超大型数据库应用系统。目前商业
并行数据库系统的扩展能力、接入能力和查询效率都不是太理想,尤其随着系统的
扩展,数据规模增大,系统性能急剧下降[12-16]。为此,我们设计并实现了一个网格
环境下海量数据的 JOIN 算法，以使其适应新的环境的要求，并在该环境下进行了
摘要：

摘要随着信息技术的飞速发展和日益普及，海量信息的处理和高性能计算的需求越来越迫切。并行计算机和并行环境一直是高性能计算研究热点之一，现已出现许多高性能的专用并行计算机如IBMSB2、SGIPowerChallenge、CrayT3d以及国内的曙光系列并行机等，但它们都具备难以接受的高昂的价格。网格和数据网格以其良好的自治性、自相似性、异构性、管理多样性、强大的并行I/O能力、非常高的性能价格比等特性成为高性能计算的最佳解决方案之一。由于网格并行计算具有复杂性、动态性，而现在基于网格的数据并行型计算的研究才刚刚起步，存在着动态管理、扩展性和可靠性问题。本课题研究的是以网格和数据网格并行计算为基本...

展开>> 收起<<
基于网格的海量数据并行JOIN算法研究与实现.pdf

共80页,预览8页

还剩页未读， 继续阅读

相关推荐

更多
立即下载
作者：陈辉 分类：高等教育资料 价格：15积分 属性：80 页 大小：1.31MB 格式：PDF 时间：2024-11-19

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

推荐作者

热门标签

/ 80
评分 收藏
分享
立即下载 VIP免费下载
客服
关注