CS3350B Computer Organization Chapter 1: CPU and Memory Cache Miss Types Explained
Alex Brandt
Department of Computer Science University of Western Ontario, Canada
Monday January 25, 2021
Alex Brandt
Chapter 1: CPU and Memory, Cache Miss Types Explained Monday January 25, 2021 1 / 7
Three Types of Cache Misses
Cold Miss
ë Caused by the first time you try to access a particular memory address
(and it is not contained in some other previously accessed cache block). Capacity Miss
ë Occurs when you are working with too much memory at one time.
ë Must involve re-using some previously referenced data that is no longer
in cache because the cache filled with other data.
ë This is caused by poor temporal locality.
Conflict Miss
ë ë ë ë
Occurs when two different memory addresses being accessed map to the same cache block.
Expect a cache hit based on the cache’s capacity and good temporal locality, but it ends up being a miss.
“Conflict misses are misses that would not occur if the cache was fully-associative and had LRU replacement.” (Jouppi, 1990) Just because two addresses map to the same block does not mean it is a conflict miss.
Alex Brandt
Chapter 1: CPU and Memory, Cache Miss Types Explained Monday January 25, 2021 2 / 7
Differentiating By Example: Cold Miss
Say we have a direct-mapped cache with two one-word lines:
0 1
and the sequence of memory accesses: 0, 1, 2, 3, 4, 5, 6, …
These will all be cold misses.
No capacity misses. These imply poor
temporal locality and working with too much data at one time.
Since no address is accessed twice, it all cold misses.
0
1
00 1
00 11
202 11
02 13
04 13
04 15
3
4
5
6 06 15
Alex Brandt Chapter 1: CPU and Memory, Cache Miss Types Explained
Monday January 25, 2021
3 / 7
Differentiating By Example: Cold Miss
Same cache as before. Two lines:
0 1
New sequence of memory accesses: 0, 1, 2, 3, 0, 1, 2, …
First few are cold misses, then we get capacity misses.
We use too much data before accessing 0, 1, 2 again.
(For this limited cache size) poor temporal locality in 0, 1, 2.
cold
cold
cold
cold
capacity
capacity
capacity 02
10
0, 1, 2, 3, 0, 1, 2,
00 1
00 11
02 11
02 13
00 13
00 11
Alex Brandt Chapter 1: CPU and Memory, Cache Miss Types Explained
Monday January 25, 2021
4 / 7
Differentiating By Example: Conflict Miss 1
Same cache as before. Two lines:
0 1
New sequence of memory accesses: 0, 16, 0, 16, 0, 16, 0, …
Temporal locality is good, and everything fits into the cache’s size, but we get many misses.
Characteristic thrashing.
0, cold 16, cold 0, conflict
16, conflict 0, conflict 16, conflict
0, conflict
00 1
0 16 1
00 1
0 16 1
00 1
0 16 1
00 1
Alex Brandt Chapter 1: CPU and Memory, Cache Miss Types Explained Monday January 25, 2021 5 / 7
Differentiating By Example: Conflict Miss 2
Now a direct-mapped cache with two two-word lines:
0 1
New sequence of memory accesses: 0,16,17,1,18,2,18,…
Would increasing associativity fix the miss?
0, cold 16, cold 17, hit
1, conflict 18, cold
2, cold
18, conflict
001 1
0 16 17 1
0 16 17 1
001 1
001 1 18 19
001 123
001 1 18 19
Alex Brandt Chapter 1: CPU and Memory, Cache Miss Types Explained Monday January 25, 2021 6 / 7
Differentiating By Example: Conflict Miss 3
0, cold 16, cold 17, hit 1, hit 18, cold 2, cold 18,hit
01
0
Now a cache with two two-word lines but 2-way associativity:
0
Same sequence of memory accesses:
0, 16, 17, 1, 18, 2, 18, …
Increasing associativity made previous conflict misses hits!
0 01 16 17
0
0
01 16 17
01 16 17
0 01 18 19
0
23 18 19
0 2 3 18 19
Alex Brandt Chapter 1: CPU and Memory, Cache Miss Types Explained Monday January 25, 2021 7/7