Research On Conditional Connectivity And Fault-Tolerant Routing Of Generalized Hypercubes

With the rapid development of information society,high performance computing has been the third pillar of scientific research following theoretical sciences and experimental sciences.Speaking strategically,high performance computing technology is a manifestation of a country's comprehensive national strength,and plays an indispensable role in the field of national defense security,high-techology development and national economic construction.In the research of high performance computing,improving operation efficiency has al-ways been the primary goal of its development.Parallel computing is an effective means to improve the computing speed of the systems.In a parallel computing system,the connection between processing units can be viewed as a network,which is named as the interconnection network.Interconnection network can be abstracted 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 interconnec-tion network,and E?G?is the set of edges in G,representing the set of links between various processors.With the increasing demand of computing,the number of processors is gradually in-creasing,which leads to an increase in the probability of processor failure.Whether the network with faulty processors can continue to operate normally or not depends on the fault-tolerance of this network,which is a key index to measure the performance of the intercon-nection network.And connectivity is an important parameter to measure the fault-tolerance of a network.However,restricted connectivity and extra connectivity which are two kinds of conditional connectivity can more accurately measure the fault-tolerance than traditional connectivity in actual situations.At the same time,how to perform routing between pro-cessors in a network which remains connected after deleting faulty processors is a problem which needs to be considered when studying the fault-tolerance of this network.Generalized hypercubes is a common interconnection network in multiprocessor sys-tem,which has many excellent properties such as regularity,symmetry,good embeddability and extensibility.At present,generalized hypercubes have been used in the structure of many large multi-processor parallel systems,data center networks and optical fiber commu-nication networks.In this paper,the restricted connectivity and extra connectivity of the r-dimensional generalized hypercubes G(m_r,m_r-1,...,m₁)are studied,and two fault-tolerant routing algo-rithms are given.The major contributions are listed as follows.1.Based on the definition of restricted connectivity,this paper gives the 1-restricted connectivity of G(m_r,m_r-1,...,m₁),and the detailed proof of this result is given.At the same time,this paper presents a fault-tolerant routing algorithm in G(m_r,m_r-1,...,m₁)with faulty vertices under the conditions that the number of faulty vertices is less than 1-restricted con-nectivity and each fault-free vertex has at least one fault-free neighbor.The time complexity of this algorithm is O(?(G(m_r,m_r-1,...,m₁))³),where?(G(m_r,m_r-1,...,m₁))represents the restricted-connectivity of G(m_r,m_r-1,...,m₁).2.Based on the definition of external connectivity,this paper presents the 1-extra con-nectivity and 2-extra connectivity of G(m_r,m_r-1,...,m₁),and the detailed proofs are given.At the same time,this paper presents a fault-tolerant routing algorithm in G(m_r,m_r-1,...,m₁)with fault vertices under the conditions that the number of faulty vertices is less than2-extra connectivity and each component left has at least three fault-free vertices.And the time complexity of the algorithm is O(?(G(m_r,m_r-1,...,m₁))³).