Anatomy of a cache: the four questions and the exam cache table

What one line of the cache holds

Lesson 22 left the cache as a small, fast memory that keeps copies of memory blocks: a hit when the block is there, a miss when it must be fetched. Now open it. The paper's cache has eight lines, called a to h, in front of a main memory of 32 blocks numbered 0 to 31. Cache and memory exchange whole blocks, and the paper counts in blocks: its "memory addresses" 0 … 31 are block numbers, or block addresses.

• V, the valid bit — the line holds a real block. At power-up, the paper's "cold start", every V is 0: the cache is empty. Without V, the random bits of an unused tag could match an address by accident.
• D, the dirty bit (write-back caches only) — the block was written in the cache and main memory still holds the old copy. Dirty means memory is stale, not that the cache is wrong.
• Tag — the high-order part of the block address: the part that the position of the line does not already tell.
• Data — the words of the block.
• LRU bits — which block of the set was used least recently; they choose the victim of a miss (section 4).

Read block 18 in five bits: 10010. Its last bit, 0, chose set 0; the four bits before it, 1001, are the tag the line stores. The tag is what tells block 18 from the fifteen other even blocks that could sit in set 0 — four bits for sixteen candidates.

Why the high-order bits for the tag and the low-order bits for the place? Because consecutive blocks — the next elements of an array, the next instructions of a loop — differ in their low bits. Taking the place from the low bits spreads them over consecutive sets, where they do not compete. Had the high bits chosen the place, a whole array would pile into one set and evict itself.

Every design decision of a cache answers one of four questions (notes, p. 304; Hennessy and Patterson ask the same four): where can a block be placed, how is it found, which block is replaced on a miss, and what happens on a write. Sections 2–5 take them in turn; section 6 puts them together in the exam table.

Placement: where may a block go?

Start with a loop that reads one array and writes another, in the mnemonics of the exam papers (registers without the dollar sign, as the 2026 paper writes them; older papers write $F2):

I0  LOOP: LD    F2, 0(R1)
I1        FMUL  F4, F2, F0
I2        SD    F4, 0(R2)
I3        ADDUI R1, R1, 8
I4        ADDUI R2, R2, 8
I5        BNE   R1, R3, LOOP

I0 reads X[i], I2 writes Y[i]. Take blocks of four doubles (32 bytes) and suppose that X[0 … 3] sit in memory block 12 and Y[0 … 3] in block 20. The first four iterations touch the blocks 12, 20, 12, 20, 12, 20, 12, 20 — the alternation of the notes' example on p. 306. Where may an eight-line cache put them?

Direct-mapped: every block has exactly one place, line (block address) mod 8. Here 12 mod 8 = 4 and 20 mod 8 = 4: both blocks want line 4. I0 brings block 12 in, I2 throws it out to make room for block 20 (with write-allocate, section 5), the next I0 throws block 20 out again — and since I2 wrote it, a write-back cache must first copy it to memory. Every access misses while seven lines stay idle.

2-way set-associative: the same eight lines, grouped in four sets of two. Now the rule picks a set, not a line: 12 mod 4 = 0 and 20 mod 4 = 0, so both go to set 0 — which has two places. Two misses fill it, and every later access hits.

The two organisations are one rule with different numbers. Group the lines of the cache into sets of n lines, the ways; a block may go into any way of exactly one set:

Direct-mapped is the case n = 1: every set is one line, so the set number is the line number — the notes' equation (73), line = block address mod #blocks. Fully associative is the other end, n = #blocks: one single set, no set number at all, and the whole block address is the tag; a block may go anywhere. Everything in between is n-way set-associative, the notes' equation (74).

A block goes to exactly one set — block address mod #sets — and into any free way of that set.

What the freedom costs. To find a block, the cache compares the tags of all n ways of the set at once: n comparators as wide as the tag, plus a multiplexer that picks the data of the way that matched. A direct-mapped cache needs one comparator and can hand out the data while the tag is still being checked, which makes it the simplest and fastest. A fully associative cache needs one comparator per line: the most flexible, the most expensive, the slowest — kept for small structures. Set-associative is the compromise: few conflicts for a few comparators.

Identification: tag, index, offset

The paper hands you block numbers. A processor issues addresses of bytes (or words), and a block holds many of them. Take I0 of the loop in its third iteration: it reads X[2], at byte address 400 if X starts at 384 = 12 × 32. Then 400 = 12 × 32 + 16: block 12, byte 16 of the block. With 16-bit addresses and the 2-way cache of Fig. 2 (32-byte blocks, 4 sets), the bits of 400 split as 000000011 | 00 | 10000: the last five bits are the byte inside the block (16), the next two the set (12 mod 4 = 0), the remaining nine the tag (12 div 4 = 3).

The cache reads these three fields off every address, from right to left: the offset (which byte or word inside the block), the index (which set) and the tag (everything else). With powers of two, each field is a count of bits:

In the paper's units the offset is gone — its addresses are already block numbers — and the split is 5 = 4 + 1: a 4-bit tag and a 1-bit index, the last bit, which says whether the block is even (set 0) or odd (set 1).

Finding a block is one parallel step. The index selects the set; the tag of every way in it is compared with the tag of the address, all at once; a way hits when its V is 1 and its tag is equal. The index itself is never compared with anything — a line does not even store it, because its position is the index. That is why only the tag needs storing.

The July 2024 quiz, one step at a time

Quiz 2 of the same paper asks for exactly these widths: "main memory size = 4 Giga word; 4-way set-associative cache with cache size = 1 Mega word and block size = 256 word", addressed at word level, and four candidate structures of the 32-bit address.

1. Address width. The memory holds \(4\text{ G} = 2^{32}\) words and the address counts words:

   \[ A = 32 . \]

2. Offset. A block holds \(256 = 2^{8}\) words, so the word inside it takes

   \[ \text{offset} = \log_2 256 = 8 \text{ bits}. \]

3. Lines of the cache: cache size over block size.

   \[ \#\text{blocks} = \frac{2^{20}}{2^{8}} = 2^{12} = 4096 . \]

4. Sets: four ways share each set, and the index numbers the sets.

   \[ \#\text{sets} = \frac{4096}{4} = 2^{10} \] \[ \text{index} = \log_2 2^{10} = 10 \text{ bits}. \]

5. Tag: what is left of the 32 bits.

   \[ \text{tag} = 32 - 10 - 8 = 14 \text{ bits}. \]

   The address reads |14-bit tag | 10-bit index | 8-bit offset| — Answer 3.

6. The other answers are the same cache at other associativities: 12 | 12 | 8 is direct-mapped (4096 sets), 24 | — | 8 fully associative (one set, no index), 13 | 11 | 8 two-way. Doubling the ways halves the sets: one bit moves from the index to the tag, and the offset never moves.

Replacement: which block leaves?

Access 8 of the paper, R06, needs a line in set 0 (6 is even), and set 0 is full: block 16 came in at access 1 and was written again at access 5; block 14 came in at access 2 and was read at access 4; block 12 came at access 6, block 18 at access 7. One of the four must go. A direct-mapped cache never faces this choice — the block's only line is emptied, whatever it holds. With n ways there are n candidates, and a replacement policy picks one:

• Random — any way. Trivial hardware; it ignores locality, so it may throw out a block in heavy use.
• FIFO (first in, first out) — the block that has been in the set longest: the oldest arrival. A queue per set; it ignores use, so a block read a moment ago still goes if it came in first.
• LRU — the block whose last use is oldest; a use is any access, read or write, hit or fill. It follows temporal locality, and it must track the order of use and update it on every access, hits included.
• Pseudo-LRU — an approximation of LRU with fewer bits, for many ways (below).

"LRU evicts the oldest block" is the trap: oldest by arrival is FIFO. Block 16 is older than 14, but it was used more recently. The notes' Example 7 (p. 310) is the two-way version: set 0 holds block 4, last used 5 cycles ago, and block 8, last used 20 cycles ago; block 12 misses into set 0 and LRU replaces block 8.

What LRU costs. A set of n ways can be in n! orders of use, so exact LRU needs \(\lceil \log_2 n! \rceil\) bits per set: 1 bit for 2 ways, 5 for 4 ways, 16 for 8 ways, rewritten on every hit. Beyond four ways designers settle for pseudo-LRU — a binary tree of n − 1 bits that points away from the half used most recently — or for random, which costs nothing and loses little in a large cache. (The bit counts are not in the notes, which give only the trend, p. 318: LRU for 2–4 ways, pseudo-LRU or random above.)

What happens on a write

A read leaves cache and memory equal; a write makes them differ. Take a loop that keeps a running total in memory:

I0  LOOP: LD    F2, 0(R1)
I1        FADD  F4, F4, F2
I2        SD    F4, 0(R3)
I3        ADDUI R1, R1, 8
I4        BNE   R1, R2, LOOP

In eight iterations I2 stores eight times to the same word S. What does main memory see? Two separate decisions answer it: where a write goes, and what a write miss does.

Where the write goes

Write-through: the value is written into the cache line (if the block is there) and into main memory. Memory is always up to date and the policy is simple — but every store becomes a memory write, eight for the loop, each as slow as main memory. A write buffer hides that time: the store drops address and value into a small queue and the processor goes on while the buffer drains to memory; it stalls only when the buffer is full.

Write-back: the value is written into the cache only, and the line's dirty bit is set. Memory receives the block once, when the dirty block is evicted: the eight stores of the loop cost one block write. The price is a dirty bit per line, a memory that is stale until the eviction, and a miss whose victim is dirty must write it back before (or while) it fetches the new block — exactly the "read that writes" of the puzzle.

What a write miss does

The first I2 misses: S has never been in the cache. Write-allocate treats a write miss like a read miss: fetch the block into a line, then write it there — the next seven stores hit. No-write-allocate (write-around) sends the word straight to memory and leaves the cache alone — so the next store to S misses again. It suits data written once and not read soon, such as an output array: no fetch, no useful block evicted.

Why the policies pair as they do (the notes' Table 26). With write-back, allocation pays: once the block is in the cache, every later store to it is a hit that costs no traffic. With write-through, every store goes to memory anyway, so fetching the block on a write miss buys nothing but the fetch. Hence write-back with write-allocate, and write-through with no-write-allocate.

With write-back, memory is written only when a dirty block leaves the cache — that is the "Write in memory" column of the exam.

The exam cache table, end to end

Back to Exercise 3. The paper first asks "How many sets?": 8 blocks / 4 ways = 2, Answer 1. The 5-bit block address then splits into a 4-bit tag and a 1-bit set: set = address mod 2 (is the address even or odd?), tag = address div 2. Lines a–d form set 0, lines e–h set 1 (the natural reading; the paper does not say). A missing block goes into the first free line of its set in alphabetical order — the paper's given row 1 puts block 16 into line a — and into the LRU line once the set is full. Each row then takes six moves:

1. Set = address mod #sets; Cache Tag = address div #sets, in binary — four digits here.
2. Look in the set. Same tag with V = 1: Hit, in that line. Otherwise a miss, and the first reference to a block is a Cold-start Miss — the paper's name for a compulsory miss (lesson 24 names the other kinds).
3. Cache Address: the line that hit; on a miss, the first free line of the set, or the LRU line if the set is full.
4. Dirty bit: 1 after a write (write-allocate fills the line, then writes it), 0 after a read fill; a read hit leaves it as it was.
5. Write in memory: Yes only when the evicted block is dirty — never because of the write itself.
6. Update the order of use of the set: the accessed block becomes the most recent, hits included.

The puzzle, solved. The seven writes never reached memory when they happened: write-back keeps them in the cache and sets the dirty bit. Memory is written only twice, at the two evictions of a dirty block. Access 8, a read of block 6, needs a line of the full set 0, and LRU picks block 14 — dirty since access 2, so the value written at access 2 reaches memory six accesses later, during a read. Access 9 evicts block 16, dirty since accesses 1 and 5. Access 10 evicts block 12, which was only ever read: clean, nothing to write. Eight misses in ten accesses, a miss rate of 80 %; and when the sequence ends, blocks 4, 30, 18 and 7 are still dirty in the cache — their writes reach memory only when they are evicted.