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

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

Yeh parent note Network-on-Chip (NoC) topologies ke peeche ki picture-story hai. Ise upar se neeche padho; har symbol earn hone ke baad use hota hai.

Step 1 — "Node", "link", aur "hop" kya hota hai?

KYA. Ek node ek router hai jisme ek core attached hai — ise ek dot ki tarah draw karo. Ek link do dots ke beech ek wire hai — ise ek line ki tarah draw karo. Ek hop ek link ke upar ek safar hai. Agar ek packet 3 links cross karke apni destination tak pahunchta hai, toh woh trip 3 hops ki hai.

KYUN. Isse pehle ki hum "kitna dur" ya "kitna zyada" ki baat karein, humein sabse chhote countable pieces chahiye. Is page par baaki sab kuch dots, lines, aur hops count karna hai. Yahi poora trick hai.

PICTURE. Do dots ek line se jude hue = ek hop. Teesra dot add karo aur packet ab 2 hops mein far end tak pahunchta hai. Hops ki number literally utni hi lines hain jinke upar se tum walk karte ho.

Step 2 — Mesh ko layout karo aur distance ko "blocks walked" ki tarah padho

KYA. Nodes ko ek $N \times M$ grid par arrange karo: $N$ columns, $M$ rows. Har interior dot apne 4 neighbours se juda hai: North, South, East, West. Koi diagonal wires nahi hain.

KYUN. Ek chip ek flat rectangle hai, isliye routers ki ek flat rectangular grid woh layout hai jo sabse kam wire waste karti hai. Isliye Mesh default hai. Lekin "no diagonals" ka ek consequence hai jo hum measure karenge: across aur upar jaane ke liye, tum corner nahi kaat sakte — tum use city blocks ki tarah walk karte ho.

PICTURE. Bottom-left corner se top-right corner tak ke red path ko dekho. Woh right, right, right jaata hai (columns ke across) phir up, up, up (rows upar). Woh kabhi diagonally nahi ja sakta, isliye woh hamesha dono directions ka poora payment karta hai.

Step 3 — Do corners ko apart push karo: Mesh diameter

KYA. Jo do dots sabse zyada door hain woh opposite corners hain. Bottom-left column $0$ , row $0$ par hai; top-right column $N - 1$ , row $M - 1$ par hai.

KYUN. Diameter worst case ke roop mein define hoti hai, isliye hum woh pair dhundna chahte hain jo Step 2 ka formula maximize kare. Corners dono $∣ x_{2} - x_{1} ∣$ aur $∣ y_{2} - y_{1} ∣$ ko ek saath maximize karte hain.

PICTURE. Amber staircase poori width ( $N - 1$ columns) aur poori height ( $M - 1$ rows) span karti hai. Amber steps count karo: woh count hi diameter hai.

Ek $4 \times 4$ mesh ke liye: $D = (4 - 1) + (4 - 1) = 6$ hops — bilkul parent note se match karta hai.

Step 4 — Chip ko half mein kato: Mesh bisection bandwidth

KYA. Grid ko do equal halves mein split karo. Ek square $N \times N$ grid ke liye hum kisi bhi taraf cut kar sakte hain — ek vertical cut (columns ko half karna) ya horizontal cut (rows ko half karna) — aur count karo ki knife kitne links sever karti hai. Ek vertical cut ek link per row sever karta hai ( $M$ of them); ek horizontal cut ek link per column sever karta hai ( $N$ of them). Hum woh cut rakhte hain jo kam links sever kare, kyunki wahi asli bottleneck hai. Har severed link $B_{link}$ bits per second carry karta hai. Multiply karo.

KYUN. Imagine karo ki ek half ke har node ko doosri half ke ek node se ek saath baat karni hai. Saara traffic exactly anhi links se squeeze hoga jo cut ne sever ki hain. Isliye bisection bandwidth "sabka chip ke across baat karna" traffic ki sachchi ceiling hai — yeh woh number hai jo diameter nahi bata sakta. Hum fewest-link cut choose karte hain kyunki bottleneck tightest squeeze se define hota hai, loosest se nahi.

PICTURE. Dashed cyan vertical cut horizontal link per row sever karta hai; faint dashed horizontal cut vertical link per column sever karta hai. Square grid par dono same count sever karte hain; tall thin grid par shorter cut jeet jaati hai. Har cut wire amber glow karta hai.

Ek $4 \times 4$ mesh ke liye $B_{link} = 64 bits \times 2 GHz = 128 Gb/s$ ke saath: $B_{b} = 4 \cdot 128 Gb/s = 512 Gb/s$ parent ke worked example se match karta hai.

Step 5 — Ek rule badlo: edges wrap karo → Torus

KYA. Same mesh lo aur wraparound links add karo: sabse left column sabse right se jud jaata hai, top row bottom se jud jaati hai. Ab grid dono directions mein loop hai.

KYUN. Mesh mein, corner-to-corner expensive tha kyunki tum poori width walk karte the. Agar far edge ab ek single hop door hai (wrap ke through), toh worst case shrink ho jaata hai. Yahi wajah hai ki torus exist karta hai: same layout, shorter worst path.

PICTURE. Amber wrap arrow right edge se seedha left edge par ek hop mein leap karta hai. Achanak "farthest" node sirf half grid door hai har direction mein, kyunki tum jo bhi taraf shorter ho woh jaate ho.

Ek $8 \times 8$ ke liye: $D_{torus} = 4 + 4 = 8$ vs. mesh $14$ — $43%$ drop, bilkul parent ki figure. Cost: woh wrap wires poori chip cross karti hain → zyada power, dekho Power Management in SoCs.

Step 6 — Rule ko aur zyada badlo: nodes ko binary mein label karo → Hypercube

KYA. $N = 2^{k}$ nodes ko binary names $000 \dots$ se $111 \dots$ tak do ( $k$ bits). Do nodes ko connect karo agar aur sirf agar unke names ek bit mein alag hon.

KYUN. Mesh mein, "distance" blocks walked thi. Yahaan distance ban jaati hai do names ke beech kitne bits alag hain (Hamming distance). Kyunki har hop exactly ek bit flip karta hai, hops ki number un bits ki number ke barabar hai jo agree nahi karti. Bits flip karna ek grid cell step karne se kahin zyada powerful move hai — tum poori address space mein jump kar sakte ho.

PICTURE. Node $011$ se $111$ , $001$ , $010$ tak links hain — har neighbour ek flipped bit hai (flipped bit amber glow karta hai). Kisi bhi node tak pahunchne ka matlab hai galat bits ko ek ek karke fix karna.

Ab doosra metric — bisection. $N = 2^{k}$ names ko do halves mein split karo top bit dekh ke: saare names jo $0$ se start hote hain left par, saare jo $1$ se start hote hain right par. Is cut ko cross karne wale sirf wahi links hain jo woh top bit flip karte hain — aur har node ka exactly ek aisa link hai. Toh cut ek link per node-pair sever karta hai, yaani $N /2$ links.

Cost. Har node ko $k = lo g_{2} N$ links chahiye, isliye router size chip ke saath grow karta hai — ek classic latency-vs-cost trade-off. Aur dimension $> 2$ ka cube flat draw nahi ho sakta, isliye 2D silicon mein lay out karna mushkil hai.

Step 7 — Root ki taraf wires moto karo → Fat-Tree

KYA. Ek tree build karo: bottom par leaves cores hain, internal nodes switches hain, aur sab kuch ek single root ki taraf funnel karta hai aur wapas neeche. Pehle branching factor fix karo: ek == $k$ -ary tree== ka matlab hai ki har switch ke neeche exactly $k$ children hain. Toh $k = 2$ ek binary tree hai (2 children each), $k = 4$ ek quad tree hai, aur aise aage. Yeh ek number $k$ control karta hai ki tree kitni tezi se fan out karta hai. Doosri trick yeh hai ki upar jaate waqt har level par links wider (zyada wires) hote jaate hain — level 0 links $B$ carry karte hain, level 1 $2 B$ , level 2 $4 B$ , aur aise aage. Yahi widening hai isliye ise fat-tree kehte hain.

KYUN. Ek plain tree root par bottleneck ho jaata hai: saara left-to-right traffic ek thin link se funnel hota hai. Agar hum har level upar link width double karein, toh root itna wide hai ki sab kuch carry kar sake — bottleneck disappear ho jaata hai. Toh fat-tree uniform bandwidth buy karta hai wires kharach karke jahaan traffic concentrate hota hai.

PICTURE. Amber links climb karte waqt thick hote jaate hain: leaves par thin, ek level upar twice as thick, phir usse bhi upar twice again, root par fattest. Ek packet ek common ancestor switch tak upar jaata hai, phir apni destination par wapas neeche.

"Up then down = $2 lo g_{k} N$ " kyun — agli picture mein trace karo. Tree ki height $lo g_{k} N$ levels hai: har level upar jaana multiply karta hai ki neeche kitne leaves hain $k$ se, isliye sab $N$ leaves cover karne mein $lo g_{k} N$ multiplications lagte hain. Ek leaf se doosre dur leaf tak ek packet ka leaves par koi sideways link nahi hota — uska ek hi route hai ki woh us lowest switch tak climb kare jo dono leaves ka ancestor ho, phir descend kare. Worst case mein woh common ancestor root hota hai, isliye packet full $lo g_{k} N$ levels climb karta hai aur full $lo g_{k} N$ levels descend karta hai: $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. $16$ leaves wale binary tree mein $lo g_{2} 16 = 4$ levels of links hain. Leaf link $= 64 b \times 2 GHz = 128$ Gb/s. Har level upar doubling: level 0 $= 128$ , level 1 $= 256$ , level 2 $= 512$ , level 3 (root mein) $= 1024$ Gb/s. Toh root link width leaf link ka $8 \times$ hai $= 1024$ Gb/s, aur yeh seedha "double per level" rule se aata hai ( $128 \times 2^{3} = 1024$ ), kisi bhi division se nahi. Bisection: tree ko bilkul top par cut karo — yeh do half-subtrees sever karta hai. Us cut ke across total width $N \cdot B_{link} = 16 \cdot 128 = 2048$ Gb/s hai. Note karo $2048$ (poora cut) $= 2 \times 1024$ (ek root link), kyunki binary fat-tree ke top mein do root-level links hain, ek nahi. Yeh apparent clash resolve karta hai: $1024$ ek fat link hai, $2048$ bisection cut mein dono hain.

Cost. Woh wide root switches area aur power mein huge hain, isliye fat-trees datacenters mein zyada rule karti hain banasbat tiny SoCs ke.

Step 8 — Degenerate extreme: ise loop tak strip karo → Ring

KYA. Har node ko exactly 2 links do, ek single cycle banao. Yeh minimum possible network hai jo ab bhi sabko connect karta hai.

KYUN. Hum yeh case isliye include karte hain kyunki yeh failure mode dikhata hai: ek node ke paas sirf 2 links hone par, ring ke through koi bhi cut sirf 2 links sever karta hai, chahe kitne bhi nodes hon. Bisection bandwidth grow karna band ho jaati hai — ek constant par stuck ho jaati hai.

PICTURE. Dashed cut ring ko slice karta hai aur exactly 2 wires (amber) touch karta hai, jabki diameter opposite node tak ka lamba rasta hai — ring ka aadha.

Jab 64 cores network ko coherence broadcasts se flood karte hain, woh flood narrowest cut survive karna chahta hai — Ring ka flat $B_{b}$ choke karta hai, jabki Hypercube aur Fat-Tree ( $B_{b} \propto N$ ) breathe karte hain.

Ek-picture summary

Har topology same dots hain alag connection rule ke saath, aur har rule do numbers move karta hai — diameter (kitna dur, worst case) aur bisection (kitna zyada, tightest cut par).

Recall Feynman retelling — kisi dost ko samjhane ki tarah bolo

Routers ka ek sheher imagine karo as dots. Ek hop ek road pe ek drive hai. Do sawaal decide karte hain ki sheher kaam karta hai ya nahi: "sabse lamba safar kisi ko kabhi bhi karna pad sakta hai?" (woh hai diameter) aur "agar mein sheher ko half mein split karun, toh kitni roads saara cross-town traffic carry karti hain?" (woh hai bisection bandwidth). Ek plain grid se shuru karo — mesh. Koi diagonal roads nahi, isliye corner-to-corner trip poori width aur poori height ke liye pay karti hai: $(N - 1) + (M - 1)$ hops. Ise halves mein kato aur tum ek road per row (ya per column, jo bhi kam ho) sever karte ho, isliye bandwidth $min (N, M)$ roads wide hai. Agar ek side mein odd number of towns hain, toh do halves ek town se differ karti hain lekin cut ab bhi same number of roads cross karta hai — formula nahi budta. Edges ko around wrap karo — torus — aur far edge ek hop door hai, worst trip half ho jaati hai aur cut ki width double ho jaati hai (ek straight knife hamesha ek loop ko do jagahon par cross karta hai). Grid ki jagah, dots ko binary mein name karo aur un names ko connect karo jo ek bit mein alag hain — hypercube — aur ek trip bas "galat bits ek ek karke fix karo" hai, isliye worst trip sirf $lo g_{2} N$ bits lambi hai, aur top bit par split karne se pata chalta hai ki $N /2$ roads cut cross karti hain. Ek tree grow karo aur root ki taraf wires moto karo — fat-tree — jahan har switch ke $k$ children hain isliye tree $lo g_{k} N$ levels tall hai; ek packet shared ancestor tak climb karta hai aur wapas neeche aata hai, woh height do baar pay karta hai ( $2 lo g_{k} N$ ), aur kyunki wires har level upar double hoti hain, koi level bottleneck nahi hota, isliye poora $N$ roads worth bandwidth survive karta hai. Sab kuch strip karke ek single loop banao — ring — aur har cut hamesha sirf 2 roads touch karta hai, isliye yeh kabhi scale nahi karta. Yahi poora page hai: same dots, ek rule badlo, diameter aur bisection ko move hote dekho.