Memory Hierarchy

For which access pattern is hardware prefetching especially effective?

  1. AReading an array in order at a fixed interval (stride)
  2. BFollowing a linked list one element at a time from the head
  3. CLooking up a hash table with random keys
Show answer and explanation

Answer: A. Reading an array in order at a fixed interval (stride)

A hardware prefetcher detects regularity in recent addresses, such as sequential or constant-stride patterns, predicts upcoming addresses and loads them ahead of time. Reading an array at a fixed stride is easy to predict, so the benefit is large. In a linked list the next element's address is unknown until the current one is read, so there is no pattern to predict. Random-key hash lookups also lack address regularity, so prefetching helps little.

  • A. Correct. Regular strides are easy to predict, so the benefit is large.
  • B. The next address is unknown until the current element is read, so it cannot be predicted.
  • C. Addresses have no regularity, so the benefit is small.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. When inserting software prefetch instructions, which statement about how far ahead to fetch (the prefetch distance) is correct?
  2. 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?
  3. What is the main purpose of loop blocking (tiling), used for example in matrix multiplication?
  4. 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?
  5. What is the main advantage of splitting the L1 cache into an instruction cache (I-cache) and a data cache (D-cache)?