Network-on-Chip (NoC) topologies: Visual walkthrough

This is the picture-story behind everything in the parent note, Network-on-Chip (NoC) topologies. Read it top to bottom; every symbol is earned before use.

Step 1 — What is a "node", a "link", and a "hop"?

WHAT. A node is one router with a core attached — draw it as a dot. A link is a wire between two dots — draw it as a line. A hop is one journey along one link. If a packet crosses 3 links to reach its destination, that trip is 3 hops.

WHY. Before we can talk about "how far" or "how much", we need the smallest countable pieces. Everything else on this page is counting dots, lines, and hops. That is the whole trick.

PICTURE. Two dots joined by one line = one hop. Add a third dot and the packet now needs 2 hops to reach the far end. The number of hops is literally the number of lines you walk over.

Step 2 — Lay out the Mesh and read off distance as "blocks walked"

WHAT. Arrange nodes on an $N \times M$ grid: $N$ columns, $M$ rows. Every interior dot links to its 4 neighbours: North, South, East, West. No diagonal wires exist.

WHY. A chip is a flat rectangle, so a flat rectangular grid of routers is the layout that wastes the least wire. This is why the Mesh is the default. But "no diagonals" has a consequence we must measure: to go across and up, you cannot cut the corner — you walk it like city blocks.

PICTURE. Look at the red path from the bottom-left corner to the top-right corner. It steps right, right, right (across the columns) then up, up, up (up the rows). It can never go diagonally, so it always pays for both directions in full.

Step 3 — Push the two corners apart: the Mesh diameter

WHAT. The two dots that are farthest apart are opposite corners. Bottom-left is at column $0$ , row $0$ ; top-right is at column $N - 1$ , row $M - 1$ .

WHY. Diameter is defined as the worst case, so we must find the pair that maximises Step 2's formula. Corners maximise both $∣ x_{2} - x_{1} ∣$ and $∣ y_{2} - y_{1} ∣$ at once.

PICTURE. The amber staircase spans the full width ( $N - 1$ columns) and full height ( $M - 1$ rows). Count the amber steps: that count is the diameter.

For a $4 \times 4$ mesh: $D = (4 - 1) + (4 - 1) = 6$ hops — exactly matching the parent note.

Step 4 — Cut the chip in half: the Mesh bisection bandwidth

WHAT. Split the grid into two equal halves. For a square $N \times N$ grid we can cut either way — a vertical cut (halving the columns) or a horizontal cut (halving the rows) — and count how many links the knife severs. A vertical cut severs one link per row ( $M$ of them); a horizontal cut severs one link per column ( $N$ of them). We keep whichever cut severs fewer links, because that is the true bottleneck. Each severed link carries $B_{link}$ bits per second. Multiply.

WHY. Imagine every node on one half wants to talk to a node on the other half at the same time. All that traffic must squeeze through exactly the links the cut severed. So the bisection bandwidth is the true ceiling on "everyone talks across the chip" traffic — it is the number the diameter cannot tell you. We choose the fewest-link cut because a bottleneck is defined by the tightest squeeze, not the loosest.

PICTURE. The dashed cyan vertical cut severs one horizontal link per row; the faint dashed horizontal cut severs one vertical link per column. On a square grid both sever the same count; on a tall thin grid the shorter cut wins. Each cut wire glows amber.

For a $4 \times 4$ mesh with $B_{link} = 64 bits \times 2 GHz = 128 Gb/s$ : $B_{b} = 4 \cdot 128 Gb/s = 512 Gb/s$ matching the parent's worked example.

Step 5 — Change ONE rule: wrap the edges → the Torus

WHAT. Take the same mesh and add wraparound links: the leftmost column joins the rightmost, the top row joins the bottom. Now the grid is a loop in both directions.

WHY. In the mesh, corner-to-corner was expensive because you had to walk the whole width. If the far edge is now a single hop away (through the wrap), the worst case shrinks. This is the whole reason a torus exists: same layout, shorter worst path.

PICTURE. The amber wrap arrow leaps from the right edge straight back to the left edge in one hop. Suddenly the "farthest" node is only half a grid away in each direction, because you go whichever way is shorter.

For an $8 \times 8$ : $D_{torus} = 4 + 4 = 8$ vs. mesh $14$ — a $43%$ drop, exactly the parent's figure. Cost: those wrap wires cross the whole chip → more power, see Power Management in SoCs.

Step 6 — Change the rule harder: label nodes in binary → the Hypercube

WHAT. Give $N = 2^{k}$ nodes binary names $000 \dots$ to $111 \dots$ ( $k$ bits). Connect two nodes if and only if their names differ in exactly one bit.

WHY. In a mesh, "distance" was blocks walked. Here distance becomes how many bits differ between two names (the Hamming distance). Since each hop flips exactly one bit, the number of hops equals the number of bits that disagree. Flipping bits is a far more powerful move than stepping one grid cell — you can jump across the whole address space.

PICTURE. Node $011$ links to $111$ , $001$ , $010$ — each neighbour is one flipped bit (the flipped bit glows amber). Reaching any node just means fixing the wrong bits one at a time.

Now the second metric — bisection. Split the $N = 2^{k}$ names into two halves by looking at the top bit: all names starting with $0$ on the left, all names starting with $1$ on the right. The only links crossing this cut are the ones that flip that top bit — and every node has exactly one such link. So the cut severs one link per node-pair, i.e. $N /2$ links.

Cost. Each node needs $k = lo g_{2} N$ links, so router size grows with the chip — a classic latency-vs-cost trade-off. And a cube of dimension $> 2$ cannot be drawn flat, so it is hard to lay out in 2D silicon.

Step 7 — Fatten the wires toward the root → the Fat-Tree

WHAT. Build a tree: leaves at the bottom are the cores, internal nodes are switches, and everything funnels up toward a single root and back down. First fix the branching factor: a == $k$ -ary tree== means every switch has exactly $k$ children below it. So $k = 2$ is a binary tree (2 children each), $k = 4$ is a quad tree, and so on. This one number $k$ controls how fast the tree fans out. The second trick is that links get wider (more wires) at every level going up — level 0 links carry $B$ , level 1 carry $2 B$ , level 2 carry $4 B$ , and so on. That widening is why it is called a fat-tree.

WHY. A plain tree bottlenecks at the root: all left-to-right traffic funnels through one thin link. If instead we double the link width at each level up, the root is wide enough to carry everything — the bottleneck disappears. So the fat-tree buys uniform bandwidth by spending wires where the traffic concentrates.

PICTURE. The amber links thicken as they climb: thin at the leaves, twice as thick one level up, twice again above that, fattest at the root. A packet goes up to a common ancestor switch, then back down to its destination.

Why "up then down = $2 lo g_{k} N$ " — trace it in the next picture. The height of the tree is $lo g_{k} N$ levels: each level up multiplies how many leaves sit below by $k$ , so it takes $lo g_{k} N$ multiplications to cover all $N$ leaves. A packet from one leaf to a distant leaf has no sideways link at the leaves — its only route is to climb to the lowest switch that is an ancestor of both leaves, then descend. In the worst case that common ancestor is the root, so the packet climbs the full $lo g_{k} N$ levels and descends the full $lo g_{k} N$ levels: $lo g_{k} N + lo g_{k} N = 2 lo g_{k} N$ .

Worked example 16-node binary fat-tree (

$k = 2$ ) Diameter: $D = 2 lo g_{2} 16 = 2 \cdot 4 = 8$ hops (leaf → root → leaf). Link widths, level by level. A binary tree over $16$ leaves has $lo g_{2} 16 = 4$ levels of links. Leaf link $= 64 b \times 2 GHz = 128$ Gb/s. Doubling each level up: level 0 $= 128$ , level 1 $= 256$ , level 2 $= 512$ , level 3 (into the root) $= 1024$ Gb/s. So the root link width is $8 \times$ the leaf link $= 1024$ Gb/s, and this comes straight from the "double per level" rule ( $128 \times 2^{3} = 1024$ ), not from any division. Bisection: cut the tree at its very top — this severs the two half-subtrees. The total width across that cut is $N \cdot B_{link} = 16 \cdot 128 = 2048$ Gb/s. Note $2048$ (the whole cut) $= 2 \times 1024$ (one root link), because the top of a binary fat-tree carries two root-level links, not one. That resolves the apparent clash: $1024$ is one fat link, $2048$ is both of them across the bisection cut.

Cost. Those wide root switches are huge in area and power, which is why fat-trees rule datacenters more than tiny SoCs.

Step 8 — The degenerate extreme: strip it to a loop → the Ring

WHAT. Give every node exactly 2 links, forming a single cycle. This is the minimum possible network that still connects everyone.

WHY. We include this case because it shows the failure mode: with only 2 links per node, any cut through the ring severs only 2 links, no matter how many nodes there are. The bisection bandwidth stops growing — it is stuck at a constant.

PICTURE. The dashed cut slices the ring and touches exactly 2 wires (amber), while the diameter is the long way to the opposite node — half the ring.

When 64 cores flood the network with coherence broadcasts, that flood must survive the narrowest cut — a Ring's flat $B_{b}$ chokes, while the Hypercube and Fat-Tree ( $B_{b} \propto N$ ) breathe.

The one-picture summary

Every topology is the same dots with a different connection rule, and each rule moves the two numbers — diameter (how far, worst case) and bisection (how much, at the tightest cut).

Recall Feynman retelling — say it like you're explaining to a friend

Picture a city of routers as dots. A hop is one drive down one street. Two questions decide if the city works: "what's the longest trip anyone ever has to make?" (that's the diameter) and "if I split the city in half, how many roads carry all the cross-town traffic?" (that's the bisection bandwidth). Start with a plain grid — the mesh. No diagonal roads, so a corner-to-corner trip pays for the full width and the full height: $(N - 1) + (M - 1)$ hops. Cut it into halves and you sever one road per row (or per column, whichever is fewer), so bandwidth is $min (N, M)$ roads wide. If a side has an odd number of towns, the two halves differ by one town but the cut still crosses the same number of roads — the formula doesn't budge. Now wrap the edges around — the torus — and the far edge is one hop away, halving the worst trip and doubling the cut's width (a straight knife always crosses a loop in two places). Instead of grids, name the dots in binary and connect names that differ by one bit — the hypercube — and a trip is just "fix the wrong bits one at a time", so the worst trip is only $lo g_{2} N$ bits long, and splitting on the top bit shows $N /2$ roads cross the cut. Grow a tree and fatten the wires toward the root — the fat-tree — where every switch has $k$ children so the tree is $lo g_{k} N$ levels tall; a packet climbs to a shared ancestor and comes back down, paying that height twice ( $2 lo g_{k} N$ ), and because the wires double each level up, no level is a bottleneck, so all $N$ roads' worth of bandwidth survives. Strip everything down to a single loop — the ring — and every cut touches just 2 roads forever, so it never scales. That's the whole page: same dots, change one rule, watch diameter and bisection move.