Misses and Associativity in Caches

---

Question: Finding the Number of Misses
Assume there are three small caches, each consisting of four one-word blocks:

• one cache is fully associative,
• a second is two-way set-associative, and
• the third is direct-mapped.

Find the number of misses for each cache organization given the following sequence of block addresses: 0, 8, 0, 6, and 8.

Answer:

The answers for the three caches are given as follows:

Direct-mapped cache

The table on the right shows to which cache block each block address maps. The following table shows the cache contents after each reference.

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

A blank entry means that the block is invalid, colored text in italic type shows a new entry added to the cache for the associated reference, and plain text shows an old entry in the cache:

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

The direct-mapped cache generates five misses for the five accesses.