Cache Optimizations

Reducing Miss Rate
- Larger Block size
- Larger Caches
- Higher Associativity

Reducing Miss Penalty
- multi-level Caches
- Victim caches

A. Reducing Miss Rate

Miss categories (3C)

• Compulsory – first time when we want to access a block, cold-start misses.
• Capacity – if cache cannot hold all blocks needed in a program
• Conflict – if we use direct-mapped or setassociative strategy two blocks may map to the same record in cache. Also called collision
  miss.

1. Larger Block Size

number of cache line = cache size / block size

Reduce number of compulsory misses

• Larger blocks take advantage of spatial
  locality

But

• Larger block size means that fewer blocks will be in cache – this increases conflict misses
• Increase the miss penalty

Both has optimal region.

$AMAT=Hit time+Miss rate×Miss penalty$

Overall: Increasing block size initially helps through spatial locality. Excessively large blocks can waste cache space and take longer to fetch, making AMAT worse. The block size with the lowest miss rate does not necessarily give the lowest AMAT.

Example 1

Memory system takes 80 clock cycles of overhead and then delivers 16 bytes every 2 clock cycles. Miss rates for various block sizes are as follows.

Which block size gives us the smallest average memory access time?

Why doesn’t the lowest miss rate always win?
For the 64 KB cache, increasing the block from 64 B to 128 B lowers the miss rate from 1.06% to 1.02%, but increases the miss penalty from 88 to 96 cycles. The longer penalty outweighs the small miss-rate improvement.

If you can choose both cache size and block size, the smallest AMAT in this table is $H+0.4488$ cycles, using a 256 KB cache with 64 B blocks.

Memory:
Low latency + low bandwith : small
Hight latency + hight bandwith: large

2. Larger Caches

• Reduce number of capacity misses

• But increase hit time and have higher cost

3. Higher Associativity

Experiments show that:

• 8-way set associative cache has almost the same miss rate as fully associative cache
• Direct mapped cache of size N has about the same miss rate as 2-way set associative cache of size N/2 (2:1 cache rule of thumb)

Greater associativity can come at the cost of increased hit time

Remember: Larger blocks help spatial locality;
larger caches reduce capacity misses;
higher associativity reduces conflict misses.

---