Embeddings, fault tolerance and communication strategies in K-ary n-cube Interconnection networks

Abstract

Abstract : The k-ary n-cube interconnection network Qk, 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 k" identical processors, each provided with its own sizable 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 Q and show how a Hamiltonian cycle can be embedded in Qh using the Gray codes strategy. We also completely classify when a Q% contains a cycle of some given length. The problem of embedding a large cycle in a Q% with both faulty nodes and faulty links is considered. We describe a technique for embed- ding a large cycle in a k-ary n-cube Q 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 stud- ied. 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. Several communication algorithms for the k-ary n-cube network are considered; in particular, we develop and analyse routing, single-node broadcasting, multi-node broadcasting, single-node scattering, and total exchange algorithms. we also show how Hamiltonian cycles of the k-ary n-cube can be exploited to develop fault-tolerant multi-node broadcast and single-node scatter algorithms for the one-port I/O k-ary n-cube model, and how link-disjoint Hamiltonian cycles of the k-ary n-cube can be used to develop multi-node broadcast and single-node scatter algo- rithms for the multi-port I/O k-ary n-cube model.