The Binary k-cube

A binary k-cube, often referred to as a hypercube, connects N = 2^k network nodes in the form of a cube constructed in k-dimensional space. The corners of this cube represent the nodes, and the edges represent the inter-nodal connections. More formally, if the nodes are numbered from 2^k - 1, nodes whose binary numbering differs in exactly one position have connections between them. Figure 1 shows how binary k-cubes are constructed for k in the range 0 to 4.

The binary k-cube therefore has k routing functions, C_i {0 ≤ i ≤ k - 1}, one routing within each dimension, defined thus

C_i(x) = {ε_i | I}(x)

Informally, for each dimension either an exchange permutation (ε_i) or an identity permutation (I) is applied to x in order to establish a route from any source to any destination node. A route from any source to any destination label can be found by starting at the source node and then comparing each bit in the source and destination labels in turn. If the bits are the same, then the identity permutation is applied to the source label and the route is not extended. If the bits are different, then the exchange permutation is applied to the source label, and the route extends along the link connecting the current node to a new node with a label equal to ε_i(current label). Such a route is illustrated in Figure 2. It is also apparent that since the maximum number of bits required to identify n processors uniquely is k = ⌈log₂n ⌉, the path length between an arbitrary pair of nodes is at most k.

It is immediately apparent that the binary k-cube has a very rich interconnection structure, with a total of k.2^{k - 1} bidirectional connections, and k communication links per node. One possible problem, which could limit the number of nodes in an k-cube network, is the number of communication links required per node, and hence the physical complexity of the whole network. In fact, it is the length of the interconnecting wires which poses the most serious problem for networks with large values of k. This can be shown by examining the rate of growth of the volume of the network.

The rate of growth of the inter-nodal distances in a binary k-cube depends on the length of one side of the machine. Since most machines are constructed physically in three-dimensional space, one side of a machine must have length which is O(N^1/3). Consequently, the time delay associated with the transmission of messages across the most significant dimension of the network will also be equal to O(N^1/3). If the system is synchronous then the clock speed of the machine must decrease in proportion to this increasing delay; alternatively, if each processor runs at O(1) instructions per second then the interval between each communication event must increase in proportion to the increased transmission delay. The net effect of increasing wire length is that the communication bandwidth per node decreases as the system becomes larger. This is essentially a problem of physical scalability.