Hypercube Interconnection Structures
- The hypercube or binary n cube multiprocessor structure is loosely coupled system composed of N=2n processors, interconnected in the n-dimensional binary cube.
- Each processor forms a node of the cube.
- Each processor has direct communication paths to other neighbor processors.
- Moreover, These paths correspond to the edges of the cube.
- There are 2n distinct n-bit binary addresses that can be assigned to the processors.
- Each processor address differs from that of each of its n neighbors by exactly one-bit position.
- Also, The figure shows the hypercube structure for n = 1, 2, and 3.
- A one-cube structure has n = 1 and 2n = 2. It contains two processors interconnected by a single path.
- A two-cube structure has 21 = 2 and 2n = 4. It contains four nodes interconnected as a square.
Figure: Hypercube structures for n = 1,2,3
- A three-cube structure has eight nodes interconnected as a cube.
- An n-cube structure has 2n nodes with a processor residing in each node.
- Each node is assigned a binary address in such a way that the addresses of two neighbors differ in exactly one-bit position.
- Also, For example, the three neighbors of the node with address 100 in a three-cube structure are 000,110, and 101.
- Each of these binary numbers differs from address 100 by one-bit value.
- For example, in a three-cube structure, node 000 can communicate directly with node 001.
- So, It must cross at least two links to communicate with 011 (from 000 to 001 to 011 or from 000 to 010 to 011).
- It is necessary to go through at least three links to communicate from node 000 to node 111.
- A routing procedure can develop by computing the exclusive-OR of the source node address with the destination node address.
- Also, For example, in a three-cube structure, a message at 010 going to 001 produces an exclusive-OR of the two addresses equal to 011.
- Moreover, The message can send along the second axis to 000 and then through the third axis to 001.