Skip to main content

Hypercube interconnection network

Short answer

An n-cube connects N=2ⁿ processors, each with n links to nodes whose addresses differ in one bit. Routing XORs source and destination; e.g., 000→101 via 000→001→101. Diameter is log₂N.

Discuss hypercube interconnection network with example.

A hypercube (binary n-cube) interconnection network connects N = 2ⁿ processors. Each processor is a node with its own local memory and has n direct links to other nodes. Two nodes are neighbours if their binary addresses differ in exactly one bit.

   3-cube (n = 3, 8 nodes)
       010 ------- 011
       /|          /|
     110 ------- 111|
      | 000 -----|-001
      |/         |/
     100 ------- 101

Each node has 3 links; for example 000 is linked to 001, 010 and 100.

Routing (message passing)

Source and destination addresses are XORed; the 1 bits show the dimensions along which the message must travel. Example: from 000 to 101: 000 XOR 101 = 101, so the message goes along dimension 0 and then dimension 2: 000 → 001 → 101 (2 hops). The maximum distance is n hops (the diameter = log₂N).

  • Advantages: short diameter (log₂N), many alternate paths, scalable, a large number of processors with moderate connections.
  • Disadvantages: each node needs n links and the number of links per node grows with N; wiring is complex. Examples: Intel iPSC and nCUBE.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computer Organization and Architecture chapter 8 questions →