Summary

And in Conclusion$\dots$

Replacement policies:

• For direct-mapped caches, each block of memory maps to one specific block in our cache. On a cache miss, if there is data present in that cache block, then we must evict the block to make room for our new data.
• For non-direct-mapped caches, we can choose one of multiple cache blocks to place our new data. When our cache is full, we will have to decide which block to evict to make space for the new data. Block Replacement policies decide which block should be replaced.
  • Least recenty used (LRU)
  • First-in, first-out (FIFO)
  • Random 见 #tab-cache-replacement Write policies: 见 #tab-cache-write

Textbook Readings

P&H 5.1-5.4, 5.8, 5.9, 5.13

Additional References

• Cache Flowchart

Amazing Illustrations by Ketrina (Yim) Thompson: CS Illustrated Cache Handouts

• Cache Basics
• Cache Associativity
• Cache Misses

Exercises

Check your knowledge!

Short Exercises

Solution

False.

Solution

True. A direct-mapped cache needs to index every block of the cache, whereas a 4-way set associative cache needs to index every set of 4 blocks. The 4-way set associative cache will have 2 fewer index bits than the direct-mapped cache.

Solution

False. Similar to the previous question, the impact depends on the program. If a program iterates through contiguous memory (like an array), having larger block sizes with fewer blocks may be beneficial as each block contains more contiguous data. For instance, if Cache A has 10 blocks and a block size of 8 bytes while Cache B has 20 block and a block size of 4 bytes, and we loop through an array of 80 characters, Cache A will experience 10 cache misses and 70 hits, while Cache B will have 20 misses and 60 hits.