Worked examples — NUMA architectures

This page is the drill hall for the NUMA topic note. The parent note built the theory; here we grind through every kind of number a NUMA question can throw at you. Before touching a single formula, we lay out a map of all the cases so you never meet a scenario cold.

Everything we use is already earned in the parent note, but we re-anchor each symbol the first time it appears, so a reader who jumped straight here still starts from zero.

Recall The three tools we reuse (from the parent)

NUMA factor $F_{NUMA}=\frac{t_{remote}}{t_{local}}$ — "how many times slower is far memory than near memory?" It is a plain ratio of two times, so it has no units (nanoseconds cancel nanoseconds). Average access time $t_{avg}=t_{local}\left[(1-f)+f{F}_{NUMA}\right]$ where $f$ is the fraction of accesses that go remote. Speedup vs all-remote $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}$. If any of these look strange, read NUMA architectures first — we do not re-derive them, we apply them.

---

The scenario matrix

Think of every NUMA numeric question as landing in exactly one cell below. Our examples (E1–E9) are placed so that every cell is hit at least once.

Cell	Case class	What is weird / extreme about it	Covered by
C1	Baseline mixed — normal $0<f<1$	the ordinary 80/20 world	E1
C2	Degenerate $f=0$ (all local)	remote term vanishes	E2
C3	Degenerate $f=1$ (all remote)	$t_{avg}$ hits its ceiling	E2
C4	Degenerate $F_{NUMA}=1$ (UMA)	NUMA collapses to uniform	E3
C5	Limiting $F_{NUMA}\to \infty$	remote is "infinitely" costly	E3
C6	Multi-node latency table (per-hop)	build $F_{NUMA}$ from a hop map	E4
C7	Address → node mapping (interleave vs range)	integer floor/mod, sign of address	E5
C8	Coherence 3-hop cost (false sharing)	add message times, not ratios	E6
C9	Real-world word problem (bandwidth GB/s)	translate latency win into throughput	E7
C10	Inverse question — solve for required $f$	algebra run backwards	E8
C11	Exam twist — mixed nodes, weighted $f$	$f$ itself is a weighted average	E9

---

E1 — Baseline mixed access (cell C1)

Forecast: guess the average — it's mostly local (80%), so expect $t_{avg}$ to sit closer to 80 than to 160. Jot down your guess.

1. Compute the NUMA factor. $F_{NUMA}=\frac{t_{remote}}{t_{local}}=\frac{160}{80}=2.0$ Why this step? $F_{NUMA}$ is the single number that says "remote is $2\times$ slower". Every later formula wants this ratio, not the raw times.

2. Plug into $t_{avg}$. $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}$ Why this step? We are averaging two costs weighted by how often each happens: $80\%$ of the time we pay $1.0\times$, $20\%$ of the time we pay $2.0\times$.

3. Compute the speedup over all-remote. $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}=\frac{2.0}{0.8+0.4}=\frac{2.0}{1.2}=1.67$ Why this step? All-remote would cost $80\times 2.0=160$ ns. Our $96$ ns is $160/96=1.67\times$ faster — the speedup is exactly the ratio of the two.

Verify: $160/96=1.667$, matching $S$. Units: $t_{avg}$ came out in ns (good, we multiplied a ns by a dimensionless bracket). $S$ is a pure ratio ($1.67$, no units). Your forecast — was $96$ closer to $80$ than $160$? Yes. ✓

---

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

Forecast: the two answers should be $80$ ns and $160$ ns — the extremes the average can never leave.

1. Set $f=0$. $t_{avg}=80[(1-0)+0\cdot 2]=80\times 1=80\text{ns}$ Why this step? When nothing is remote, the $f{F}_{NUMA}$ term is switched off. $t_{avg}$ collapses to pure $t_{local}$ — this is the floor.

2. Set $f=1$. $t_{avg}=80[(1-1)+1\cdot 2]=80\times 2=160\text{ns}$ Why this step? When everything is remote, the local term $(1-f)$ vanishes and we pay $t_{local}\cdot F_{NUMA}=t_{remote}$ every time — the ceiling.

3. Interpret the whole range as a straight line. For any $f$ in between, $t_{avg}$ is a straight line rising from $80$ ns (at $f=0$) up to $160$ ns (at $f=1$). The figure below makes this concrete.

Verify: the E1 result $f=0.2\Rightarrow 96$ ns must lie on this line: $80+(160-80)\times 0.2=80+16=96$. ✓ Floor $\le$ E1 $\le$ ceiling: $80\le 96\le 160$. ✓

---

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

Forecast: (a) if remote costs the same as local, NUMA-awareness should buy nothing → $S=1$. (b) if remote is unboundedly slow, the $20\%$ remote accesses dominate everything → $S$ should settle to a finite number, not infinity.

1. Part (a), set $F_{NUMA}=1$. $S=\frac{1}{(1-f)+f\cdot 1}=\frac{1}{(1-f)+f}=\frac{1}{1}=1$ Why this step? This is the sanity check that NUMA reduces to UMA when far and near cost the same — the $f$ cancels entirely, so $S=1$ for every $f$.

2. Part (b), take the limit $F_{NUMA}\to \infty$ with $f=0.2$. Divide top and bottom of $S$ by $F_{NUMA}$: $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$ Why this step? Dividing by the growing quantity turns the runaway term into $f$. The message: no matter how slow remote gets, keeping $80\%$ local caps your win at $1/f=5\times$. That $20\%$ remote is the anchor.

Verify: limit is $1/f=5$. Cross-check with a large finite value, $F_{NUMA}=1000$: $S=1000/(0.8+0.2\times 1000)=1000/200.8=4.98$, which is $\approx 5$. ✓ Part (a): plug $f=0.5$: $1/(0.5+0.5)=1$. ✓

---

E4 — Building $F_{NUMA}$ from a hop-latency table (cell C6)

Forecast: the "effective remote" time is the average of $140,165,168$ — around $158$ ns — so $F_{NUMA}$ is a bit under $2$.

1. Average the three remote latencies. $t_{remote}=\frac{140+165+168}{3}=\frac{473}{3}=157.67\text{ns}$ Why this step? "Evenly over nodes 1,2,3" means each remote access is equally likely to hit each — so the representative remote cost is the plain mean of the three.

2. Form the effective NUMA factor (local is node 0 = $85$ ns). $F_{NUMA}=\frac{157.67}{85}=1.855$ Why this step? $F_{NUMA}$ always compares whatever "remote" means against local. Here remote is the averaged remote.

3. Average access time with $f=0.3$. $t_{avg}=85[(1-0.3)+0.3\times 1.855]=85[0.7+0.5565]=85\times 1.2565=106.8\text{ns}$ Why this step? Same weighting as always — $70\%$ local at $85$ ns, $30\%$ remote at $\approx 158$ ns.

Verify: compute $t_{avg}$ the direct way: $0.7\times 85+0.3\times 157.67=59.5+47.3=106.8$ ns. Matches step 3. ✓ Units: ns throughout. Forecast: $F_{NUMA}=1.855$, indeed just under 2. ✓

---

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

Forecast: two different schemes, so probably two different node IDs for the same address — that's the whole point of the comparison.

1. Interleaved: which cache line is this? $\lfloor \frac{A}{L_{cacheline}}\rfloor =\lfloor \frac{20480}{64}\rfloor =320$ Why this step? Interleaving assigns whole cache lines round-robin, so first we ask "which line number is $A$ in?" The floor $\lfloor \rfloor$ throws away the byte offset inside the line (addresses are non-negative, so floor just drops the fraction — no sign trap here).

2. Interleaved: mod by node count. $\text{node\_id}=320\mathrm{mod}4=0$ Why this step? $\mathrm{mod}{N}_{nodes}$ wraps the line number around the 4 nodes: line 0→node0, line1→node1, …, line4→node0. Line 320 is a multiple of 4, so it lands on node 0.

3. Range-based: divide by node size. $\text{node\_id}=\lfloor \frac{A}{S_{node}}\rfloor =\lfloor \frac{20480}{16384}\rfloor =1$ Why this step? Range-based gives each node a contiguous block of $S_{node}$ bytes. $A=20480$ is past the first block ($0$–$16383$) but inside the second ($16384$–$32767$) → node 1.

4. Degenerate $A=0$. Interleaved: $\lfloor 0/64\rfloor \mathrm{mod}4=0$. Range: $\lfloor 0/16384\rfloor =0$. Both give node 0. Why this step? The lowest address always sits in node 0 under both schemes — a useful anchor to check your arithmetic direction.

Verify: interleaved node $=0$, range node $=1$ — genuinely different, confirming interleave scatters while range keeps locality (why range-based enables first-touch affinity). $A=0$ → node 0 both ways. ✓

---

E6 — Coherence 3-hop cost from false sharing (cell C8)

Forecast: we are adding message times (not multiplying ratios), so expect a big sum — a few hundred ns — far worse than the $30$ ns local miss.

1. Sum the 3-hop protocol stages. $t_{miss}=t_{dir}+t_{msg}+t_{wb}+t_{msg}+t_{xfer}$ $=20+55+30+55+40=200\text{ns}$ Why this step? Unlike latency ratios, coherence traffic is a chain of sequential events — each must finish before the next starts, so total time is their sum, not a product.

2. Compare to a local L3 miss. $\text{slowdown}=\frac{200}{30}=6.67\times$ Why this step? This ratio is the true cost of false sharing: the same logical operation is nearly $7\times$ slower because the line ping-pongs across the interconnect.

Verify: $20+55+30+55+40=200$. ✓ $200/30=6.67$. ✓ Units: all summands are ns → sum is ns; the slowdown is a pure ratio. Sanity: sum ($200$) sits in the "$200$–$400$ ns" range the parent quotes for 3-hop protocols. ✓

---

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

Forecast: $45$ is a bit under $4\times$ of $12$, so expect roughly a $3.7\times$ speedup and a runtime dropping from $30$ s to around $8$ s.

1. Bandwidth speedup. $\text{speedup}=\frac{45}{12}=3.75$ Why this step? For a bandwidth-bound kernel, throughput is the performance metric, so the ratio of the two GB/s figures is the speedup directly.

2. New runtime. A bandwidth-bound job moves a fixed amount of data $D$; time $=D/\text{bandwidth}$, so time scales inversely with bandwidth. $t_{new}=t_{old}\times \frac{12}{45}=30\times \frac{12}{45}=30\times 0.2667=8.0\text{s}$ Why this step? Same data, higher rate → proportionally less time. We multiply by the inverse bandwidth ratio because time and bandwidth are inversely related.

Verify: $t_{old}/t_{new}=30/8=3.75=$ the bandwidth speedup. ✓ Units: $\text{GB}/(\text{GB/s})=\text{s}$, so time comes out in seconds. Forecast: $3.75\times$, $8$ s — matches. ✓

---

E8 — Inverse question: what locality do I need? (cell C10)

Forecast: with remote $3\times$ slower and only a $25\%$ budget, the allowable remote fraction should be small — a rough one-in-eight kind of number.

1. Write the constraint using $t_{avg}$. $t_{local}[(1-f)+f{F}_{NUMA}]\le 1.25t_{local}$ Why this step? We want the average not to exceed $1.25\times$ local. Divide both sides by $t_{local}$ (positive, so the inequality direction is safe) to get a pure-number condition.

2. Simplify the bracket. $(1-f)+3f\le 1.25\Rightarrow 1+2f\le 1.25$ Why this step? Combine like terms: $(1-f)+3f=1+2f$. The $2f$ is exactly $(F_{NUMA}-1)f$, the "extra cost per unit of remote traffic".

3. Solve for $f$. $2f\le 0.25\Rightarrow f\le 0.125$ Why this step? Isolate $f$. The answer: no more than $12.5\%$ of accesses may be remote to stay within the $1.25\times$ budget.

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

---

E9 — Exam twist: $f$ as a weighted average across phases (cell C11)

Forecast: overall $f$ is between $0.10$ and $0.50$, pulled toward $0.10$ (since phase A weighs more) → guess about $0.22$.

1. Combine the two phases into one $f$. $f=w_A{f}_A+w_B{f}_B=0.70(0.10)+0.30(0.50)=0.07+0.15=0.22$ Why this step? $f$ is "fraction of all accesses that are remote". Since phases contribute accesses in proportion $w_A:w_B=0.7:0.3$, the overall remote fraction is their access-weighted average — you cannot just average $0.10$ and $0.50$.

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}$ Why this step? Once $f$ is a single number, the standard formula applies unchanged.

3. Speedup over all-remote. $S=\frac{F_{NUMA}}{(1-f)+f{F}_{NUMA}}=\frac{2.5}{0.78+0.55}=\frac{2.5}{1.33}=1.88$ Why this step? All-remote would be $80\times 2.5=200$ ns; $200/106.4=1.88$.

Verify: direct check $200/106.4=1.880$, matches $S$. ✓ Weighted $f$: $0.07+0.15=0.22$, and it lies between $0.10$ and $0.50$, pulled below the midpoint $0.30$ — consistent with phase A's larger weight. ✓ This weighting logic is exactly what NUMA-aware algorithm design optimizes: shrink the big-weight phase's $f$ first.

---

Recall Self-test (cover the answers)

Local $=100$ ns, remote $=250$ ns, $f=0.4$. Find $F_{NUMA}$. ::: $250/100=2.5$ Same numbers — find $t_{avg}$. ::: $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$ If $F_{NUMA}\to \infty$ with $f=0.25$, limiting speedup? ::: $1/f=4$