Memory Hierarchy, Cache Mapping & MESI | Draftsbook

Memory Latency & Cache Hierarchies

While CPU clock frequencies have surged by orders of magnitude over the past four decades, dynamic random-access memory (DRAM) access latencies have improved at a drastically slower pace—a widening performance disparity known in computer architecture as the Memory Wall. To prevent gigahertz processor cores from stalling endlessly on main memory fetches, modern architectures deploy a multi-tiered Memory Hierarchy powered by SRAM caches (L1, L2, L3) governed by spatial and temporal locality. In this article, we analyze cache placement mappings, write policies, replacement heuristics, and the MESI Coherence Protocol in shared-memory multicore chips.

1. The Principle of Locality of Reference

Cache memory operates effectively due to the empirical property that computer programs do not access all code and data uniformly:

Temporal Locality (Locality in Time): If a memory location is referenced at time $t$, it is highly probable to be referenced again in the immediate future (e.g., loop index counters, accumulator variables, inner loop code blocks).
Spatial Locality (Locality in Space): If a memory location at address $A$ is referenced, locations physically adjacent to it ($A+1, A+2$) are highly probable to be referenced soon (e.g., contiguous array traversals, sequential instruction streams).

To exploit spatial locality, cache does not transfer isolated individual bytes from DRAM; it transfers contiguous multi-byte blocks termed Cache Lines (standardized at 64 bytes across modern x86 and ARM processors).

2. Cache Placement Policies & Address Partitioning

A physical memory address is mathematically dissected by cache controllers into three distinct bit fields: [Tag | Set Index | Block Offset].

Direct-Mapped Cache

Each memory block maps to exactly one cache line.

\text{Line Index} = (\text{Block Addr}) \bmod N

Fastest lookup, minimal silicon area; highly vulnerable to conflict misses when multiple addresses compete for the same slot.

N-Way Set-Associative Cache

The cache is partitioned into sets of $N$ lines.

\text{Set Index} = (\text{Block Addr}) \bmod (\text{Sets})

A block can reside in any of the $N$ ways inside its designated set. Standard in modern L1 (8-way) and L2 (16-way) caches.

Fully Associative Cache

No set index; block can reside in any entry.

\text{Tag matched across all lines in parallel}

Requires expensive Content-Addressable Memory (CAM); reserved for small high-priority structures like TLBs.

3. Cache Write Policies: Write-Through vs. Write-Back

Write-Through with Write Buffer

Every write to cache immediately updates the underlying DRAM main memory simultaneously. Main memory is always pristine and coherent.

Trade-Off: Floods the memory bus with high write traffic on every store operation.

Write-Back with Dirty Bit

Writes update only the fast cache line and mark an internal Dirty Bit as active. The modified line is written back to main memory only when it is evicted by a newer block.

Trade-Off: Dramatically reduces bus bandwidth consumption; standard in modern L1/L2 caches.

4. Multicore Cache Coherence: The MESI Protocol

In modern multi-core processors, each CPU core possesses a private L1/L2 cache, while sharing a unified L3 cache and main memory. If Core 0 writes to variable $X$ in its private cache while Core 1 reads $X$ from its private cache, Core 1 risks observing stale data—the classic Cache Coherence Problem.

Hardware maintains coherence using bus-snooping state machines governed by the MESI Protocol. Every 64-byte cache line maintains two status bits representing four valid states:

State	Line Valid?	Matches Memory?	Copies in Other Caches?	Write Permission?
Modified (M)	Yes	No (Dirty)	None (Exclusive)	Can write directly
Exclusive (E)	Yes	Yes (Clean)	None (Exclusive)	Can write (transitions to M)
Shared (S)	Yes	Yes (Clean)	May exist in other caches	Must broadcast invalidate first
Invalid (I)	No	N/A	N/A	Read triggers cache miss