Memory Hierarchy

In contrast to LRU, which evicts the least recently used block, optimal replacement (OPT) evicts the block that will not be used for the longest time. Which statement about OPT is correct?

  1. AIt is the most common replacement policy, widely used in real caches
  2. BIt cannot be built but gives a lower bound on misses
  3. CIt produces exactly the same number of misses as LRU for every access sequence
Show answer and explanation

Answer: B. It cannot be built but gives a lower bound on misses

Optimal replacement (Bélády's OPT) assumes the future access order is known and evicts the block whose next use is furthest away, giving the theoretical minimum number of misses. Real hardware cannot see the future, so it cannot be implemented; instead it is applied to recorded access traces to evaluate how close policies such as LRU come to optimal. It evicts different blocks than LRU, so miss counts generally differ.

  • A. It requires knowing the future, so real caches cannot use it.
  • B. Correct. It cannot be built but provides a lower bound on misses.
  • C. It evicts different blocks, so miss counts generally differ.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. What generally happens to hit time as cache capacity increases, and why?
  2. Why does traversing the linked list above tend to be much slower than reading an array with the same number of elements in order?
  3. Each miss fetches a 64-byte line and memory latency is 100 ns. With only one miss outstanding at a time, read bandwidth is about 0.64 GB/s. If 10 misses can be outstanding at once, what is the bandwidth approximately (assuming no other limits)?
  4. When writing out a large amount of data that will not be read back for a while, what is the main benefit of non-temporal stores that bypass the cache?
  5. If the cache hit rate is 95%, what is the miss rate?