Cache Memories and Direct Mapping

A cache is the hardware that turns locality into speed. It is a small, fast SRAM memory sitting between the processor and main memory, holding copies of blocks of DRAM that the program has used recently. On each memory reference the processor checks the cache first; if the data is there — a hit — it comes back in a cycle or two, and the slow DRAM is never touched. The work is entirely in the bookkeeping: given an address, where in the cache could this block be, and is it actually there? This lesson answers both questions for the simplest organization, the direct-mapped cache, and the answer is a precise slicing of the address.

Cache geometry: S, E, B

A cache is organized as a two-dimensional array of cache lines. The lines are grouped into sets, and the parameters are fixed by powers of two.

• There are $S=2^s$ sets.
• Each set holds $E$ lines (also called ways).
• Each line stores one block of $B=2^b$ contiguous bytes of memory, plus a valid bit (is this line holding real data?) and a tag (which block of memory is it?).

The total data capacity is the product of the three:

Each line carries overhead the capacity figure ignores: the valid bit and the tag are needed to identify and validate the block, but they do not count toward $C$.

Slicing the address

Now the central idea. Because $B=2^b$ and $S=2^s$ are powers of two, the bits of a memory address split cleanly into three contiguous fields, read from the low-order end up:

• The low $b$ bits are the block offset: which byte within the block. With $B=2^b$ bytes per block, $b={\log }_{2}B$ bits name a byte inside it.
• The next $s$ bits are the set index: which set the block maps to. With $S=2^s$ sets, $s={\log }_{2}S$ bits choose one.
• The remaining high bits are the tag: they identify which of the many memory blocks that map to this set is actually stored. If the address is $m$ bits wide, the tag is $t=m-s-b$ bits.

Stated plainly: the offset locates a byte in a block, the index locates a set, and the tag disambiguates which block is in that set. Adjacent addresses share a tag and set index and differ only in offset, and that is why a single block captures spatial locality — a stride-1 walk stays inside one block until the offset overflows.

Why these bits and not some other slicing? The choice is deliberate, and it is what makes spatial locality land in one place. The low bits change fastest as you walk memory, so putting the offset there means consecutive addresses stay in one block — the whole point of a block. The index sits just above the offset, so consecutive blocks fall into consecutive sets and spread across the cache instead of piling into one. If the index were taken from the high bits instead, a stride-1 sweep would hammer a single set while the rest of the cache sat empty. The address split is the mechanism that maps the program's locality onto the cache's geometry.

A concrete geometry, worked

Fix one tiny cache for the rest of this lesson: $S=4$ sets, $E=1$ line per set, $B=4$ bytes per block, on 6-bit addresses (a 64-byte memory). Then $b=2$, $s=2$, and $t=6-2-2=2$: the low two bits pick a byte, the middle two pick a set, and the top two are the tag. The cache holds $C=4\times 1\times 4=16$ bytes. Take the address 0x2C $=44={101100}_2$ and read the fields off:

So address 0x2C refers to byte 0 of the block that lives (if present) in set 3, and that block is legitimate only if set 3's stored tag equals 2. The 64-byte memory holds 16 blocks; with 4 sets, exactly $2^t=4$ of them map to each set, one per tag value, and the tag is what tells them apart.

One more example. Take 0x17 $=23={010111}_2$. The low two bits 11 are offset 3; the middle two 01 are set 1; the top two 01 are tag

1. So byte 23 is byte 3 of the block occupying set 1 with tag 1 — and indeed block number $\lfloor 23/4\rfloor =5$, whose four bytes are 20–23, all sharing set 1 and tag 1. The arithmetic guarantees that because the set index is the middle bits, the sixteen memory blocks fan out across the four sets in a strict repeating cycle — blocks 0, 4, 8, 12 to set 0; blocks 1, 5, 9, 13 to set 1; and so on. Every fourth block collides in the same set — the collision pattern the trace below will exploit.

Direct-mapped access

A direct-mapped cache is the special case $E=1$: exactly one line per set. Each memory block therefore has a single legal home, the set its index bits name, and no choice of placement remains. That makes the lookup mechanical. To service an address the cache does three steps.

1. Set selection. Extract the $s$ index bits and use them to select set number $\text{index}$. There is no search across sets: the index is the set number.
2. Line matching. The selected set has one line. It is a hit if and only if that line's valid bit is 1 and its stored tag equals the address's tag. If either fails, it is a miss.
3. Byte selection. On a hit, use the $b$ offset bits to pick the requested byte (or word) out of the block and return it.

When step 2 reports a miss, the cache fetches the entire $B$-byte block from the next level down, installs it in the (single) line of that set, overwriting whatever was there, sets the valid bit, records the tag, and then completes the access as a hit. Because the home is forced, installing the new block evicts the old one unconditionally.

A trace, end to end

Run the worked cache ($S=4$, $B=4$, 6-bit addresses, initially empty) on seven reads. Each row splits the address into tag / set / offset and applies the three-step algorithm.

The trace exhibits every behavior the structure allows. Access 2 is spatial locality at work: byte 1 hits in the block that byte 0 fetched. Accesses 5 and 6 are the direct-mapped pathology: addresses 0 and 32 differ by 32, a multiple of $S\cdot B=16$, so they share set 0 while carrying different tags, and each install evicts the other. Access 7 hits because set 2 was never disturbed.

Why misses happen

The structure itself explains the kinds of misses a cache can suffer.

Cold misses are unavoidable and mostly harmless: every block pays one. Capacity misses mean the working set is too large; to address them, restructure the computation (the last lesson of this module does exactly that). Conflict misses are an artifact of rigid placement, and they can be severe.

Thrashing: the two-array ping-pong

Conflict misses turn pathological when a loop alternates between two blocks that share a set. Reuse the worked capacity, reorganized as $S=2$ sets of $B=8$ bytes (two ints per block, still 16 bytes of cache), and take a dot product:

int dotprod(int x[4], int y[4]) {
  int sum = 0;
  for (int i = 0; i < 4; i++)
    sum += x[i] * y[i];
  return sum;
}

Suppose the linker places x at address 0 and y right behind it at address 16. Then x[0..1] occupy the block at 0 (set 0), x[2..3] the block at 8 (set 1), y[0..1] the block at 16 (and $16/8=2$ is even, so it maps to set 0 again), and y[2..3] the block at 24, set 1. Every x block shares a set with the y block the loop uses at the same time:

• x[0] misses and installs x's first block in set 0.
• y[0] misses and evicts it, installing y's first block.
• x[1] would have been a hit, the block was just here, but it was evicted: miss, evict y's block.
• y[1] misses, evicts x's block. And so on through both sets.

Eight accesses, eight misses. The spatial locality is real (two ints per block) but the cache never gets to use it, because the two arrays thrash: they ping-pong in and out of the same sets. The fix is simple: move y. Pad x by one block (int x[6]; costs 8 bytes) so y starts at 24, which maps to set 1. Now the pairs the loop touches together live in different sets, the ping-pong stops, and the trace collapses to the four cold misses spatial locality predicts: a miss rate of $1/2$ instead of $1$.

Thrashing of this shape is common in practice: arrays whose sizes are powers of two land on it constantly, because power-of-two dimensions make different rows and different arrays differ by exact multiples of $S\cdot B$. That is why performance folklore says to avoid power-of-two leading dimensions, and why a byte of padding can be worth a 2x speedup.

The case for and against direct mapping

Direct mapping looks weak — one home per block, conflict misses by construction — yet it survived in real designs for a precise reason.

The direct-mapped hit is the fastest possible. Hennessy and Patterson make the argument sharply: a direct-mapped cache reads out the one candidate line and checks its tag in parallel, so the data is available the instant the tag compare confirms it (Hennessy & Patterson, Computer Architecture: A Quantitative Approach, §2).¹ An associative cache cannot forward the data until it knows which way matched, putting a multiplexer in the critical path. On the tightest L1 timing budgets that difference can decide the clock period, which is why several influential processors used direct-mapped L1 caches even after associativity was cheap. Mark Hill's analysis stated the trade-off as direct-mapped is often faster per hit, associative misses less — and which wins depends on whether the hit time or the miss rate is the binding constraint (Hill, A case for direct-mapped caches, IEEE Computer 1988).²

Victim caches reclaim most of the loss cheaply. The direct-mapped weakness is narrow: a handful of hot blocks that collide in one set. Jouppi's victim cache attacks exactly that — a tiny fully-associative buffer (4 to 16 lines) that catches blocks as they are evicted from the direct-mapped cache, so a block thrashed out by a conflict can be pulled back from the victim cache in one extra cycle instead of going all the way to memory (Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, ISCA 1990).³ A few extra lines recover most of the conflict misses that associativity would have prevented, at a fraction of the hardware — a recurring theme in cache design: attack the specific pathology, not the general case.

Giving each set several lines, and choosing which to evict, is set-associativity — along with the policies that govern what happens on a write.