---
title: "Hypercube interconnection network"
subject: "Computer Organization and Architecture"
chapter: 8
key: "semester_5/computer_organization_and_architecture:hypercube"
source: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/hypercube
site: BCT Engineering
---

# Hypercube interconnection network

Computer Organization and Architecture · Chapter 8: Multiprocessors

- Asked in: 2076 Chaitra, 4 marks
- Video: [Hypercube Networks | Parallel Algorithm Tutorial](https://www.youtube.com/watch?v=HkJ6zoFjvpI) — Last Minute Study
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_5/computer_organization_and_architecture/hypercube
- Whole chapter: https://www.bctengineer.com/md/semester_5/computer_organization_and_architecture/chapter-8

## Question

Discuss hypercube interconnection network with example.

## 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.

## Answer

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.

```text
   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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How many processors does an n-cube have?
   A. 2n
   B. 2^n
   C. n^2
   D. n
   Answer: B. N = 2^n nodes, each with n links. (Key point: Number of nodes)

2. When are two hypercube nodes neighbours?
   A. Addresses differ in all bits
   B. Addresses are equal
   C. They are adjacent in memory
   D. Addresses differ in exactly one bit
   Answer: D. Neighbours differ by one address bit. (Key point: Neighbours)

3. From 000 to 101, which dimensions does the message travel?
   A. Dimension 0 and dimension 2
   B. All three
   C. Dimension 1 only
   D. None
   Answer: A. 000 XOR 101 = 101, the 1 bits are dimensions 0 and 2. (Key point: Routing)

4. What is the diameter of a hypercube with N nodes?
   A. N/2
   B. N
   C. log2 N
   D. 1
   Answer: C. Maximum distance is n = log2 N hops. (Key point: Diameter)

## Related in other subjects

- [Role of interconnection and reactive power control](https://www.bctengineer.com/question.md?key=semester_5%2Fpower_system_analysis_ii%3Ainterconnection-reactive-control) — Power System Analysis II, chapter 1