Associativity

Direct-mapped is fast but blocks collide (12 and 20 fight over line 4). Associativity gives a block more than one place to sit, cutting the miss rate. Final Q3(c) is about the degrees of associativity.

1. The three placement schemes

Where can memory block 12 go in an 8-line cache?

Green = a line where block 12 is allowed. More associativity ⇒ more choices ⇒ fewer conflict misses.

Scheme	Places for a block	Index	Trade-off
Direct-mapped	exactly 1 (1-way)	full index	fastest lookup, most conflicts
n-way set assoc.	n lines (one set)	smaller index (selects a set)	balance
Fully associative	any line	no index — all tag	fewest misses, slowest/most-costly search

2. Degrees of associativity — the counting rule

A cache with

2^n

blocks/entries has

(n+1)\ \text{possible configurations of associativity: } 1,\,2,\,4,\,\ldots,\,2^{n}\text{-way}

Cache size	Configurations	List
8 blocks $(2^3)$	4	1-, 2-, 4-, 8-way
16 blocks $(2^4)$	5	1-, 2-, 4-, 8-, 16-way
$2^n$ blocks	$n+1$	$1,\,2,\,\ldots,\,2^n$ -way

The two extremes are just special cases:

1-way = direct-mapped (each set holds one line).
$2^n$ -way = fully associative (one set holds every line).

So for a

2^n

-entry cache: direct-mapped is the 1-way config; fully associative is the

2^n

-way config.

Section checklist

Define direct / set-associative / fully associative and where a block may go in each.
A 2ⁿ-block cache has n+1 associativity configurations (1 … 2ⁿ-way).
Direct-mapped = 1-way; fully associative = 2ⁿ-way.