Network-on-Chip (NoC) topologies — Hinglish notes

6.3.6 · Hardware › Interconnects, Buses & SoC

Core Intuition

Traditional buses 2-8 cores ke liye kaam karti hain, lekin usse aage contention (multiple cores ka bus ke liye larna) aur wire delay (signals ko chip cross karne mein multiple cycles lagte hain) performance ko khatam kar deti hain. NoC yeh problems solve karta hai:

Parallelism: Multiple packets alag-alag links par simultaneously travel karte hain
Locality: Data nearby routers se route hota hai, jisse hops kam hote hain
Scalability: Cores add karne se network collapse nahi hota

Figure — Network-on-Chip (NoC) topologies

Fundamental Concepts

Chip Par Packet-Switching Kyun?

Zaroorat ki Derivation:

Wire delay dominate karta hai modern tech nodes mein: 7nm par ek 10mm wire ko signal propagate karne mein ~20 cycles lagte hain.
Shared bus bandwidth: $B_{bus} = f \cdot w$ (frequency × wire width). 64 cores ke liye jo 2GHz par 128-bit bus share kar rahe hain: $2 GHz \cdot 128 b = 256 Gb/s$ total, toh 4 Gb/s per core—bahut kam hai.
Dedicated point-to-point links linearly scale karte hain: Har router-router link full bandwidth provide karta hai, aur multiple links parallel mein operate karti hain.

Major NoC Topologies

1. Mesh (2D Grid)

Ye formulas kyun hain?

Diameter: Worst case corner-to-opposite corner hai. Ek $N \times M$ grid mein, tum ek dimension mein $(N - 1)$ steps aur doosre mein $(M - 1)$ steps chalte ho. Koi diagonal moves nahi, isliye $D = (N - 1) + (M - 1)$ .
Bisection bandwidth: Grid ko half mein kato. Smaller dimension decide karta hai kitne links cut cross karte hain. Ek $4 \times 4$ mesh mein, vertically kaatne se 4 links kat jaati hain.

Pros: Simple layout, 2D chip floorplan se match karta hai, easy routing (XY-routing). Cons: High diameter → door ke nodes ke liye high latency. Edge nodes ka degree kam → asymmetric performance.

2. Torus (Wraparound Mesh)

Diameter ki Derivation: Torus mein, tum "wrap around" kar sakte ho. Ek $N \times N$ torus ke liye, sabse door ka node har dimension mein $⌊ N /2 ⌋$ distance par hai (agar $> N /2$ ho toh wrap karo). Example: $8 \times 8$ torus, node (0,0) se (7,7) tak. 14 hops (mesh) ki jagah, (0,0) → (0, -1≡7) 1 hop mein jao, phir (4,7) tak 4 hops, phir (7,7) tak 3 = 8 hops. Actually, $⌊ 8/2 ⌋ + ⌊ 8/2 ⌋ = 8$ .

Pros: Lower diameter, higher bisection BW, symmetric (sabhi nodes equal). Cons: Wraparound wires lambi hoti hain (poore chip edge cross karti hain) → zyada power, harder physical layout.

3. Hypercube

Derivation: Nodes ko 0 se $2^{k} - 1$ tak binary mein label karo. Node $i = b_{k - 1} b_{k - 2} \dots b_{0}$ node $i \oplus 2^{j}$ se connect hota hai (bit $j$ flip karo). Example: 4D hypercube ( $k = 4$ , 16 nodes). Node 5 = 0101 in connect karta hai:

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

Diameter: Koi bhi node kisi bhi doosre node tak at most $k$ bits flip karke pahunch sakta hai (Hamming distance ≤ $k$ ).

Pros: Logarithmic diameter (best scalability). High bisection BW. Cons: Degree $N$ ke saath badhta hai → complex routers. Non-planar (2D silicon mein lay out karna mushkil).

4. Fat-Tree

"Fat" kyun? Traditional trees root par bottleneck create karte hain (saara traffic ek link se funnel hota hai). Fat-tree har level upar jaane par link bandwidth double karta hai. Ek binary tree ke liye jisme $N$ leaves hain:

Level 0 (leaves): Har link = $B$
Level 1: Links = $2 B$
Level 2: Links = $4 B$
Root: Link = $N B /2$

Yeh sabhi cuts mein constant bisection bandwidth maintain karta hai.

Pros: High bandwidth, fault-tolerant (root tak multiple paths). Cons: Area/power poorly scale karta hai (root switches bahut bade). Deep hierarchy → latency.

5. Ring

Diameter = $⌊ N /2 ⌋$ kyun? Worst case: Ring ka opposite side. Ek 10-node ring mein, node 0 se node 5 tak 5 hops hain (clockwise ya counter-clockwise). $N$ nodes ke liye, max = $⌊ N /2 ⌋$ .

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

Comparative Analysis

Topology	Diameter	Bisection BW	Degree	Best For
Mesh	$O (N^{1/2})$	$O (N^{1/2})$	4	2D chips, balanced cost
Torus	$O (N^{1/2} /2)$	$O (N^{1/2})$	4	Lower latency, uniform traffic
Hypercube	$O (lo g N)$	$O (N)$	$O (lo g N)$	High performance, non-planar OK
Fat-Tree	$O (lo g N)$	$O (N)$	Varies	Datacenters, bandwidth-critical
Ring	$O (N)$	$O (1)$	2	Low-cost, light traffic

Common Mistakes

Design Trade-Offs

Latency vs. Throughput

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

Power vs. Performance

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

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

Yeh kyun matter karta hai: Lambi links (torus wraparound, fat-tree root) mein high $C$ hota hai → high $P_{link}$ . Hypercube mein zyada routers hote hain → high $N_{routers}$ . Mesh dono ko minimize karta hai.

Scalability

Mesh/Torus: 100s of nodes tak scale karte hain (Intel ka 72-core Xeon Phi 2D mesh use karta hai).
Hypercube: Hard limit ~1024 nodes (10-port routers impractical hain).
Ring: 8-10 nodes ke baad dead hai (bisection BW collapse).

Real-World Examples

Intel Xeon Phi (Knights Landing): 72 cores, 2D mesh NoC. Har tile = core + L2 cache slice + router. 2D layout, reasonable diameter (max 18 hops), 4-port routers ke liye mesh choose kiya.
Tilera TILE-Gx: 64 cores, 8×8 mesh. XY-routing (pehle X phir Y jao) deadlock-free deterministic paths ke liye.
AMD Ryzen (Infinity Fabric): Pure NoC nahi, lekin chiplet designs mein die-to-die links ke liye mesh-inspired topology use karta hai.
Nvidia GPUs: Internal interconnect SM (streaming multiprocessor) clusters ke liye torus jaisi hai—symmetric latency ke liye wraparound.

Active Recall Practice

Recall Ek 12-Saal Ke Bachche Ko Samjhao

Socho tumhara chip ek sheher hai jisme 64 mohalle (cores) hain. Tumhe unke beech chitthi (data) bhejna hai. Ek bus ek aisi sarak hai jise sab share karte hain—traffic jam! Ek NoC poora road network hai. Topology woh map hai: roads kaise connect hoti hain.

Mesh: Grid mein roads, jaise sheher ke blocks. Simple, lekin corner se corner door hai.
Torus: Grid + secret tunnels (wraparound)—distance aadha ho jaata hai!
Hypercube: Har mohalle mein un mohallono ke shortcuts hain jinke "address" mein 1 bit ka fark hai. Super fast, lekin har jagah kai roads chahiye.
Fat-Tree: Roads "downtown" hub ki taraf jaate-jaate wider hoti jaati hain, toh downtown kabhi jam nahi hota.
Ring: Ek bada loop. Sasta, lekin loop ka opposite side slow hai.

Sabse acha map depend karta hai: Tumhare paas kitni jagah hai? Kitna power? Kya sabhi mohalle equally baat karte hain, ya kuch zyada baat karte hain? Chip designers woh map choose karte hain jo unki zarooratein poori kare!

Connections

Bus Architectures: NoC scale par shared buses ko replace karta hai.
Cache Coherence Protocols: NoC coherence messages (snoops, invalidations) route karta hai.
Routing Algorithms: NoC packet paths ke liye XY, adaptive, deadlock avoidance.
System-on-Chip (SoC) Design: NoC modern SoCs ki backbone hai.
Power Management in SoCs: NoC links idle hone par power-gate ho sakti hain.
Latency and Throughput Trade-offs: NoC topology directly dono ko impact karta hai.

#flashcards/hardware

Network-on-Chip (NoC) kya hota hai? :: Ek packet-switched on-chip interconnect jahan cores/memory routers aur links ke zariye connect hote hain, traditional buses ke baad parallel data transfer aur scalable communication enable karta hai.

NoC topologies ke key metrics kya hain?

Hop count (traverse kiye gaye routers), bisection bandwidth (cut ke across max data), diameter (kisi bhi do nodes ke beech max hops), degree (router per links).

N \times M

mesh ka diameter formula kya hai?

D = (N - 1) + (M - 1)

, kyunki worst case corner-to-corner Manhattan distance hai jisme koi diagonal moves nahi hote.

Torus diameter mesh se kaise compare karta hai?

Torus diameter

⌊ N /2 ⌋ + ⌊ M /2 ⌋

mesh diameter se roughly aadha hota hai kyunki wraparound links shortcuts create karti hain.

2 GHz par 64-bit links wale 4×4 mesh ki bisection bandwidth kya hai?

B_{b} = 4 \cdot 64 b \cdot 2 GHz = 512 Gb/s

(midline cut ko 4 links cross karti hain).

Torus mein mesh se zyada bisection BW kyun hoti hai?

Torus mein bisection BW double hoti hai kyunki wraparound links cross-cut paths add karti hain:

B_{b} = 2 \cdot min (N, M) \cdot B_{link}

N

nodes wale hypercube ki degree kya hoti hai?

Degree =

k = lo g_{2} (N)

, kyunki har node un nodes se connect hota hai jo

k

dimensions mein ek bit flip se different hain.

Hypercube ka diameter kya hota hai?

D = lo g_{2} (N)

, kyunki koi bhi do nodes at most

k

bits mein differ karte hain, aur sabhi differing bits flip karne ke liye

k

hops chahiye.

Hypercube connections kaise determine hote hain?

Node

i

node

i \oplus 2^{j}

se connect hota hai

j = 0, 1, \dots, k - 1

ke liye (har bit position ek baar flip karo).

Hypercube topology ka main disadvantage kya hai?

Non-planar layout (2D silicon par map karna mushkil) aur degree $N$ ke saath badhta hai (1024 nodes ke liye 10+ ports), jisse routers complex aur expensive ho jaate hain.

Fat-tree "fat" kyun hota hai?

Links root ki taraf wider (zyada bandwidth) hoti jaati hain, har level par double hoti hain taaki bottlenecks na aayein: root link =

N \cdot B_{link} /2

Fat-tree ka diameter kya hota hai?

D = 2 lo g_{k} (N)

(

k

-ary tree levels se root tak upar hop karo, phir destination tak neeche).

Ring ki bisection bandwidth kya hoti hai?

B_{b} = 2 \cdot B_{link}

(kisi bhi cut ko sirf 2 links cross karti hain, jo ise ek severe bottleneck banata hai).

Ring topology 8 nodes ke baad rarely kyun use hoti hai?

Diameter

O (N)

aur bisection BW

O (1)

hone ki wajah se

N

badhne par severe congestion hoti hai; saara cross-traffic 2 links share karta hai.

Mesh topology ka main advantage kya hai?

Silicon floorplan se match karta hua simple 2D layout, moderate diameter/bisection BW, aur sirf 4-port routers (low cost).

Torus wraparound links ki hidden cost kya hai?

Ye poore chip edges span karti hain (10+ mm), high capacitance, power drain, aur repeaters/upper metal layers ki zaroorat cause karti hain.

Fat-tree sabhi bottlenecks eliminate kyun nahi karta?

Yeh root bottleneck prevent karta hai lekin hot-spot (many-to-one) traffic nahi rokta, jahan destination ka last-hop link abhi bhi sirf

B

capacity ka hota hai.

NoC power equation kya hai?

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

, jahan

P_{link} \propto C \cdot V^{2} \cdot f \cdot α

Intel Xeon Phi kaun sa NoC topology use karta hai?

2D mesh (72 cores, 8×9 grid), 2D layout, reasonable diameter (max 18 hops), aur 4-port routers ke liye choose kiya gaya.

XY-routing kya hota hai?

Mesh/torus ke liye ek deterministic routing algorithm: packets pehle X dimension mein, phir Y mein move karte hain, cyclic dependencies avoid karke deadlock rokta hai.