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

6.3.6 · D4 · Hardware › Interconnects, Buses & SoC › Network-on-Chip (NoC) topologies

Yeh page ek self-test ladder hai. Har exercise apna level batata hai (L1 → L5). Pehle khud try karo, phir collapsible solution kholо. Har formula jo tumhe chahiye woh parent topic mein build kiya gaya tha — lekin hum use karte waqt har baar re-state kar dete hain, taaki tumhe koi symbol dhundhna na pade.

Reference numbers jo poore mein use hote hain: ek link $w = 64$ bits per cycle carry karta hai frequency $f = 2 GHz$ par, toh ek link ki bandwidth hai $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

YEH kya hai: routers ka ek grid jisme sirf up/down/left/right links hain aur koi edge-wrapping nahi, woh Mesh (2D grid) hai. Degree = ek router se nikalne wale links ki sankhya. Figure s01 dekho.

Centre router ke saare chaar neighbours present hain → degree $= 4$ .
Corner router sirf do neighbours ko touch karta hai → degree $= 2$ . Answer: Mesh; centre degree $4$ , corner degree $2$ .

Recall Solution 1.2

Ek closed loop jisme har router sirf apne do loop-neighbours se link karta hai woh Ring hai. Har node mein exactly $2$ links hote hain, isliye degree $= 2$ uniformly hoti hai. Answer: Ring.

Level 2 — Application

Recall Solution 2.1

Yahan $N = M = 4$ . $D = (4 - 1) + (4 - 1) = 3 + 3 = 6 hops .$ Answer: $D = 6$ hops. (Figure s02 dekho: bottom-left se top-right tak ka red staircase 6 links lamba hai.)

Recall Solution 2.2

Formula: $B_{b} = min (N, M) \cdot B_{link}$ . Ek $4 \times 4$ mesh mein vertical cut har row mein ek link = $4$ links tod deta hai. $B_{b} = 4 \times 128 Gb/s = 512 Gb/s .$ Answer: $512 Gb/s$ .

Recall Solution 2.3

Diameter: worst case woh node hai jo loop ke directly "across" hai. $D = ⌊ N /2 ⌋ = ⌊ 8/2 ⌋ = 4$ hops. Bisection: loop ko kahin bhi kato aur tum hamesha exactly $2$ links todoge (loop mein do arcs hain), isliye $B_{b} = 2 \times 128 = 256 Gb/s .$ Answer: $D = 4$ hops, $B_{b} = 256 Gb/s$ — tiny bisection hi reason hai ki rings heavy traffic mein choke ho jaate hain (dekho Latency and Throughput Trade-offs).

Level 3 — Analysis

Recall Solution 3.1

Mesh: $D = (8 - 1) + (8 - 1) = 14$ hops. Torus: wraparound ka matlab hai ki har dimension mein tumhe zyada se zyada aadha chakkar lagana padega, $⌊ 8/2 ⌋ = 4$ . Toh $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 — $\approx 43%$ ki drop. Wraparound links shortcuts hain.

Recall Solution 3.2

$\oplus$ hai XOR = chosen bit flip karo. 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$ (degree $= k$ ). Diameter: koi bhi do nodes at most $k$ bit positions mein differ karte hain, aur har hop ek bit fix karta hai, isliye $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

Har ek compute karo (sab $N = 16$ ke saath):

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)$ .
Diameter par winner: Torus aur Hypercube ka $4$ par tie hai. Yahan dono ka degree bhi $4$ hai, isliye $N = 16$ par degree cost identical hai — deciding factors ban jaate hain physical layout (torus ko long wraparound wires chahiye; hypercube non-planar hai) aur bisection bandwidth. Layout constraint ke liye System-on-Chip (SoC) Design dekho.
Answer: Torus aur Hypercube diameter $4$ par tie karte hain, dono degree $4$ ; Ring sabse kharab $8$ par.

Recall Solution 4.2

Hypercube degree $= lo g_{2} N$ . Solve karo $lo g_{2} N > 4 \Rightarrow N > 16$ . Agla power of two hai $N = 32$ , jahan degree $= lo g_{2} 32 = 5$ . Answer: $N = 32$ par (degree $5 > 4$ ). Yeh kyun matter karta hai: har extra port ek crossbar row/column, buffers, aur arbitration logic add karta hai, isliye router area/power roughly degree ke saath scale karta hai. $N = 16$ se aage hypercube ka router grow karta hai jabki torus ka $4$ par fixed rehta hai — yeh ek real power aur area penalty hai, chahe hypercube ka diameter abhi bhi tiny ho.

Level 5 — Mastery

Recall Solution 5.1

$N = 16$ , $B_{link} = 128 Gb/s$ , binary tree isliye $k = 2$ . (a) Root link $= \frac{16 \times 128}{2} = 1024 Gb/s$ — ek leaf link ka $8 \times$ , yahi reason hai ki ise fat tree kehte hain. (b) $B_{b} = 16 \times 128 = 2048 Gb/s$ — kisi bhi cut par koi bottleneck nahi. (c) $D = 2 lo g_{2} 16 = 2 \times 4 = 8$ hops (leaf upar root tak, root neeche leaf tak). (d) Mesh bisection $512 Gb/s$ tha; fat-tree $2048 Gb/s$ hai = $4 \times$ zyada. Price paid: huge $1024 Gb/s$ root switch bada aur power-hungry hai, aur $8$ -hop diameter (mesh ke $6$ ki tulna mein) ka matlab hai nearby nodes ke liye higher latency. Bandwidth-critical designs (datacenter-jaisa traffic) yeh accept karte hain; latency-critical designs shayad na karein.

Recall Solution 5.2

All-to-all traffic bisection bandwidth par stress dalta hai (aadhe cores doosre aadhe ko flood karte hain). Power budget jo long wires forbid karta hai woh Torus (wraparound wires chip span karti hain) aur Hypercube (non-planar long links) aur Fat-Tree root wires ko penalise karta hai. Bisection numbers $N = 16$ par ( $B_{link} = 128$ Gb/s):

Topology	Bisection BW	Long wires?
Ring	$256$ Gb/s	no
Mesh	$512$ Gb/s	no (saare 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: highest-bisection options (Fat-Tree, Torus, Hypercube) sab "no long wires" constraint violate karte hain. Wire-friendly, planar options mein (Ring, Mesh), Mesh ring ki bisection double karta hai ( $512$ vs $256$ Gb/s) sirf short, local links ke saath.
Winner: Mesh — physically-allowed, short-wire topologies mein best bisection, aur uska regular grid 2D floorplan par cleanly map hota hai. Agar power rule relax ho jaaye, toh Torus (hypercube jaisa diameter, uniform degree $4$ , mesh se double bisection) aage aa jaata.