Network-on-Chip (NoC) topologies

Core Intuition

Traditional buses work for2-8 cores, but beyond that, contention (multiple cores fighting for the bus) and wire delay (signals take multiple cycles to cross the chip) kill performance. NoC solves this by:

1. Paralelism: Multiple packets travel simultaneously on different links
2. Locality: Data routes through nearby routers, reducing hops
3. Scalability: Adding cores doesn't collapse the network

Fundamental Concepts

Why Packet-Switching on a Chip?

Derivation of the need:

1. Wire delay dominates in modern tech nodes: A 10mm wire at 7nm takes ~20 cycles to propagate a signal.
2. Shared bus bandwidth: $B_{\text{bus}} = f \cdot w$ (frequency × wire width). For 64cores sharing 128-bit bus at 2GHz: $2 \text{GHz} \cdot 128b = 256 \text{Gb/s}$ total, so 4 Gb/s per core—too little.
3. Dedicated point-to-point links scale linearly: Each router-router link provides full bandwidth, and multiple links operate in parallel.

Major NoC Topologies

1. Mesh (2D Grid)

Why these formulas?

• Diameter: Worst case is corner-to-oppositecorner. In an $N \times M$ grid, you move $(N-1)$ steps in one dimension and $(M-1)$ in the other. No diagonal moves, so $D = (N-1) + (M-1)$.
• Bisection bandwidth: Cut the grid in half. The smaller dimension determines how many links cross the cut. For a $4 \times 4$ mesh, cutting vertically severs 4 links.

Pros: Simple layout, matches 2D chip floorplan, easy routing (XY-routing).
Cons: High diameter → high latency for distant nodes. Edge nodes have lower degree → asymetric performance.

2. Torus (Wraparound Mesh)

Derivation of diameter:
In a torus, you can "wrap around." For an $N \times N$ torus, the farthest node is at distance $\lfloor N/2 \rfloor$ in each dimension (wrap if $> N/2$). Example: $8 \times 8$ torus, node (0,0) to (7,7). Instead of 14 hops (mesh), go (0,0) → (0, -1≡7) in 1 hop, then 4 hops to (4,7), then 3 to (7,7) = 8 hops. Actually, $\lfloor 8/2 \rfloor + \lfloor 8/2 \rfloor = 8$.

Pros: Lower diameter, higher bisection BW, symmetric (all nodes equal).
Cons: Wraparound wires are long (cross entire chip edge) → higher power, harder physical layout.

3. Hypercube

Derivation:
Label nodes 0 to $2^k - 1$ in binary. Node $i =_{k-1} b_{k-2} \ldots b_0$ connects to $i \oplus 2^j$ (flip bit $j$). Example: 4D hypercube ($k=4$, 16 nodes). Node 5 = 0101 connects to:

• $5 \oplus 2^0 = 0100 = 4$ (flip bit 0)
• $5 \oplus 2^1 = 0111 = 7$ (flip bit 1)
• $5 \oplus 2^2 = 001 = 1$ (flip bit 2)
• $5 \oplus 2^3 = 1101 = 13$ (flip bit 3)

Diameter: Any node reaches any other by flipping at most $k$ bits (Hamming distance ≤ $k$).

Pros: Logarithmic diameter (best scalability). High bisection BW.
Cons: Degree grows with $N$ → complex routers. Non-planar (hard to lay out in 2D silicon).

4. Fat-Tree

Why "fat"?
Traditional trees bottleneck at the root (all traffic funnels through one link). Fat-tree doubles link bandwidth at each level up. For a binary tree with $N$ leaves:

• Level 0 (leaves): Each link = $B$
• Level 1: Links = $2B$
• Level 2: Links = $4B$
• Root: Link = $NB/2$

This maintains constant bisection bandwidth across all cuts.

Pros: High bandwidth, fault-tolerant (multiple paths to root).
Cons: Area/power scales poorly (root switches huge). Deep hierarchy → latency.

5. Ring

Why diameter = $\lfloor N/2 \rfloor$?
Worst case: Opposite side of ring. In a 10-node ring, node 0 to node 5is 5 hops (clockwise or counter-clockwise). For $N$ nodes, max = $\lfloor N/2 \rfloor$.

Pros: Simplest layout, lowest wiring cost, low power.
Cons: Awful bisection BW (major bottleneck), high average latency.

Comparative Analysis

Common Mistakes

Design Trade-Offs

Latency vs. Throughput

• Low latency: Hypercube, torus (low diameter).
• High throughput: Fat-tree, hypercube (high bisection BW).
• Mesh: Compromise—moderate both.

Power vs. Performance

$P_{\text{NoC}} = P_{\text{router}} \cdot N_{\text{routers}} + P_{\text{link}} \cdot N_{\text{links}} \cdot L_{\text{link}}$

Where $P_{\text{link}} \propto C \cdot V^2 \cdot f \cdot \alpha$ ($C$ = wire capacitance, $\alpha$ = activity factor).

Why this matters: Long links (torus wraparound, fat-tree root) have high $C$ → high $P_{\text{link}}$. Hypercube has more routers → high $N_{\text{routers}}$. Mesh minimizes both.

Scalability

• Mesh/Torus: Scale to 100s of nodes (Intel's 72-core Xeon Phi uses 2D mesh).
• Hypercube: Hard limit ~1024 nodes (10-port routers are impractical).
• Ring: Dead beyond 8-10 nodes (bisection BW collapse).

Real-World Examples

1. Intel Xeon Phi (Knights Landing): 72 cores, 2D mesh NoC. Each tile = core + L2 cache slice + router. Chose mesh for 2D layout, reasonable diameter (18 hops max), 4-port routers.
2. Tilera TILE-Gx: 64 cores, 8×8 mesh. XY-routing (go X then Y) for deadlock-free deterministic paths.
3. AMD Ryzen (Infinity Fabric): Not pure NoC, but uses mesh-inspired topology for die-to-die links in chiplet designs.
4. Nvidia GPUs: Internal interconnect resembles torus for SM (streaming multiprocessor) clusters—wraparound for symmetric latency.

Active Recall Practice

Connections

• Bus Architectures: NoC replaces shared buses at scale.
• Cache Coherence Protocols: NoC routes coherence messages (snoops, invalidations).
• Routing Algorithms: XY, adaptive, deadlock avoidance for NoC packet paths.
• System-on-Chip (SoC) Design: NoC is the backbone of modern SoCs.
• Power Management in SoCs: NoC links can be power-gated when idle.
• Latency and Throughput Trade-offs: NoC topology directly impacts both.

#flashcards/hardware

What is a Network-on-Chip (NoC)? :: A packet-switched on-chip interconnect where cores/memory connect via routers and links, enabling parallel data transfer and scalable communication beyond traditional buses.

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)