CPU Cache: The Portable Little Warehouse That Boosts Performance

Why Cache Is Needed

CPU executes an instruction in about 0.3 ns while a memory access takes roughly 100 ns, a 300× difference. If the CPU waited for memory on every access, utilization would be very low. Inserting a faster cache between CPU and memory stores frequently used data and reduces the average access latency.

Cache Working Principle

Principle of Locality

Programs exhibit temporal locality (recently accessed data is likely to be accessed again, e.g., loop variables) and spatial locality (addresses near a recently accessed address are likely to be accessed, e.g., array traversal). These patterns justify caching.

Cache Hit and Miss

A hit occurs when the requested data resides in the cache, yielding a fast access. A miss occurs when the data is absent, requiring a fetch from a slower memory level.

┌────────────────────────────────────────┐
│                CPU                     │
│                ↓                       │
│          ┌──────────────┐               │
│          │   L1 Cache   │ ← fast hit   │
│          └──────┬───────┘               │
│                ↓   miss                │
│          ┌──────────────┐               │
│          │   L2 Cache   │ ← faster     │
│          └──────┬───────┘               │
│                ↓   miss                │
│          ┌──────────────┐               │
│          │   L3 Cache   │ ← moderate   │
│          └──────┬───────┘               │
│                ↓   miss                │
│          ┌──────────────┐               │
│          │   Memory     │ ← slow       │
│          └──────────────┘               │
└────────────────────────────────────────┘

Cache Hierarchy

┌─────────────────────────────────────────────┐
│               CPU Core                      │
│   ┌─────────────────────────────────┐     │
│   │ L1 Cache                        │
│   │ - L1‑I: Instruction (32 KB)     │
│   │ - L1‑D: Data (32 KB)            │
│   └─────────────────────────────────┘     │
│   ↓                                         │
│   ┌─────────────────────────────────┐     │
│   │ L2 Cache (per core)             │
│   │ 256 KB – 1 MB                   │
│   └─────────────────────────────────┘     │
│   ↓                                         │
│   ┌─────────────────────────────────┐     │
│   │ L3 Cache (shared)               │
│   │ Few MB – Tens MB                │
│   └─────────────────────────────────┘     │
│   ↓                                         │
│   Memory                                 │
└─────────────────────────────────────────────┘

Level Comparison

L1 : 32‑64 KB, 1‑2 ns latency, highest bandwidth, private to each core.

L2 : 256 KB‑1 MB, 3‑10 ns latency, high bandwidth, private or shared per core.

L3 : few MB‑tens MB, 10‑20 ns latency, medium bandwidth, shared among cores.

Memory : 8 GB‑64 GB, 50‑100 ns latency, low bandwidth, accessible by all cores.

Cache Operation

Cache Line

Data is transferred in fixed-size cache lines, typically 64 bytes. Each memory fetch moves an entire line, reducing bus transactions, exploiting spatial locality, and simplifying hardware.

Mapping Methods

1. Direct Mapped – each memory block maps to exactly one cache line (simple, prone to conflicts).
2. Set Associative – cache is divided into sets; each set holds multiple lines (common: 4‑way, 8‑way).
3. Fully Associative – any block can occupy any line (used mainly for TLB).

N‑Way Set‑Associative Example

4‑way set associative:
Memory block address → set index → 4 candidate lines
Set0: [line0] [line1] [line2] [line3] ← one line selected for storage
Set1: [line0] [line1] [line2] [line3] …
Lookup process:
1. Compute set number from address.
2. Compare tag with the 4 lines in the set.
3. If a tag matches → hit; otherwise → miss and replace a line.

Cache Replacement Policies

Common Policies

1. LRU (Least Recently Used) – evicts the line that has not been used for the longest time (often approximated as pseudo‑LRU).
2. FIFO (First In First Out) – evicts the oldest line.
3. Random – evicts a randomly chosen line.
4. LFU (Least Frequently Used) – evicts the line with the lowest access frequency.

Modern CPU Choice

Intel and AMD implement pseudo‑LRU because it is hardware‑friendly. Research cited in the article shows random replacement performs close to optimal LRU, and the practical difference between LRU and random is small.

Write Policies

Write‑Through

On a write, the cache line is updated and the same data is written to main memory simultaneously.
Pros: memory always holds the latest value.
Cons: every write incurs a memory access, slowing performance.

Write‑Back

On a write, only the cache line is updated and marked as dirty.
When the dirty line is evicted, it is written back to memory.
Pros: fewer memory writes, higher speed.
Cons: hardware must track dirty bits, adding complexity.

Write Allocate vs. No‑Allocate

On a write miss:
- Write Allocate: load the corresponding block into the cache, then write.
- No‑Allocate: write directly to memory, leaving the cache unchanged.
The article notes modern CPUs typically use write allocate on read misses and no‑allocate on write misses, though exact behavior depends on implementation.

Cache Performance Metrics

Hit Rate

Hit Rate = number of hits / total accesses.
Typical hit rates: L1 ≈ 90‑95 %, L2 ≈ 95‑99 %, L3 > 99 %.
Overall hit rate is approximately the product of the three levels, yielding a very high effective rate.

Average Memory Access Time (AMAT)

AMAT = Hit_time + Miss_rate × Miss_penalty.
Example: L1 Hit_time = 1 ns, Miss_rate = 5 %.
L2 Miss_penalty = 10 ns.
AMAT = 1 ns + 0.05 × 10 ns = 1.5 ns.
If L2 were absent, Miss_penalty would be ~100 ns, giving AMAT = 1 ns + 0.05 × 100 ns = 6 ns (four‑times slower).

Impact on Programs

Sequential Access (Cache‑Friendly)

int sum = 0;
int array[1000];
for (int i = 0; i < 1000; i++) {
    sum += array[i]; // sequential, exploits spatial locality
}

Random Access (Cache‑Unfriendly)

int sum = 0;
int array[1000];
for (int i = 0; i < 1000; i++) {
    sum += array[i * 97 % 1000]; // jumps break spatial locality
}

Row‑Major vs. Column‑Major Traversal

int matrix[1000][1000];
// Row‑major (good for row‑major layout)
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        sum += matrix[i][j]; // cache‑friendly
    }
}
// Column‑major (bad for row‑major layout)
for (int j = 0; j < 1000; j++) {
    for (int i = 0; i < 1000; i++) {
        sum += matrix[i][j]; // each iteration jumps to next row, hurting locality
    }
}

Summary

Cache acts as a small, fast storage layer for the CPU.
Key concepts:
1. Exploits temporal and spatial locality.
2. Three‑level hierarchy (L1, L2, L3) with increasing size and latency.
3. 64‑byte cache lines are the basic transfer unit.
4. Set‑associative mapping dominates modern designs.
5. Write‑back generally yields higher efficiency than write‑through.
Performance impact:
- Hit rate directly determines effective speed.
- Misses incur large latency penalties.
- Writing cache‑friendly code keeps the CPU operating at near‑peak throughput.