Cache Fundamentals
A cache is a small, fast memory that keeps copies of the data a program is most likely to reuse. We saw in
the memory wall
why we want one. This page is about how it actually works — and the answer is a beautiful
piece of address arithmetic. Every memory address the CPU generates is silently chopped into three fields,
and those fields decide, in a single fast step, whether the data is already in the cache and exactly where
to look.
Get this arithmetic into your bones and the rest of the module unlocks. Miss it and everything downstream —
the three C's, the TLB, virtual memory — stays fuzzy. So we will go slow, with real numbers.
Blocks, not bytes
The cache never stores a single byte. Because of spatial locality it stores fixed-size blocks
(also called lines) — typically 64 bytes on modern x86 and ARM
chips. When you touch one byte, its whole 64-byte block is pulled in, on the bet that its neighbours are
coming. So an address has two parts straight away: which block, and which byte within the block.
The low \log_2(\text{block size}) bits are the block offset; the
rest is the block address.
For a 64-byte block, the offset is \log_2 64 = 6 bits. The remaining high bits
name the block.
Tag, index, offset
Where does a block go in the cache? We give the cache a fixed number of sets. The middle
bits of the block address — the index — select which set. The high bits — the
tag — are stored alongside the data so we can confirm that the block sitting in that set is
really the one we wanted (many different blocks share the same index). And the low bits are the offset. So
every address is:
\underbrace{\;\text{tag}\;}_{\text{who}} \;\Big|\; \underbrace{\;\text{index}\;}_{\text{which set}} \;\Big|\; \underbrace{\;\text{offset}\;}_{\text{which byte}}
Reading a cache is then: use the index to jump to a set; compare the stored tags in that
set against your address's tag; if one matches and its valid bit is set, it is a
hit and the offset picks your byte out of the block. Otherwise, a
miss.
The valid bit
A tag match is not enough. When the machine powers on, the cache is full of random garbage whose tag bits
might accidentally match. So every line carries a valid bit, cleared at reset and set only
when real data is loaded. A hit requires valid bit set and tag matches.
It is one bit that saves you from trusting noise.
Three ways to map blocks to sets
How many places can a given block live? That single choice defines the three classic cache organisations:
| Organisation | Where a block may go | Trade-off |
|---|
| Direct-mapped | exactly one set (1 way) | fastest, simplest lookup; worst conflicts |
| n-way set-associative | any of the n ways in its set | the practical middle ground (2–16 ways) |
| Fully associative | anywhere in the cache | fewest conflicts; costliest to search |
Direct-mapped is a set-associative cache with 1 way; fully associative is one big
set with no index bits at all. They are the two ends of one dial, and real L1/L2/L3 caches sit
somewhere in between (an L1 is often 8-way, an L3 might be 12- or 16-way). More ways means fewer collisions
but more tag comparators firing in parallel and a slower, hotter lookup.
The geometry, in one formula
For a cache of capacity C bytes, block size B bytes,
and associativity n ways, the number of sets is
\#\text{sets} = \frac{C}{B \times n}, \qquad
\text{offset bits} = \log_2 B, \qquad
\text{index bits} = \log_2(\#\text{sets}),
and the tag takes whatever is left of the address:
\text{tag bits} = \text{address bits} - \text{index bits} - \text{offset bits}.
Watch what associativity does: doubling n halves the number of sets, so it steals
one bit from the index and hands it to the tag. A fully-associative cache has zero index bits — every bit
above the offset is tag.
// Split an address into tag / index / offset for a given cache geometry.
function decode(addrBits: number, capacityBytes: number, blockBytes: number, ways: number) {
const sets = capacityBytes / (blockBytes * ways);
const offsetBits = Math.log2(blockBytes);
const indexBits = Math.log2(sets);
const tagBits = addrBits - indexBits - offsetBits;
return { sets, offsetBits, indexBits, tagBits };
}
// A classic 32 KB, 64-byte-block, 8-way L1 on a 32-bit address.
const g = decode(32, 32 * 1024, 64, 8);
console.log(`sets = ${g.sets}`);
console.log(`offset = ${g.offsetBits} bits, index = ${g.indexBits} bits, tag = ${g.tagBits} bits`);
// Now decode a concrete address into its three fields.
const addr = 0xDEADBEEF;
const offMask = (1 << g.offsetBits) - 1;
const idxMask = (1 << g.indexBits) - 1;
const offset = addr & offMask;
const index = (addr >>> g.offsetBits) & idxMask;
const tag = addr >>> (g.offsetBits + g.indexBits);
console.log(`addr 0x${addr.toString(16)} -> tag 0x${tag.toString(16)}, set ${index}, byte ${offset}`);
When a set is full: replacement
In an n-way set, a new block that misses must evict one of the
n residents. Which one is the replacement policy. The
classic answer is LRU — least recently used: evict whichever way has gone longest without a
touch, betting (via temporal locality) that it is the least likely to be needed next. True LRU needs
ordering bits per set and gets expensive past a few ways, so real chips approximate it (tree-PLRU, or even
just random for high associativity). Direct-mapped caches need no policy at all — there is only one place a
block can go, so eviction is forced.
// A tiny direct-mapped cache simulator: watch hits and misses on an access stream.
// 4 sets, so the set index is (blockAddr % 4); the tag is (blockAddr / 4).
const SETS = 4;
const valid: boolean[] = new Array(SETS).fill(false);
const tags: number[] = new Array(SETS).fill(-1);
function access(blockAddr: number): string {
const set = blockAddr % SETS;
const tag = Math.floor(blockAddr / SETS);
const hit = valid[set] && tags[set] === tag;
valid[set] = true;
tags[set] = tag; // load the block (evicting whatever was there)
return `block ${blockAddr} -> set ${set}: ${hit ? "HIT" : "miss"}`;
}
// Blocks 0 and 4 both map to set 0 — watch them evict each other (a conflict miss!).
for (const b of [0, 1, 2, 0, 4, 0, 4]) console.log(access(b));
It looks arbitrary until you think about spatial locality. Consecutive blocks — block 100, 101, 102 — differ
in their low bits, so taking the index from the low-ish middle bits spreads neighbouring blocks
across different sets, letting them all live in the cache at once. If you indexed with the
top bits instead, a whole contiguous array would pile into a single set and thrash catastrophically
while the rest of the cache sat empty. The offset must be the lowest bits (bytes within a block are truly
adjacent), so the index naturally lands in the middle. It is a deliberate choice that turns spatial locality
into spread-out sets.
Students often assume more tag bits = more capacity. The opposite can be true. The tag width is just
"whatever the index and offset don't use". Make a cache more associative at the same capacity and
the number of sets drops, the index shrinks, and the tag grows — even though you stored no
extra data, only rearranged where blocks may sit. Tag bits are overhead (SRAM you must pay for but that
holds no program data); a fully-associative cache has the widest tags and the most overhead of all. Capacity
is C; the tag width is a consequence of how you sliced it, not a measure of size.
What comes next
You can now decode any address and simulate hits and misses by hand. The obvious next question is: how
much do misses cost, and why do they happen? That is the
three C's and AMAT.
Then we ask what happens on a write —
write policies —
and later reuse this exact tag/index/offset machinery to cache address translations in the
TLB.