hypercube

A cube of more than three dimensions. A single (2^0 = 1)

point (or "node") can be considered as a zero dimensional

cube, two (2^1) nodes joined by a line (or "edge") are a one

dimensional cube, four (2^2) nodes arranged in a square are a

two dimensional cube and eight (2^3) nodes are an ordinary

three dimensional cube. Continuing this geometric

progression, the first hypercube has 2^4 = 16 nodes and is a

four dimensional shape (a "four-cube") and an N dimensional

cube has 2^N nodes (an "N-cube"). To make an N+1 dimensional

cube, take two N dimensional cubes and join each node on one

cube to the corresponding node on the other. A four-cube can

be visualised as a three-cube with a smaller three-cube

centred inside it with edges radiating diagonally out (in the

fourth dimension) from each node on the inner cube to the

corresponding node on the outer cube.

Each node in an N dimensional cube is directly connected to N

other nodes. We can identify each node by a set of N

Cartesian coordinates where each coordinate is either zero

or one. Two node will be directly connected if they differ in

only one coordinate.

The simple, regular geometrical structure and the close

relationship between the coordinate system and binary numbers

make the hypercube an appropriate topology for a parallel

computer interconnection network. The fact that the number of

directly connected, "nearest neighbour", nodes increases with

the total size of the network is also highly desirable for a

parallel computer.

(1994-11-17)