NUMA architectures

The Problem NUMA Solves

Why UMA fails at scale:

Single point of contention: All memory requests serialize through one controller
Bus saturation: Electrical bus cannot scale beyond ~4-8 processors physically
Cache coherence traffic: With more cores, coherence messages flood the interconnect
Latency insensitivity: Every access pays the same cost, no locality optimization

How NUMA Works

Definition NUMA Architecture

A NUMA system partitions physical memory into nodes, each with:

One or more processors (CPU dies or sockets)
A local memory bank (DRAM directly attached)
A memory controller integrated with the node
An interconnect (e.g., Intel QPI, AMD Infinity Fabric, HyperTransport) linking nodes

Key property: A processor can access any memory location, but: $t_{access} = \begin{cases} t_{local} & \text{if memory in same node} \\ t_{remote} & \text{if memory in different node} \end{cases}$

where $t_{remote} = t_{local} + t_{interconnect} + t_{remote\_controller}$ , typically $1.3$ x to $3$ x slower.

Derivation: Why Access Time Differs

Start from physical topology. In UMA: $t_{UMA} = t_{processor \to bus} + t_{bus\_arbitration} + t_{bus \to memory} + t_{memory\_access}$

All paths are symmetric, so $t_{UMA}$ is constant.

In NUMA with $N$ nodes:

Local access (processor0 → memory0): $t_{local} = t_{processor \to controller} + t_{DRAM\_access}$ No shared bus, no arbitration queue. This is the baseline.
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}$$ where $h$ is the number of hops in the interconnect topology (1 for direct link, more for mesh/torus).$

Why this matters: If $t_{interconnect}$ is 50 ns and $t_{local}$ is 80 ns, $t_{remote}$ might be 130-180 ns. This 2x penalty means algorithms must be NUMA-aware to keep data local.

NUMA Node Structure

Each node is effectively a mini-SMP:

Multiple cores share L3 cache and memory controller within the node
Cores within a node see uniform latency to that node's memory
The node ID is part of the physical address space partitioning

Formula Physical Address Mapping

A physical address $A$ is mapped to a node using interleaving or range-based schemes: Interleaved (cache-line granularity): $\text{node\_id} = \left\lfloor \frac{A}{L_{cacheline}} \right\rfloor \mod N_{nodes}$ Spreads consecutive addresses across nodes—good for bandwidth, bad for locality.

Range-based (OS allocates contiguous ranges per node): $\text{node\_id} = \begin{cases} 0 & 0 \leq A < S_{node} \\ 1 & S_{node} \leq A < 2S_{node} \\ \vdots \end{cases}$ where $S_{node}$ is the memory size per node. This enables affinity: OS can allocate memory from the node where the thread runs.

Why range-based is preferred: The OS can implement a first-touch policy—when a thread first writes a page, allocate it from the thread's node. This exploits temporal locality.

Cache Coherence in NUMA (ccNUMA)

Coherence Overhead Derivation

Consider a cache line accessed by processors on different nodes. In a directory-based protocol:

Each cache line has a home node (where the memory resides)
The directory tracks which nodes have cached copies

Cost of a remote read miss: $t_{miss} = t_{local\_cache\_lookup} + t_{directory\_lookup} + t_{remote\_read} + t_{data\_transfer}$

If the line is modified elsewhere (node 2): $t_{miss} = t_{directory} + t_{msg\_to\_node2} + t_{node2\_writeback} + t_{msg\_to\_node0} + t_{data\_transfer}$

This 3-hop protocol can take 200-400 ns—much worse than a local L3 miss (~30 ns). The key insight: false sharing (two threads on different nodes writing different words in the same cache line) causes ping-ponging with $O(N_{threads})$ coherence messages per write.

Worked example NUMA Latency Measurement

Setup: 4-node system, each node has 8 cores and 16 GB RAM. Measure lat_memrd from node 0 to all nodes:

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
Why the jumps?

Node 1: Direct QPI link from node 0 →1, adds interconnect latency (~55 ns).
Nodes 2-3: Indirect route (0 → 1 → 2), adds another hop (~25 ns) plus queuing. Application impact: A hash table lookup that randomly accesses remote nodes sees 1.8x average slowdown. If we pin the thread and allocate the hash table locally, we recover 1.0x latency.

Worked example NUMA-Aware Thread Placement

Problem: Parallel matrix multiplication $C = AB$ , where $A$ , $B$ , $C$ are $N \times N$ . 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];

Without NUMA awareness: OS might place thread $T_i$ on node 0, but allocate $C[i]$ on node 1 (first-touch by initialization thread). Every write to $C[i][j]$ is remote.

NUMA-aware fix:

Partition rows: Thread $T_i$ owns rows $[i \cdot R .. (i+1) \cdot R)$ of $C$ .

First-touch initialization:

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

This allocates

C[i]

on the node where thread

i

runs.

Pin threads: numactl --cpunodebind=0 --membind=0 to enforce affinity. Result: Bandwidth increases from 12 GB/s (remote-heavy) to 45 GB/s (all-local). Why this step? First-touch ensures memory is local. Without it, the OS round-robins allocations, defeating locality.

Performance Model: NUMA Factor

Formula NUMA Factor

Define the NUMA factor as the ratio of remote to local latency: $F_{NUMA} = \frac{t_{remote}}{t_{local}}$

For an application with fraction $f$ of remote accesses: $t_{avg} = t_{local} \left[ (1 - f) + f \cdot F_{NUMA} \right]$

Speedup over all-remote: $S = \frac{t_{local} \cdot F_{NUMA}}{t_{avg}} = \frac{F_{NUMA}}{(1-f) + f \cdot F_{NUMA}}$

Derivation: If all accesses were remote, $t_{all\_remote} = t_{local} \cdot F_{NUMA}$ . With mixed access: $t_{avg} = (1-f) t_{local} + f \cdot t_{remote} = t_{local}[(1-f) + f \cdot F_{NUMA}]$ Speedup is ratio of all-remote to mixed.

80/20 insight: If $f = 0.2$ (80% local) and $F_{NUMA} = 2.0$ , then: $S = \frac{2.0}{0.8 + 0.4} = 1.67\text{x}$ Achieving 80% locality gives 1.67x speedup. Push to 95% local ( $f=0.05$ ) and $S \approx 1.9$ x. The last5% of remote accesses still cost 10% performance.

OS and Runtime Support

When to use which:

First-touch + thread pining: Data-parallel workloads with static partitioning (HPC, databases).
Interleaving: Read-only shared data accessed uniformly (large lookup tables).
Explicit allocation: When you know the access pattern (graph partitioning, NUMA-aware allocators).

Common Mistakes

Common mistake False Sharing Across NUMA Nodes

Wrong idea: "I protected shared counters with padding to avoid false sharing in L1, I'm good."

Why it feels right: Padding eliminates intra-core cache line bouncing. On a single NUMA node, coherence traffic is fast.

The trap: Two threads on different nodes increment adjacent counters (even if paded to separate cache lines in L1/L2). Each increment:

Invalidates remote cache line (directory broadcast)
Triggers remote fetch
Bounces the line back on next increment

With $F_{NUMA}=2$ and a 3GHz core, you go from 3B increments/sec (L1 hit) to ~300M/sec (remote bounce). 10x slowdown.

Fix: Use per-node counters, then reduce:

__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;
}

Now each thread writes only to its own cache line, and summation is infrequent.

Connections

6.1.04-cache-coherence-protocols: NUMA extends coherence across nodes; directory protocols are essential for scalability.
6.1.05-memory-consistencymodels: NUMA does not change the consistency model (still TSO/SC), but reordering can make remote accesses more visible.
6.1.06-multicore-synchronization: Lock contention on NUMA is worse—a lock cache line bouncing across nodes pays2-3x penalty per acquire.
6.2.03-thread-scheduling: OS scheduler must be NUMA-aware to avoid migrating threads across nodes.
6.3.01-parallel-algorithms: Algorithms must partition data by NUMA node to scale (e.g., per-node hash tables, partitioned ques).

Recall Explain to a 12-Year-Old

You know how when you're at home, you can grab your toys from your room super fast? But if you want your friend's toy from their house across the street, you have to walk over there, ask, and walk back—takes way longer.

NUMA is like that for computers. Each processor has its own "room" with its own memory (RAM) right next to it. If it needs data from its own memory, it's super fast—like grabbing a toy from your shelf. But if it needs data from another processor's memory, it has to send a message across special wire (the interconnect), wait for the other processor to find it, then send it back. That takes 2-3 times longer.

So the trick is: keep your data in own "room." If you're doing math with some numbers, store those numbers in the memory that's closest to you. If everyone does that, the whole computer runs much faster, because nobody is waiting for stuff from far away. But if you're not careful and your data ends up in someone else's room by accident, suddenly everything is slow.

Flashcards

#flashcards/hardware

What does NUMA stand for and what is the key property? :: Non-Uniform Memory Access. Memory access time depends on the physical location of the memory relative to the processor—local memory is faster than remote memory.

Why does UMA (Uniform Memory Access) fail to scale beyond ~8-16 cores?

All cores share a single memory controller and bus, creating a bandwidth bottleneck. Effective bandwidth per core drops as

B_{eff} \approx B_{total}/N

, and coherence traffic saturates the interconnect.

In a NUMA system, what is the typical ratio of remote to local memory latency?

Typically

1.3

x to

3

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

What is the first-touch policy in NUMA?

When a thread first writes to a memory page (page fault), the OS allocates that page from the memory node where the thread is currently running, exploiting locality.

Derive the average memory access time in NUMA with fraction $f$ remote accesses :: $t_{avg} = (1-f) t_{local} + f \cdot t_{remote} = t_{local}[(1-f) + f \cdot F_{NUMA}]$ where $F_{NUMA} = t_{remote}/t_{local}$ .

What is ccNUMA?

Cache-coherent NUMA—hardware maintains cache coherence across NUMA nodes using protocols like directory-based MESI, providing a single shared address space.

Why does false sharing cause worse performance on NUMA than on UMA?

False sharing causes cache line ping-ponging. On NUMA, each transfer incurs remote latency (2-3x local), and coherence messages traverse the interconnect, multiplying the cost.

What are two strategies to reduce remote memory accesses in NUMA?

(1) Thread affinity: pin threads to specific nodes. (2) Memory affinity: allocate memory from the node where the thread runs (first-touch or explicit allocation).

When should you use interleaved memory allocation on NUMA?

For read-only or read-mostly shared data accessed uniformly by all cores, to maximize aggregate bandwidth by spreading load across all memory controllers.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

NUMA ka matlab hai Non-Uniform Memory Access—yani memory ka access time uniform nahi hai, depend karta hai ki memory processor ke kitne pas hai. Socho agar tumhare pas 4 sockets hain ek server mein, har socket ke pas apna local RAM hai. Agar ek CPU apne hi RAM se data read kare, toh woh bahut fast hai (80 nanoseconds). Lekin agar woh kisi dusre socket ke RAM se data mangaye, toh pehle message interconnect (jaise Intel QPI) pe jayega, phir woh dusra controller datahondega, phir wapas bhejega—total time 140-180 ns. Matlab 2x slow.

Ye problem tab ati hai jab tum bade systems pe kaam karte ho—jaise 64 cores, 4 NUMA nodes. Agar tumne threads ko randomly run karne diya aur memory bhi random allocate kar di, toh har thread ko apna data remote nodes se lena padega, aur throughput 2-3x drop ho jayega. Solution yeh hai ki tumhe "first-touch policy" use karni chahiye: jab thread pehli baar kisi page ko touch kare (write kare), toh OS us page ko us node pe allocate kare jahan thread chal raha hai. Isse locality maintain hoti hai.

Practical example: agar tum matrix multiplication kar rahe ho aur threads ko pin nahi kiya, toh data kisi aur node pe allocate ho sakta hai. Har access remote ho jayega aur bandwidth ghir jayega. Lekin agar tum "numactl" se threads aur memory dono ko ek hi node pe pin karo, toh sab local access ho jayega aur speed2-3x badh jayegi. NUMA mein 80/20 rule follow karo: 80% accesses local hone chahiye, tabhi performance achi milegi.

The Problem NUMA Solves

How NUMA Works

Derivation: Why Access Time Differs

NUMA Node Structure

Cache Coherence in NUMA (ccNUMA)

Coherence Overhead Derivation

Performance Model: NUMA Factor

OS and Runtime Support

Common Mistakes

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Parallelism & Multicore

Connections