Network-on-Chip (NoC) topologies: Exercises — Hardware deep dive

This page is a self-test ladder. Each exercise names its level (L1 → L5). Try it first, then open the collapsible solution. Every formula you need was built in the parent topic — but we re-state each one the moment we use it, so you never chase a symbol.

Reference numbers used throughout: a link carries $w = 64$ bits per cycle at frequency $f = 2 GHz$ , so one link's bandwidth is $B_{link} = 64 bits \times 2 \times 1 0^{9} Hz = 128 \times 1 0^{9} bits/s = 128 Gb/s .$

Figure — Network-on-Chip (NoC) topologies

Level 1 — Recognition

Recall Solution 1.1

WHAT it is: a grid of routers with only up/down/left/right links and no edge-wrapping is a Mesh (2D grid). Degree = number of links leaving a router. Look at figure s01.

Centre router has all four neighbours present → degree $= 4$ .
Corner router touches only two neighbours → degree $= 2$ . Answer: Mesh; centre degree $4$ , corner degree $2$ .

Recall Solution 1.2

A closed loop where each router links only to its two loop-neighbours is a Ring. Every node has exactly $2$ links, so degree $= 2$ uniformly. Answer: Ring.

Level 2 — Application

Recall Solution 2.1

Here $N = M = 4$ . $D = (4 - 1) + (4 - 1) = 3 + 3 = 6 hops .$ Answer: $D = 6$ hops. (See figure s02: the red staircase from bottom-left to top-right is 6 links long.)

Recall Solution 2.2

Formula: $B_{b} = min (N, M) \cdot B_{link}$ . A vertical cut through a $4 \times 4$ mesh severs one link per row = $4$ links. $B_{b} = 4 \times 128 Gb/s = 512 Gb/s .$ Answer: $512 Gb/s$ .

Recall Solution 2.3

Diameter: worst case is the node directly "across" the loop. $D = ⌊ N /2 ⌋ = ⌊ 8/2 ⌋ = 4$ hops. Bisection: cut the loop anywhere and you always sever exactly $2$ links (the loop has two arcs), so $B_{b} = 2 \times 128 = 256 Gb/s .$ Answer: $D = 4$ hops, $B_{b} = 256 Gb/s$ — the tiny bisection is why rings choke under heavy traffic (see Latency and Throughput Trade-offs).

Level 3 — Analysis

Recall Solution 3.1

Mesh: $D = (8 - 1) + (8 - 1) = 14$ hops. Torus: wraparound means the farthest you must travel in each dimension is halfway around, $⌊ 8/2 ⌋ = 4$ . So $D = ⌊ 8/2 ⌋ + ⌊ 8/2 ⌋ = 4 + 4 = 8 hops .$ Reduction: $\frac{14 - 8}{14} = \frac{6}{14} = 0.4286 = 42.9%$ . Answer: Mesh $14$ , Torus $8$ hops — a $\approx 43%$ drop. The wraparound links are the shortcuts.

Recall Solution 3.2

$\oplus$ is XOR = flip the chosen bit. Node $10 = 101 0_{2}$ .

$10 \oplus 2^{0} = 10 \oplus 1 = 101 1_{2} = 11$
$10 \oplus 2^{1} = 10 \oplus 2 = 100 0_{2} = 8$
$10 \oplus 2^{2} = 10 \oplus 4 = 111 0_{2} = 14$
$10 \oplus 2^{3} = 10 \oplus 8 = 001 0_{2} = 2$ Neighbours: ${11, 8, 14, 2}$ — exactly $k = 4$ of them (degree $= k$ ). Diameter: any two nodes differ in at most $k$ bit positions, and each hop fixes one bit, so $D = k = lo g_{2} N = lo g_{2} 16 = 4$ hops. Answer: neighbours ${2, 8, 11, 14}$ ; $D = 4$ .

Level 4 — Synthesis

Recall Solution 4.1

Compute each (all with $N = 16$ ):

Topology	Diameter	Degree
$4 \times 4$ Mesh	$(4 - 1) + (4 - 1) = 6$	$4$ (interior)
$4 \times 4$ Torus	$⌊ 4/2 ⌋ + ⌊ 4/2 ⌋ = 4$	$4$ (uniform)
4D Hypercube	$lo g_{2} 16 = 4$	$4$
16-node Ring	$⌊ 16/2 ⌋ = 8$	$2$
Ranking (best→worst diameter): Torus $=$ Hypercube $(4)$ < Mesh $(6)$ < Ring $(8)$ .
Winner on diameter: tie at $4$ between Torus and Hypercube. Here both also have degree $4$ , so at $N = 16$ the degree cost is identical — the deciding factors become physical layout (torus needs long wraparound wires; hypercube is non-planar) and bisection bandwidth. See System-on-Chip (SoC) Design for the layout constraint.
Answer: Torus and Hypercube tie at diameter $4$ , both degree $4$ ; Ring is worst at $8$ .

Recall Solution 4.2

Hypercube degree $= lo g_{2} N$ . Solve $lo g_{2} N > 4 \Rightarrow N > 16$ . The next power of two is $N = 32$ , where degree $= lo g_{2} 32 = 5$ . Answer: at $N = 32$ (degree $5 > 4$ ). Why it matters: each extra port adds a crossbar row/column, buffers, and arbitration logic, so router area/power roughly scales with degree. Beyond $N = 16$ the hypercube's router grows while the torus's stays fixed at $4$ — a real power and area penalty even though the hypercube's diameter is still tiny.

Level 5 — Mastery

Recall Solution 5.1

$N = 16$ , $B_{link} = 128 Gb/s$ , binary tree so $k = 2$ . (a) Root link $= \frac{16 \times 128}{2} = 1024 Gb/s$ — $8 \times$ a leaf link, which is exactly why it's called a fat tree. (b) $B_{b} = 16 \times 128 = 2048 Gb/s$ — no bottleneck at any cut. (c) $D = 2 lo g_{2} 16 = 2 \times 4 = 8$ hops (leaf up to root, root down to leaf). (d) Mesh bisection was $512 Gb/s$ ; fat-tree is $2048 Gb/s$ = $4 \times$ higher. Price paid: the huge $1024 Gb/s$ root switch is large and power-hungry, and the $8$ -hop diameter (vs mesh's $6$ ) means higher latency for nearby nodes. Bandwidth-critical designs (datacenter-like traffic) accept this; latency-critical ones may not.

Recall Solution 5.2

All-to-all traffic stresses bisection bandwidth (half the cores flood the other half). Power budget forbidding long wires penalises Torus (wraparound wires span the chip) and Hypercube (non-planar long links) and the Fat-Tree root wires. Bisection numbers at $N = 16$ ( $B_{link} = 128$ Gb/s):

Topology	Bisection BW	Long wires?
Ring	$256$ Gb/s	no
Mesh	$512$ Gb/s	no (all links short/local)
Torus	$2 \times 4 \times 128 = 1024$ Gb/s	yes (wraparound)
Hypercube	$(16/2) \times 128 = 1024$ Gb/s	yes (non-planar)
Fat-Tree	$2048$ Gb/s	yes (fat root wires)
Reasoning: the highest-bisection options (Fat-Tree, Torus, Hypercube) all violate the "no long wires" constraint. Among the wire-friendly, planar options (Ring, Mesh), the Mesh doubles the ring's bisection ( $512$ vs $256$ Gb/s) with only short, local links.
Winner: Mesh — best bisection among the physically-allowed, short-wire topologies, and its regular grid maps cleanly onto a 2D floorplan. If the power rule were relaxed, the Torus (same diameter as hypercube, uniform degree $4$ , double the mesh bisection) would take over.