Unit 1.2 · about 4 h
231 / 324Caches, working sets, bandwidth and NUMA
Assume Programming's layout-alignment-locality unit, including its AoS/SoA experiment. This unit moves to cache ownership, working-set regimes and physical placement rather than repeating that layout comparison.
- explain
- measure
You can now
- Explain cache-line fills, coherence and false sharing separately from language-level synchronization.
- Measure a traversal-order change with a fixed working set and a correctness oracle.
- Estimate useful bytes and line traffic with units, and distinguish bandwidth from dependent-load latency.
- Explain CPU affinity and NUMA page placement without claiming remote-memory measurements on a one-node host.
Covers
- Cache lines, hierarchy, locality, coherence and false sharing
- Working sets, memory bandwidth, latency and storage hierarchy
- NUMA placement and local versus remote memory vocabulary
Study, in this order
3 steps
- Bandwidth, latency and cache lines, measuredAlgorithmica - Algorithms for Modern Hardware
RAM & CPU Caches: Experimental Setup; Memory Bandwidth through Directional Access; Memory Latency, including Theoretical Latency; Cache Lines
Depth · Every curve is the author's Ryzen 7 4700U at a fixed 2 GHz with boost off. Predict your own cliffs from the cache sizes in
/sysrather than copying his. The snippets are simplified; the runnable versions are in the code repository the chapter links. Skip Bypassing the Cache. - Coherence and false sharingAlgoMaster: hardware and container storage companions
Cache Coherence vs. Memory Consistency; False Sharing: Independent Data, Shared Cache Line; True Sharing and False Sharing; Separating Frequently Written Data
Depth · Leave atomics and the multicore benchmark to the concurrency section. A single-core-pinned run cannot demonstrate lines bouncing between cores.
- NUMA placement vocabularyAlgoMaster: hardware and container storage companions
NUMA: Memory Locality through NUMA Problems in Backend Services
Depth · Inspect topology only. On a one-node machine, skip commands requiring node 1 and do not report a local/remote timing ratio.
Focus on
- Read
cpu2/cache/index*/{level,type,size,coherency_line_size,shared_cpu_list}under/sys/devices/system/cpuand runlscpubefore estimating line traffic. Aggregatelscpucache sizes are not per-core capacities. - A stream can overlap independent misses and use bandwidth; a pointer chain waits for each next address and exposes latency. Useful bytes/time is not automatically DRAM traffic/time.
- Coherence coordinates writes to locations. It does not establish the language's cross-location publication order; false sharing is independent writers sharing one line.
- Working-set fit, conflicts, prefetch, translation and frequency all affect a curve. CPU pinning does not relocate pages; NUMA distance values are not measured nanoseconds.
Reproduce closed-book
static volatile int matrix[4096][4096], initialized to (r+c)&255 before timing, with row-first and column-first sums into long long and CLOCK_MONOTONIC around each traversal. Build with gcc -O2 -Wall -Wextra and run taskset -c 2 ./locality five times. Each traversal sums to 2139095040; the array is 64 MiB when sizeof(int)==4, so it cannot stay resident in a 30 MiB last-level cache. Predict the ratio before timing: on an i9-12900K with Linux 7.0 and gcc 15.2, five pinned runs gave 8.1 to 8.2 ms row-first and 80 to 87 ms column-first. Record yours with kernel, CPU and GCC version, derive line utilization from the inspected line size, then explain why TLB behavior and volatile loads keep this from being a pure DRAM-bandwidth benchmark.Traps
- Turning a slower strided run into a cache-miss count. Timing alone cannot separate cache, TLB, prefetch and instruction effects.
- Using
perf c2cor system-wide counters without the permission they need. Withkernel.perf_event_paranoidat 2, keep counters to your own pinned process and user-space cycles and instructions; on hybrid Intel CPUscpu_coreandcpu_atomare separate PMUs. - Reporting NUMA remote latency from a one-node machine. There is no second memory node to measure.
Practice
The section mini-project covers this: working-set and stride sweeps across inspected cache capacities, a dependent pointer chase versus a stream, matched checksums, pinned five-repeat raw timings, and a topology note explicitly excluding remote NUMA claims.
Self-test
-
Algorithmica's loop that increments every 16th
intruns about as fast as the loop that increments every one, once the array no longer fits in cache. Why?With 64-byte lines and four-byte integers, both loops fetch every line of the array; the strided loop uses \(4/64 = 1/16\) of each. When memory transfers dominate, count cache lines touched, not elements. Useful-byte utilization is not a measured traffic multiplier. -
Why can two race-free counters still contend in hardware?
Separate counters can share one cache line. Writes on different cores repeatedly require ownership of that line even though neither counter has multiple writers. -
Does a working set smaller than cache capacity guarantee hits?
No. Conflicts, competing code/data and other users of shared cache can evict lines; compulsory fills still occur. -
What can
numactl --hardwareestablish on a one-node host?Visible CPUs, node membership and node capacity. It cannot supply an observed remote-memory penalty.
Completion criterion
Stop when
Both traversal checksums agree, your evidence records topology and cache state, and you can explain useful-byte traffic, latency versus bandwidth and a hypothetical false-sharing layout without treating timing as causal proof.
Mark passed, then open 1.3 Only mark this when you can do it without notes.Leads to
- 1.5 Virtual memory, page tables, TLBs, page faults and mmap Add translation and residency to the memory-access path.
- 2.8 Deterministic schedules, stress tests and contention Measure cache-line ownership traffic under actual multicore contention.
Comes after
- 1.1 Instruction pipelines, branches and SIMDExplain why wider arithmetic still has to wait for data.
Resources for this unit
- Algorithmica - Algorithms for Modern Hardware Use the Instruction-Level Parallelism, SIMD Parallelism and RAM & CPU Caches chapters for measured pipeline, branch, vectorization, bandwidth, latency and cache-line effects. The figures are the author's Zen 2 measurements at a fixed 2 GHz: predict and measure your own.
- AlgoMaster: hardware and container storage companions Use Memory Ordering, Barriers, and False Sharing (coherence and false-sharing headings only); Huge Pages, NUMA, and ASLR (NUMA headings only); Storage Hardware; RAID Fundamentals (comparison and backup boundaries); and Container File Systems. These fill hardware and image-layer gaps outside the pool's selected OS revision lessons.
Also in this section
- Operating Systems: Three Easy Pieces - selected foundations Read Chapters 4-7, 13-15, 18-21, 36, 39-40, 42 and 45. Work from process state to address translation, devices, files, journaling and integrity. For every chapter, draw the owned state and one failure boundary instead of collecting summaries.
- MIT 6.1810 - selected xv6 process and memory labs Use Fall 2025 Lectures 1, 3-6, 8 and 10-11. Complete the util lab, one syscall task, and the page-table inspection plus ugetpid task from pgtbl. Add cow only if copy-on-write remains unclear. Keep all work in your own course checkout and stop before the full xv6 sequence.
- OSTEP homework - process, paging, disk and integrity simulators Solve process-run.py, paging-linear-translate.py, paging-policy.py, disk.py, fsck.py and checksum.py for at least two seeds each before using the answer flag. Then reproduce one prediction using strace, /proc or a small local program.
- AlgoMaster Operating Systems - selected observation route After OSTEP, use the matching lessons as a second explanation and recall check: fork, exec, wait, and exit; Zombies and Orphans; Signals; Context Switching; The Process Address Space; Paging; The TLB: Hits, Misses, and Invalidation; Page Faults; Copy-on-Write; mmap and Memory-Mapped Files; How malloc Works; VSZ, RSS, PSS, and What They Mean; File Descriptors; The Page Cache and Write-Back; Durability and fsync; Crash Consistency; Linux Namespaces; Control Groups; PID 1 and Signal Handling; Container Resource Failures; and the Investigating lessons. Treat quizzes as recall checks and keep your own traces as evidence.
- Linux proc and strace references Use proc(5), getrusage(2), mmap(2), fsync(2), rename(2), wait(2) and signal(7) while tracing a parent-child pipe, page faults, file publication and a resource-limit failure. Record exact commands and raw observations.
- Nand2Tetris - Projects 1 and 4 only Use Project 1 for Boolean logic and Project 4 for machine-language execution only if the binary or instruction-level entry check fails. Do not take the full course as a second systems curriculum.
- MIT 6.S894 Accelerated Computing - Throughput Processors Use Lecture 2 for the processor model behind this section: superscalar issue, out-of-order execution, speculation and SIMD's need for coherent control. The labs run on the course's remote machines and target AVX-512 and NVIDIA GPUs, so they belong to the GPU track.
- Auto-Vectorization in LLVM Use The Loop Vectorizer Usage and Diagnostics sections for the Clang remarks the pipelines unit asks for; the Features list is optional depth.