NUMA architectures: Exercises — Hinglish deep dive

6.1.7 · D4 · Hardware › Parallelism & Multicore › NUMA architectures

Intuition Is page ko kaise use karein

Ye problems ek ladder ki tarah chadhti hain. L1 sirf check karta hai ki tum words pehchante ho ya nahi. L5 tumse kehta hai ki ek system scratch se design karo. Har solution ek collapsible [!recall]- box ke andar chhupa hua hai — pehle problem try karo, phir reveal karo. Yahan ke saare numbers parent note NUMA architectures se seedhe aaye hain; agar koi term naya lage, us note ne use build kiya tha.

Jis ek tool par hum baar baar rely karte hain woh hai average-time law: $t_{a v g} = t_{l oc a l} [(1 - f) + f \cdot F_{N U M A}]$ jahan $f$ un memory accesses ka fraction hai jo remote hain aur $F_{N U M A} = t_{r e m o t e} / t_{l oc a l}$ NUMA factor hai. Hum yahi formula use karte hain, raw sum nahi, kyunki yeh "kitna door hai" ( $F_{N U M A}$ ) aur "kitni baar hota hai" ( $f$ ) — in dono knobs ko alag karta hai, jinhe tum actually control karte ho.

Prerequisites jo tum open rakhna chahoge: 6.1.05-memory-consistencymodels, 6.1.06-multicore-synchronization, 6.2.03-thread-scheduling, 6.3.01-parallel-algorithms.

Level 1 — Recognition

Exercise 1.1

Har phrase ko sahi term se match karo: (a) memory access time kabhi bhi location par depend nahi karta, (b) memory access time location par depend karta hai, (c) NUMA jisme nodes ke across hardware coherence ho. Options: UMA / SMP, NUMA, ccNUMA.

Recall Solution

(a) → UMA / SMP — Uniform ka matlab hai ek flat cost.
(b) → NUMA — Non-uniform: local fast, remote slow.
(c) → ccNUMA — "cc" hai cache-coherent: caches nodes ke across automatically sync rehti hain.

Kyun: poora subject ek sawaal par split hota hai — kya distance cost ko change karta hai? UMA kehta hai nahi, NUMA kehta hai haan, ccNUMA kehta hai haan aur tumhare liye caches ko honest bhi rakhta hai.

Exercise 1.2

Ek 4-node NUMA machine node 0 se ye latencies report karta hai: local 85 ns, remote 140 ns. Us remote node ke liye NUMA factor batao.

Recall Solution

NUMA factor by definition ratio $F_{N U M A} = t_{r e m o t e} / t_{l oc a l}$ hai. $F_{N U M A} = \frac{140}{85} = 1.647 \dots \approx 1.65$ Factor 1.0 ka matlab hoga "koi penalty nahi" (pure UMA). 1.0 se upar kuch bhi door shelf tak jaane ki cost hai.

Level 2 — Application

Exercise 2.1

Ek application apne 80% accesses locally karta hai. Local latency 85 ns hai, remote 140 ns hai. Average access time nikalo.

Recall Solution

80% local ka matlab hai remote fraction $f = 1 - 0.80 = 0.20$ hai. (Formula remote fraction ke terms mein likha gaya hai — inhe mix karo aur har baad ka problem drift karega.) $F_{N U M A} = \frac{140}{85} = 1.647$ $t_{a v g} = 85 [(1 - 0.20) + 0.20 \times 1.647] = 85 [0.80 + 0.329] = 85 \times 1.129 = 96.0 ns$ Directly: $0.80 \times 85 + 0.20 \times 140 = 68 + 28 = 96.0$ ns. Dono tarike agree karte hain — bracket form sirf direct sum ko $t_{l oc a l}$ se factor karke hai.

Exercise 2.2

Interleaved mapping $node_id = ⌊ A / L_{c a c h e l in e} ⌋ mod N_{n o d es}$ use karte hue, cache line size $L = 64$ bytes aur $N_{n o d es} = 4$ ke saath, byte address $A = 8320$ ko kaun sa node own karta hai?

Recall Solution

Step 1 — yeh byte kis cache line mein hai? Line size se divide karo aur remainder drop karo: $⌊ \frac{8320}{64} ⌋ = ⌊ 130 ⌋ = 130$ Step 2 — line 130 ko kaun sa node hold karta hai? Ise node count se modulo lo (interleaving lines ke across $0, 1, 2, 3, 0, 1, \dots$ cycle karta hai): $130 mod 4 = 2$ Toh address 8320 node 2 par rehta hai.

Kyun pehle floor phir mod: floor ek line ke saare 64 bytes ko ek line number mein collapse karta hai (ek poori line ek node par rehti hai), aur mod consecutive lines ko bandwidth ke liye nodes par round-robin spread karta hai.

Level 3 — Analysis

Exercise 3.1

$F_{N U M A} = 2.0$ ke liye, $f = 0.2$ aur $f = 0.05$ par all-remote baseline ke upar speedup $S = \frac{F _{N U M A}}{( 1 - f ) + f F _{N U M A}}$ compute karo. Gap ko interpret karo.

Recall Solution

$S$ measure karta hai ki tumhara mixed workload us disaster case se kitna fast hai jahan har access remote hoti hai. $f = 0.2$ par: $S = \frac{2.0}{0.8 + 0.2 \times 2.0} = \frac{2.0}{0.8 + 0.4} = \frac{2.0}{1.2} = 1.667$ $f = 0.05$ par: $S = \frac{2.0}{0.95 + 0.05 \times 2.0} = \frac{2.0}{0.95 + 0.10} = \frac{2.0}{1.05} = 1.905$ Interpretation: 80% local se 95% local jaane par sirf $1.905/1.667 = 1.14 \times$ zyada milta hai. Curve dekho (figure): yeh $f = 0$ ke paas bahut flat ho jaata hai. Remote traffic ke aakhiri kuch percent ko hataana expensive hai aur bahut kam extra deta hai — yeh wahi "last 5%" cost hai jo parent note ne flag ki thi.

Exercise 3.2

Do threads alag-alag nodes par baar baar alag 4-byte words likhte hain jo usi 64-byte cache line mein baithe hote hain. Ek local L3 miss 30 ns cost karta hai; ek 3-hop coherence bounce 300 ns cost karta hai. Agar, isko tune karne ke baad is cheez se bachne ke liye, har write 30 ns ka local hit hoti, toh is false sharing ki wajah se per-write slowdown kya hai?

Recall Solution

False sharing ka matlab hai do words logically independent hain par ek hi coherence unit (line) share karte hain. Har write doosre node ki copy ko invalidate kar deta hai, 3-hop bounce force karta hai: $slowdown = \frac{t _{b o u n ce}}{t _{l oc a l}} = \frac{300}{30} = 10 \times$ Kyun hota hai: coherence poori lines track karta hai, individual words nahi. Hardware nahi bata sakta ki do threads kabhi same bytes nahi touch karte — woh sirf same line ko ping-pong hote dekhta hai. Fix: har thread ke word ko apni khud ki cache line par pad karo (64 bytes align karo) taaki woh alag coherence units mein jaayein.

Level 4 — Synthesis

Exercise 4.1

Tumhare paas ek workload hai jisme $t_{l oc a l} = 85$ ns aur $F_{N U M A} = 2.0$ hai. Tumhara budget tumhe $t_{a v g}$ ko zyada se zyada 100 ns tak laane deta hai. Maximum remote fraction $f$ kya hai jo tum tolerate kar sakte ho?

Recall Solution

Average-time law ko budget ke barabar set karo aur $f$ ke liye solve karo: $85 [(1 - f) + 2.0 f] = 100$ $1 - f + 2 f = \frac{100}{85} = 1.17647$ $1 + f = 1.17647 ⟹ f = 0.17647$ Toh tum zyada se zyada ≈17.6% remote accesses allow kar sakte ho (≈82.4% local). Isse zyada loose karo aur tum 100 ns budget blow kar doge.

Kyun $f$ ke liye solve karein: design question ulta hai — "given a mix, what's the time?" nahi, balki "given a time target, what mix is allowed?" Same equation, rearranged. Yeh OS scheduler ko batata hai ki NUMA placement kitna aggressive hona chahiye.

Exercise 4.2

Matrix-multiply example mein, NUMA-unaware run 12 GB/s deta hai; first-touch + thread pinning ke baad yeh 45 GB/s hit karta hai. (a) Bandwidth speedup kya hai? (b) Agar compute ko 90 GB traffic chahiye, toh har version kitna wall-clock time leta hai, aur NUMA tuning ne kitna bachaya?

Recall Solution

(a) Speedup $= 45/12 = 3.75 \times$ . (b) Time = data ÷ bandwidth (bandwidth bytes per second mein hai, toh divide karne par seconds milte hain):

Unaware: $90/12 = 7.5$ s
Tuned: $90/45 = 2.0$ s
Bachaya: $7.5 - 2.0 = 5.5$ s.

Kyun first-touch ne fix kiya: OS ek page us node par allocate karta hai jiska thread use pehle write karta hai. Har thread ko apni rows pehle zero karwa ke, hum force karte hain ki $C [i]$ thread $i$ ke node par live kare — toh baad ki har write local hoti hai, aur interconnect bottleneck rehna band ho jaata hai.

Level 5 — Mastery

Exercise 5.1

Design target: ek 4-node ccNUMA server ko apne flagship app ke liye $t_{a v g} \leq 1.10 t_{l oc a l}$ rakhna hai. Measured $F_{N U M A} = 1.8$ hai. (a) Software ko kaunsi locality (local accesses ki percentage ke roop mein) achieve karni chahiye? (b) Agar profiling dikhaye ki app naturally sirf 70% local hit karta hai, toh parent note se do concrete mechanisms batao jo ise line ke upar push kar sakein, aur argue karo ki har ek kyun help karta hai.

Recall Solution

(a) $t_{a v g} \leq 1.10 t_{l oc a l}$ chahiye, matlab bracket $\leq 1.10$ : $(1 - f) + 1.8 f \leq 1.10$ $1 + 0.8 f \leq 1.10 ⟹ 0.8 f \leq 0.10 ⟹ f \leq 0.125$ Toh remote fraction zyada se zyada 12.5% hona chahiye, matlab ≥87.5% local.

(b) 70% local ( $f = 0.30$ ) se hume $f \leq 0.125$ tak pahunchna hai:

First-touch allocation — pages us node par land karte hain jis thread ne unhe pehle likha, toh ek thread ka working set local ban jaata hai. Remote accesses ko directly local mein convert karta hai.
Thread pinning numactl --cpunodebind --membind ke zariye — scheduler ko mid-run mein ek thread ko uske data se door migrate karne se rokta hai, jo silently local pages ko remote bana deta. First-touch ne jo affinity establish ki usse lock in karta hai.

Optionally, range-based address mapping (interleaved nahi) wahi hai jo first-touch ko possible banata hai, kyunki yeh OS ko ek thread ko ek contiguous local block dene deta hai.

Exercise 5.2

Prove karo ki speedup formula $S = \frac{F _{N U M A}}{( 1 - f ) + f F _{N U M A}}$ ka ek hard ceiling $F_{N U M A}$ hai, aur $f$ ki woh value batao jo ise attain karti hai. Phir, $F_{N U M A} = 1.8$ ke liye, best possible speedup do.

Recall Solution

$S$ tab sabse bada hota hai jab iska denominator sabse chhota ho. Denominator $(1 - f) + f F_{N U M A}$ $f$ mein ek straight line hai; kyunki $F_{N U M A} \geq 1$ hai, $f$ badhane se woh kabhi decrease nahi karta. Toh minimum denominator sabse chhote $f$ par hota hai, yaani $f = 0$ (sab local): $denominator = (1 - 0) + 0 = 1 ⟹ S_{ma x} = \frac{F _{N U M A}}{1} = F_{N U M A}$ Is tarah $S$ $F_{N U M A}$ se zyada nahi ho sakta, aur equality exactly $f = 0$ par milti hai (perfect locality). $F_{N U M A} = 1.8$ ke liye best possible speedup $1.8 \times$ hai.

Kyun yeh ceiling hai: baseline hai "sab remote." Absolute best jo tum kar sakte ho woh hai "sab local," jo $F_{N U M A}$ times fast hai — koi tuning physics ko nahi beat kar sakti.

Recall Self-test cloze

Average-time law mein do knobs hain ::: remote fraction $f$ aur NUMA factor $F_{N U M A}$ All-remote ke upar maximum possible speedup barabar hai ::: $F_{N U M A}$ , $f = 0$ par attain hota hai First-touch allocation ek page us node par rakhta hai jo ::: pehle usse write karta hai False sharing ping-pong karta hai kyunki coherence track karta hai ::: poori cache lines, individual words nahi