【作者】 纪鸿飞；

【导师】 马英红；

【作者基本信息】 山东师范大学 ， 管理科学与工程， 2010， 硕士

【摘要】 随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一。各种拓扑结构的互连网络,如环、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网络进行修正,使网络的平均路径长度及聚类系数等性质更进一步提高,同时对现实网络的其它统计性质进行研究,并讨论网络修正后在这些统计性质上的提高。更多还原

【Abstract】 With the development of computer networks and computing 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 topology 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 embedded in. Thus, it becomes one of the most important and attractive network models. In this thesis, based on the Petersen graph, the routing algorithms and dynamic correction of GPN are studied. Several aspects of work mainly to be done are as follows.1. Elaborated the concept of parallel computer systems and classification, and then introduces parallel computer models, features, and common interconnection network topologies, including a linear array, ring, Mesh, Torus、tree topology, hypercube, Petersen graph and GP(n, k) graph.2. GPN network structure is proposed based on Petersen graph, and its properties are studied, proving that the GPN network has the nature of regularity and good scalability, but also has a ratio of RP (k), 2-D Torus shorter diameter and good parallelism. In addition, routing algorithm is given based on GPN network, proving that it has better communication efficiency.3. Modifies dynamically based on the GPN network, in order to obtain the network model in line with the actual network and further improve the nature of network. Rectifies the GPN network by the small world model constructed by WS and BA free model network construction algorithm GPN, simulates average path length and clustering coefficient of the network after correction, and checks the nature of the revised network. This article has studied some basic properties of the GPN network. However, there are still a lot of work to continue, including mainly:1. Further analyzes various natures of the GPN network, such as the nature of being grouped, and gives fault-tolerant routing algorithm and adaptive algorithm of the network.2. Modifies the GPN network applying construction algorithm of other models, so as to make the network average path length and clustering coefficient nature of the further increase, meanwhile, concerns about other statistical properties of real networks, and reflectes in the amendments and simulation of the network.更多还原