Hypercube variant interconnection networks

Abstract

The attractive properties of the hypercube have made it a popular interconnection network topology for the design of multicomputers. Researchers have been modifying the hypercube topology in subtle ways to improve upon a few of its properties, thus leading to the evolution of a plethora of hypercube variants. The growth of hypercube variants has, however, been unsystematic, and ad hoc methods of deriving various hypercube variants have been proposed. In this thesis, we perform a systematic study of hypercube variants - in general, and a study of some issues in a new class of hypercube variants - in particular. We propose a taxonomy of hypercube variants to enable a systematic study of such variants. We also propose a new class of hypercube variants, called Hypercube-Like (HL) Networks. We give a general method of constructing HL-networks, derive the properties of these networks, and identify known hypercube variants belonging to this class. We also present in detail schemes for routing, broadcast, partitioning and reconfiguration in such networks, and discuss issues related to embedding of important algorithmic graphs. Finally, we present a new HL-network, derive some of its properties and give a routing strategy for this network. We believe that the work presented in this thesis would provide a sound basis for a systematic study of several issues in hypercube variants, and thus would be useful to designers of multicomputers.