Write-allocate vs no-allocate: Foundations — Hardware deep dive

Before you can even ask that question, you need to know what a "cache", a "block", a "miss", and a "write" actually are — as pictures, not words. This page builds every one of them from nothing. Nothing below assumes you have seen the parent note; we construct each tool the moment we need it.

0. The stage: CPU, cache, and memory

Everything in this chapter happens between three boxes. Let us draw them once and never forget the picture.

The whole reason the cache exists: memory is slow. If the CPU had to walk all the way to RAM for every single byte, programs would crawl. The cache keeps copies of recently-used data close by.

1. Address — the "house number" of every byte

Every single byte of memory has a unique number called its address. That's it. It is just a label so the CPU can say which byte it means.

Why hexadecimal (the `0x` prefix)?

You will see numbers like 0x28. The 0x is just a flag that says "read the following digits in base-16". This matters here because addresses split cleanly into pieces when written in binary, and hex is a compact way to write binary.

Recall What decimal number is

0x2F? 0x2F ::: $2 \times 16 + 15 = 47$ .

2. Block (cache line) — the cache moves data in chunks

Here is the single most important fact for this whole topic. The cache never moves one byte at a time. It moves fixed-size chunks called blocks (or cache lines).

The related vault note is Cache Line Size — the chunk size is a real design knob.

Why chunks and not single bytes?

Two reasons, both physical:

Fetching from RAM has a big fixed cost. Once you pay the "walk to the warehouse" cost, grabbing 64 neighbouring bytes is barely more expensive than grabbing 1. So you grab them all.
Programs use neighbours. If you touch byte 40, you very likely touch byte 41 soon. This is called spatial locality — nearby-in-space data tends to be used together.

Which block does an address belong to?

To find a byte's block number, you throw away the low bits that pick the byte inside the block. With an 8-byte block, dividing the address by 8 (i.e. shifting right by 3, written >> 3) gives the block number.

3. The cache's shelves: lines, index, and mapping

The cache has a small number of slots (physical lines). A block from memory must land in one of them. The rule for which slot is called the mapping.

Why the `%` (modulo) symbol?

The cache has, say, 4 lines but memory has millions of blocks. Many blocks must share each slot. mod 4 wraps every block number into the range $0, 1, 2, 3$ — the remainder tells you which of the 4 slots. That is exactly what "wrap around" means.

4. Valid bit and Dirty bit — the cache's two sticky notes

Each cache line carries two one-bit flags. A bit is just a switch that is either 0 or 1.

Why we need the dirty bit: if the cache is allowed to hold a changed copy without immediately telling memory, something must remember "memory is stale here." That memo is the dirty bit — and it only makes sense if the changed data actually lives in the cache, which is the deep reason write-back forces write-allocate.

5. Hit and Miss — did we find it?

When the CPU asks for an address, the cache checks the one slot that address maps to.

Write-allocate: on a write miss, fetch the block in first, then write.
No-allocate: on a write miss, write straight to memory, cache untouched.

What 0x28 equals in decimal ::: $40$ .
What >> 3 does to a number ::: chops off the lowest 3 bits = integer-divides by 8.
What block number 0x28 lives in (8-byte blocks) ::: block 5, since $40 \div 8 = 5$ .
What % 4 (mod 4) computes ::: the remainder after dividing by 4 — the direct-mapped slot index.
Which line 0x28 maps to in a 4-line, 8-byte cache ::: line 1, since $5 mod 4 = 1$ .
What the valid bit tells you ::: whether a cache line holds real data (1) or is empty garbage (0).
What the dirty bit tells you ::: whether the cached copy has been changed and memory is now stale.
The difference between a hit and a miss ::: hit = block already in its slot; miss = must go to slow memory.
What a write miss specifically is ::: a store to an address whose block is not currently in the cache.
What $P (reuse ∣ write)$ reads as ::: the probability you'll use the data again, given you just wrote it.

Foundations — Write-allocate vs no-allocate