Combinatorial Investigation Of Several Class Of Interconnection Networks

The first step in the designing and implementing large scale parallel computing system is to construct interconnection networks topological structure. Interconnection networks is also foundation of implementing all kinds of protocol and it plays an important role in the performance , system dependability, and cost of the networks. Interconnection networks are often modeled as a graph with vertex representing processor and an edge representing communication channel between processors. So the study of topological structure of interconnection networks is turned to the study structure of graph. And the study of fault-tolerant of network can transform to the study the parameter of graph. The parameters to evaluate the performance of interconnection networksare as follows:(1)Hardware complexity. It can be evaluated by the degree of vertex of topological graph.(2)Commuication expenses. It can be evaluated the diameter or average distance of topological graph.(3)Expandability. It can be come down to the problem of embedability of some special structures.(4)Fault tolerance.It can be evaluated by the connectivity, edge-connectivity, fault-tolerant diameter, width diameter of graph.The widely studied topological structure are mesh-connected networks, tree networks, hypercube networks and star networks. We mainly consider the fault-tolerant properties of these networks in this thesis. Our research concentrate on the following:First, We survey the fault tolerant parameters of topological structure of interconnection networks such as communication delay, fault-tolarant diameter, width diamater and connectivity.based on this, we propose some problem that worth further studying.Then, we studied the variation of hypercube-----varietal hypercube. Thevarietal hypercube are widely studied, many parameters are determined, including connectivity > recursion >. embed ring and meslK diameter > routing algorithm > broadcast algorithm. In this thesis, we studied the fault-tolerant diameter and width diameter of varietal hypercube and proved that the fault tolerant diameter and width diameter is equal to diameter plus 1 or 2.' Finally, we constructed a new type of larger scale topological structure of networks with the lifts of graphs. We prove that the vertex number and edge number of the lift graph of hypercube times that of hypercube,- but its' diameter is less than 5. This1provided a new way to construct interconnection networks with good performance .