Why CPUs Need Cache: A Deep Dive into Cache Mechanics and Coherence

1. Why Cache Is Needed

1.1 Motivation

CPU performance has grown dramatically with advances in process technology, while DRAM memory speed improves far more slowly, creating a gap where storage capacity limits computation. The trade‑off between capacity and speed means we must exploit data locality—accesses tend to be near each other in memory—to bridge this gap.

When code repeatedly accesses nearby data, placing that data in a small, fast storage unit (the cache) dramatically reduces access latency.

Example loop illustrating locality:

for (j = 0; j < 100; j = j + 1)
    for (i = 0; i < 5000; i = i + 1)
        x[i][j] = 2 * x[i][j];

The nested loops repeatedly touch elements that are contiguous in memory, making them ideal candidates for caching.

1.2 Cache in Real Systems

A typical memory hierarchy consists of CPU registers, L1/L2/L3 caches, DRAM, and finally secondary storage. Data is first looked up in registers, then L1, then L2, and so on, until it is found or fetched from the disk.

Cache lines store data in blocks (typically 64 bytes). This block‑oriented transfer contrasts with the byte‑addressable CPU interface.

1.3 Cache Classification

I‑Cache vs D‑Cache : Instruction cache holds executable code (read‑only), while data cache holds mutable data and can be written back.

Size : <4 KB blocks are considered “small” caches (e.g., L1), >4 KB are “large” (e.g., L2, L3).

Location : Inner caches are part of the CPU core (L1/L2), outer caches reside outside the core (L3, last‑level cache).

Inclusion : Inclusive caches contain all data from lower levels; exclusive caches store only data not present in higher levels.

2. Cache Operation Principles

Four key questions define cache behavior:

How is data placed?

How is data looked up?

How is data replaced?

How are write operations handled?

2.1 Data Placement

Assume 32 memory blocks and an 8‑line cache. To store block 12, three mapping schemes exist:

Fully associative : The block may occupy any cache line.

Direct‑mapped : The block maps to a single line (e.g., 12 mod 8 = 4).

Set‑associative : The cache is divided into sets; block 12 can occupy any line within its set (e.g., a 2‑way set‑associative cache has 4 sets, so block 12 maps to set 0 and can use line 0 or 1).

Increasing associativity reduces conflict misses but enlarges the comparison circuitry.

2.2 Data Lookup

Addresses are divided into tag, index (set identifier), and block offset. In a set‑associative cache, the index selects a set, and the tag is compared against all lines in that set to determine a hit.

2.3 Replacement Policies

Random replacement: Choose any line arbitrarily on a miss.

Least‑Recently‑Used (LRU): Evict the line that has not been accessed for the longest time.

First‑In‑First‑Out (FIFO): Evict the line that entered the cache earliest.

Replacement can be triggered on a cache miss, on a read miss (load‑on‑miss), or on a write miss (write‑allocate).

2.4 Write Policies

Write‑through : Every write updates both the cache line and the underlying memory immediately, incurring higher write latency.

Write‑back : Writes modify only the cache; the dirty line is written back to memory when it is evicted.

Write buffer (write‑back with buffer) : Writes are first placed in a buffer; the buffer drains to memory later, reducing write‑through traffic.

3. Cache Coherence

In multi‑core systems, each core has its own private caches. If one core writes a memory location, other cores may still hold a stale copy, leading to incorrect results. Coherence protocols ensure that all caches see a consistent view of memory.

Strategy 1 – Snooping

All caches monitor the bus for write operations. Two possible reactions:

Write‑update : The writing cache broadcasts the new data, and all other caches update their copies.

Write‑invalidate : The writing cache invalidates the corresponding line in all other caches.

Strategy 2 – Directory‑Based

A central directory in main memory tracks which caches hold each block. Common protocols include:

SI (Shared/Invalid)

MSI (Modified/Shared/Invalid)

MESI (Modified/Exclusive/Shared/Invalid)

The MESI protocol is widely used. Its state transitions are:

I (Invalid) : No valid copy.

S (Shared) : Clean copy present in multiple caches.

E (Exclusive) : Clean copy present in only one cache.

M (Modified) : Dirty copy present in only one cache; must be written back before another cache can read.

4. Summary

Cache bridges the speed gap between fast CPUs and slower main memory by exploiting spatial and temporal locality. Understanding placement, lookup, replacement, write policies, and coherence mechanisms is essential for designing efficient computer systems. Readers can dive deeper into any of these topics for advanced study.