Exercises — NUMA architectures

• (a) → UMA / SMP — Uniform means one flat cost.
• (b) → NUMA — Non-uniform: local fast, remote slow.
• (c) → ccNUMA — the "cc" is cache-coherent: caches stay in sync automatically across nodes.

Why: the whole subject splits on one question — does distance change the cost? UMA says no, NUMA says yes, ccNUMA says yes and keeps caches honest for you.

The NUMA factor is by definition the ratio $F_{NUMA}=t_{remote}/t_{local}$. $F_{NUMA}=\frac{140}{85}=1.647\dots \approx 1.65$ A factor of 1.0 would mean "no penalty" (pure UMA). Anything above 1.0 is the cost of walking to a farther shelf.

80% local means the remote fraction is $f=1-0.80=0.20$. (The formula is written in terms of remote fraction — mix these up and every later problem drifts.) $F_{NUMA}=\frac{140}{85}=1.647$ $t_{avg}=85[(1-0.20)+0.20\times 1.647]=85[0.80+0.329]=85\times 1.129=96.0\text{ns}$ Directly: $0.80\times 85+0.20\times 140=68+28=96.0$ ns. Both routes agree — the bracket form is just the direct sum factored by $t_{local}$.

Step 1 — which cache line is this byte in? Divide by the line size and drop the remainder: $\lfloor \frac{8320}{64}\rfloor =\lfloor 130\rfloor =130$ Step 2 — which node holds line 130? Take it modulo the node count (interleaving cycles $0,1,2,3,0,1,\dots$ across lines): $130\mathrm{mod}4=2$ So address 8320 lives on node 2.

Why floor then mod: the floor collapses all 64 bytes of a line to one line number (a whole line lives on one node), and the mod spreads consecutive lines round-robin across nodes for bandwidth.

$S$ measures how much faster your mixed workload is compared to the disaster case where every access is remote. At $f=0.2$: $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$ At $f=0.05$: $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: going from 80% local to 95% local only buys $1.905/1.667=1.14\times$ more. Look at the curve (figure): it flattens hard near $f=0$. The final few percent of remote traffic are expensive to remove and give little extra — this is the "last 5%" cost the parent note flagged.

False sharing means the two words are logically independent but share a coherence unit (the line). Every write invalidates the other node's copy, forcing a 3-hop bounce: $\text{slowdown}=\frac{t_{bounce}}{t_{local}}=\frac{300}{30}=10\times$ Why it happens: coherence tracks whole lines, not words. The hardware can't tell the two threads never touch the same bytes — it only sees the same line ping-ponging. Fix: pad each thread's word onto its own cache line (align to 64 bytes) so they land in different coherence units.

Set the average-time law equal to the budget and solve for $f$: $85[(1-f)+2.0f]=100$ $1-f+2f=\frac{100}{85}=1.17647$ $1+f=1.17647⟹f=0.17647$ So you may allow up to ≈17.6% remote accesses (≈82.4% local). Any looser and you blow the 100 ns budget.

Why solve for $f$: the design question is inverted — not "given a mix, what's the time?" but "given a time target, what mix is allowed?" Same equation, rearranged. This tells the OS scheduler how aggressive its NUMA placement must be.

(a) Speedup $=45/12=3.75\times$. (b) Time = data ÷ bandwidth (bandwidth is bytes per second, so dividing gives seconds):

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

Why first-touch fixed it: the OS allocates a page on the node whose thread first writes it. By making each thread zero its own rows first, we force $C[i]$ to live on thread $i$'s node — so every later write is local, and the interconnect stops being the bottleneck.

(a) Require $t_{avg}\le 1.10t_{local}$, i.e. the bracket $\le 1.10$: $(1-f)+1.8f\le 1.10$ $1+0.8f\le 1.10⟹0.8f\le 0.10⟹f\le 0.125$ So remote fraction must be at most 12.5%, i.e. ≥87.5% local.

(b) From 70% local ($f=0.30$) we must reach $f\le 0.125$:

1. First-touch allocation — pages land on the node of the thread that first writes them, so a thread's working set becomes local. Directly converts remote accesses to local ones.
2. Thread pinning via numactl --cpunodebind --membind — stops the scheduler from migrating a thread away from its data mid-run, which would silently turn local pages remote. Locks in the affinity that first-touch established.

Optionally, range-based address mapping (not interleaved) is what makes first-touch possible, since it lets the OS hand a thread a contiguous local block.

$S$ is largest when its denominator is smallest. The denominator $(1-f)+f{F}_{NUMA}$ is a straight line in $f$; since $F_{NUMA}\ge 1$, increasing $f$ never decreases it. So the minimum denominator occurs at the smallest $f$, namely $f=0$ (all local): $\text{denominator}=(1-0)+0=1⟹S_{max}=\frac{F_{NUMA}}{1}=F_{NUMA}$ Thus $S$ cannot exceed $F_{NUMA}$, and equality holds exactly at $f=0$ (perfect locality). For $F_{NUMA}=1.8$ the best possible speedup is $\boxed{1.8\times }$.

Why this is the ceiling: the baseline is "all remote." The absolute best you can do is "all local," which is $F_{NUMA}$ times faster — no tuning can beat physics.

The two knobs in the average-time law are ::: the remote fraction $f$ and the NUMA factor $F_{NUMA}$ The maximum possible speedup over all-remote equals ::: $F_{NUMA}$, attained at $f=0$ First-touch allocation places a page on the node that ::: first writes to it False sharing ping-pongs because coherence tracks ::: whole cache lines, not individual words