Misses and Associativity in Caches (Cont.)

---

Set-associative cache

The cache has two sets (with indices 0 and 1) with two elements per set. The table on the right shows to which cache block each block address maps.

Block address Cache block 0 0 modulo 2 = 0 6 6 modulo 2 = 0 8 8 modulo 2 = 0


A replacement rule is needed for a choice of which entry in a set to replace on a miss. Set-associative caches usually replace the least recently used block within a set. The table below shows sample contents of a set-associative cache. The two-way set-associative cache has four misses, one less than the direct-mapped cache.



Address of memory block accessed	Hit or miss	Contents of cache blocks after reference
		Set 0	Set 0	Set 1	Set 1
0	miss	Memory[0]
8	miss	Memory[0]	Memory[8]
0	hit	Memory[0]	Memory[8]
6	miss	Memory[0]	Memory[6]
8	miss	Memory[8]	Memory[6]




Fully associative cache

The fully associative cache has four cache blocks (in a single set); any memory block can be stored in any cache block. The fully associative cache has the best performance, with only three misses:



Address of memory block accessed	Hit or miss	Contents of cache blocks after reference
		Block 0	Block 1	Block 2	Block 3
0	miss	Memory[0]
8	miss	Memory[0]	Memory[8]
0	hit	Memory[0]	Memory[8]
6	miss	Memory[0]	Memory[8]	Memory[6]
8	hit	Memory[0]	Memory[8]	Memory[6]