Simulation of the Crossed Cubes by the Shuffle Exchange Network

The structure of the interconnection network can be the deciding and limiting factor in performance and cost of parallel computers. Hypercube is one of the most popular interconnection networks. The symmetry, logarithmic diameter, regularity, fault-tolerance, high connectivity, simple routing, and reconfigurability of the hypercube make it a very attractive network for parallel computers. Extensive research has been done to study and improve its properties. Many interconnection networks like crossed cube, cube connected cycles, shuffle exchange graph etc. were proposed to improve one or more properties of hypercube. For example crossed cube, proposed to improve on the diameter of the hypercube and the diameter of the crossed cube is approximately half that of the hypercube [special characters omitted]. The hypercube and crossed cube both possesses a major drawback which is their variable degree i.e., degree of the node increases as the network grows in size. As an alternative to the hypercube, the shuffle exchange network is recently receiving much attention. The shuffle exchange network not only provides a logarithmic diameter, fault-tolerance, and simple routing but it also possess a constant node degree '3' which is independent of the network size. The shuffle-exchange graph is a Cayley graph and is especially attractive for parallel processing. The attractive properties of the crossed cube and the shuffle exchange graph have drawn my attention towards this thesis. In this thesis, we investigate the genus of the shuffle exchange graph and prove that the crossed cube of dimension 'n' can be simulated by the shuffle exchange graph with dilation '4'. In order to achieve constant dilation, we only consider normal algorithms.