Research On Path Cover And Fault-tolerant Path Problems In Meshes And Tori

With the rapid development of information society,high performance computing has become the third pillar after theoretical sciences and experimental sciences.From a strategic perspective,high performance computing technology is the performance of a country's com-prehensive national strength and has an indispensable position in all aspects of social life.The performance of a high performance computer is largely determined by the connection between the processors within the system(interconnection network).The interconnection network can be expressed as a simple graph G=(V(G),E(G)),where V(G)is the set of vertices in G,representing the set of processors in the interconnection network,and E(G)is the set of edges in G,representing the set of links between the various processors.The disjoint path cover problem of interconnection network not only plays a very sig-nificant role in code optimization and software testing,but also has been widely applied to the database design,the topology control of wireless sensor networks and the design of VLSI etc.In the interconnection network,the disjoint path cover problem can not only improve the efficiency of broadcast communications,but also plays an important role in im-proving the efficiency of data collection and distribution.For example,when using disjoint path cover for broadcast communication on mesh network,we can not only speed up the communication,but also only need to access each processor once.With the continuous expansion of the interconnection network,the number of proces-sors in the network is increasing.When a large multiprocessor parallel computer system is put into use,failure is unavoidable.Therefore,the research on fault tolerance of intercon-nection networks has become an important research topic in recent years.Hamiltonian properties play an important role in information communication,such as hamiltonian path can be used in a class of communication systems to reduce congestion and deadlock.In addition,hamiltonian properties can also be used in the fault diagnosis of the interconnection network,by reducing the number of fault diagnosis to improve the efficiency of fault diagnosis.However,due to the different structure of the network,not any arbitrary network has a hamiltonian path.So we look for the longest path in the network.Mesh network is one of the earlier studied topologies,and is still one of the most important and most attractive network models.It has the advantages of simple structure,good scalability and easy to design VLSI circuits.Torus network is a symmetric direct interconnection network topology.It has many excellent characteristics,such as the rules of symmetry,path diversity and good expansibility,so it is widely used in many commercial systems.In this paper,based on traditional spanning connectivity and spanning laceability,we proposed strong spanning connectivity and strong spanning laceability,then give the strong spanning laceability of two-dimensional mesh.We also discuss the length of the longest path in 4~*-container of two vertices in different partite of two-dimensional torus.Inspired by the structure connectivity and substructure connectivity,we discuss the longest fault-free path between any two fault-free vertices in the case of the failure of a large area vertices and the failure of a vertex and its neighbors on torus,and the longest fault-free path between any two fault-free vertices in the case of the failure of a large area vertices on mesh.We also give the fault-tolerant longest fault-free path routing algorithm on torus in the case of the failure of a large area vertices and the failure of a vertex and its neighbors.The results show that there is a good performance in time-consuming and the length of path.