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).

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