Please use this identifier to cite or link to this item:
Title: Embeddings, fault tolerance and communication strategies in k-ary n-cube interconnection networks
Authors: Ashir, Yaagoub A.
Award date: 1998
Presented at: University of Leicester
Abstract: 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.
Type: Thesis
Level: Doctoral
Qualification: PhD
Rights: Copyright © the author. All rights reserved.
Appears in Collections:Theses, Dept. of Mathematics
Leicester Theses

Files in This Item:
File Description SizeFormat 
U530825.pdf3.43 MBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.