《gpn网络的通信算法和动态修正》由会员分享，可在线阅读，更多相关《gpn网络的通信算法和动态修正（53页珍藏版）》请在金锄头文库上搜索。
1、学 号 ：学 号 ： 20070211200702111919 姓 名 ：姓 名 ： 纪 鸿 飞纪 鸿 飞 联 系 电 话 ：联 系 电 话 ： 1 138641874013864187401 EmailEmail： jihongfei2000jihongfei2000 所 在 学 院 ： 管 理 与 经 济 学 院所 在 学 院 ： 管 理 与 经 济 学 院 单 位 代 码单 位 代 码 1044510445 学学 号号 200702111200702111 9 9 分分 类类 号号 TPTP393393 硕士学位论文 论论文文题题目目 GPNGPN 网络的通信算法和动态修正网络的通信算法
2、和动态修正 学科专业名称学科专业名称 管理科学与工程管理科学与工程 申 请 人 姓 名申 请 人 姓 名 纪纪 鸿鸿 飞飞 指 导 教指 导 教 师师 马 英 红 教 授马 英 红 教 授 论文提交时间论文提交时间 20102010 年年 5 5 月月 2626 日日 独独 创创 声声 明明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得_ (注：如没有其他需要特别声明的，本栏 可空)或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做的
3、任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 导师签字： 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解 学校学校 有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 学校学校 可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。(保密的学位论文在解密后适用本授权书) 学位论文作者签名： 导师签字： 签字日期：2010 年 月 日 签字日期：2010 年 月 日 山东师范大学硕士学位论文 目 录 摘 要. Abstract.
4、III 第一章 绪论. 1 1.1 研究背景 . 1 1.2 国内外相关研究现状 . 2 1.3 本文的主要工作 . 2 第二章 并行计算机系统及互连网络. 4 2.1 并行计算机系统及其分类 . 4 2.2 互连网络的特性 . 7 2.3 常见的互连网络拓扑结构 . 8 第三章 GPN 网络性质及通信算法 . 15 3.1 GPN 网络的构造. 15 3.2 GPN 网络的性质. 16 3.3 GPN 网络上的通信算法设计. 20 3.3.1 单播路由. 20 3.3.2 置换路由. 21 3.3.3 广播路由. 22 3.3.4 All-to-All 路由 . 23 第四章 GPN 网络的
5、动态修正 . 24 4.1 预备知识 . 24 4.1.1 描述真实网络统计特征的主要概念. 24 4.1.2 WS 小世界模型构造算法与 BA 无标度模型构造算法 . 26 4.2 GPN 网络的动态修正. 27 4.2.1 基于 WS 小世界模型构造算法的 GPN 网络修正. 27 4.2.2 基于 BA 无标度模型构造算法的 GPN 网络修正. 29 第五章 总结与展望. 35 5.1 本文的主要内容 . 35 山东师范大学硕士学位论文 5.2 进一步的研究工作 . 35 参考文献. 35 攻读硕士学位期间发表论文及参加科研项目情况. 39 致 谢. 42 山东师范大学硕士学位论文 I
6、GPN 网络的通信算法和动态修正 摘 要 随着计算机网络技术与计算科学的发展，并行计算机及其互连网络作为一个跨数学、 计算科学与信息科学等多门学科的领域，逐渐成为计算机科学研究的热点之一。各种拓扑 结构的互连网络，如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互 连网络中，处理器之间的有效通信是衡量系统性能的一个重要标准。Petersen 图是多处理 机系统中常见的一种互连网络，这种网络拓扑结构由于具有直径小、结构对称、网络寻路 算法简单等优点，且多种拓扑结构的互连网络都可以很容易的嵌入其中，因而成为最重要 和最具吸引力的网络模型之一。本文即是基于 Petersen 图进行扩
7、展，并对扩展得到 GPN 网络路由算法和动态修正进行研究，主要研究内容如下： 1. 阐述了并行计算机系统的概念和分类，然后详细介绍了并行计算机模型、特性以 及常用的互连网络拓扑结构，包括一维线性阵列、环、Mesh、Torus、树形拓扑、超立方 体、Petersen 图和 GP(n,k)网络。 2. 基于 Petersen 图，提出了 GPN 的网络结构，并对其特性进行了研究，证明了 GPN 网络具有正则性以及良好的可扩展性,同时还具有比 RP(k)、2-D Torus 更短的直径和良好 的并行能力。另外,还基于 GPN 网络给出了路由算法,证明其具有较好的通信效率。 3. 为得到更符合实际网络
8、的网络模型，并将网络性质进一步提高，在 GPN 网络基础 上，通过 WS 小世界模型构造算法与 BA 无标度模型构造算法对 GPN 网络进行修正，模拟修 正后网络的平均路径长度和聚类系数，并将修正后网络的性质与规则 GPN 网络、随机 GPN 网络进行比对，得到修正后的 GPN 网络在平均路径长度和聚类系数方面分别具有更好的性 质。 本文已经对 GPN 网络的一些基本性质作了研究，并进行了动态修正，但是仍有很多工 作需要继续,主要是： 1.进一步分析 GPN 网络的各种性质，如可分组性，并且给出网络的容错路由算法和自 适应算法等。 山东师范大学硕士学位论文 II 2.应用其它模型构造算法对 G
9、PN 网络进行修正，使网络的平均路径长度及聚类系数等 性质更进一步提高，同时对现实网络的其它统计性质进行研究，并讨论网络修正后在这些 统计性质上的提高。 关键词：关键词：Petersen Petersen 图；图；GPNGPN 网络；路由算法；网络；路由算法； 动态修正动态修正 分类号：分类号：TPTP393393 山东师范大学硕士学位论文 III Communication algorithms and dynamic correction of GPN graph Abstract With the development of computer networks and computin
10、g science, paralleling computer and interconnection networks, covering mathematics, computing science, information science and so on, are becoming one of the hotspots of computer science research. All kinds of interconnection networks with different topologies, such as Ring, Mesh, Hypercube, star to
11、pology network etc. have developed rapidly. In the interconnection networks with multiprocessor, it is an important standard to evaluate the efficient communication among different processors. Petersen graph is one of the common interconnection networks. It has the metrics of small diameter, symmetrical structure and simple path searching algorithms, etc., what is more, many interconnection networks with different topologies can be easily embe
