Worked examples — Network-on-Chip (NoC) topologies

This page is a drill. We take the five topologies from the parent note and squeeze every kind of question out of them: normal cases, tiny/degenerate networks, the extreme limits, a word problem, and an exam-twist. Before we start, one promise: no symbol appears here that we haven't already earned. Let's re-pin the three numbers we keep computing, in plain words.

Keep the number 128 Gb/s per link in your pocket — most examples reuse it.

---

The scenario matrix

Every question this topic throws is one of these cells. Each worked example below is tagged with the cell it fills.

#	Case class	What makes it tricky	Filled by
A	Normal mesh — rectangular, interior + edge nodes	mixing the two grid dimensions	Ex 1
B	Torus wraparound — does the shortcut help?	deciding wrap vs. no-wrap per axis	Ex 2
C	Hypercube routing — bit-flip path	reading routes off binary labels	Ex 3
D	Fat-tree bandwidth — link fattening	link width changes per level	Ex 4
E	Ring degenerate — worst bisection	tiny bisection, even vs odd $N$	Ex 5
F	Zero/degenerate input — $1\times N$ mesh, $N=1$, $N=2$ ring	formulas at their edge	Ex 6
G	Limiting behaviour — big-$N$ growth order	which topology wins as $N\to \infty$	Ex 7
H	Real-world word problem — pick a topology under a power budget	translating English → constraints	Ex 8
I	Exam twist — non-square torus, odd dimension floor	$\lfloor \cdot \rfloor$ traps	Ex 9

---

Example 1 — Normal mesh (cell A)

Figure s01, read it before the steps: a 3-row by 5-column grid of yellow node-dots joined by white links. A thick pink line traces the worst-case route from the bottom-left node $(0,0)$ rightwards four links then up two links to the top-right node $(2,4)$ — that is the diameter path. A vertical blue dotted line drops between two columns; it crosses one horizontal link in each of the 3 rows, so it severs 3 links — that is the bisection cut.

Steps.

1. Identify the two grid sizes: rows $N=3$, columns $M=5$. Why this step? The mesh diameter formula $D=(N-1)+(M-1)$ needs both dimensions separately, because you travel each axis independently — no diagonals exist on a grid.

2. Diameter: worst case is one corner to the opposite corner (the pink path in figure s01). $D=(3-1)+(5-1)=2+4=6\text{hops}.$ Why this step? You must walk 2 rows and 4 columns; each walked link is one hop, and there is no shortcut, so you sum them.

3. Bisection: split the 15 nodes as evenly as possible. Since $3\times 5=15$ is odd, a perfectly equal split is impossible, so "halves" means 7 nodes on one side and 8 on the other (differ by one — allowed by the definition above). The blue dotted vertical cut in figure s01 achieves such a split and severs the fewest links: one horizontal link per row, i.e. $\min (N,M)$ links. A horizontal cut instead would sever $\max (N,M)=5$ links — more, so we reject it. Why this step? Bisection width is the minimum balanced cut. The vertical cut severs $\min (3,5)=3$ links; that minimum is the true bottleneck. $B_b=\min (3,5)\cdot B_{\text{link}}=3\times 128=384\text{Gb/s}.$

Recall Verify Example 1

Units: hops are dimensionless (link counts) ✓. Bandwidth: $3\times 128\text{Gb/s}=384\text{Gb/s}$ ✓. Sanity: diameter 6 matches the $4\times 4$ mesh (also 6) because $2+4=3+3$ — same total travel. Good, a wider-but-shorter grid can tie a square one.

---

Example 2 — Torus wraparound (cell B)

Figure s02, read it before the steps: the same rectangular grid of yellow node-dots and white links, but now every row's leftmost and rightmost node are joined by a blue dashed wrap link, and every column's top and bottom node likewise — these dashed links are the shortcuts. A thick pink segment shows one such shortcut on a single row: node 0 jumps straight to node 5 in one wrap-hop instead of walking five links.

Steps.

1. Torus diameter formula: $D=\lfloor N/2\rfloor +\lfloor M/2\rfloor$ where $\lfloor x\rfloor$ means round down (the biggest whole number $\le x$). Why the floor? On a ring of $N$ nodes you never walk more than half the ring — past the halfway point it's shorter to go the other way. Half of $N$, rounded down, is that worst-case half-trip.

2. Plug in $N=4$, $M=6$: $D=\lfloor 4/2\rfloor +\lfloor 6/2\rfloor =2+3=5\text{hops}.$ Why this step? Each axis contributes its own half-ring worst case; the two axes are independent so we add.

3. Compare to the mesh (Ex-1 style): mesh $D=(4-1)+(6-1)=8$. So the wrap does help on both axes, cutting 8 → 5. Why this step? The blue dashed wrap links in figure s02 are the shortcuts; on a 6-long axis, node 0 reaches node 5 in one wrap-hop instead of five.

4. Bisection: split the $4\times 6=24$ nodes into two equal halves of 12 each (24 is even, so a perfectly equal split exists). A vertical cut now severs twice as many links as the mesh: one straight link per row and one wrap link per row cross the same vertical line, because the ring on each row is a loop and any cut of a loop passes through it twice. $B_b=2\cdot \min (N,M)\cdot B_{\text{link}}=2\times 4\times 128=1024\text{Gb/s}.$ Why this step? $\min (4,6)=4$ links straight, plus 4 wrap links, gives 8 links across the minimum balanced cut; doubling the links doubled the bandwidth.

Recall Verify Example 2

Diameter: $2+3=5$ ✓, and $5<8$ (mesh) ✓ so wrap helps. Bisection: $2\times 4\times 128=1024\text{Gb/s}$ ✓, exactly double a $4\times 6$ mesh's $4\times 128=512$.

---

Example 3 — Hypercube bit-flip routing (cell C)

Figure s03, read it before the steps: sixteen yellow node-dots, each labelled with its 4-bit binary code, drawn as two nested squares (a cube-of-cubes projection). Thin white links join every pair of nodes whose labels differ in exactly one bit. Thick pink arrows trace the routing path $9\to 8\to 10\to 14\to 6$: at each arrow exactly one bit of the label flips, and after four arrows we arrive at 6.

Steps.

1. Write both node numbers in 4-bit binary. Bit $j$ has "place value" $2^j$: bit 0 = 1s, bit 1 = 2s, bit 2 = 4s, bit 3 = 8s. $9=1001_2,6=0110_2.$ Why binary? A hypercube node is labelled by bits, and a link exists only between nodes that differ in exactly one bit. So the labels are the map.

2. Compare bit by bit. Symbol $\oplus$ ("XOR") outputs 1 where the two bits differ, 0 where they agree: $9\oplus 6=1001\oplus 0110=1111_2.$ Why XOR? It literally spotlights the disagreeing bits. Each 1 in the answer is one link we must cross to fix that bit.

3. Count the 1s (the Hamming distance): $1111$ has four 1s → 4 hops. Why this equals hop count? Each hop flips exactly one bit; you need to flip four bits; therefore four hops minimum, and any order works.

4. Walk the path flipping bits low-to-high (each step follows the pink arrows in figure s03): $9(1001)\stackrel{\text{flip }{2}^0}{\to }1000=8\stackrel{\text{flip }{2}^1}{\to }1010=10\stackrel{\text{flip }{2}^2}{\to }1110=14\stackrel{\text{flip }{2}^3}{\to }0110=6.$ Why this order? Order is free — the XOR guarantees all four flips land us on 6 regardless of sequence.

Recall Verify Example 3

$9\oplus 6=15=1111_2$, popcount $=4$ ✓. Final node after flipping all bits of 9: $9\oplus 15=6$ ✓. Path endpoints correct, 4 hops $=k={\log }_{2}16$ ✓.

---

Example 4 — Fat-tree link fattening (cell D)

Here $k$ is the tree's branching factor — the number of children each internal switch has. A binary fat-tree has $k=2$ (every switch fans out to two children). We use $k=2$ throughout this example.

Figure s04, read it before the steps: a binary tree drawn bottom-up. The bottom row has 8 yellow leaf-dots (the processing elements). Above them sit 4 switches, then 2, then a single root at top. The links get visibly thicker each level up: thin white leaf links (128 Gb/s), thicker blue level-1 links (256 Gb/s), thickest pink links into the root (512 Gb/s). The thickening is the "fat" in fat-tree.

Steps.

1. Levels of a binary ($k=2$) fat-tree with $N=8$ leaves: ${\log }_{2}8=3$ switch levels above the leaves. Link bandwidth doubles each level up. Why double? Half as many switches at each higher level must carry all the traffic below, so each higher link must be twice as fat to avoid choking.

2. Root link bandwidth. The rule from the parent note: root link $=\frac{N}{2}\cdot B_{\text{link}}$. $B_{\text{root}}=\frac{8}{2}\times 128=4\times 128=512\text{Gb/s}.$ Why $N/2$? The single top cut splits the tree into two halves of $N/2$ leaves each; the root must carry all cross-traffic between them.

3. Bisection bandwidth: cut the tree at its narrowest balanced point. For a fat-tree the tightest balanced cut is right at the root — it splits the 8 leaves into two groups of 4, and the only links crossing that cut are the links into the root. In a binary fat-tree the root is reached by 2 top links (one from each level-2 switch), each of width $\frac{N}{4}{B}_{\text{link}}=2\times 128=256$ Gb/s, so 4 leaf-equivalent links = 512 Gb/s cross the cut. $B_b=\frac{N}{2}\cdot B_{\text{link}}=4\times 128=512\text{Gb/s}.$ Why $\frac{N}{2}{B}_{\text{link}}$ and not $N{B}_{\text{link}}$? The minimum balanced cut severs only the links entering the root, which together carry $\frac{N}{2}$ leaf-links worth of bandwidth — not every leaf link. The fattening keeps this cut from being worse than the leaves' aggregate, but the bisection is set at the root cut, giving $\frac{N}{2}{B}_{\text{link}}=512$ Gb/s. The point of "fat" is that this root cut is not a bottleneck relative to a thin tree, not that it magically doubles the aggregate.

4. Diameter: leaf up to root, then down to another leaf: $D=2{\log }_{k}N=2{\log }_{2}8=2\times 3=6$ hops. Why $2{\log }_{k}N$? Up the tree is ${\log }_{k}N$ levels (that is why $k$, the branching factor, sits in the base of the log — more children per switch means fewer levels); back down is another ${\log }_{k}N$ levels; worst case does both. With $k=2$: $2{\log }_{2}8=6$.

Recall Verify Example 4

Root: $4\times 128=512$ ✓. Bisection: $\frac{N}{2}\times 128=4\times 128=512$ Gb/s ✓ (the minimum balanced cut is at the root — 4 leaf-links' worth, not 8). Diameter: $2\times 3=6$ ✓.

---

Example 5 — Ring, the bisection villain (cell E)

Figure s05, read it before the steps: eight yellow node-dots arranged evenly around a circle, numbered 0–7, joined by white links into one closed loop. A horizontal blue dotted line slices the loop; because the loop is a single closed curve, the line crosses it in exactly two places — severing 2 links. A thick pink arc traces the diameter route from node 0 to node 4 (4 hops, the far side of the ring).

Steps.

1. Diameter $=\lfloor N/2\rfloor =\lfloor 8/2\rfloor =4$ hops. Why? A ring is a single loop of nodes; the farthest node is diametrically opposite, half-way around either direction.

2. Bisection: no matter where you cut a ring into two equal halves of 4 nodes each, a straight line crosses exactly 2 links (the two arcs of the loop, as shown in figure s05). $B_b=2\times B_{\text{link}}=2\times 128=256\text{Gb/s}.$ Why only 2? A ring is one loop; any cut of a loop severs it in exactly two places. This is constant — it never grows with $N$.

3. "Terrible?" Compare per-node: 8 nodes sharing 256 Gb/s across the cut = 32 Gb/s effective per node, versus the mesh's much larger bisection. As $N$ grows the ring's bisection stays 256 while traffic grows — the bottleneck worsens. Why this matters: bisection bandwidth is the ceiling for balanced all-to-all traffic; a fixed ceiling with rising demand is the definition of a bottleneck (Latency and Throughput Trade-offs).

Recall Verify Example 5

Diameter $\lfloor 8/2\rfloor =4$ ✓. Bisection $2\times 128=256\text{Gb/s}$ ✓, independent of $N$.

---

Example 6 — Degenerate & zero inputs (cell F)

Steps.

1. (a) $1\times 5$ mesh. $N=1$ row, $M=5$ columns. $D=(1-1)+(5-1)=0+4=4$. Why the 0? With one row there's nothing to travel vertically, so that term vanishes — the mesh has collapsed into a line (a ring without the wrap). The formula degrades gracefully.

2. (b) 1-node network. Diameter $=0$ (a node is 0 hops from itself). Bisection: you cannot split one node into two non-empty groups, so bisection is undefined / effectively 0. Why 0 hops? Diameter is the max distance between two distinct nodes; with one node there is no pair, so the max over an empty set is 0 by convention. This is the true "zero input."

3. (c) 2-node ring. Diameter $=\lfloor 2/2\rfloor =1$: the two nodes are 1 hop apart. Commit to one convention: we model a ring as an undirected cycle graph, where between any two adjacent nodes there is exactly one link. At $N=2$ the "cycle" degenerates — graph theory would place two parallel edges between the two nodes, but the standard NoC convention is a single physical link, so we use one link. Applying the ring bisection formula $B_b=2\cdot B_{\text{link}}$ blindly would claim 2 links cross the cut — but there is only one link in the degenerate 2-node ring, so the formula overcounts here. The honest value from the definition (minimum links to split 2 nodes into 1+1) is 1 link: $B_b^{(N=2)}=1\times B_{\text{link}}=128\text{Gb/s}.$ Why the formula breaks: the "$2$" in $2\cdot B_{\text{link}}$ counts the two arcs of a genuine loop, but a 2-node ring has no genuine loop (a cycle needs $\ge 3$ nodes), so only one link exists to cut. Edge cases are exactly where blind formula-plugging fails.

Recall Verify Example 6

(a) $0+4=4$ ✓. (b) diameter $0$ ✓. (c) diameter $\lfloor 2/2\rfloor =1$ ✓; bisection committed to $1\times 128=128$ Gb/s (single-link convention), not the formula's spurious 256 ✓.

---

Example 7 — Limiting behaviour as $N\to \infty$ (cell G)

Figure s06, read it before the steps: a plot of diameter (vertical axis, hops) against node count $N$ (horizontal axis, drawn on a log scale so doublings are evenly spaced). Three curves rise: a steep pink line labelled "ring $O(N)$" that shoots up to 512, a gentler blue curve labelled "mesh $O(\sqrt{N})$" reaching 62, and a nearly-flat yellow curve labelled "hypercube $O(\log N)$" barely reaching 10. The visual gap between the curves is the scalability story.

Steps.

1. Square mesh: $32\times 32$ (since $32^2=1024$). $D=(32-1)+(32-1)=62$. Why $\sqrt{N}$? A square grid side is $\sqrt{N}$, and diameter $\approx 2\sqrt{N}$ — it grows like $O(\sqrt{N})$.

2. Hypercube: need $2^k=1024\Rightarrow k=10$. $D=k=10$. Why $\log$? Each dimension doubles the node count, so the number of dimensions (and hops) is ${\log }_{2}N$ — the slowest-growing of the three.

3. Ring: $D=\lfloor 1024/2\rfloor =512$. Why $O(N)$? A ring's worst case is half the ring, so it grows linearly — the fastest-growing, by far the worst.

4. Rank (fastest→slowest growth): Ring $O(N)$ → Mesh $O(\sqrt{N})$ → Hypercube $O(\log N)$. Why this ordering — the visual reasoning behind it: watch what happens to each formula when you double $N$ (one step right on figure s06's log axis).

   • Ring $D=N/2$: doubling $N$ doubles $D$ — the pink line's height doubles every step, so it rockets upward. Linear growth means the diameter is a fixed fraction of the whole network, so it never stops climbing.
   • Mesh $D\approx 2\sqrt{N}$: doubling $N$ multiplies $D$ by only $\sqrt{2}\approx 1.41$ — the blue curve rises, but each doubling adds a smaller jump than the ring. The square-root cushions the growth because widening a square grid by side $\sqrt{N}$ spreads $N$ nodes over two dimensions, not one.
   • Hypercube $D={\log }_{2}N$: doubling $N$ adds just +1 hop (one more dimension = one more bit) — the yellow curve is nearly flat. Adding a whole dimension only costs a single extra flip, so diameter grows the slowest possible way. The numbers confirm the ordering visually and arithmetically: $512\gg 62\gg 10$. Why this matters: for thousand-core chips only the log-class topologies keep latency sane — at the cost of high router degree (System-on-Chip (SoC) Design).

Recall Verify Example 7

Mesh $2\times 31=62$ ✓; hypercube ${\log }_{2}1024=10$ ✓; ring $512$ ✓. Ordering $512>62>10$ ✓. Doubling test: ring $\times 2$, mesh $\times \sqrt{2}$, hypercube $+1$ ✓.

---

Example 8 — Real-world word problem (cell H)

Steps.

1. Tabulate degree and diameter for each candidate at $N=16$:

   • Ring: degree 2, $D=\lfloor 16/2\rfloor =8$.
   • Mesh $4\times 4$: degree 4 (interior), $D=(4-1)+(4-1)=6$.
   • Hypercube $k=4$: degree 4, $D=4$. Why these numbers? Degree drives router power (Power Management in SoCs); diameter drives worst-case latency.

2. Apply the latency constraint "$\le 8$ hops": ring $8\le 8$ ✓ (just barely), mesh $6\le 8$ ✓, hypercube $4\le 8$ ✓. All pass. Why check this first? A design that violates a hard constraint is disqualified regardless of power.

3. Apply the power priority (minimize degree): ring wins with degree 2, half the ports of mesh/hypercube. Why degree, not diameter, decides? The problem says power is the strict budget and traffic is light & local — so bisection bandwidth (the ring's weakness) barely matters, while low port count directly saves power.

4. Choice: Ring. It meets the 8-hop ceiling exactly, has minimal degree 2, lowest wiring/power, and the light local traffic never stresses its poor bisection. Why not mesh? Mesh's better latency (6 vs 8) isn't needed here, and its degree-4 routers burn more power — a bad trade under this budget.

Recall Verify Example 8

Ring diameter $\lfloor 16/2\rfloor =8=$ the limit ✓ (satisfies $\le 8$). Degrees: ring 2 $<$ mesh 4 $=$ hypercube 4 ✓. Ring is the min-degree feasible option ✓.

---

Example 9 — Exam twist: non-square torus with odd dimension (cell I)

Steps.

1. Correct diameter: $D=\lfloor 5/2\rfloor +\lfloor 3/2\rfloor =2+1=3$ hops. Why floor each term separately? On an odd-length ring of 5, the farthest node is 2 hops away, not 2.5 — you can't take half a hop. Rounding the sum (the student's $4$) double-counts fractional hops that don't exist.

2. Spot the student's error: they computed $2.5+1.5=4$. The truth floors before adding: $2+1=3$. The mistake inflates the diameter by 1. Why does order matter? $\lfloor a\rfloor +\lfloor b\rfloor \le \lfloor a+b\rfloor$; flooring first is the physically correct per-axis half-ring, and it's smaller.

3. Bisection: $B_b=2\cdot \min (5,3)\cdot B_{\text{link}}=2\times 3\times 128=768\text{Gb/s}$. Why $\min$ and $\times 2$? Cut across the short axis (3 rows) to sever the fewest links, then double for the torus wrap. $\min (5,3)=3$.

Recall Verify Example 9

$\lfloor 5/2\rfloor +\lfloor 3/2\rfloor =2+1=3$ ✓ (student's 4 is wrong). Bisection $2\times 3\times 128=768\text{Gb/s}$ ✓.

---

Recall Self-test

A $6\times 6$ mesh diameter? ::: $(6-1)+(6-1)=10$ hops. A $6\times 6$ torus diameter? ::: $\lfloor 6/2\rfloor +\lfloor 6/2\rfloor =3+3=6$ hops. Hops from hypercube node 0 to node 15 (in a 4-cube)? ::: $0\oplus 15=1111$, four 1s → 4 hops. Why does a ring's bisection never grow? ::: any cut of a single loop severs exactly 2 links.

See also: Routing Algorithms (how packets actually pick these paths), Cache Coherence Protocols (what traffic rides the network), Latency and Throughput Trade-offs (why diameter vs. bisection is a design tension).