Communication Algorithms And Dynamic Correction Of GPN Graph

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.