When caches reach capacity, we need a policy block replacement.

  • Least Recently Used (LRU): Replace the entry that has not been used for the longest time. But we need complicated hardware to keep track of access history.
  • Most Recently Used (MRU): Replace the entry that has the newest previous access.
  • Random - When we decide to evict a cache block to make space, we randomly select one of the blocks in the cache to evict.
  • FIFO: Replace the oldest block in the set (queue)
  • LIFP: Replace the newest block in the set (stack).

Store instructions write to memory, which changes values. Hardware needs to ensure that cache and memory have consistent information.

  • Write-through: Write to the cache and memory at the same time. (writes to memory take longer)
  • Write-back: Write data in cache and set a dirty bit to 1. When this block gets evicted from the cache (and “back” to memory), write to memory.
  • Write-around: It means that in every situation, data is written to main memory only; if we have the block we’re writing in the cache, the valid bit of the block is changed to invalid. Essentially, there is no such thing as a write hit in a write-around cache; a write “hit” does the same thing as a write miss.

There are also two miss policies you should know about:

  • Write-allocate means that on a write miss, you pull the block you missed on into the cache. For write-back, write-allocate caches, this means that memory is never written to directly; instead, writes are always to the cache and memory is updated upon eviction.
  • No write-allocate means that on a write miss, you do not pull the block you missed on into the cache. Only memory is updated.

The ordinary pairing of hit policy/miss policy is write-back/write-allocate and write-through/no write-allocate.

Direct Mapped Cache : Put a new block in one specific place. Each memory address is associated with exactly one possible block in the cache. Its index is compute by its index bit modulo

If the number of entries in the cache is a power of 2, we’ll use $\log_2{X}$ index bits, where X is number of blocks in the cache. Its cache index will be its index bits modulo X.

For example, if we have 8 blocks in the cache, then we’ll use 3 index bits.

If we need to read the memory at address 0x43F, it can be spiled into

\[\underbrace{0100 \,\, 0}_\text{tag} \underbrace{011\,\, 1}_\text{index}\underbrace{111}_\text{offset}\]

Types of misses

  • Compulsory miss: Caused by the first access to a block that has never been in the cache
  • Capacity miss
  • Conflict miss: Multiple blocks compete for the same location in the cache, even when the cache has not reached full capacity. It occurs in direct mapped caches but not occur in a fully associative cache.