vault

Cache-Conscious and NUMA-Aware Parallelism

15 min read

Cache-Conscious and NUMA-Aware Parallelism

Parallel code rarely fails to scale because it runs out of cores — it fails because it runs out of memory system. Modern processors compute far faster than they can fetch operands from DRAM (the memory wall), so the performance of a parallel program is usually decided by how well it exploits the cache hierarchy and how it places data across the machine’s memory nodes, not by raw arithmetic throughput. Cache-conscious parallelism is the discipline of arranging data and access patterns so cores work out of fast local caches instead of stalling on memory, and NUMA-aware parallelism extends the same idea to whole machines where physical RAM is partitioned into nodes with non-uniform access cost (NUMA). This note is the language-agnostic theory of that discipline — locality, cache-line ownership, false sharing, cache-aware vs cache-oblivious algorithms, and first-touch NUMA placement. The concrete kernel and hardware mechanisms it points at — NUMA Memory Model, Cache Coherence and the Store Buffer, Memory Alignment and False Sharing — live elsewhere in the vault and are cross-linked, not restated.

Mental Model — The Roofline and the Memory Hierarchy

The single most useful frame is the Roofline model of Williams, Waterman, and Patterson (2009), which plots attainable performance against a kernel’s arithmetic intensity — its ratio of useful work to memory traffic, in floating-point operations per byte moved (Roofline model).

flowchart LR
    subgraph R["Roofline: attainable = min(peak compute, bandwidth × intensity)"]
        MB["Memory-bound region<br/>low arithmetic intensity<br/>limited by DRAM bandwidth"]
        RIDGE["Ridge point<br/>intensity where the two<br/>ceilings meet"]
        CB["Compute-bound region<br/>high arithmetic intensity<br/>limited by peak FLOP/s"]
        MB --> RIDGE --> CB
    end
    L["Data layout &<br/>cache blocking<br/>(cut memory traffic)"] -->|"raises intensity →<br/>moves kernel right"| RIDGE

What it shows and the insight to take: the attainable performance of a kernel is P = min(π, β × I) — the smaller of the machine’s peak compute π (in FLOP/s) and the product of peak memory bandwidth β and the kernel’s arithmetic intensity I (Roofline model). Walk the formula: if I is small (few operations per byte fetched), the β × I term dominates and the kernel is memory-bound — the cores idle waiting on DRAM, and adding cores or wider vectors buys nothing. If I is large, π dominates and the kernel is compute-bound — now more cores and SIMD help. The ridge point is the intensity at which the two ceilings meet: below it you are memory-limited, above it compute-limited. The entire discipline of cache-conscious parallelism is the leftward-pointing arrow’s inverse: by reducing memory traffic (blocking, better layout, reuse), you raise arithmetic intensity and slide the kernel rightward off the bandwidth roof toward the compute roof where parallelism actually pays. The take-away: most parallel kernels start memory-bound, and the win comes from feeding the cores, not from adding them.

Why Locality Is the Whole Game

The memory wall is not rhetoric — it is a widening gap between processor speed and DRAM latency documented since the 1990s and laid out in detail in Ulrich Drepper’s “What Every Programmer Should Know About Memory” (Drepper 2007). A cache miss to main memory costs on the order of hundreds of processor cycles; an L1 hit costs a handful. The hardware bridges this gap with a cache hierarchy (L1 per core, L2 per core or per pair, a shared last-level L3) that keeps recently and nearby-used data close. Software’s job is to make the hierarchy’s bets pay off, which comes down to exploiting two kinds of locality:

  • Temporal locality — if you touch a datum, you will likely touch it again soon, so keep it resident. This is what loop blocking (below) exploits: reuse a block while it is hot in cache before moving on.
  • Spatial locality — if you touch an address, you will likely touch its neighbors, so the hardware fetches a whole cache line (typically 64 bytes) at once. Sequential, unit-stride access rides this for free; scattered access wastes most of every line fetched.

Cache operates at the granularity of the cache line, not the individual variable, and that granularity is the source of both the biggest wins (spatial locality) and the nastiest parallel bug in this space (false sharing). A parallel program that streams contiguous memory with high reuse can approach peak bandwidth; one that chases pointers or strides randomly can spend 90% of its cycles stalled, and no number of threads fixes a design that is bottlenecked on the memory bus they all share.

Cache-Line Ownership and False Sharing

The interaction of caching with parallelism introduces a failure mode that has no single-threaded analog. Under a cache-coherence protocol (MESI/MOESI — see Cache Coherence and the Store Buffer), a cache line can be held in a Modified/Exclusive state by at most one core at a time; before a core can write a line, it must acquire exclusive ownership via a Request For Ownership (RFO) that invalidates every other core’s copy. When two cores repeatedly write the same line, ownership ping-pongs between them, each write dragging the line across the interconnect.

False sharing is when this happens even though the two cores are logically touching different data — two independent variables that merely happen to land on the same 64-byte line (false sharing). There is no real data dependency, no correctness issue, and no shared variable a programmer would recognize — yet the coherence protocol behaves as if the threads were fighting over one location, forcing the line to reload on every access. The Wikipedia measurement makes the magnitude concrete: on a 12th-gen Intel Core i7, contended false sharing ran roughly 50× slower than the padded version (false sharing). The classic instance is an array of per-thread counters, counts[tid]++, where all counters share a line — a “parallel” loop that runs slower than serial. The fixes are padding/alignment so each thread’s hot data occupies its own line (alignas(64) in C++, cache-line-sized padding structs), and restructuring so per-thread state is genuinely separated. Diagnosis on Linux uses perf c2c (“cache-to-cache”), which pinpoints lines suffering coherence contention. The vault’s Memory Alignment and False Sharing note walks the concrete Go realization (sync.Pool padding, the CacheLinePad idiom) — cross-link, don’t duplicate.

The mirror image of false sharing is true sharing contention: a genuinely shared hot variable (a global counter, a lock word) that every core writes. That is a real dependency, not an accident of layout, and its remedy is algorithmic — sharding the counter, per-CPU accumulation, or a lock-free design — treated in Scalability Bottlenecks and Contention.

Cache-Aware versus Cache-Oblivious Algorithms

Given that locality is the game, there are two philosophies for writing algorithms that respect the cache hierarchy.

A cache-aware (equivalently cache-conscious) algorithm is tuned with explicit knowledge of the cache parameters — line size and cache capacity — and reshapes its work to fit. The canonical technique is loop tiling (also loop blocking or cache blocking): partition the iteration space into blocks sized so the working set of each block fits in cache, then finish all reuse of a block while it is resident before moving on (loop tiling). Dense matrix multiplication is the textbook case: the naïve triple loop re-streams the entire B matrix N times, hammering memory; blocking the loops so a sub-block of A and B stay cache-resident cuts the number of times each element is fetched from DRAM by a factor proportional to the block dimension, converting a memory-bound kernel into a compute-bound one (loop tiling). The block size is a hardware-specific tuning parameter: too large and it spills the cache (or the registers), too small and reuse is under-exploited. The strength of cache-aware code is peak performance on the machine it was tuned for; its weakness is that the tuning is fragile — an optimal L1 block size on one CPU is wrong on the next generation, and you may need separate parameters per cache level.

A cache-oblivious algorithm, by contrast, achieves near-optimal cache behavior without the line size B or the cache size M appearing anywhere in the code — the seminal result of Frigo, Leiserson, Prokop, and Ramachandran in 1999 (cache-oblivious algorithm). The trick is recursive divide-and-conquer: keep subdividing the problem until, at some level of the recursion, the subproblem happens to fit in whatever cache the machine has — automatically, at every level of a multi-level hierarchy at once. Analysis uses the idealized-cache model: a two-level memory with blocks of size B, a fully associative cache of M objects with optimal replacement, and the tall-cache assumption M = Ω(B²); performance is counted in cache misses rather than instructions (cache-oblivious algorithm). Cache-oblivious matrix transpose and multiply, and cache-oblivious sorts like funnelsort, hit the same asymptotic cache-miss bounds as the best cache-aware algorithms, e.g. O(1 + mn/B) misses for transpose, but with a single portable implementation. The honest trade-off: cache-oblivious code carries constant-factor overhead from recursion and often loses to a well-tuned cache-aware kernel when data fits in RAM, while winning when data spills to a slower level (disk, remote memory) where portability across the hierarchy matters most (cache-oblivious algorithm).

Uncertain

Verify: the specific cache-miss bounds (e.g. O(1 + mn/B) for cache-oblivious transpose, funnelsort’s O((N/B)·log_{M/B}(N/B))) and the exact tall-cache condition M = Ω(B²). Reason: these come from an encyclopedic summary of the Frigo et al. 1999 paper, not the primary paper itself (the FOCS/ACM PDF was not fetched during this task). To resolve: read Frigo, Leiserson, Prokop & Ramachandran, “Cache-Oblivious Algorithms” (FOCS 1999 / ACM TALG 2012) directly. #uncertain

NUMA — Locality at the Machine Scale

On a multi-socket (or large multi-core) server, “main memory” is not one uniform pool. Under Non-Uniform Memory Access (NUMA), RAM is partitioned across nodes, each attached to a subset of cores, and a core reaches its own node’s memory faster and with more bandwidth than a remote node’s memory across the inter-socket interconnect (NUMA). The ratio of remote to local access cost is the NUMA factor or distance. Real coherent-NUMA (ccNUMA) hardware keeps caches consistent across nodes, but the article warns that ccNUMA “may perform poorly when multiple processors attempt to access the same memory area in rapid succession” — i.e., cross-node coherence traffic is expensive (NUMA). The vault’s NUMA Memory Model covers the kernel data structures (per-node pglist_data, zonelists) in depth; here the concern is the parallel-programming consequence.

The load-bearing policy is first-touch allocation: the operating system does not commit a physical page when memory is malloc’d, but when it is first written, and it places that page on the node of the CPU that did the first write. This has a decisive, often surprising, implication for parallel code. If a single master thread initializes a large array (memset, or a serial init loop) and then forks worker threads to process it in parallel, all the pages were first-touched by the master and live on one node — so every worker on every other node pays remote-access cost, and they all contend on that one node’s memory controller. The fix is to parallelize the initialization the same way you parallelize the computation, so each thread first-touches the pages it will later work on, landing them on its own node. This “initialize in parallel” rule is the single most important NUMA-awareness technique and the reason a NUMA-oblivious omp parallel for over a serially-initialized array can run at a fraction of its potential.

Uncertain

Verify: that first-touch is the default page-placement policy on mainstream Linux (as opposed to interleave or an explicit numactl policy), and the precise “on first write” trigger. Reason: the NUMA Wikipedia page did not state first-touch quantitatively, and this claim is drawn from general HPC/OpenMP knowledge rather than a primary kernel/OpenMP source fetched in this task. To resolve: confirm against the Linux numa(7)/set_mempolicy(2) man pages and the existing NUMA Memory Policies note. #uncertain

The second NUMA lever is affinity / pinning. If the scheduler is free to migrate a thread to a core on a different node than its data, first-touch placement is wasted — the thread now runs remote to its own pages. Thread pinning binds a thread to a specific core or node (Linux sched_setaffinity, numactl --cpunodebind, taskset, OpenMP’s OMP_PROC_BIND/OMP_PLACES), and memory binding (numactl --membind, set_mempolicy) pins allocation to a node. Together they keep a worker and its data co-resident. The vault’s CPU Affinity and sched_setaffinity and NUMA Memory Policies notes are the concrete instances. The alternative policy — interleaving pages round-robin across all nodes (numactl --interleave=all) — deliberately spreads a shared, uniformly-accessed dataset so no single node’s controller becomes the bottleneck; it trades away best-case local latency for worst-case-avoidance and is the right choice for large shared structures with no clean per-thread partition.

Data Layout — Structure-of-Arrays and Alignment

Locality is not only about access order; it is baked into data layout. The recurring decision is Array-of-Structures (AoS) versus Structure-of-Arrays (SoA). AoS stores each logical record contiguously (struct particle { float x,y,z,mass; } arr[N]); SoA stores each field in its own array (float x[N], y[N], z[N], mass[N]). When a parallel/vectorized kernel touches only one field of every record — say it sums all the masses — AoS wastes most of every cache line (it drags x, y, z along for nothing) and defeats vectorization (the masses are strided, not contiguous), whereas SoA packs the accessed field densely, streams it at full bandwidth, and vectorizes cleanly. This is precisely where cache-conscious layout meets SIMD: the unit-stride, aligned, single-field access that SoA produces is exactly what a vector unit wants. Alignment matters for the same reason — placing a hot per-thread structure on its own cache-line boundary both enables aligned vector loads and prevents false sharing, a double win covered mechanically in Memory Alignment and False Sharing.

Failure Modes and Common Misunderstandings

The commonest mistake is adding cores to a memory-bound kernel and expecting speedup. If the kernel is left of the roofline ridge, all the cores share one saturated memory bus; more of them just wait together. The diagnostic is arithmetic intensity, not core count.

The second is invisible false sharing — a “parallel” data structure (per-thread counters, adjacent lock words, a padded-then-un-padded refactor) that shares lines and runs slower than serial. It is invisible because the source shows no shared variable; only perf c2c or a layout audit reveals it.

The third is the NUMA first-touch trap: correct, race-free parallel code that is slow purely because a serial initialization phase homed all pages on one node. The code is functionally perfect and performs terribly, and no amount of lock-tuning fixes it — the cure is in the allocation and placement, not the synchronization.

The fourth is over-tuning cache-aware block sizes to one machine and shipping fragile constants that regress on the next CPU generation — the failure that motivates cache-oblivious designs in the first place.

Alternatives and When to Reach for Each

Reach for cache-aware blocking when you control the deployment hardware and need peak throughput on it — HPC kernels, tuned BLAS, database join buffers sized to L2/L3. Reach for cache-oblivious recursion when portability across an unknown or multi-level hierarchy matters more than the last 20% of performance, especially when data may spill to a much slower level. Reach for NUMA pinning + parallel first-touch whenever you run on multi-socket servers and can partition data per thread. Reach for interleaving when the dataset is genuinely shared and uniformly accessed, so spreading it beats concentrating it. And accept that for most application code the highest-leverage move is neither exotic — it is choosing SoA layout, sequential access, and per-thread data so the cache and the vector unit are fed, which is 80% of the benefit for 20% of the effort. When even that is not enough because the bottleneck is a genuinely shared hot structure, the problem has moved from locality to contention and belongs to Scalability Bottlenecks and Contention.

Production Notes

The database and systems literature is full of cache-conscious redesigns: column stores (which are SoA for analytics) exist precisely because scanning one column at full bandwidth beats dragging whole rows through cache; hash-join and sort implementations are cache-blocked and increasingly NUMA-partitioned. The kernel itself is aggressively per-CPU and cache-line-padded to avoid false sharing on hot counters and lock structures, and Linux ships perf c2c and NUMA-balancing machinery (Automatic NUMA Balancing) because these effects dominate real server workloads. The unifying production lesson mirrors the roofline: before parallelizing, ask whether the kernel is memory-bound or compute-bound. If memory-bound, the payoff is in layout and locality — blocking, SoA, first-touch, pinning — because those raise arithmetic intensity and unlock the parallelism you already have; only once the kernel is compute-bound does throwing more cores and wider vectors at it actually pay. Parallelism without locality awareness is, more often than not, a faster way to wait on memory.

See Also

Graph View

Backlinks