Memory Hierarchy §

Why sequential access saturates bandwidth: A DRAM column read returns 64 bytes per burst. If the next request is to the adjacent column in the same row, the row is already open and the controller skips tRCD, issuing only tCL. For a fully sequential stream, every access after the first is a “row hit” and the effective latency drops to tCL (~13 cycles). The bus is never idle, so bandwidth equals the bus rate.

Why random access is latency-bound: Each random access likely hits a different row, forcing a full tRCD + tCL sequence (~30 cycles) per access. With only one outstanding request, the effective bandwidth is 64 B / 30 cycles ≈ 2 GB/s per channel—far below the 25.6 GB/s bus rate. Modern CPUs hide this with out-of-order execution and multiple outstanding loads, but the fundamental limit remains.

Worked example: A program reads 1 GB sequentially from a dual-channel DDR4-3200 system (51.2 GB/s peak). Time = 1 GB / 51.2 GB/s ≈ 19.5 ms. The same 1 GB read with random 64-byte accesses at 100 ns each: 16,384,000 accesses × 100 ns = 1.64 s—84× slower.

Cache line and mapping §

The cache line (typically 64 bytes) is the unit of transfer between levels. A miss loads the entire line, not a single byte. This exploits spatial locality: nearby data is likely to be accessed soon.

Mapping determines which set a given address can occupy:

• Direct-mapped: address → exactly one set (set = addr mod num_sets). Simple, but two addresses that map to the same set conflict.
• Set-associative ($k$-way): address → one of $k$ sets in a group. Balances conflict and tag-comparison cost.
• Fully associative: address → any set. Maximum flexibility; requires comparing the tag against every entry.

Replacement and write policies §

Replacement (when a set is full):

• LRU (Least Recently Used): evict the line not accessed for the longest time.
• Random: evict a random line. Surprisingly effective for streaming workloads where LRU thrashes.

Write policy:

• Write-through: write to cache and to the next level simultaneously. Simple but every write pays the next-level latency.
• Write-back: write to cache only; write to the next level when the line is evicted. Fast, but requires a dirty bit per line.
• Write-allocate: on a write miss, load the line into the cache first (preferred when the line will be read again) or write directly to the next level (no-write-allocate).

Store buffers and write combining §

Between the CPU pipeline and L1, two distinct hardware stages decouple stores from the rest of the machine:

• Store buffer: a small FIFO (typically 16–64 entries) that accepts store data from the pipeline immediately. The pipeline retires the store instruction in 1 cycle; the store buffer drains to L1 in the background. This is what allows the CPU to retire stores without waiting for the cache.
• Write-combining buffer: coalesces multiple partial-line writes (e.g., four 16-byte stores) into a single full-line write before committing to L1. Without it, four partial writes would cause four separate cache-line modifications; with it, one full-line write suffices.

These buffers are the hardware substrate of the x86-TSO (Total Store Order) memory model: stores are visible to other cores in program order, but loads may be reordered with respect to stores. The mfence instruction flushes the store buffer, making all prior stores globally visible. On ARM, the weaker default ordering (stores may be reordered with other stores) requires explicit dmb (Data Memory Barrier) instructions. See Parallelism for the full memory-model discussion.

Locality §

• Temporal: recently accessed data is likely to be accessed again (e.g., a loop counter).
• Spatial: data near recently accessed data is likely to be accessed soon (e.g., the next element in an array).

Worked example: tracing a write §

Trace a 4-byte write to virtual address 0x1000 through a 2-way set-associative L1 (32 KB, 64-byte lines, write-back, write-allocate):

1. Address decomposition: 32 KB / 64 B = 512 lines. 2-way → 256 sets. Offset = 6 bits (64 B), Index = 8 bits (256 sets), Tag = remaining bits. For 0x1000: offset = 0x00, index = 0x10 (set 16), tag = 0x1.
2. Tag compare: Check both ways in set 16. Suppose way 0 holds tag 0x1 (hit) → write the 4 bytes into the cached line. Mark the line dirty (write-back).
3. Store buffer: The 4-byte store enters the store buffer. The pipeline retires immediately.
4. Write-combining: If this is the first partial write to this line, it is buffered. If a second 4-byte write to the same line arrives before the line is committed, both are coalesced.
5. Commit: When the store buffer drains, the 4 bytes are written into L1 way 0, set 16. The dirty bit is set. No write to L2 occurs until the line is evicted.

Types of prefetchers §

• Next-line prefetcher: on a cache miss, also fetch the adjacent cache line. Exploits spatial locality for sequential access. Simple, low overhead.
• Stride prefetcher: maintains a small history table (typically 16–64 entries) indexed by the PC or address. On each miss, it records the address. If the last two misses to the same table entry have a constant difference (the stride), it prefetches current + stride. For example, accessing a[0], a[4], a[8], … (stride = 4 × element_size) is detected after the second miss.
• Stream prefetcher: detects a stream of sequential accesses across multiple lines and prefetches a window ahead (e.g., 4–8 lines). More aggressive than next-line; used for large array scans.

Cost of a wrong prefetch §

A wrong prefetch (the predicted address is never accessed) has three costs:

1. Cache pollution: the prefetched line occupies a cache set and may evict a useful line (increasing the miss rate for the actual workload).
2. Bandwidth waste: the DRAM bus is occupied transferring data that is never used, reducing bandwidth available for real requests.
3. Coherence traffic: in a multicore system, the prefetched line enters the coherence protocol (MESI), generating snoop traffic for a line no core will use.

Modern prefetchers use a confidence counter: a prefetch is issued only after the stride has been confirmed by 2–3 consecutive accesses. If a prefetch is not consumed before the line is evicted, the counter is decremented, eventually disabling the prefetch for that pattern.

Prefetch depth and cache size §

The prefetch distance (how many lines ahead to fetch) must be large enough to cover the DRAM latency (100 cycles) but small enough to fit in the cache. For a 32 KB L1 (512 lines), a prefetch distance of 8–16 lines is safe; 64 lines would evict the working set. The optimal distance is approximately DRAM_latency / access_interval. For a sequential scan at 1 line per 4 cycles, the distance is 100/4 = 25 lines.

Worked example: stride-4 over a 1 MB array §

A program accesses a[0], a[4], a[8], … over a 1 MB array (16,384 elements of 64 B each, i.e., 16,384 cache lines). The L1 is 32 KB (512 lines).

• Without prefetch: Each access is a compulsory miss (stride 4 means only 1 in 4 lines is touched, and the working set of touched lines is 16,384/4 = 4,096 lines >> 512). Hit rate ≈ 0%. Average access = 100 cycles (DRAM).
• With stride-4 prefetch: After the first two misses, the prefetcher detects stride = 4 lines and prefetches current + 4. The prefetch distance is 8 lines (covers 100-cycle DRAM latency at 12-cycle L1 hit rate). The prefetched lines arrive just in time: hit rate ≈ 80% (the first few accesses and the tail are still misses). Average access ≈ 0.8 × 4 + 0.2 × 100 = 23.2 cycles—a 4.3× speedup.

MESI protocol §

Each cache line is in one of four states:

• M (Modified): the line is dirty (written) and exists only in this cache.
• E (Exclusive): the line is clean and exists only in this cache.
• S (Shared): the line is clean and may exist in multiple caches.
• I (Invalid): the line is not valid in this cache.

MOESI: adds an O (Owned) state between M and S. The owner holds the dirty line and can serve reads to other cores without writing back to memory, reducing bus traffic.

Snoop vs. directory protocols §

• Snoop-based: every cache monitors the bus. When a core issues a read or write, all other caches check whether they hold the line and respond. Simple for a small number of cores; bus traffic grows linearly with core count.
• Directory-based: a central directory (in L3 or a dedicated controller) tracks which caches hold a copy of each line. Only the relevant caches are contacted. Used in many modern multicore and NUMA designs.

False sharing §

False sharing occurs when two cores write to different variables that reside in the same 64-byte cache line. The coherence protocol sees writes to the same line and invalidates the other core’s copy on every write, causing a coherence ping-pong: each write forces the other core to re-fetch the line from memory (or from the other core’s cache), adding 40–100 cycles per access.

Example: Two threads each increment a counter. If counter_a and counter_b are adjacent in memory (same 64-byte line), every increment of counter_a invalidates counter_b‘s line in the other core’s cache, and vice versa. The fix is padding: allocate each counter in its own cache line (e.g., struct { int counter; char pad[60]; }).

False sharing is the most common real-world coherence performance problem. It is invisible in single-threaded benchmarks and manifests only under parallel load. See Parallelism for the broader concurrency context.

Coherence traffic cost §

A coherence miss (e.g., a write to a line in Shared state) requires: (1) invalidating all other copies, (2) waiting for acknowledgments, (3) then proceeding. This adds 20–40 cycles on top of the base DRAM latency. In a 16-core system with a snoop protocol, a single write can generate 15 snoop responses, saturating the interconnect.

The DRAM cell and why DRAM is slow §

A DRAM cell is a 1T1C structure: one transistor (access switch) and one capacitor (stores a charge = 1 bit). The capacitor leaks charge, so DRAM must be refreshed every 64 ms (all rows re-read and re-written). This is why DRAM is called “dynamic.”

A DRAM chip is organized into banks (8–32 per chip), each containing a grid of rows and columns. An access to a specific cell requires a three-step sequence:

1. Row activation (tRCD ≈ 14 cycles): open the row in the row buffer (sense the entire row, ~1 Kbit).
2. Column read (tCL ≈ 14 cycles): read the specific column from the row buffer.
3. Precharge (tRAS ≈ 35 cycles): close the row and restore the capacitor charges.

The minimum time between two accesses to the same bank is tRCD + tCL + tRAS ≈ 63 cycles. This is the fundamental source of DRAM latency. The memory controller hides this by interleaving accesses across banks (see Latency vs. Bandwidth).

SRAM §

An SRAM cell is a 6T latch (two cross-coupled inverters + two access transistors). No refresh is needed (the state is maintained by positive feedback), but the 6 transistors occupy 6× the area of a 1T1C DRAM cell. This makes SRAM suitable only for small, fast caches (L1–L3), not for main memory.

NVRAM and emerging tiers §

• Intel Optane (3D XPoint): 100–200 ns latency, byte-addressable, non-volatile. Discontinued in 2022.
• CXL-attached memory: uses the Compute Express Link (CXL) protocol over PCIe to attach additional DRAM or persistent memory to a CPU. Adds a tier between local DRAM and remote NUMA memory.

ECC and bandwidth §

ECC (Error-Correcting Code): adds parity bits (typically 8 per 64-byte word) to detect and correct single-bit errors. Standard in server DRAM; optional in consumer systems.

Bandwidth: DRAM bandwidth = number of channels × bus width × transfer rate. A dual-channel DDR4-3200 system: $2 \times 8 \text{ B} \times 3200 \text{ MT/s} = 51.2 \text{ GB/s}$.

Page tables §

A page table maps virtual page numbers to physical frame numbers. On x86-64, a 4-level table: PML4 → PDPT → PD → PT. Each level is a 512-entry table (9 bits of address per level). The default page size is 4 KB (12 bits of offset).

TLB and huge pages §

The TLB is a small, fully-associative hardware cache of recent page-table entries (typically 64–1024 entries). A TLB hit: 1 cycle. A TLB miss: 4–5 memory accesses (walk the page table), adding 400–500 cycles.

Huge pages reduce TLB pressure dramatically:

• A 2 MB page (512 × 4 KB) reduces the number of TLB entries needed by 512×. A 1 GB working set needs only 512 TLB entries with 2 MB pages instead of 262,144 with 4 KB pages.
• A 1 GB page (512 × 2 MB) reduces entries by 262,144×. Used for very large, contiguous allocations (e.g., database buffers, GPU mappings).

The OS enables huge pages via madvise(MADV_HUGEPAGE) or the hugetlbfs filesystem. Linux Transparent Huge Pages (THP) automatically coalesce 4 KB pages into 2 MB pages in the background. Huge pages are critical for workloads with large, sequential working sets (databases, JVM heaps, scientific computing) where TLB misses dominate.

Page faults §

A page fault occurs when a virtual address is not mapped to a physical frame. The OS loads the page from disk (SSD: $\approx 100 \mu s$, HDD: $\approx 10$ ms). A major fault (page on disk) is expensive; a minor fault (page in RAM but not mapped to this process) is cheap (~1 µs).

The software management of virtual memory—swap policy, working-set model, thrashing mitigation, and per-process memory layout (text, data, heap, stack)—is covered in Operating System.

A 2-socket server with 2 NUMA nodes: each socket has its own DRAM channels (see Physical memory). The interconnect connects the two memory controllers. A core on node 0 reading from node 1’s memory incurs the interconnect latency on top of the DRAM latency, and the coherence protocol must snoop node 1’s caches (see Cache coherence).

Operating systems and runtimes can pin threads and memory allocations to a specific node to minimize remote accesses:

• Linux: numactl --cpunodebind=0 --membind=0 ./program
• Java: -XX:+UseNUMA (G1/ZGC)
• Go: GOMAXPROCS + numactl

A common anti-pattern: allocating a large array on node 0 (because the allocating thread is pinned there) and then having threads on node 1 access it. The fix is first-touch policy: have the thread that will use the memory perform the first write, so the page is allocated on its local node.

HDD anatomy: platters (magnetic storage), actuator arm (positions the read/write head), spindle motor (spins the platter at 5400–15000 RPM). Seek time (5–10 ms) dominates; rotational latency (2.5–4 ms) is the wait for the sector to rotate under the head.

SSD: NAND flash cells store 1–4 bits each (SLC, MLC, TLC, QLC). Wear leveling: distribute writes evenly across cells to prevent premature failure. Garbage collection: erase and rewrite blocks to free space. Write amplification: the ratio of bytes written to NAND vs. bytes written by the host. SSDs connect via NVMe over PCIe, which reduces protocol overhead compared to SATA.

• RAID 0 (striping): data is interleaved across $n$ disks. Read throughput scales linearly; a single disk failure loses all data.
• RAID 1 (mirroring): each disk has an identical copy. Read throughput doubles (read from either mirror); write throughput is unchanged (write to both).
• RAID 5 (distributed parity): parity is spread across all disks. A read of a missing block reconstructs it from the other $n-2$ data blocks + parity. Write penalty: read-modify-write of the parity block.
• RAID 6 (double parity): two independent parity blocks. Tolerates 2 simultaneous disk failures. Important for large arrays where a rebuild of a 16 TB disk takes hours, during which a second failure would be catastrophic.

Part 1 (Cache hit rate): A program accesses a 1 MB array sequentially. The L1 cache is 32 KB (8-way, 64-byte lines), the L2 is 1 MB (16-way), and DRAM is 100 cycles. What is the average access time if the L1 hit rate is 90%, the L2 hit rate is 95% (of L1 misses), and DRAM is 100 cycles?

Part 2 (NUMA): A thread on node 0 reads 50 MB from node 1’s memory. The remote DRAM bandwidth is 25 GB/s (half of local, due to interconnect contention) and the remote latency is 160 cycles. Estimate the total time.

Part 3 (Virtual memory / TLB): A process touches 1 GB of memory sequentially with 4 KB pages. The TLB has 1024 entries (fully associative, LRU). Estimate the TLB miss rate and the average address-translation cost (TLB hit = 1 cycle, TLB miss = 4 memory accesses at 100 cycles each).