Foundations — Set-associative and fully associative caches

Before you can read the parent note on set-associative and fully associative caches, you must own every symbol it throws at you. This page builds each one from nothing — plain words, then a picture, then why the topic needs it. Read top to bottom; each block only uses things defined above it.

0. The picture behind everything: memory as a giant ruler

Everything in this chapter lives on one idea: memory is one long line of numbered boxes, each box holding one byte (8 bits). The number of a box is its address.

• The book = main memory (huge, slow), millions of numbered boxes.
• The notebook = the cache (tiny, fast), only a handful of boxes.
• The whole game: copy a chunk of the book into the notebook so the CPU can read it quickly.

Keep this picture in your head. Every symbol below is a label on some part of it.

1. Bit, byte, and "how many things can this count?"

Why do we care? Because addresses are written in bits, and the number of bits tells us how many boxes we can name.

$n\text{ bits}⟶2^n\text{ distinct patterns}$

• $6$ bits $\to 2^6=64$ patterns.
• $8$ bits $\to 2^8=256$ patterns.
• $32$ bits $\to 2^{32}\approx 4.3$ billion — that is why a "32-bit address" can name about 4 GB of boxes.

2. The exponent $2^n$ and its undo: ${\log }_2$

We just used $2^n$ ("two multiplied by itself $n$ times"). The topic constantly needs the opposite question:

"I have $S$ things to name. How many bits do I need?"

That question is answered by ==${\log }_2$== (log base 2).

Why this tool and not ordinary division or ordinary logarithm? Because hardware addresses are made of bits, and each bit is a doubling. Counting doublings is exactly what ${\log }_2$ does — no other function answers "how many bit-switches?".

3. Hexadecimal — a shorthand for bits

Long strings of bits are painful. Hexadecimal ("hex") packs 4 bits into one symbol, using $0$–$9$ then $a$–$f$ for $10$–$15$. Hex numbers are written with a 0x prefix.

Why the topic needs it: addresses like 0x001A4C0 are just bit-strings in disguise. To split an address into pieces you convert hex $\to$ bits, chop, and read.

4. The address, and cutting it into three pieces

The CPU asks for a byte by its address: a fixed-width bit number (here $A=32$ bits wide, $A$ = "address width"). The cache does not treat all bits equally — it slices the address into three named fields.

Read the slice from the picture, least-significant (rightmost) first, because the low bits change fastest as you walk along the ruler:

Why three pieces and not one? Because a cache slot must answer three separate questions: where inside the block? (offset), which shelf do I search? (index), is this really the block I wanted? (tag). Each question gets its own bits.

$\underset{\text{total bits}}{\underbrace{A}}=\underset{\text{tag}}{\underbrace{t}}+\underset{\text{index}}{\underbrace{i}}+\underset{\text{offset}}{\underbrace{b}}$

5. Block and block size $B$

Why copy a whole bundle instead of one byte? Spatial locality — programs almost always use neighbouring boxes soon after, so grabbing the bundle saves future trips.

• $B$ = block size in bytes (e.g. $B=64$).
• Offset bits $b={\log }_2(B)$. With $B=64$, $b={\log }_2(64)=6$: exactly enough to name any of the $64$ bytes inside.

6. Line, cache size $C$, and total lines $L$

• $C$ = total cache size in bytes.
• Total number of lines: $L=\frac{C}{B}$

Why? Each line stores exactly $B$ bytes, and there are $C$ bytes of room, so $C/B$ lines fit. In the picture, cut the small notebook into $L$ equal shelves.

7. Sets $S$, ways $N$, and associativity

Now the star of the parent note. We group the $L$ lines into sets.

Why this formula? You have $L$ shelves; you bundle them $N$ at a time; the number of bundles is $L/N$. Substitute $L=C/B$ to get $C/(B\cdot N)$.

Read the three cases straight off the picture:

• Index bits $i={\log }_2(S)$ — enough bits to pick one of the $S$ sets.
• When $S=1$ (fully associative), $i={\log }_2(1)=0$: no index field at all. That is why the parent's fully-associative address has only tag + offset.

The direct-mapped extreme is developed further in Direct-mapped caches; the miss-type payoff is the subject of Conflict misses vs capacity misses.

8. Comparator and "parallel"

Why it matters: an $N$-way set needs $N$ comparators; a fully-associative cache of $L$ lines needs $L$ comparators. That growing pile of hardware is the price of associativity, and it drives the tradeoff table in the parent note.

9. Tag bits, assembled

Putting Sections 4–7 together gives the parent's master equation:

Prerequisite map

Related topics that build on these same foundations: Cache replacement policies, Cache performance metrics, Write policies, Cache coherence, Translation Lookaside Buffer (TLB). Prefer Hinglish? See 5.4.03 Set-associative and fully associative caches (Hinglish).

Equipment checklist

Cover the right side; can you answer each before revealing?