Foundations — Network-on-Chip (NoC) topologies

Before you can read a single formula in the topic note, you need the vocabulary. This page defines every symbol, word, and picture the parent leans on — starting from nothing.

0. The two building blocks: node and link

Everything in a Network-on-Chip is built from exactly two things.

Look at the figure: black circles are nodes, black lines between them are links, and the overall pattern they form is the topology. The whole rest of the topic is just "how do we arrange these dots and lines?"

1. Counting nodes: $N$ and $M$

Picture: count the dots. That's it. $N$ and $M$ are never mysterious — they are how many circles you can see.

Why the topic needs it: every formula (diameter, bandwidth) is written in terms of $N$, because we want to know how the network behaves as we add more cores. A formula in $N$ tells you the future — what happens at 64 or 256 cores.

2. A hop, and the picture of "distance"

In the figure, the red path goes from the top-left node to the bottom-right node in 4 hops. Each red segment is exactly one hop. Distance on a chip is not measured in millimetres here — it is measured in hops, because each hop costs a router's worth of delay.

3. Diameter $D$ — the worst-case trip

Now we can define the first real metric.

Picture: stand at the most awkward corner, walk the shortest route to the most awkward opposite corner, and count hops. That count is $D$.

Let us make this concrete for a grid, so you can see exactly where the parent's mesh formula comes from.

4. Degree — how many roads meet at a junction

In the figure the red node in the middle has degree 4 (roads North, South, East, West). A node on the edge has fewer roads, so lower degree.

5. Bisection bandwidth $B_b$ — the traffic across a cut

This is the metric people get wrong most often, so we build it slowly.

The red dashed line in the figure cuts the grid down the middle. Only the links it crosses (there are 4 of them) can carry traffic between the left half and the right half. If both halves want to talk to each other at full blast, all that traffic must squeeze through those few links.

6. Link bandwidth $B_{\text{link}}$ — and where $f\cdot w$ comes from

Every $B_b$ formula is written as "(number of links crossing) $\times B_{\text{link}}$." So what is $B_{\text{link}}$?

7. The special symbols the parent uses

The formulas sprinkle a few pieces of maths notation. Here is each, from zero.

7.1 The floor bracket $\lfloor \rfloor$

Why the topic needs it: hops are whole numbers — you cannot make half a hop. The ring's diameter $\lfloor N/2\rfloor$ says "go at most halfway around, rounded down." For $N=8$, $\lfloor 8/2\rfloor =4$ hops.

7.2 The logarithm ${\log }_{2}N$

7.3 The XOR symbol $\oplus$ and binary bits

7.4 Big-O notation $O(\cdot )$

Why the topic needs it: the comparison table uses $O(\cdot )$ so you can compare topologies at a glance without picking a specific $N$. It answers "which topology wins as chips get huge?" — the theme of System-on-Chip (SoC) Design scaling.

Prerequisite map

Read it top-to-bottom: the two atoms (node, link) feed every metric, the metrics plus the maths notation feed the formulas, and the formulas are the parent topic. Power and coherence sit downstream — see Power Management in SoCs and Cache Coherence Protocols.

Equipment checklist

Cover the answers; you are ready when you can say each aloud.