论文部分内容阅读
随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一。各种拓扑结构的互连网络,如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互连网络中,处理器之间的有效通信是衡量系统性能的一个重要标准。Petersen图是多处理机系统中常见的一种互连网络,这种网络拓扑结构由于具有直径小、结构对称、网络寻路算法简单等优点,且多种拓扑结构的互连网络都可以很容易的嵌入其中,因而成为最重要和最具吸引力的网络模型之一。本文即是基于Petersen图进行扩展,并对扩展得到GPN网络路由算法和动态修正进行研究,主要研究内容如下:1.阐述了并行计算机系统的概念和分类,然后详细介绍了并行计算机模型、特性以及常用的互连网络拓扑结构,包括一维线性阵列、环、Mesh、Torus、树形拓扑、超立方体、Petersen图和GP(n,k)网络。2.基于Petersen图,提出了GPN的网络结构,并对其特性进行了研究,证明了GPN网络具有正则性以及良好的可扩展性,同时还具有比RP(k)、2-D Torus更短的直径和良好的并行能力。另外,还基于GPN网络给出了路由算法,证明其具有较好的通信效率。3.为得到更符合实际网络的网络模型,并将网络性质进一步提高,在GPN网络基础上,通过WS小世界模型构造算法与BA无标度模型构造算法对GPN网络进行修正,模拟修正后网络的平均路径长度和聚类系数,并将修正后网络的性质与规则GPN网络、随机GPN网络进行比对,得到修正后的GPN网络在平均路径长度和聚类系数方面分别具有更好的性质。本文已经对GPN网络的一些基本性质作了研究,并进行了动态修正,但是仍有很多工作需要继续,主要是:1.进一步分析GPN网络的各种性质,如可分组性,并且给出网络的容错路由算法和自适应算法等。2.应用其它模型构造算法对GPN网络进行修正,使网络的平均路径长度及聚类系数等性质更进一步提高,同时对现实网络的其它统计性质进行研究,并讨论网络修正后在这些统计性质上的提高。