| The performance of a parallel computing system heavily depends on the effectiveness of the underlying interconnection network. An interconnection network is usually represented by a graph, with nodes and edges corresponding to processors and communication links between processors, respectively. The graph embedding ability of an interconnection network (host graph) is an indicator of how efficiently parallel algorithms with regular task graphs (guest graphs) can be executed on this network. An ideal interconnection network (host graph) is supposed to possess excellent graph embedding ability.With the increasing size of parallel computing systems, it is unavoidable that there exist faulty processors and faulty communication links in such a system. Ideally, when components fail to work, the system should continue to function with reduced capacity. Hence, it is essential to evaluate the fault-tolerant ability of an interconnection network. In particular, the fault-tolerant graph embedding ability of an interconnection network is an important issue in parallel computing.Most of the previous works on graph embedding take cycle, path, tree, mesh, and torus as guest graphs, because these graphs represent the task graphs of a great number of parallel algorithms. In this thesis, we study the (fault-tolerant) embeddings of these popular guest graphs in some well-known interconnection networks. The major contributions are listed as follows.(1) Chapter 1 is dedicated to introduce the authors to the field of interconnection networks for parallel computing, and present the fundamental graph theoretic knowledge related to interconnection network and graph embedding.(2) Chapter 2 addresses the fault-tolerant hamiltonicity of honeycomb torus networks. The honeycomb torus networks are a family of promising interconnection networks for parallel computing. The node degree of honeycomb torus networks is three-quarter that of the traditional torus networks.①We find that the hexagonal honeycomb torus is fault-tolerant Hamiltonian, in the presence of two faulty nodes of distance 3 in any cycle of length 6.②Assume that m≥2 and d≥8 are of the same parity. The generalized honeycomb torus GHT ( m, 2 d ,d ) contains two faulty nodes ( w, y ) and ( x ,y ). We prove that if w < x, w + y is even and x + y is odd, then GHT ( m, 2 d ,d ) contains a fault-free Hamiltonian cycle. The results show that a cycle-structured parallel algorithm can be efficiently executed on a faulty honeycomb torus network.(3) Chapter 3 explores the (fault-tolerant) graph embedding abilities of the crossed cubes. Crossed cubes are a family of hypercube variants with potential application prospects. We obtain the following results:①For n≥4 ( n≥6, respectively), a family of two (four, respectively) node-disjoint 3-dimensional meshes of size 2×2×2n -3 ( 4×2×2n -5, respectively) can be embedded into an n-dimensional crossed cube with dilation 1;②For odd k, a 2 k×2k mesh of trees (containing 3×2 2 k - 2k+1 nodes) can be embedded into a ( 2 k + 2)-dimensional crossed cube (containing 2 2 k+ 2 nodes) with dilation 1 and expansion about 4/3;③For n≥5 and f≤2 n- 7, there exists a fault-free cycle of length at least 2 n - f - ( n- 5) in an n-dimensional crossed cube with f faulty nodes. The results show that 3-dimensional mesh, mesh of trees, and fault-tolenant cycle parallel algorithms can be efficiently executed on a crossed cube.(4) Chapter 4 considers the (fault-tolerant) embeddings of meshes and tori in the twisted cubes. Twisted cubes are another kind of attractive hypercube variants with potential application prospects. We get the following results:①For odd n≥3 and 0≤m≤( n- 3 )2, A family of 2m node-disjoint k-dimensional meshes of size 1 22 2 2t×t××tk can be embedded into the n-dimensional twisted cube with dilation 1, where∑ik = 1 t i= n -m and { }max 1≤i≤k t i≥n - 2 m- 1;②For odd n≥5, f≤n- 4 and l≤2n-2- f, a mesh (torus) of size 2×2l can be embedded into the n-dimensional twisted cube with f faulty nodes and/or faulty edges, where the dilation and congestion are both 1 (2). The results show that a (fault-tolerant) mesh-structured parallel algorithm can be efficiently executed on a twisted cube.(5) Chapter 5 deals with the fault-tolerant cycle and path embedding properties of 3-ary n-cubes. The k-ary n-cubes are important generalization of hypercubes, which has theoretical value and application prospects. We prove for n≥2 and f v + f e≤2 n- 2 ( f v + f e≤2 n- 3), there exists a fault-free cycle (a fault-free path between any two fault-free nodes, respectively) of any length ranging from 3 to 3n - fv (from 2 n - 1 to 3n - fv- 1, respectively) in the 3-ary n-cube with f v faulty nodes and f e faulty edges. The results show that a cycle/path-structured parallel algorithm can be efficiently executed on a faulty 3-ary n-cube.(6) Chapter 6 investigates the fault-tolerant hamiltonicity of generalized matching networks. The generalized matching network was proposed by Yang et. al., which includes the hypercube, variants of the hypercube, the star graph, and some other network structures. Assume that a generalized matching network G contains at least four building graphs, each of which is of cardinality q, f-fault Hamiltonian-connected and ( f + 1)-fault Hamiltonian. We prove that if f + 5≤q ( n-1), and the external neighbor nodes of any two nodes of distance 2 or less in the same building graph are not in the same building graph, then G is ( f + 1)-fault Hamiltonian-connected and ( f + 2)-fault Hamiltonian. The result has extensive application prospects.(7) Finally, we make a summary of our works as well as the outlook for further study in Chapter 7.
|
PDF Full Text Request