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

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

Yeh page ek drill hai. Hum parent note se paanch topologies lete hain aur unse har tarah ke questions nikalte hain: normal cases, tiny/degenerate networks, extreme limits, ek word problem, aur ek exam-twist. Shuru karne se pehle ek vaada: koi bhi symbol yahaan nahi aayega jo humne pehle earn nahi kiya ho. Chalo teen numbers ko phir se pin karte hain jo hum baar baar compute karte hain, seedhe saadhe shabdon mein.

128 Gb/s per link number apni jeb mein rakh lo — zyaatatar examples ise reuse karte hain.

---

The scenario matrix

Is topic ke har question ka answer inhi cells mein se ek mein hai. Har worked example neeche us cell ke tag ke saath aaya hai jisko woh fill karta hai.

#	Case class	Tricky kyun hai	Filled by
A	Normal mesh — rectangular, interior + edge nodes	do grid dimensions ko mix karna	Ex 1
B	Torus wraparound — kya shortcut help karta hai?	har axis par wrap vs. no-wrap decide karna	Ex 2
C	Hypercube routing — bit-flip path	binary labels se routes padhna	Ex 3
D	Fat-tree bandwidth — link fattening	link width har level par change hoti hai	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 apne edge par	Ex 6
G	Limiting behaviour — big-$N$ growth order	$N\to \infty$ par kaun sa topology jeetta hai	Ex 7
H	Real-world word problem — power budget ke under topology choose karna	English → constraints translate karna	Ex 8
I	Exam twist — non-square torus, odd dimension floor	$\lfloor \cdot \rfloor$ ke traps	Ex 9

---

Example 1 — Normal mesh (cell A)

Figure s01, steps se pehle padho: yellow node-dots ki ek 3-row by 5-column grid jo white links se judi hai. Ek thick pink line worst-case route trace karti hai bottom-left node $(0,0)$ se chaar links right, phir do links upar top-right node $(2,4)$ tak — yahi diameter path hai. Ek vertical blue dotted line do columns ke beech girti hai; yeh 3 rows mein se har ek mein ek horizontal link cross karti hai, toh 3 links cut hoti hain — yahi bisection cut hai.

Steps.

1. Do grid sizes identify karo: rows $N=3$, columns $M=5$. Yeh step kyun? Mesh diameter formula $D=(N-1)+(M-1)$ ko dono dimensions alag alag chahiye, kyunki aap har axis par independently travel karte ho — grid par koi diagonal nahi hota.

2. Diameter: worst case ek corner se opposite corner tak hai (figure s01 mein pink path). $D=(3-1)+(5-1)=2+4=6\text{hops}.$ Yeh step kyun? Aapko 2 rows aur 4 columns walk karne hain; har walked link ek hop hai, aur koi shortcut nahi hai, toh aap unhe sum karte ho.

3. Bisection: 15 nodes ko jitna ho sake evenly split karo. Kyunki $3\times 5=15$ odd hai, perfectly equal split impossible hai, toh "halves" matlab hai ek side par 7 nodes aur doosri par 8 (ek se differ karte hain — upar di gayi definition ke hisaab se allowed). Figure s01 mein blue dotted vertical cut aisa split achieve karti hai aur fewest links severate karti hai: har row mein ek horizontal link, yaani $\min (N,M)$ links. Horizontal cut instead $\max (N,M)=5$ links sever karti — zyada, toh hum use reject karte hain. Yeh step kyun? Bisection width minimum balanced cut hai. Vertical cut $\min (3,5)=3$ links sever karti hai; woh minimum hi true bottleneck hai. $B_b=\min (3,5)\cdot B_{\text{link}}=3\times 128=384\text{Gb/s}.$

Recall Example 1 Verify karo

Units: hops dimensionless hain (link counts) ✓. Bandwidth: $3\times 128\text{Gb/s}=384\text{Gb/s}$ ✓. Sanity: diameter 6, $4\times 4$ mesh se match karta hai (woh bhi 6) kyunki $2+4=3+3$ — same total travel. Accha, ek wider-but-shorter grid ek square se tie kar sakta hai.

---

Example 2 — Torus wraparound (cell B)

Figure s02, steps se pehle padho: yellow node-dots aur white links ki same rectangular grid, lekin ab har row ke leftmost aur rightmost node blue dashed wrap link se jude hain, aur har column ke top aur bottom node bhi — yeh dashed links hi shortcuts hain. Ek thick pink segment ek single row par ek aisa shortcut dikhata hai: node 0 paanch links walk karne ke bajaye seedha node 5 par wrap-hop mein pahunch jaata hai.

Steps.

1. Torus diameter formula: $D=\lfloor N/2\rfloor +\lfloor M/2\rfloor$ jahan $\lfloor x\rfloor$ ka matlab hai round down (woh sabse bada whole number jo $\le x$ ho). Floor kyun? $N$ nodes ki ring par aap kabhi ring ka half se zyada nahi walk karte — halfway point ke baad doosri taraf se jaana shorter hota hai. $N$ ka half, rounded down, woh worst-case half-trip hai.

2. $N=4$, $M=6$ plug in karo: $D=\lfloor 4/2\rfloor +\lfloor 6/2\rfloor =2+3=5\text{hops}.$ Yeh step kyun? Har axis apna half-ring worst case contribute karta hai; do axes independent hain toh hum add karte hain.

3. Mesh se compare karo (Ex-1 style): mesh $D=(4-1)+(6-1)=8$. Toh wrap dono axes par help karta hai, 8 → 5 cut karke. Yeh step kyun? Figure s02 mein blue dashed wrap links hi shortcuts hain; 6-long axis par, node 0 paanch ki bajaye ek wrap-hop mein node 5 tak pahunch jaata hai.

4. Bisection: $4\times 6=24$ nodes ko 12-12 ke do equal halves mein split karo (24 even hai, toh perfectly equal split exist karta hai). Ek vertical cut ab mesh se do baar zyada links sever karti hai: har row mein ek straight link aur ek wrap link same vertical line cross karte hain, kyunki har row ki ring ek loop hai aur loop ka koi bhi cut usse do jagah pass karta hai. $B_b=2\cdot \min (N,M)\cdot B_{\text{link}}=2\times 4\times 128=1024\text{Gb/s}.$ Yeh step kyun? $\min (4,6)=4$ straight links, plus 4 wrap links, minimum balanced cut par 8 links deta hai; links double hone se bandwidth double ho gayi.

Recall Example 2 Verify karo

Diameter: $2+3=5$ ✓, aur $5<8$ (mesh) ✓ toh wrap help karta hai. Bisection: $2\times 4\times 128=1024\text{Gb/s}$ ✓, exactly $4\times 6$ mesh ki $4\times 128=512$ se double.

---

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

Figure s03, steps se pehle padho: solah yellow node-dots, har ek apne 4-bit binary code ke saath labelled, do nested squares (cube-of-cubes projection) ki tarah drawn. Thin white links har do nodes ko jodti hain jinka label exactly ek bit mein differ karta hai. Thick pink arrows routing path $9\to 8\to 10\to 14\to 6$ trace karte hain: har arrow par label ka exactly ek bit flip hota hai, aur chaar arrows ke baad hum 6 par pahunch jaate hain.

Steps.

1. Dono node numbers ko 4-bit binary mein likho. Bit $j$ ki "place value" $2^j$ hai: bit 0 = 1s, bit 1 = 2s, bit 2 = 4s, bit 3 = 8s. $9=1001_2,6=0110_2.$ Binary kyun? Ek hypercube node bits se label hota hai, aur link sirf un nodes ke beech exist karta hai jo exactly ek bit mein differ karte hain. Toh labels hi map hain.

2. Bit by bit compare karo. Symbol $\oplus$ ("XOR") 1 output karta hai jahan do bits differ karte hain, 0 jahan agree karte hain: $9\oplus 6=1001\oplus 0110=1111_2.$ XOR kyun? Yeh literally disagreeing bits ko spotlight karta hai. Answer mein har 1 ek aisa link hai jo hume us bit ko fix karne ke liye cross karna hai.

3. 1s gino (Hamming distance): $1111$ mein chaar 1s hain → 4 hops. Yeh hop count ke barabar kyun hai? Har hop exactly ek bit flip karta hai; aapko chaar bits flip karne hain; isliye minimum chaar hops, aur koi bhi order kaam karta hai.

4. Low-to-high bits flip karte hue path walk karo (figure s03 mein pink arrows follow karo): $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.$ Yeh order kyun? Order free hai — XOR guarantee karta hai ki saare chaar flips hume 6 par hi land karenge, sequence chahe jo bhi ho.

Recall Example 3 Verify karo

$9\oplus 6=15=1111_2$, popcount $=4$ ✓. 9 ke saare bits flip karne ke baad final node: $9\oplus 15=6$ ✓. Path endpoints correct, 4 hops $=k={\log }_{2}16$ ✓.

---

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

Yahaan $k$ tree ka branching factor hai — har internal switch ke kitne children hain. Ek binary fat-tree mein $k=2$ hota hai (har switch do children tak fan out karta hai). Is example mein hum poore time $k=2$ use karte hain.

Figure s04, steps se pehle padho: ek binary tree bottom-up drawn. Sabse neeche ki row mein 8 yellow leaf-dots hain (processing elements). Unke upar 4 switches hain, phir 2, phir top par ek root. Links har level upar jaane par visibly thicker hoti jaati hain: thin white leaf links (128 Gb/s), thicker blue level-1 links (256 Gb/s), thickest pink links root mein (512 Gb/s). Yahi thickening "fat" hai fat-tree mein.

Steps.

1. Binary ($k=2$) fat-tree mein $N=8$ leaves ke saath levels: leaves ke upar ${\log }_{2}8=3$ switch levels hain. Link bandwidth har level upar double hoti hai. Double kyun? Har higher level par half switches ko saari neeche ki traffic carry karni hoti hai, toh choke se bachne ke liye har higher link ko do baar fat hona padta hai.

2. Root link bandwidth. Parent note ka rule: root link $=\frac{N}{2}\cdot B_{\text{link}}$. $B_{\text{root}}=\frac{8}{2}\times 128=4\times 128=512\text{Gb/s}.$ $N/2$ kyun? Single top cut tree ko $N/2$ leaves ke do halves mein split karta hai; root ko unke beech saari cross-traffic carry karni hoti hai.

3. Bisection bandwidth: tree ko uske narrowest balanced point par kaato. Fat-tree mein tightest balanced cut root par hi hota hai — yeh 8 leaves ko 4-4 ke do groups mein split karta hai, aur us cut ko cross karne wale only links root mein jaane wale links hain. Binary fat-tree mein root tak 2 top links pahunchte hain (har level-2 switch se ek), har ek ki width $\frac{N}{4}{B}_{\text{link}}=2\times 128=256$ Gb/s hai, toh cut par 4 leaf-equivalent links = 512 Gb/s hain. $B_b=\frac{N}{2}\cdot B_{\text{link}}=4\times 128=512\text{Gb/s}.$ $\frac{N}{2}{B}_{\text{link}}$ kyun, $N{B}_{\text{link}}$ kyun nahi? Minimum balanced cut sirf root mein enter karne wale links sever karta hai, jo milke $\frac{N}{2}$ leaf-links worth bandwidth carry karte hain — har leaf link nahi. Fattening is cut ko leaves ke aggregate se worse nahi hone deta, lekin bisection root cut par set hoti hai, giving $\frac{N}{2}{B}_{\text{link}}=512$ Gb/s. "Fat" ka point yeh hai ki root cut ek thin tree ke relative bottleneck nahi hai, yeh nahi ki yeh magically aggregate double kar deta hai.

4. Diameter: leaf se root tak, phir doosre leaf tak: $D=2{\log }_{k}N=2{\log }_{2}8=2\times 3=6$ hops. $2{\log }_{k}N$ kyun? Tree upar ${\log }_{k}N$ levels hai (isliye $k$, branching factor, log ke base mein hai — har switch par zyada children matlab kam levels); neeche bhi ${\log }_{k}N$ levels; worst case dono karta hai. $k=2$ ke saath: $2{\log }_{2}8=6$.

Recall Example 4 Verify karo

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

---

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

Figure s05, steps se pehle padho: aath yellow node-dots ek circle mein evenly arranged, 0–7 numbered, white links se ek closed loop mein joined. Ek horizontal blue dotted line loop ko slice karti hai; kyunki loop ek single closed curve hai, line exactly do jagah use cross karti hai — 2 links sever karti hai. Ek thick pink arc node 0 se node 4 tak diameter route trace karta hai (4 hops, ring ka far side).

Steps.

1. Diameter $=\lfloor N/2\rfloor =\lfloor 8/2\rfloor =4$ hops. Kyun? Ring nodes ka ek single loop hai; sabse door node diametrically opposite hai, dono directions se half-way around.

2. Bisection: chahe aap ring ko 4-4 nodes ke do equal halves mein kahin bhi kaato, ek seedhi line exactly 2 links cross karti hai (loop ke do arcs, figure s05 mein dikhaye gaye hain). $B_b=2\times B_{\text{link}}=2\times 128=256\text{Gb/s}.$ Sirf 2 kyun? Ring ek loop hai; loop ka koi bhi cut use exactly do jagah sever karta hai. Yeh constant hai — yeh $N$ ke saath kabhi grow nahi karta.

3. "Terrible?" Per-node compare karo: 8 nodes 256 Gb/s cut share kar rahe hain = 32 Gb/s effective per node, mesh ke bahut bade bisection ke muqable. Jaise jaise $N$ badhta hai ring ki bisection 256 par hi rehti hai jabki traffic badhti hai — bottleneck worse hota jaata hai. Yeh kyun matter karta hai: bisection bandwidth balanced all-to-all traffic ki ceiling hai; rising demand ke saath fixed ceiling hi bottleneck ki definition hai (Latency and Throughput Trade-offs).

Recall Example 5 Verify karo

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

---

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$. 0 kyun? Ek row ke saath vertically kuch travel karna hi nahi, toh woh term zero ho jaata hai — mesh ek line mein collapse ho gaya (wrap ke bina ring). Formula gracefully degrade karta hai.

2. (b) 1-node network. Diameter $=0$ (ek node khud se 0 hops door hai). Bisection: aap ek node ko do non-empty groups mein split nahi kar sakte, toh bisection undefined / effectively 0 hai. 0 hops kyun? Diameter do distinct nodes ke beech max distance hai; ek node ke saath koi pair nahi, toh empty set par max 0 hai by convention. Yahi true "zero input" hai.

3. (c) 2-node ring. Diameter $=\lfloor 2/2\rfloor =1$: do nodes 1 hop apart hain. Ek convention par commit karo: hum ring ko ek undirected cycle graph model karte hain, jahan koi bhi do adjacent nodes ke beech exactly ek link hota hai. $N=2$ par "cycle" degenerate ho jaata hai — graph theory do parallel edges do nodes ke beech rakhega, lekin standard NoC convention ek single physical link ka hai, toh hum ek link use karte hain. Ring bisection formula $B_b=2\cdot B_{\text{link}}$ blindly lagaana claim karega ki 2 links cut cross karte hain — lekin degenerate 2-node ring mein sirf ek link hai, toh formula yahaan overcount karta hai. Definition se honest value (minimum links to split 2 nodes into 1+1) 1 link hai: $B_b^{(N=2)}=1\times B_{\text{link}}=128\text{Gb/s}.$ Formula kyun break karta hai: $2\cdot B_{\text{link}}$ mein "2" ek genuine loop ke do arcs count karta hai, lekin 2-node ring mein koi genuine loop nahi hai (cycle ke liye $\ge 3$ nodes chahiye), toh sirf ek link hai katne ke liye. Edge cases exactly wahan hain jahan blind formula-plugging fail hoti hai.

Recall Example 6 Verify karo

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

---

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

Figure s06, steps se pehle padho: diameter (vertical axis, hops) ka node count $N$ (horizontal axis, log scale par drawn taaki doublings evenly spaced hon) ke against ek plot. Teen curves rise karti hain: ek steep pink line "ring $O(N)$" labelled jo 512 tak shoot karti hai, ek gentler blue curve "mesh $O(\sqrt{N})$" labelled jo 62 tak pahunchti hai, aur ek nearly-flat yellow curve "hypercube $O(\log N)$" labelled jo 10 tak barely pahunchti hai. Curves ke beech visual gap hi scalability story hai.

Steps.

1. Square mesh: $32\times 32$ (kyunki $32^2=1024$). $D=(32-1)+(32-1)=62$. $\sqrt{N}$ kyun? Square grid ki side $\sqrt{N}$ hoti hai, aur diameter $\approx 2\sqrt{N}$ — yeh $O(\sqrt{N})$ ki tarah grow karta hai.

2. Hypercube: $2^k=1024\Rightarrow k=10$ chahiye. $D=k=10$. $\log$ kyun? Har dimension node count double karta hai, toh dimensions ki sankhya (aur hops) ${\log }_{2}N$ hai — teeno mein sabse slow-growing.

3. Ring: $D=\lfloor 1024/2\rfloor =512$. $O(N)$ kyun? Ring ka worst case half ring hai, toh yeh linearly grow karta hai — fastest-growing, by far the worst.

4. Rank (fastest→slowest growth): Ring $O(N)$ → Mesh $O(\sqrt{N})$ → Hypercube $O(\log N)$. Yeh ordering kyun — iske peeche visual reasoning: dekho kya hota hai jab aap $N$ double karte ho (figure s06 ke log axis par ek step right).

   • Ring $D=N/2$: $N$ double karne se $D$ double ho jaata hai — pink line ki height har step par double hoti hai, toh woh rocket ki tarah upar jaati hai. Linear growth matlab diameter poore network ka ek fixed fraction hai, toh woh climb karna kabhi band nahi karta.
   • Mesh $D\approx 2\sqrt{N}$: $N$ double karne se $D$ sirf $\sqrt{2}\approx 1.41$ multiply hota hai — blue curve rise karti hai, lekin har doubling ring se chota jump add karta hai. Square-root growth ko cushion karta hai kyunki square grid ko side $\sqrt{N}$ se wide karna $N$ nodes ko ek ki jagah do dimensions mein spread karta hai.
   • Hypercube $D={\log }_{2}N$: $N$ double karne se sirf +1 hop add hota hai (ek aur dimension = ek aur bit) — yellow curve nearly flat hai. Poora ek dimension add karne ka cost sirf ek extra flip hai, toh diameter sabse slow possible tarike se grow karta hai. Numbers ordering visually aur arithmetically confirm karte hain: $512\gg 62\gg 10$. Yeh kyun matter karta hai: thousand-core chips ke liye sirf log-class topologies latency sane rakhti hain — high router degree ki cost par (System-on-Chip (SoC) Design).

Recall Example 7 Verify karo

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. $N=16$ par har candidate ke liye degree aur diameter tabulate karo:

   • 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$. Yeh numbers kyun? Degree router power drive karta hai (Power Management in SoCs); diameter worst-case latency drive karta hai.

2. Latency constraint "$\le 8$ hops" apply karo: ring $8\le 8$ ✓ (just barely), mesh $6\le 8$ ✓, hypercube $4\le 8$ ✓. Sab pass karte hain. Pehle yeh kyun check karo? Jo design hard constraint violate kare woh disqualify ho jaata hai chahe power kitni bhi acchi ho.

3. Power priority apply karo (degree minimize karo): ring degree 2 se jeetta hai, mesh/hypercube ke ports ka half. Degree kyun, diameter nahi, decide karta hai? Problem kehti hai power strict budget hai aur traffic light & local hai — toh bisection bandwidth (ring ki weakness) koi khas matter nahi karti, jabki low port count directly power bachata hai.

4. Choice: Ring. Yeh 8-hop ceiling exactly meet karta hai, minimal degree 2 hai, lowest wiring/power hai, aur light local traffic kabhi iske poor bisection ko stress nahi karta. Mesh kyun nahi? Mesh ki better latency (6 vs 8) yahaan needed nahi hai, aur iske degree-4 routers zyada power burn karte hain — is budget ke under ek bura trade.

Recall Example 8 Verify karo

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

---

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

Steps.

1. Sahi diameter: $D=\lfloor 5/2\rfloor +\lfloor 3/2\rfloor =2+1=3$ hops. Har term alag kyun floor karo? 5 ki odd-length ring par, sabse door node 2 hops door hai, 2.5 nahi — aap half hop nahi le sakte. Sum ko round karna (student ka $4$) fractional hops double-count karta hai jo exist hi nahi karte.

2. Student ki error pakdo: unhone $2.5+1.5=4$ compute kiya. Sach floor before adding karta hai: $2+1=3$. Yeh mistake diameter ko 1 se inflate kar deti hai. Order kyun matter karta hai? $\lfloor a\rfloor +\lfloor b\rfloor \le \lfloor a+b\rfloor$; pehle floor karna physically correct per-axis half-ring hai, aur yeh chota hota hai.

3. Bisection: $B_b=2\cdot \min (5,3)\cdot B_{\text{link}}=2\times 3\times 128=768\text{Gb/s}$. $\min$ aur $\times 2$ kyun? Short axis (3 rows) ke across kaato taaki fewest links sever ho, phir torus wrap ke liye double karo. $\min (5,3)=3$.

Recall Example 9 Verify karo

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

---

Recall Self-test

Ek $6\times 6$ mesh ka diameter? ::: $(6-1)+(6-1)=10$ hops. Ek $6\times 6$ torus ka diameter? ::: $\lfloor 6/2\rfloor +\lfloor 6/2\rfloor =3+3=6$ hops. Hypercube node 0 se node 15 tak hops (4-cube mein)? ::: $0\oplus 15=1111$, chaar 1s → 4 hops. Ring ki bisection kabhi kyun nahi badhti? ::: single loop ka koi bhi cut exactly 2 links sever karta hai.

Yeh bhi dekho: Routing Algorithms (packets actually yeh paths kaise choose karte hain), Cache Coherence Protocols (network par kaunsi traffic ride karti hai), Latency and Throughput Trade-offs (diameter vs. bisection design tension kyun hai).