Topological Properties of Hypercubes.

The n-dimensional hypercube or n-cube is a highly concurrent multiprocessor architecture consisting of 2 to the nth nodes each connected or n neighbors. Such machines have been advocated as ideal ensemble architectures because of their powerful interconnection. In this paper we examine the hypercube architecture from the graph theory point of view and we consider those features which make the hypercube interconnection so appealing. Among other things, we propose a theoretical characterization of the hypercube as a graph and show how to map various other architectures into a hypercube. The hypercube is a loosely coupled parallel multiprocessor based on a binary n-cube network and introduced under different names for example, cosmic cube, n-cube, binary n-cube, and boolean n-cube. A few machines based on the hypercube topology have been implemented by several groups, see 7 for references, and others are now being built. An n-cube parallel multiprocessor consists of 2 identical processors, each provided with its own sizable memory, and connected to n neighbors in the form of a binary n-cube network. There are essentially two broad classes of MIMD parallel multiprocessor processor designs with large number of processors. The first type of architecture consists of a large number of identical processors connected to one another according to some convenient pattern. In these machines there is no shared memory and no global synchronization. The second important class of parallel multiprocessors consists of those systems with N identical processors connected via a large switching network to N memories.