Worked examples — NUMA architectures

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

Yeh page NUMA topic note ka drill hall hai. Parent note ne theory build ki; yahan hum har tarah ke numbers grind karte hain jo ek NUMA question aap par throw kar sakta hai. Koi bhi formula touch karne se pehle, hum saare cases ka ek map lay out karte hain taaki aap koi bhi scenario se kabhi cold na milo.

Jo kuch bhi hum use karte hain woh parent note mein already earn ho chuka hai, lekin hum har symbol ko pehli baar re-anchor karte hain, taaki ek reader jo seedha yahan jump kiya ho woh bhi zero se start kare.

Recall Teen tools jo hum reuse karte hain (parent se)

NUMA factor $F_{NUMA}=\frac{t_{remote}}{t_{local}}$ — "far memory, near memory se kitni times slow hai?" Yeh do times ka plain ratio hai, isliye iska koi unit nahi (nanoseconds cancel ho jaate hain). Average access time $t_{avg}=t_{local}\left[(1-f)+f{F}_{NUMA}\right]$ jahan $f$ un accesses ka fraction hai jo remote jaate hain. Speedup vs all-remote $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}$. Agar inme se koi strange lage, pehle NUMA architectures padho — hum inhe re-derive nahi karte, hum inhe apply karte hain.

---

Scenario matrix

Har NUMA numeric question ko neeche exactly ek cell mein girta hua socho. Hamare examples (E1–E9) is tarah place kiye gaye hain ki har cell kam se kam ek baar hit ho.

Cell	Case class	Isme kya weird / extreme hai	Covered by
C1	Baseline mixed — normal $0<f<1$	ordinary 80/20 duniya	E1
C2	Degenerate $f=0$ (sab local)	remote term vanish ho jaata hai	E2
C3	Degenerate $f=1$ (sab remote)	$t_{avg}$ apni ceiling hit karta hai	E2
C4	Degenerate $F_{NUMA}=1$ (UMA)	NUMA uniform ho jaata hai	E3
C5	Limiting $F_{NUMA}\to \infty$	remote "infinitely" costly hai	E3
C6	Multi-node latency table (per-hop)	$F_{NUMA}$ ek hop map se build karo	E4
C7	Address → node mapping (interleave vs range)	integer floor/mod, address ka sign	E5
C8	Coherence 3-hop cost (false sharing)	message times add karo, ratios nahi	E6
C9	Real-world word problem (bandwidth GB/s)	latency win ko throughput mein translate karo	E7
C10	Inverse question — required $f$ ke liye solve karo	algebra backwards run	E8
C11	Exam twist — mixed nodes, weighted $f$	$f$ khud ek weighted average hai	E9

---

E1 — Baseline mixed access (cell C1)

Forecast: average guess karo — yeh mostly local hai (80%), isliye expect karo $t_{avg}$ 80 ke zyada paas hoga, 160 ke nahi. Apna guess likh lo.

1. NUMA factor compute karo. $F_{NUMA}=\frac{t_{remote}}{t_{local}}=\frac{160}{80}=2.0$ Yeh step kyun? $F_{NUMA}$ woh single number hai jo kehta hai "remote $2\times$ slower hai". Baad ke har formula ko yeh ratio chahiye, raw times nahi.

2. $t_{avg}$ mein plug karo. $t_{avg}=t_{local}[(1-f)+f{F}_{NUMA}]=80[(1-0.2)+0.2\times 2.0]$ $=80[0.8+0.4]=80\times 1.2=96\text{ns}$ Yeh step kyun? Hum do costs ko average kar rahe hain jitni baar each hoti hai: $80\%$ time hum $1.0\times$ pay karte hain, $20\%$ time hum $2.0\times$ pay karte hain.

3. All-remote par speedup compute karo. $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}=\frac{2.0}{0.8+0.4}=\frac{2.0}{1.2}=1.67$ Yeh step kyun? All-remote $80\times 2.0=160$ ns cost karta. Hamara $96$ ns $160/96=1.67\times$ faster hai — speedup exactly dono ka ratio hai.

Verify: $160/96=1.667$, $S$ se match. Units: $t_{avg}$ ns mein aaya (sahi, humne ek ns ko ek dimensionless bracket se multiply kiya). $S$ ek pure ratio hai ($1.67$, koi unit nahi). Tumhara forecast — kya $96$ $80$ ke zyada paas tha ya $160$ ke? Haan. ✓

---

E2 — Dono degenerate ends: $f=0$ aur $f=1$ (cells C2, C3)

Forecast: dono answers $80$ ns aur $160$ ns honge — woh extremes jinhe average kabhi nahi chhodta.

1. $f=0$ set karo. $t_{avg}=80[(1-0)+0\cdot 2]=80\times 1=80\text{ns}$ Yeh step kyun? Jab kuch bhi remote nahi, $f{F}_{NUMA}$ term switch off ho jaata hai. $t_{avg}$ pure $t_{local}$ mein collapse ho jaata hai — yeh floor hai.

2. $f=1$ set karo. $t_{avg}=80[(1-1)+1\cdot 2]=80\times 2=160\text{ns}$ Yeh step kyun? Jab sab kuch remote hai, local term $(1-f)$ vanish ho jaata hai aur hum har baar $t_{local}\cdot F_{NUMA}=t_{remote}$ pay karte hain — yeh ceiling hai.

3. Poori range ko ek straight line ki tarah interpret karo. Beech ke kisi bhi $f$ ke liye, $t_{avg}$ ek straight line hai jo $80$ ns (at $f=0$) se $160$ ns (at $f=1$) tak jaati hai. Neeche ki figure yeh concrete banati hai.

Verify: E1 result $f=0.2\Rightarrow 96$ ns is line par hona chahiye: $80+(160-80)\times 0.2=80+16=96$. ✓ Floor $\le$ E1 $\le$ ceiling: $80\le 96\le 160$. ✓

---

E3 — Do aur degenerate knobs: $F_{NUMA}=1$ aur $F_{NUMA}\to \infty$ (cells C4, C5)

Forecast: (a) agar remote utna hi cost karta hai jitna local, toh NUMA-awareness kuch bhi nahi khareedti → $S=1$. (b) agar remote unboundedly slow hai, toh $20\%$ remote accesses sab kuch dominate karte hain → $S$ ek finite number par settle hona chahiye, infinity nahi.

1. Part (a), $F_{NUMA}=1$ set karo. $S=\frac{1}{(1-f)+f\cdot 1}=\frac{1}{(1-f)+f}=\frac{1}{1}=1$ Yeh step kyun? Yeh sanity check hai ki NUMA UMA mein reduce ho jaata hai jab far aur near same cost karte hain — $f$ completely cancel ho jaata hai, isliye $S=1$ har $f$ ke liye.

2. Part (b), $f=0.2$ ke saath limit $F_{NUMA}\to \infty$ lo. $S$ ke top aur bottom ko $F_{NUMA}$ se divide karo: $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}=\frac{1}{\frac{1-f}{F_{NUMA}}+f}\stackrel{F_{NUMA}\to \infty }{\to }\frac{1}{0+f}=\frac{1}{f}=\frac{1}{0.2}=5$ Yeh step kyun? Growing quantity se divide karna runaway term ko $f$ mein turn karta hai. Message yeh hai: remote chahe kitना bhi slow ho jaaye, $80\%$ local rakhna tumhara win $1/f=5\times$ par cap karta hai. Woh $20\%$ remote anchor hai.

Verify: limit $1/f=5$ hai. Large finite value se cross-check karo, $F_{NUMA}=1000$: $S=1000/(0.8+0.2\times 1000)=1000/200.8=4.98$, jo $\approx 5$ hai. ✓ Part (a): $f=0.5$ plug karo: $1/(0.5+0.5)=1$. ✓

---

E4 — Hop-latency table se $F_{NUMA}$ build karna (cell C6)

Forecast: "effective remote" time $140,165,168$ ka average hai — around $158$ ns — isliye $F_{NUMA}$ thoda $2$ se kam hoga.

1. Teen remote latencies average karo. $t_{remote}=\frac{140+165+168}{3}=\frac{473}{3}=157.67\text{ns}$ Yeh step kyun? "Nodes 1,2,3 par evenly" ka matlab hai har remote access equally likely hai har ek ko hit karne ke liye — isliye representative remote cost teen ka plain mean hai.

2. Effective NUMA factor banao (local node 0 = $85$ ns hai). $F_{NUMA}=\frac{157.67}{85}=1.855$ Yeh step kyun? $F_{NUMA}$ hamesha "remote" ka matlab jo bhi ho usse local se compare karta hai. Yahan remote averaged remote hai.

3. $f=0.3$ ke saath average access time. $t_{avg}=85[(1-0.3)+0.3\times 1.855]=85[0.7+0.5565]=85\times 1.2565=106.8\text{ns}$ Yeh step kyun? Same weighting jaise hamesha — $70\%$ local at $85$ ns, $30\%$ remote at $\approx 158$ ns.

Verify: $t_{avg}$ direct way se compute karo: $0.7\times 85+0.3\times 157.67=59.5+47.3=106.8$ ns. Step 3 se match. ✓ Units: poora ns mein. Forecast: $F_{NUMA}=1.855$, indeed just under 2. ✓

---

E5 — Address → node mapping: interleave vs range (cell C7)

Forecast: do alag schemes, isliye probably same address ke liye do alag node IDs — yahi comparison ka poora point hai.

1. Interleaved: yeh kaun si cache line hai? $\lfloor \frac{A}{L_{cacheline}}\rfloor =\lfloor \frac{20480}{64}\rfloor =320$ Yeh step kyun? Interleaving poori cache lines round-robin assign karta hai, isliye pehle hum poochte hain "$A$ konse line number mein hai?" Floor $\lfloor \rfloor$ line ke andar byte offset throw kar deta hai (addresses non-negative hain, isliye floor sirf fraction drop karta hai — yahan koi sign trap nahi).

2. Interleaved: node count se mod karo. $\text{node\_id}=320\mathrm{mod}4=0$ Yeh step kyun? $\mathrm{mod}{N}_{nodes}$ line number ko 4 nodes par wrap karta hai: line 0→node0, line1→node1, …, line4→node0. Line 320 ek multiple of 4 hai, isliye node 0 par land karta hai.

3. Range-based: node size se divide karo. $\text{node\_id}=\lfloor \frac{A}{S_{node}}\rfloor =\lfloor \frac{20480}{16384}\rfloor =1$ Yeh step kyun? Range-based har node ko $S_{node}$ bytes ka ek contiguous block deta hai. $A=20480$ pehle block ($0$–$16383$) se past hai lekin doosre mein ($16384$–$32767$) → node 1.

4. Degenerate $A=0$. Interleaved: $\lfloor 0/64\rfloor \mathrm{mod}4=0$. Range: $\lfloor 0/16384\rfloor =0$. Dono node 0 dete hain. Yeh step kyun? Lowest address hamesha dono schemes ke under node 0 mein baith ta hai — ek useful anchor apni arithmetic direction check karne ke liye.

Verify: interleaved node $=0$, range node $=1$ — genuinely different, confirming karta hai ki interleave scatter karta hai jabki range locality rakhta hai (isliye range-based first-touch affinity enable karta hai). $A=0$ → dono taraf node 0. ✓

---

E6 — False sharing se Coherence 3-hop cost (cell C8)

Forecast: hum message times add kar rahe hain (ratios multiply nahi), isliye expect karo ek bada sum — kuch sau ns — $30$ ns local miss se kaafi zyada bura.

1. 3-hop protocol stages sum karo. $t_{miss}=t_{dir}+t_{msg}+t_{wb}+t_{msg}+t_{xfer}$ $=20+55+30+55+40=200\text{ns}$ Yeh step kyun? Latency ratios se alag, coherence traffic sequential events ki ek chain hai — har ek ko agle se pehle khatam hona chahiye, isliye total time unka sum hai, product nahi.

2. Local L3 miss se compare karo. $\text{slowdown}=\frac{200}{30}=6.67\times$ Yeh step kyun? Yeh ratio false sharing ki true cost hai: same logical operation nearly $7\times$ slower hai kyunki line interconnect par ping-pong karta hai.

Verify: $20+55+30+55+40=200$. ✓ $200/30=6.67$. ✓ Units: saare summands ns hain → sum ns hai; slowdown ek pure ratio hai. Sanity: sum ($200$) parent ke 3-hop protocols ke liye quote kiye "$200$–$400$ ns" range mein hai. ✓

---

E7 — Real-world word problem: locality se bandwidth (cell C9)

Forecast: $45$ thoda $12$ ke $4\times$ se kam hai, isliye roughly $3.7\times$ speedup expect karo aur runtime $30$ s se $8$ s ke around drop hoga.

1. Bandwidth speedup. $\text{speedup}=\frac{45}{12}=3.75$ Yeh step kyun? Bandwidth-bound kernel ke liye, throughput hi performance metric hai, isliye do GB/s figures ka ratio directly speedup hai.

2. New runtime. Ek bandwidth-bound job fixed amount of data $D$ move karta hai; time $=D/\text{bandwidth}$, isliye time bandwidth ke inversely scale karta hai. $t_{new}=t_{old}\times \frac{12}{45}=30\times \frac{12}{45}=30\times 0.2667=8.0\text{s}$ Yeh step kyun? Same data, zyada rate → proportionally kam time. Hum inverse bandwidth ratio se multiply karte hain kyunki time aur bandwidth inversely related hain.

Verify: $t_{old}/t_{new}=30/8=3.75=$ bandwidth speedup. ✓ Units: $\text{GB}/(\text{GB/s})=\text{s}$, isliye time seconds mein aata hai. Forecast: $3.75\times$, $8$ s — matches. ✓

---

E8 — Inverse question: mujhe kaunsi locality chahiye? (cell C10)

Forecast: remote $3\times$ slower hone ke saath aur sirf $25\%$ budget ke saath, allowable remote fraction chhota hona chahiye — roughly one-in-eight jaisa number.

1. $t_{avg}$ use karke constraint likho. $t_{local}[(1-f)+f{F}_{NUMA}]\le 1.25t_{local}$ Yeh step kyun? Hum chahte hain average $1.25\times$ local se zyada na ho. Dono sides ko $t_{local}$ se divide karo (positive hai, isliye inequality direction safe hai) ek pure-number condition paane ke liye.

2. Bracket simplify karo. $(1-f)+3f\le 1.25\Rightarrow 1+2f\le 1.25$ Yeh step kyun? Like terms combine karo: $(1-f)+3f=1+2f$. $2f$ exactly $(F_{NUMA}-1)f$ hai, "remote traffic ki har unit par extra cost".

3. $f$ ke liye solve karo. $2f\le 0.25\Rightarrow f\le 0.125$ Yeh step kyun? $f$ isolate karo. Answer: $1.25\times$ budget ke andar rehne ke liye $12.5\%$ se zyada accesses remote nahi ho sakte.

Verify: $f=0.125$ back plug karo: $t_{avg}/t_{local}=1+2(0.125)=1.25$ — exactly ceiling. ✓ Forecast ne "one-in-eight" kaha tha aur $0.125=1/8$. ✓

---

E9 — Exam twist: phases par weighted average ke roop mein $f$ (cell C11)

Forecast: overall $f$ $0.10$ aur $0.50$ ke beech hai, $0.10$ ki taraf pulled (kyunki phase A zyada weigh karta hai) → guess around $0.22$.

1. Do phases ko ek $f$ mein combine karo. $f=w_A{f}_A+w_B{f}_B=0.70(0.10)+0.30(0.50)=0.07+0.15=0.22$ Yeh step kyun? $f$ "saare accesses ka woh fraction jo remote hain" hai. Kyunki phases $w_A:w_B=0.7:0.3$ proportion mein accesses contribute karte hain, overall remote fraction unka access-weighted average hai — tum sirf $0.10$ aur $0.50$ average nahi kar sakte.

2. Average access time. $t_{avg}=80[(1-0.22)+0.22\times 2.5]=80[0.78+0.55]=80\times 1.33=106.4\text{ns}$ Yeh step kyun? Jab $f$ ek single number ho jaata hai, standard formula unchanged apply hota hai.

3. All-remote par speedup. $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}=\frac{2.5}{0.78+0.55}=\frac{2.5}{1.33}=1.88$ Yeh step kyun? All-remote $80\times 2.5=200$ ns hota; $200/106.4=1.88$.

Verify: direct check $200/106.4=1.880$, $S$ se match. ✓ Weighted $f$: $0.07+0.15=0.22$, aur yeh $0.10$ aur $0.50$ ke beech hai, midpoint $0.30$ se neeche pulled — phase A ke bade weight ke saath consistent. ✓ Yeh weighting logic exactly wahi hai jo NUMA-aware algorithm design optimize karta hai: bade-weight phase ka $f$ pehle shrink karo.

---

Recall Self-test (answers cover karo)

Local $=100$ ns, remote $=250$ ns, $f=0.4$. $F_{NUMA}$ find karo. ::: $250/100=2.5$ Same numbers — $t_{avg}$ find karo. ::: $100[(0.6)+0.4(2.5)]=100(1.6)=160$ ns Interleaved: $A=4096$, line $=64$, nodes $=8$. Node? ::: $\lfloor 4096/64\rfloor \mathrm{mod}8=64\mathrm{mod}8=0$ Agar $F_{NUMA}\to \infty$ with $f=0.25$, limiting speedup? ::: $1/f=4$