Memory Hierarchy

A fully associative cache holding 2 lines with LRU replacement starts empty. If blocks are referenced in the order A, B, A, C, B, A, how many misses occur?

  1. A4
  2. B5
  3. C6
Show answer and explanation

Answer: B. 5

Step by step: A (miss, [A]), B (miss, [A,B]), A (hit, A becomes most recent), C (miss, evicts least recent B, [A,C]), B (miss, evicts least recent A, [C,B]), A (miss, evicts least recent C, [B,A]), for 5 misses. Counting 4 comes from wrongly evicting A when C arrives; under LRU, the hit on A made it the most recent. 6 overlooks the hit on the third reference.

  • A. 4 results from evicting the wrong block.
  • B. Correct. Only the third reference (A) hits, giving 5 misses.
  • C. 6 overlooks the hit on the third reference to A.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. For which access pattern is hardware prefetching especially effective?
  2. When inserting software prefetch instructions, which statement about how far ahead to fetch (the prefetch distance) is correct?
  3. In the loop above, an int is 4 bytes, a cache line is 64 bytes, and the array is not cached and starts on a line boundary. Without prefetching, what is the miss rate for reading the array?
  4. What is the main purpose of loop blocking (tiling), used for example in matrix multiplication?
  5. For a loop that sums only the x coordinates as above, why does converting to a structure of arrays (a separate array per field) tend to be faster?