How do we map cache?
Memory Address 31 to N N - 1 to 0 Cache Block size = 2^N bytes (N is offset)
Memory Address 31 to N+M-1 -> Tag N+M-1 to N -> Index N-1 to 0 -> Offset Cache Block size = 2^N Number of cache blocks = 2^M Offset = N Bits
Purpose of offset
Tells us which word to return
e.g. offset = 0100
Data = | I | J | K | L
We return J.
How to check for cache hit?
cache[index].valid == True && cache[index].tag = tag
Example
Block Number (Not address) 00000 -> 00 00001 -> 01 00010 -> 10 00011 -> 11 00100 -> 00 (Repeat) 00101 -> 01
Cache Index 00 01 10 11 …
Example
Block 12 go to which number? 12 mod 4 -> Take last 2 bits 01100 -> 00
If number of cache blocks = \(2^M\)
Tip: Cache index of n = M last bits of n
Multple blocks can be mapped to the same cache block, but the tag number is different e.g. 000 00 and 001 00 both map to 00 but tag number 000 and 001 is different.
Cache miss
Try to get from Cache
Cannot get! -> Get from memory
Cold miss
32K direct mapped cache
128k array -> no way we can fit everything in
Conflict miss
32K direct mapped cache
2*8k array -> Cfm can fit. But! They are both aligned, map to same set. This means they will not utilize the full cache size and compete for the same sets (conflict).
Types of cache
Summary
Hit: Data in cache
- Hit rate: Fraction of memory accesses that hit
- Hit time: Time to access cache
Miss: Data is not in cache
- Miss rate = 1 - Hit rate
- Miss penalty