Memory Hierarchy

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?

int a[1024];
for (i = 0; i < 1024; i++)
    sum += a[i];
  1. A12.5%
  2. B6.25%
  3. C100%
Show answer and explanation

Answer: B. 6.25%

A 64-byte line holds 64 ÷ 4 = 16 ints. Reading in order misses once on the first element of each line and hits on the remaining 15, so the miss rate is 1 ÷ 16 = 6.25%. For 1,024 elements that is 1,024 ÷ 16 = 64 misses. 12.5% would result from thinking only eight elements fit in a line. 100% occurs only when one element per line is used, such as reading every 16th element (every 64 bytes).

  • A. 12.5% results from assuming eight elements per line.
  • B. Correct. One miss every 16 elements gives 1/16 = 6.25%.
  • C. 100% occurs with strided access that uses one element per line.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. What is the main purpose of loop blocking (tiling), used for example in matrix multiplication?
  2. 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?
  3. What is the main advantage of splitting the L1 cache into an instruction cache (I-cache) and a data cache (D-cache)?
  4. 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?
  5. Why are L1 caches often virtually indexed and physically tagged (VIPT)?