Embeddings, fault tolerance and communication strategies in k-ary n-cube interconnection networks

The k-ary n-cube interconnection network Qkn, for k 3 and n 2, is n-dimensional network with k processors in each dimension. A k-ary n-cube parallel computer consists of kn identical processors, each provided with its own sizeable memory and interconnected with 2n other processors. The k-ary n-cube has some attractive features like symmetry, high level of concurrency and efficiency, regularity and high potential for the parallel execution of various algorithms. It can efficiently simulate other network topologies. The k-ary n-cube has a smaller degree than that of its equivalent hypercube (the one with at least as many nodes) and it has a smaller diameter than its equivalent mesh of processors.;In this thesis, we review some topological properties of the k-ary n-cube Qkn and show how a Hamiltonian cycle can be embedded in Qkn using the Gray codes strategy. We also completely classify when a Qkn contains a cycle of some given length.;The problem of embedding a large cycle in a Qkn with both faulty nodes and faulty links is considered. We describe a technique for embedding a large cycle in a k-ary n-cube Qkn with at most n faults and show how this result can be extended to obtain embeddings of meshes and tori in such a faulty k-ary n-cube.;Embeddings of Hamiltonian cycles in faulty k-ary n-cubes is also studied. We develop a technique for embedding a Hamiltonian cycle in a k-ary n-cube with at most 4n-5 faulty links where every node is incident with at least two healthy links. Our result is optimal as there exist k-ary n-cubes with 4n - 4 faults (and where every node is incident with at least two healthy links) not containing a Hamiltonian cycle. We show that the same technique can be easily applied to the hypercube. We also show that the general problem of deciding whether a faulty k-ary n-cube contains a Hamiltonian cycle is NP-complete, for all (fixed) k 3.