Memory Hierarchy

When inserting software prefetch instructions, which statement about how far ahead to fetch (the prefetch distance) is correct?

  1. AShorter is better; inserting it just before the next element is read is optimal
  2. BLonger is better; fetching all the data the loop will use at the very start is optimal
  3. CNeither too short nor too long; it is chosen from the miss latency and the time per iteration
Show answer and explanation

Answer: C. Neither too short nor too long; it is chosen from the miss latency and the time per iteration

A prefetch is useless unless the data arrives from memory before it is needed. If the distance is too short, the data arrives late; if too long, fetched data may be evicted before use or pollute the cache. A rule of thumb is to fetch ahead by the miss penalty divided by the time per loop iteration. Prefetching just before use cannot hide latency, and fetching everything up front does not fit in the cache.

  • A. Just before use, the fetch cannot complete in time and latency is not hidden.
  • B. Fetching everything first gets data evicted before it is used.
  • C. Correct. Choose a distance that arrives in time yet is not evicted, from the miss latency and iteration time.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. 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?
  2. What is the main purpose of loop blocking (tiling), used for example in matrix multiplication?
  3. 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?
  4. What is the main advantage of splitting the L1 cache into an instruction cache (I-cache) and a data cache (D-cache)?
  5. In a system with 4 KB pages and 64-byte lines, an L1 cache is to be virtually indexed and physically tagged (VIPT) with the index and offset taken only from page-offset bits. If it is 8-way set-associative, what is its maximum capacity?