NUMA architectures — Hinglish notes

6.1.7 · Hardware › Parallelism & Multicore

Intuition NUMA Kyun Exist Karta Hai

Ek classroom imagine karo jahan har student ko books access karni hain. Uniform Memory Access (UMA) ek central bookshelf ki tarah hai—sab queue mein lagte hain, bottleneck banta hai. NUMA har student ko uski apni nearby shelf dene jaisa hai, lekin zaroorat padne par doosri shelves tak ja bhi sakte hain. Non-Uniform Memory Access ka matlab hai memory access time is baat par depend karta hai ki memory processor ke relative kahan hai—local fast hai, remote slow hai.

Jab systems 8-16 cores se zyada scale hote hain, ek single shared bus ek bandwidth bottleneck ban jaata hai. NUMA isko solve karta hai har processor (ya cores ke group) ko uska apna local memory bank deke, jo ek high-speed interconnect ke zariye connected hota hai. Key insight yeh hai: zyaatar memory accesses local hone chahiye (80/20 principle).

Woh Problem Jo NUMA Solve Karta Hai

UMA scale par kyun fail karta hai:

Single point of contention: Saare memory requests ek controller se serialize hote hain
Bus saturation: Electrical bus physically ~4-8 processors se zyada scale nahi kar sakta
Cache coherence traffic: Zyada cores ke saath, coherence messages interconnect ko flood kar dete hain
Latency insensitivity: Har access same cost pay karta hai, koi locality optimization nahi

NUMA Kaise Kaam Karta Hai

Derivation: Access Time Alag Kyun Hoti Hai

Physical topology se shuru karte hain. UMA mein: $t_{U M A} = t_{p r ocessor \to b u s} + t_{b u s_a r bi t r a t i o n} + t_{b u s \to m e m or y} + t_{m e m or y_a ccess}$

Saare paths symmetric hain, isliye $t_{U M A}$ constant hai.

$N$ nodes wale NUMA mein:

Local access (processor0 → memory0): $t_{l oc a l} = t_{p r ocessor \to co n t r o l l er} + t_{D R A M_a ccess}$ Koi shared bus nahi, koi arbitration queue nahi. Yeh baseline hai.
Remote access (processor 0 → memory 1):
$t_{remote} &= t_{processor\_0 \to interconnect} \\ &\quad + t_{interconnect\_hop} \times h\\ &\quad + t_{node\_1controller} \\ &\quad + t_{DRAM\_access} \\ &\quad + t_{data\_return} \end{align}$$ Jahan $h$ interconnect topology mein hops ki number hai (direct link ke liye 1, mesh/torus ke liye zyada).$

Yeh kyun matter karta hai: Agar $t_{in t er co nn ec t}$ 50 ns hai aur $t_{l oc a l}$ 80 ns hai, toh $t_{r e m o t e}$ 130-180 ns ho sakta hai. Yeh 2x penalty matlab hai ki algorithms ko data local rakhne ke liye NUMA-aware hona chahiye.

NUMA Node Structure

Har node effectively ek mini-SMP hai:

Node ke andar multiple cores L3 cache aur memory controller share karte hain
Ek node ke andar ke cores us node ki memory ko uniform latency se dekhte hain
Node ID physical address space partitioning ka hissa hota hai

Range-based prefer kyun hota hai: OS ek first-touch policy implement kar sakta hai—jab ek thread pehli baar ek page mein write karta hai, use thread ke node se allocate karo. Yeh temporal locality exploit karta hai.

NUMA Mein Cache Coherence (ccNUMA)

Coherence Overhead Derivation

Ek cache line consider karo jise alag nodes par processors access karte hain. Ek directory-based protocol mein:

Har cache line ka ek home node hota hai (jahan memory rehti hai)
Directory track karta hai ki kaunse nodes ne copies cache ki hain

Remote read miss ki cost: $t_{mi ss} = t_{l oc a l_c a c h e_l oo k u p} + t_{d i r ec t or y_l oo k u p} + t_{r e m o t e_r e a d} + t_{d a t a_t r an s f er}$

Agar line kahin aur (node 2 par) modified hai: $t_{mi ss} = t_{d i r ec t or y} + t_{m s g_t o_n o d e 2} + t_{n o d e 2_w r i t e ba c k} + t_{m s g_t o_n o d e 0} + t_{d a t a_t r an s f er}$

Yeh 3-hop protocol 200-400 ns le sakta hai—local L3 miss (~30 ns) se kaafi bura. Key insight: false sharing (alag nodes par do threads same cache line mein alag words write karte hain) causes ping-ponging with $O (N_{t h r e a d s})$ coherence messages per write.

Worked example NUMA Latency Measurement

Setup: 4-node system, har node mein 8 cores aur 16 GB RAM hain. Node 0 se sabhi nodes tak lat_memrd measure karo:

Target Node	Latency (ns)	Ratio
0 (local)	85	1.0x
1 (1 hop)	140	1.65x
2 (2 hops)	165	1.94x
3 (2 hops)	168	1.98x
Jumps kyun?

Node 1: Node 0 →1 se direct QPI link, interconnect latency add hoti hai (~55 ns).
Nodes 2-3: Indirect route (0 → 1 → 2), ek aur hop add hota hai (~25 ns) plus queuing. Application impact: Ek hash table lookup jo randomly remote nodes access karta hai use average 1.8x slowdown dikhti hai. Agar hum thread pin karein aur hash table locally allocate karein, toh 1.0x latency recover ho jaati hai.

Worked example NUMA-Aware Thread Placement

Problem: Parallel matrix multiplication $C = A B$ , jahan $A$ , $B$ , $C$ $N \times N$ hain. Naive OpenMP code:

#pragma omp parallel for
for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    for (int k = 0; k < N; k++)
      C[i][j] += A[i][k] * B[k][j];

NUMA awareness ke bina: OS thread $T_{i}$ ko node 0 par place kar sakta hai, lekin $C [i]$ ko node 1 par allocate kare (initialization thread ka first-touch). $C [i] [j]$ par har write remote hoti hai.

NUMA-aware fix:

Rows partition karo: Thread $T_{i}$ $C$ ki rows $[i \cdot R .. (i + 1) \cdot R)$ own karta hai.

First-touch initialization:

#pragma omp parallel for
for (int i = 0; i < N; i++)
  C[i][0] = 0;  // Each thread touches its own rows

Yeh

C [i]

us node par allocate karta hai jahan thread

i

run karta hai.

Threads pin karo: numactl --cpunodebind=0 --membind=0 affinity enforce karne ke liye. Result: Bandwidth 12 GB/s (remote-heavy) se 45 GB/s (all-local) tak badhti hai. Yeh step kyun? First-touch ensure karta hai ki memory local hai. Iske bina, OS allocations round-robin karta hai, locality defeat ho jaati hai.

Performance Model: NUMA Factor

80/20 insight: Agar $f = 0.2$ (80% local) aur $F_{N U M A} = 2.0$ , toh: $S = \frac{2.0}{0.8 + 0.4} = 1.67 x$ 80% locality achieve karna 1.67x speedup deta hai. 95% local tak push karo ( $f = 0.05$ ) aur $S \approx 1.9$ x. Remote accesses ka last 5% abhi bhi 10% performance cost karta hai.

OS aur Runtime Support

Kab kaun sa use karein:

First-touch + thread pinning: Static partitioning wale data-parallel workloads (HPC, databases).
Interleaving: Uniformly access ki jaane wali read-only shared data (large lookup tables).
Explicit allocation: Jab tumhe access pattern pata ho (graph partitioning, NUMA-aware allocators).

Common Mistakes

Common mistake NUMA Nodes Ke Across False Sharing

Galat soch: "Maine shared counters ko L1 mein false sharing se bachane ke liye padding se protect kiya, main set hoon."

Yeh sahi kyun lagta hai: Padding intra-core cache line bouncing eliminate karta hai. Ek single NUMA node par, coherence traffic fast hoti hai.

Trap: Alag nodes par do threads adjacent counters increment karte hain (chahe L1/L2 mein alag cache lines mein padded ho). Har increment:

Remote cache line invalidate karta hai (directory broadcast)
Remote fetch trigger karta hai
Next increment par line wapas bounce karta hai

$F_{N U M A} = 2$ aur 3GHz core ke saath, tum 3B increments/sec (L1 hit) se ~300M/sec (remote bounce) par aa jaate ho. 10x slowdown.

Fix: Per-node counters use karo, phir reduce karo:

__thread int local_count;  // Thread-local, no sharing
void count() {
  local_count++;  // Pure L1, no coherence
}
int global_sum() {
  int sum = 0;
  for_each_thread(t)
    sum += t->local_count;
  return sum;
}

Ab har thread sirf apni cache line mein write karta hai, aur summation infrequent hoti hai.

Connections

6.1.04-cache-coherence-protocols: NUMA coherence ko nodes ke across extend karta hai; directory protocols scalability ke liye essential hain.
6.1.05-memory-consistencymodels: NUMA consistency model nahi badalta (still TSO/SC), lekin reordering remote accesses ko zyada visible bana sakta hai.
6.1.06-multicore-synchronization: NUMA par lock contention worse hoti hai—nodes ke across bounce karne wala ek lock cache line har acquire par 2-3x penalty pay karta hai.
6.2.03-thread-scheduling: OS scheduler ko NUMA-aware hona chahiye taaki threads nodes ke across migrate na ho.
6.3.01-parallel-algorithms: Algorithms ko scale karne ke liye NUMA node ke anusaar data partition karna chahiye (jaise per-node hash tables, partitioned queues).

Recall Ek 12-Saal Ke Bacche Ko Samjhao

Jaante ho jab tum ghar par hote ho, toh apne room se apne toys super fast grab kar sakte ho? Lekin agar tumhe apne dost ka toy chahiye jo saamne wale ghar mein hai, toh tumhe wahan jaana padega, maangna padega, aur wapas aana padega—kaafi zyada time lagta hai.

Computers ke liye NUMA waisa hi hai. Har processor ka apna "room" hota hai jisme uske paas apni memory (RAM) hoti hai. Agar use apni memory se data chahiye, toh super fast hota hai—jaise apni shelf se toy uthana. Lekin agar use doosre processor ki memory se data chahiye, toh use ek special wire (interconnect) ke zariye message bhejna padta hai, doosre processor ke find karne ka wait karna padta hai, phir wapas bhejana padta hai. Woh 2-3 times zyada time leta hai.

Toh trick yeh hai: apna data apne "room" mein rakhho. Agar tum kuch numbers ke saath math kar rahe ho, toh woh numbers us memory mein store karo jo tumhare sabse paas hai. Agar sab aisa karein, toh poora computer kaafi faster chalata hai, kyunki koi bhi door se kuch aane ka wait nahi kar raha. Lekin agar tum dhyan nahi rakhte aur tumhara data galti se kisi aur ke room mein chala jaata hai, toh achanak sab kuch slow ho jaata hai.

Flashcards

#flashcards/hardware

NUMA ka full form kya hai aur key property kya hai? :: Non-Uniform Memory Access. Memory access time processor ke relative memory ki physical location par depend karta hai—local memory remote memory se faster hoti hai.

UMA (Uniform Memory Access) ~8-16 cores se zyada scale kyun fail karta hai?

Saare cores ek single memory controller aur bus share karte hain, bandwidth bottleneck create karta hai. Effective bandwidth per core drop hoti hai

B_{e f f} \approx B_{t o t a l} / N

ke saath, aur coherence traffic interconnect ko saturate kar deti hai.

NUMA system mein remote aur local memory latency ka typical ratio kya hai?

Typically

1.3

x se

3

x slower. For example, local = 80 ns, remote = 140-240 ns depending on hops.

NUMA mein first-touch policy kya hai?

Jab ek thread pehli baar kisi memory page mein write karta hai (page fault), OS us page ko us memory node se allocate karta hai jahan thread currently run kar raha hai, locality exploit karta hai.

NUMA mein $f$ fraction remote accesses ke saath average memory access time derive karo :: $t_{a v g} = (1 - f) t_{l oc a l} + f \cdot t_{r e m o t e} = t_{l oc a l} [(1 - f) + f \cdot F_{N U M A}]$ jahan $F_{N U M A} = t_{r e m o t e} / t_{l oc a l}$ .

ccNUMA kya hai?

Cache-coherent NUMA—hardware directory-based MESI jaise protocols use karke NUMA nodes ke across cache coherence maintain karta hai, ek single shared address space provide karta hai.

False sharing NUMA par UMA se worse performance kyun cause karta hai?

False sharing cache line ping-ponging cause karta hai. NUMA par, har transfer remote latency incur karta hai (2-3x local), aur coherence messages interconnect traverse karte hain, cost multiply hoti hai.

NUMA mein remote memory accesses reduce karne ke liye do strategies kya hain?

(1) Thread affinity: threads ko specific nodes par pin karo. (2) Memory affinity: memory us node se allocate karo jahan thread run karta hai (first-touch ya explicit allocation).

NUMA par interleaved memory allocation kab use karni chahiye?

Read-only ya read-mostly shared data ke liye jo sabhi cores uniformly access karte hain, saare memory controllers mein load spread karke aggregate bandwidth maximize karne ke liye.