Cache organization — direct-mapped, n-way set associative, fully associative: Foundations

Before you can read the parent note, you must own eleven small ideas. We build them one at a time — each one earns the next. Nothing is assumed.

1. A "bit" and why we count in powers of two

Why does hardware love powers of two? Because with $k$ switches side by side you can make exactly $2^{k}$ different patterns — and every pattern is used, none wasted.

Figure — Cache organization — direct-mapped, n-way set associative, fully associative

This is the single arithmetic move the whole topic runs on:

2. The symbol $lo g_{2}$ — the tool that "un-doubles"

Why do we need a new symbol instead of ordinary multiplication? Because doubling and un-doubling are the exact question the address split asks: "I have $256$ boxes — how many switches address them?" Multiplication gives you the count forward ( $2 \times 2 \times \dots$ ); $lo g_{2}$ runs it backward.

3. A memory address and its width $m$

If $m = 32$ , there are $2^{32}$ distinct addresses, i.e. $2^{32}$ bytes of addressable memory. The parent note's " $2^{32}$ bytes" is literally " $m = 32$ " spoken out loud.

4. A block (line) and its size $B$

Memory is not copied one byte at a time — that would waste the trip. It moves in fixed chunks.

Why chunks? Because programs tend to use neighbours soon after each other (this is spatial locality) — grabbing the whole neighbourhood at once pays off.

5. Block number vs. block offset — splitting the address once

Take any byte address and ask the two questions above.

6. The floor $⌊ \cdot ⌋$ and mod $mod$ — two symbols we just used

Why these two? Because "which block" and "which byte inside" are exactly integer division and remainder.

7. The cache's shape: sets $S$ , ways $E$ , total blocks $N$

8. Tag $t$ , index $s$ , offset $b$ — the three field widths

Now we name the widths (bit counts) of the three fields. Each is a small $lo g_{2}$ .

9. The valid bit — "is this slot even filled?"

When the machine powers on, every slot holds garbage. We need one switch per slot to say "ignore me until I've been loaded."

Without it, a random leftover tag could accidentally "match" and hand you wrong data. It is the AND-guard on every lookup.

10. Hit, miss, and the comparator

This is why fully associative ( $E = N$ ) is expensive: $N$ comparators screaming on every access. It leads straight into average access time reasoning and the 3 C's miss model you'll meet later.

11. The `mod` placement rule — where a block is allowed to live

Putting it together: a block with number $k$ is sent to set

$set of block k = k mod S .$

Once $E > 1$ , two blocks sharing a set can both stay — but then you must choose whom to evict on a later miss, which is the job of replacement policies. Direct-mapped ( $E = 1$ ) never chooses: one legal slot, no policy needed.

How the pieces feed the topic

Equipment checklist

You are ready for the parent note when you can answer each without peeking.

How many distinct patterns do $k$ bits make? ::: $2^{k}$ .
What does $lo g_{2} n$ ask? ::: " $2$ to what power equals $n$ ?" — the number of doublings.
What is $lo g_{2} 64$ and why? ::: $6$ , because $2^{6} = 64$ .
What does $m$ stand for and what is $2^{m}$ ? ::: address width in bits; $2^{m}$ = number of addressable bytes.
Why is memory moved in blocks of $B$ bytes, not single bytes? ::: to exploit spatial locality — neighbours get used soon.
Given a byte address, how do you get its block number? ::: $⌊ address / B ⌋$ (chop off the low $lo g_{2} B$ bits).
What does $a mod n$ compute and why is it perfect for choosing a set? ::: the remainder; it always lands in ${0, \dots, n - 1}$ , one bin per set.
Define $S$ , $E$ , $N$ and their relationship. ::: sets, ways (blocks per set), total slots; $N = S \cdot E$ .
Give the three field widths. ::: $b = lo g_{2} B$ , $s = lo g_{2} S$ , $t = m - s - b$ , with $t + s + b = m$ .
Why does fully associative have the largest tag? ::: $s = 0$ , so $t = m - b$ ; the tag must hold the whole block number.
What two conditions make a hit? ::: valid bit $= 1$ AND stored tag equals address tag.
How many comparators does an $E$ -way cache need? ::: exactly $E$ .
Which set does block $k$ map to, and which bits does that use? ::: $k mod S$ , using the lowest $s$ bits of the block number.