Set-associative and fully associative caches: Visual walkthrough

This page builds the whole idea of a set-associative cache from absolute zero. We will start with nothing but "memory is a long list of numbered boxes" and end holding the exact formula the parent note states:

$S = \frac{C}{B \times N}$

Every symbol will be earned — drawn as a picture — before it appears in a formula. If you have never seen a cache before, start at line one and keep going.

Prerequisite worth peeking at first: Direct-mapped caches. We build on top of it.

Step 1 — Memory is a strip of numbered boxes

WHAT. Main memory is one long row of byte-sized boxes. Each box has an address — just its position number, counting from 0.

WHY. Before we can ask "where does address 76 go in the cache?", we must agree what an address is. It is nothing mysterious: it is the box's seat number in a very long row.

PICTURE. In the figure the top strip is main memory. Box 0 is on the left; the numbers climb to the right. One highlighted box is the byte we want.

For all examples on this page we use $A = 32$ bits, so there are $2^{32}$ possible addresses — about 4 billion boxes.

Step 2 — We never move one byte, we move a whole block

WHAT. Memory is not copied one byte at a time. It is copied in fixed-size chunks called blocks. A block is $B$ consecutive bytes that always travel together.

WHY. Two reasons. Hardware moves data in bursts, so grabbing 64 bytes costs almost the same as grabbing 1. And programs tend to use neighbouring bytes soon after each other (spatial locality), so the neighbours are worth grabbing now.

PICTURE. The strip from Step 1 is now fenced into groups of $B$ boxes. Each fence-group is one block. The address of the byte we want splits naturally into "which block?" plus "which byte inside that block?".

Why $lo g_{2}$ and not something else? Because each bit doubles how many things you can name: $1$ bit names $2$ , $2$ bits name $4$ , ... $b$ bits name $2^{b}$ . To name exactly $B$ boxes you invert that doubling — and the inverse of "double it $b$ times" is $lo g_{2}$ .

Step 3 — The cache is a small shelf of lines

WHAT. The cache is a small shelf. Each slot on the shelf holds exactly one block and is called a line. If the cache holds $C$ bytes total and each block is $B$ bytes, the number of lines is:

$L = \frac{C}{B}$

WHY. A line is block-shaped on purpose — it is the exact container a block drops into. Count the total bytes, divide by bytes-per-block, and you have how many blocks fit. Nothing subtler than sharing a pizza.

PICTURE. The big memory strip on top; the tiny cache shelf below it. The shelf has far fewer slots than memory has blocks — that is the whole reason we need a rule for which block sits where.

$C$ = total cache size in bytes.
$B$ = block size in bytes (same $B$ as Step 2).
$L$ = number of lines = number of block-shaped slots on the shelf.

Example: a $64 KB$ cache with $64$ -byte blocks has $L = 65536/64 = 1024$ lines.

Step 4 — Direct-mapped: one forced home (and why it hurts)

WHAT. The simplest rule: block number $mod L$ gives the one and only line the block may use. This is a direct-mapped cache.

WHY show the pain first. We need to feel the problem before we fix it. When two hot blocks both map to the same line, they play "evict tag" forever — each kicks the other out — even while the rest of the shelf sits empty. That repeated eviction is a conflict miss (see Conflict misses vs capacity misses).

PICTURE. Two coral arrows from two different memory blocks both land on the same single line. The mint lines beside it are empty — wasted. That waste is the enemy.

Step 5 — Give each block a small set of homes

WHAT. Instead of one forced home, group the lines into sets of $N$ lines each. A block still maps to one specific set, but inside that set it may sit in any of the $N$ lines. $N$ is the associativity (the number of "ways").

WHY. Choice is the cure. With $N$ slots to choose from, two colliding blocks can both stay resident — they only fight when a third block wants the same set. We traded a rigid single home for a small apartment block.

PICTURE. The shelf from Step 3 is now bracketed into sets. Each set is a little group of $N$ lines. The two previously-colliding coral blocks now happily occupy two different lines of the same set.

Step 6 — Count the sets: the central formula

WHAT. We have $L$ lines total, and we bundle them $N$ to a set. So the number of sets is $L$ divided by $N$ . Substitute $L = C / B$ from Step 3:

$S = \frac{L}{N} = \frac{C}{B \times N}$

WHY this is the result. Everything about addressing a set-associative cache falls out of $S$ . It is the parent note's headline formula — and now every letter in it is a picture you have already seen:

$C$ = total cache bytes (the whole shelf, Step 3).
$B$ = block bytes (one fence-group, Step 2).
$N$ = ways per set (apartment size, Step 5).
$S$ = number of sets (how many apartment blocks).

PICTURE. The division shown literally: $L$ lines flowing into stacks of height $N$ ; count the stacks — that count is $S$ .

Sanity checks (the two extremes must agree with Steps 4 and 8):

$N = 1 \Rightarrow S = L$ → as many sets as lines → one line per set → direct-mapped. ✓
$N = L \Rightarrow S = 1$ → a single set holding everything → fully associative. ✓

Step 7 — Cut the address into Tag / Index / Offset

WHAT. The address is now sliced into three fields, from lowest bits to highest:

$⟨ t bits Tag ∣ i bits Set Index ∣ b bits Offset ⟩$

with

$b = lo g_{2} (B), i = lo g_{2} (S), t = A - i - b$

WHY each field exists — read them right-to-left, the order they answer questions:

Offset ( $b$ bits, from Step 2): which byte inside the block?
Index ( $i$ bits): which set do I search? We need to name one of $S$ sets, and $lo g_{2} (S)$ bits name exactly $S$ things — same doubling logic as Step 2.
Tag ( $t$ bits): of all blocks that share this set, which one am I? Whatever bits are left over after offset and index — that is $A - i - b$ .

PICTURE. A single 32-bit address bar, coloured in three pastel bands, each band labelled with its job and its bit count.

Step 8 — The extreme case: fully associative (no index at all)

WHAT. Push $N$ all the way up to $L$ . Then $S = L / N = 1$ : a single set holding every line. With only one set there is nothing to choose — so the index field vanishes:

$⟨ A - b bits Tag ∣ b bits Offset ⟩$

WHY the index disappears. Index bits exist only to pick a set. With $S = 1$ there is nothing to pick — $i = lo g_{2} (1) = 0$ bits. Those bits get absorbed into the tag, which now must identify the block among all of memory, so it grows to $t = A - b$ .

PICTURE. The three-band address bar from Step 7 collapses: the index band shrinks to zero width and the tag band swells to fill it. A block-arrow points at every line — it may live anywhere.

Step 9 — Finding the block: parallel comparison and the two edge results

WHAT. Inside the chosen set, the hardware lays all $N$ tags side by side and compares them to the address's tag in the same clock cycle, using $N$ separate comparators. A line counts as a match only if its stored tag equals the address tag and its valid bit is 1.

WHY parallel, not one-by-one. Checking $N$ tags in sequence would multiply hit time by $N$ — killing the speed that made us build a cache. So we pay in hardware (N comparators) to keep time flat. That trade — more silicon for the same speed — is the true cost of associativity.

The two outcomes (both cases covered):

HIT: exactly one tag matches with valid = 1 → grab that line's bytes at the offset. Fast.
MISS: no tag matches (or the matching line is invalid) → fetch the block from memory. If the set is full, a replacement policy (LRU, FIFO, random) picks which line to evict.

Degenerate detail: on a cold cache every valid bit is 0, so every access is a MISS regardless of associativity — a compulsory miss, which no amount of ways can prevent.

PICTURE. Set 76 with its 4 tags feeding 4 comparators into one OR gate: any TRUE → HIT lights up; all FALSE → MISS lights up.

The one-picture summary

Everything above, on one canvas: address bar on top → offset picks the byte, index picks the set, tag races the $N$ comparators → HIT or MISS → and the master formula $S = C / (B N)$ tying it together, with direct-mapped ( $N = 1$ ) and fully associative ( $N = L$ ) as the two ends of the dial.

Recall Feynman retelling — say it back in plain words

Memory is a long row of numbered boxes. We copy it in fixed chunks called blocks, $B$ bytes each — so the bottom $lo g_{2} B$ bits of any address just say which byte inside the chunk. The cache is a small shelf of block-shaped slots called lines; there are $C / B$ of them. A rigid "one home per block" rule (direct-mapped) makes two hot blocks fight over one slot while the shelf sits empty — a conflict miss. So we bundle the lines into sets of $N$ , and a block may sit in any line of its set. Bundle $L$ lines $N$ -at-a-time and you get $S = C / (B N)$ sets — the one formula that runs everything. The address then splits three ways: offset (which byte), index (which of $S$ sets, needing $lo g_{2} S$ bits), tag (everything left, to tell apart the blocks sharing a set). To find data we jump to the indexed set and race all $N$ tags through $N$ comparators in one clock tick; a match with a valid bit is a HIT, otherwise a MISS and we evict someone by a replacement policy. Crank $N$ down to 1 and it's direct-mapped again; crank it up to $L$ and there's one giant set with no index — fully associative, no conflicts, but a comparator per line.

Recall

Number of sets in an N-way cache of size C with block size B ::: $S = C / (B \times N)$ Why does the index field disappear in a fully associative cache ::: Because $S = 1$ , and $lo g_{2} (1) = 0$ index bits are needed — there is nothing to choose. Two conditions for a HIT ::: The stored tag matches the address tag AND that line's valid bit is 1. What does raising associativity cost, and what does it not buy ::: Costs more comparators (area/power); does NOT add storage capacity. A cache that's nearly empty still thrashes — why ::: Conflict misses come from lack of choice (mapping), not lack of space.

See also: Cache replacement policies · Conflict misses vs capacity misses · Write policies · Cache coherence · Cache performance metrics · 5.4.03 Set-associative and fully associative caches (Hinglish)