网格并行通信模型的研究

VIP免费

3.0 赵德峰 2024-11-19 5 4 1.07MB 94 页 15积分

侵权投诉

摘要

随着信息技术的飞速发展和 Internet 的日益普及，信息爆炸已经成为当今

信息技术产业界和学术界所面临的急需解决的主要问题。针对这一问题，网格以

其良好的自治性、自相似性、异构性、管理的多样性、强大的并行 I/O 能力、非

常高的性能价格比等特点成为一个可行的解决方案。

在数据网格中，强大的数据处理、存储中心是一个研究焦点。研究表明，实

现这种中心的有效手段是构建由多个网络构成的大规模机群，进一步构建基于网

格的并行计算系统。然而，随着机群节点数目和网络数目的增加，通信将成为瓶

颈。尤其是对数据并行方式来工作的，同步只发生在数据需要交换时。数据交换

时会产生通信的峰值，当进行数据密集交换并且通信量很大时，将导致冲突。冲

突将会浪费通信资源、降低并行性。

有关并行通信的研究中，从协议和硬件的角度来实现并行通信的理论是成熟

的。但是它们还是不能满足多计算机机群网格的需要，更主要是：他们不能够高

效地解决异构网格环境下大规模并行通信的峰值通信问题。

基于 IP 协议和普通宽带网络的多级分组通信模型就是从通信策略和控制方

面来解决峰值通信冲突的研究成果。在这种多级分组通信模型中，通过有序的分

组机制来解决大规模计算中峰值通信问题，即模型通过对计算节点进行分组，把

多对多的完全图通信简化为多次并行的一对多通信。

本文对多级分组通信模型的机群内的通信分组模型进行了进一步详细的探

讨，主要工作如下：（1）根据各个计算节点能力的差异，网络的实际通信能力，

研究了一系列有效的分组策略，并优化了机群的分组通信模型。（2）给出了实现

这些通信模型的关键技术，并用 JAVA 进行了实现。（3）通过实验验证了各种分

组策略的效率。

关键词：并行计算数据网格峰值通信分组通信分组策略

ABSTRACT

For the rapid development of the information techniques and the popular use of Internet,

information explosion has become the main problem which the information technology

industry and the academe face on and must breakthrough. And Grid, with the feature of

autonomy, self-like, heterogeneity, multiple administrative domains, powerful parallel

I/O ability, and high rate between performances and its cost, etc, become a flexible way

to resolve to this problem.

Within data-grid, the powerful data computing and storage center is the high point

that must be focused on. Research that the most efficient way to realize this center is to

build a large-scale Cluster that composed of many networks, and than build a parallel

computing system upon them based on grid. Nevertheless, as the increment of

computing nodes and networks, data communication will be the bottleneck for this

system. Especially, to parallel computing, synchronization only happens during the time

that data need to be exchanged. Data exchange will lead to communication peak.

Conflict will happen when it is an intensive data exchange and massive data need to be

exchanged. Conflicts will waste communication resources and lower the degree of

concurrence.

In the research of parallel communication, theories of parallel communication carried

out from protocol and hardware are mature, but they haven’t achieved the needs of

Cluster-Grid with large amount of PCs. And more important, they couldn’t resolve the

large-scare parallel communication peak problem that happened in heterogeneity grid

platform efficiently.

Multi-level grouping communication model that based on IP protocol and networks

with common bandwidth is the exact research outcome that efficiently resolve

communication peak problem by communication strategy and control. In this

multi-level grouping communication model, communication peak problem within

large-scare parallel computing is resolved by sequence grouping mechanism. Means by

grouping computing nodes, this model simplified many to many completed graph

communication to many concurrence one to many communications that happen in

different time.

Father discussion about grouping communication model within a single Cluster for

multi-level grouping communication model is represented in this paper. The main jobs

of this paper are as following: (1) Basing the difference of computing nodes’

computation capability and the actual communication ability of networks, several

grouping strategies are described, and the grouping communication model within single

Cluster has been optimized. （2) The key technologies to realize this communication

model are described also, and this model has been realized by JAVA. (3) The efficiency

of all these grouping strategies has been experimented.

Key words: Parallel Computing, Data-Grid, Communication Peak,

Grouping Communication，Grouping Strategy.

中文摘要

ABSTRACT

第一章绪论 ......................................................... 1

§1.1 课题来源与意义 ............................................. 1

§1.2 国内外研究现状 .............................................. 2

§1.3 本文的研究工作 ............................................. 3

§1.4 论文各章节的安排 ........................................... 3

第二章网络 .......................................................... 4

§2.1 网络协议 ................................................... 4

§2.1.1 网络模型 .............................................. 4

§2.1.2 物理层协议要点和技术 .................................. 6

§2.1.3 数据链路层技术要点和协议 .............................. 7

§2.1.4 网络层技术要点和协议 .................................. 9

§2.1.5 传输层技术要点和协议 ................................. 11

§2.1.6 应用层技术要点和协议 ................................. 11

§2.2 网络硬件 .................................................. 11

§2.3 网络拓扑结构[49] ............................................ 12

第三章并行计算 ..................................................... 14

§3.1 并行计算概述 .............................................. 14

§3.1.1 并行计算模型 ......................................... 14

§3.1.2 并行程序设计语言 ..................................... 19

§3.1.3 并行程序设计目前面临的困难和发展 ..................... 20

§3.2 并行计算的应用 ............................................ 21

第四章网格并行计算 ................................................. 23

§4.1 网格概述 .................................................. 23

§4.1.1 网格的有关概念和目的[2] ................................ 23

§4.1.2 网格的特点[3] .......................................... 25

§4.1.3 网格体系结构和工具 ................................... 26

§4.2 基于网格的应用 ............................................ 29

§4.2.1 网格在科学计算上的应用 ............................... 30

§4.2.2 网格在社会经济生活上的应用 ........................... 31

§4.3 基于网格的应用所面临的有关问题 ............................ 31

§4.3.1 网格任务的分解 ....................................... 31

§4.3.2 网格通信 ............................................. 32

§4.3.3 网格资源管理 ......................................... 32

第五章网格并行计算的通信 ........................................... 34

§5.1 网格并行计算中的通信问题 .................................. 34

§5.2 目前有关的解决方法 ......................................... 35

§5.3 这些解决方法的比较 ......................................... 38

第六章多级分组通信模型[6] ........................................... 40

§6.1 数据密集型网格模型、计算过程和通信问题 ..................... 40

§6.2 单个机群分组通信模型 GCAS .................................. 42

§6.3 两个机群分组通信模型 GCAD .................................. 46

§6.4 多个机群分组通信模型 MGCM .................................. 46

§6.5 分析 ...................................................... 48

第七章优化的单个机群分组通信模型 ................................... 50

§7.1 接收数目固定的单个机群分组通信模型 ......................... 50

§7.1.1 对多级分组通信模型的改进 ............................. 50

§7.1.2 接收数目固定的分组方法 ............................... 52

§7.1.3 接收数目固定的单个机群分组通信模型 ................... 55

§7.1.4 分析 ................................................. 57

§7.2 发送和接收相匹配的单个机群分组通信模型 .................... 59

§7.2.1 对分组通信模型的改进 ................................. 59

§7.2.2 发送能力和接收能力相匹配的分组方法 ................... 62

§7.2.3 发送能力和接收能力相匹配的单个机群分组通信模型 ....... 69

§7.2.4 分析 ................................................. 72

第八章关键技术 ..................................................... 74

§8.1 通信控制技术 .............................................. 74

§8.1.1 计算节点 CN .......................................... 74

§8.1.2 队列 ................................................. 75

§8.1.3 选播标志矩阵 ......................................... 76

§8.2 计算节点过程模型 .......................................... 77

§8.3 机群 ...................................................... 80

§8.2.1 机群控制器 Master ..................................... 80

§8.2.2 计算节点 Node ........................................ 81

第九章测试 ......................................................... 82

§9.1 实验环境描述 ............................................... 82

§9.2 优化分组方法的发送误差测试 ................................ 82

§9.3 简单分组与优化分组通信的对比 ............................... 83

参考文献 ............................................................ 85

在读期间公开发表的论文和承担科研项目及取得成果 ...................... 90

致谢 ............................................................ 91

第一章绪论

§1.1 课题来源与意义

近年来，随着科学技术和信息技术的发展，各行各业的信息量剧增，信息爆

炸已经成为当今信息产业界和学术界所面临急需解决的问题，对更高性能计算机

的需求已不再局限于传统的大数据量的科学计算领域（天气预报、人造卫星等科

学计算领域），在海量数据库查询、INTERNET 等较为广泛的应用领域也提出了同

样的要求。适应这种趋势需要的解决方案显然不能再利用价格昂贵的大型机、巨

型机，而应当是使用多台微机或工作站组成的基于网格的分布式计算。

网络技术[1]和网格[2][3]以其良好的自治性、自相似性、异构性、管理的多样性、

强大的并行 I/O 能力、非常高的性价比等特性成为一个可行的解决方案。在网格

中，强大的数据处理、存储中心始终是一个研究焦点。研究表明，实现这种中心

有效手段是构建由多个网络构成的大规模机群。然而，随着机群节点数目和网络

数目的增加，通信将成为瓶颈。尤其是对数据并行方式来工作的系统，数据需要

交换，同步只发生在数据交换时，从而会周期性的出现大规模多对多通信。数据

交换时的大规模多对多通信会使网格系统产生通信的峰值，当进行数据密集交换

并且通信数据量很大时，通信的峰值问题将会产生许多负面问题，如导致通信冲

突、网络阻塞、接收缓冲区溢出、多对一通信的相互阻塞、无效传输、死锁等情

况，浪费了可贵的通信资源、降低了并行性、降低了系统的可扩展性。（典型的数

据密集交换的例子是并行 JOIN[4] [5] 操作的关系元组重分配阶段。）

通过研究表明，通信是基于网格的大规模、分布式计算瓶颈，高效的通信策

略将能有效的利用系统的通信资源、提高计算的并行度、增加系统的可扩展性。

目前国内外有关高效通信的研究有很多，与其它通信技术和通信策略相比，基于

IP 协议和普通网络带宽的多级分组通信模型[6]有明显的优势：

IP 协议是最基本、最简单且最广为使用的通信协议；

普通网络带宽对于网格系统的通信设施来说更具有普遍性；

基于 IP 协议和普通网络带宽的多级分组通信模型是把大规模多对多通信

分解为小规模并行的一对多通信，在解决了系统的通信峰值问题的同时几

乎没有给系统增加模块，节省了系统的构建和维护费用。

同时，在通信时考虑各个网格计算节点计算能力的差异、各个机群网络带宽

的差异，可以充分的利用网络带宽、各个计算节点的能力，提高效率。

因此，本课题的研究成果对于满足当前应用需要，适应信息量剧增的趋势，

网格并行通信模型的研究

进行海量数据高性能查询具有重要的作用和现实意义。

§1.2 国内外研究现状

计算机网络技术始于20世纪70年代ARPANET的出现。ARPANET是一个实验

性网络，开发了基本的数据传输协议TCP/IP和提出了一些重要的概念；通过发展，

在1986年建立了一个重要的网络NSFNET，连接了美国5个NSF超级计算机中心，

其主干网的带宽于1990年提高到45Mb/s，后来扩展为现在的Internet；在1998年，

美国建立了一种新的主干网络VBNS(very high speed backbone network service)，发

展出国家和地区的网络STAR TAP[7]（Science, Technology, And Research Transit

Access Point），为世界范围网络的出现提供了基础。

随着网络基础设施和网络技术的不断发展，将网络中的计算机作为一个并行/

分布式计算系统的构想开始形成，许多应用很自然的采用了这种计算形式。到目

前为止，并行计算[8]已经有20多年的历史。在并行计算系统中，包括并行机、并行

计算模型、并行算法。并行机是基础，并行计算模型是并行计算基本特征的抽象，

是并行算法的基础，并行算法是应用。作为并行计算系统的核心，并行计算模型

理性情况下具有简单好用和较好反映体系结构特征的特点。最重要和典型的几种

并行计算模型包括PRAM[9]

（Parallel Random Access Machine）模型、BSP[10]

（Bulk

ynchronous Parallel）模型和LogP[11]模型，贯穿其发展的一条主线是如何准确地反

映并行机特有的通信开销。这几种模型一般用于同构系统，近年发展的异构系统

和网格系统的计算模型一般是BSP模型的扩展（如异构粗粒度多处理机模型[12]、

Cluster-M[13]和异构块同步并行模型[14]等）。

与此同时，随着网络技术和计算机硬件技术的飞速发展和成熟，以及计算理

念在计算机应用领域的发展和应用，Grid技术无论是从概念还是应用技术都得到了

巨大的发展。

Grid是一种集成的计算与资源环境，它具有资源的分布性、结构的自

相似性、节点的动态可伸缩性、管理的多重性和自治性等特点。针对这一些特点，

Foster等人提出了以协议为中心的五层沙漏模型[15]和以服务为中心的OGSA[16] [17]模

型。此外，以Globus组件为核心的网格底层支撑技术为解决如跨操作系统的通信和

跨文件系统的访问等异构分布式问题提供了有效手段。

目前有关并行计算的高效通信的研究有很多。Xpress[18] 传输协议是一种适合

机群通信的协议，它除了能提供传统 TCP/UDP 协议中所有的服务外，还专门提供

适合机群通信需要的服务，如：组播管理、优先级、速率和突发控制、连接管理

等等服务；利用多个物理通信设备[19]的多通路通信机制是一种适合异构网络的通

信策略，它利用了基于性能的通路决定技术，根据不同物理网络和协议所具有的

第一章绪论

不同性能，来选择一条最佳的虚拟通路来传输不同类型数据。活动消息[20]（AM）

是一种用在专门的基于分布存储的并行处理系统（MPP）上的多种协议中的一种，

AM 是一种不需要在同步通信上有太多的开销就可以使计算并发进行的消息传递

系统。

以上有关机群的通信都是需要给系统增加硬件或软件功能模块，会导致系统

更加复杂，降低了系统的扩展性，降低了计算效率，不增加系统功能模块和系统

复杂度的高效通信策略的研究对基于网格的大规模分布式并行计算十分必要和

紧迫，目前此类研究比较少，本项目的研究和实现将填补此领域的空缺。

§1.3 本文的研究工作

在对计算机网络和并行计算和网格、并行计算和网格并行计算中的通信问题

以及两者网络问题的差异、目前阶段有关并行计算中网络问题的解决方法进行了

广泛和深入了解的基础上，详细的讨论了适合解决网格并行计算通信问题的多级

分组通信模型，进而提出改进的单个机群分组通信模型——充分考虑网格各个节

点计算能力差异和网格中各个机群网络带宽差异对通信影响的分组通信模型，以

提高计算节点能力的使用率。

根据各个计算节点能力的差异，网络的实际通信能力，研究了一系列有效的

分组策略，并优化了机群的分组通信模型。给出了实现该通信模型的关键技术，

并用 JAVA 进行了实现。通过实验验证了各种分组策略的效率。

§1.4 论文各章节的安排

本文第一章介绍了课题的来源和意义以及国内外相关领域的研究现状，第二

章介绍了网络的协议、硬件、结构，第三章介绍并行计算的概念、应用，第四章

介绍了网格的概念、网格并行计算、网格并行计算中存在的问题，第五章介绍了

目前阶段并行计算通信问题的解决方法，第六章介绍了多级分组通信模型，第七

章介绍了两个优化的分组通信模型，第八章介绍一些关键技术，第九章为分组通

信模型的测试，第十章为结束语。

网格并行通信模型的研究

第二章网络

计算机网络是用通信线路将分散在不同地点并具有独立功能的多台计算机系

统互相连接，按照网络协议进行数据通信，实现资源共享的信息系统，是计算机

技术和通信技术相结合的产物。

1954 年一种收发器终端制造出来后，计算机技术和通信相结合，计算机网络

的概念开始形成。在 20 世纪 60 年代初期广泛使用的是一种称谓面向终端的计算

机通信网，通常称为第一代计算机网络。20 世纪 60 年代末期，美国的分组交换网

ARPANET 投入运行，计算机网络进入了一个崭新的发展阶段，分组交换网是现代

计算机网络技术的基础。ARPANET 的出现标志网络技术的形成，经过发展，

ARPANET 网的以单个主机为中心的面向终端的计算机网络转变为以通信子网为

中心的分组交换网，而主机和终端则处于网络的外围构成资源子网。这种以通信

子网为中心的计算机网络通常称为第二代计算机网络。在 20 世纪 70 年代到 80 年

代初期是网络体系结构形成的时期，出现了广泛应用的系统网络体系结构 SNA

（system network architecture）和国际上广为承认的开放系统互连参考模型（OSI），

这些网络体系结构的形成大大地加快了计算机网络技术的发展，使得计算机网络

开始了所谓第三代计算机网络的新纪元。在二十世纪 80 年代中后期以来，计算机

网络进入了第四代时期，这个时期网络通信线路得到了大大的发展，网络连接的

范围逐渐由一个地区到一个国家，再到现在连接整个世界的 Internet。网络速度大

大的提高，使得计算机网络得到了更为广泛的使用。

§2.1 网络协议

§2.1.1 网络模型

计算机网络是一个非常复杂的系统，需要解决的问题很多，把计算机网络分

层来理解和设计显得十分必要。有重要影响的两个计算机分层的参考模型有 OSI

参考模型[21]和TCP/IP 参考模型[22] [23] [24]，图 2-1 显示了它们以及它们的对应关系。

第二章网络

图1-1 OSI 和TCP/IP 模型

OSI 参考模型有 7层。最底层为物理层，它涉及到通信在信道上传输的原始比

特流，包括保证高低电平在收发双方一致、处理连接的建立和拆除、标准化网络

接插件。物理层的设计主要处理了机械的、电气的、过程的接口和物理传输介质

等问题。数据链路层的主要任务是加强物理层传输原始比特的功能，使之对上层

的网络层显现为一条无错线路。包括产生和识别帧边界、解决由不正常传输（破

坏、丢失、重复）帧所产生的问题、防止高速发送方把低速接收方“淹没”。网络

层关系到子网的运行控制，包括确定分组从源端到目的端的路由、拥塞控制、记

账等等功能。传输层的基本功能包括从会话层接收数据、把数据划分成较小的数

据单元、确保到达目的端各段信息的正确性、识别报文属于的连接、控制流量。

会话层允许不同机器上的用户建立会话关系，包括允许普通数据的传输、令牌管

理、同步等。表示层完成某些常被请求的特定的功能。表示层关心所传输信息的

语法和语义，而表示层以下各层关心数据传输的可靠性问题。应用层包含大量人

们普遍需要的协议，包括定义网络虚拟终端和文件传输功能等。

在ARPANET 和ARPANET 的后继因特网中使用的参考模型是 TCP/IP 参考模

型。TCP/IP 的第一层为主机至网络层，在 TCP/IP 参考模型中，没有真正的描述这

一层，仅指出主机必须使用某种协议与网络连接。第二层为互联网层，各种各样

文件和声音传输的需求导致了基于无连接互联网络层的分组交换网的产生，所以

互联网层是整个 TCP/IP 参考模型体系结构的关键部分，它的功能是使主机可以把

分组发送给任何网络并使分组独立地传向目标。这些分组到达的顺序和发送的顺

序可能不同，如果需要按顺序发送和接收就需要在高层对分组排序。互联网层还

定义了正式的分组格式和协议，即 IP 协议。互联网层上面是传输层，它的功能是

使源端和目标端主机上的对等实体可以进行会话，定义了面向连接的协议传输协

议TCP 和面向无连接的用户数据报协议 UDP。传输层上面是应用层，这层包含了

所有高层协议，如虚拟终端协议（TELNET）、文件传输协议（FTP）、电子邮件协

议（SMTP）、域名系统服务 DNS、新闻文章传递 NNTP 协议、HTTP 协议等等。

从图 2-1 和上面介绍的可知，OSI 和TCP/IP 参考模型有很多相似的地方，如

应用

表示

会话

传输

网络

数据链路

物理

OSI

TCP/IP

应用

传输

互联网

主机至网络

在模型

中不存在

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要随着信息技术的飞速发展和Internet的日益普及，信息爆炸已经成为当今信息技术产业界和学术界所面临的急需解决的主要问题。针对这一问题，网格以其良好的自治性、自相似性、异构性、管理的多样性、强大的并行I/O能力、非常高的性能价格比等特点成为一个可行的解决方案。在数据网格中，强大的数据处理、存储中心是一个研究焦点。研究表明，实现这种中心的有效手段是构建由多个网络构成的大规模机群，进一步构建基于网格的并行计算系统。然而，随着机群节点数目和网络数目的增加，通信将成为瓶颈。尤其是对数据并行方式来工作的，同步只发生在数据需要交换时。数据交换时会产生通信的峰值，当进行数据密集交换并且通信量很大时，将导...

展开>> 收起<<

网格并行通信模型的研究.pdf

共94页,预览10页

还剩页未读，继续阅读

网格并行通信模型的研究

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: