Memory Hierarchy

Which pair gives the reason a large matrix transpose (b[j][i] = a[i][j]) tends to cause many cache misses, and a typical countermeasure?

  1. AReason: heavy computation. Countermeasure: switch floating point to integers
  2. BReason: reads are strided. Countermeasure: make only the writes sequential
  3. CReason: reads or writes are column-wise. Countermeasure: blocked transpose
Show answer and explanation

Answer: C. Reason: reads or writes are column-wise. Countermeasure: blocked transpose

In a transpose, reading a row-wise means writing b column-wise, and writing b row-wise means reading a column-wise, so one side is always strided. Splitting the matrices into small cache-sized blocks and transposing within each block uses fetched lines fully before moving on, sharply reducing misses. Making only the writes sequential just moves the strided access to the reads, solving nothing. Computation is not the issue.

  • A. A transpose does almost no computation, and changing types does not help.
  • B. Making one side sequential only makes the other side strided.
  • C. Correct. One side is always column-wise, so transpose block by block.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. In a typical computer's memory hierarchy, which property holds more strongly for upper levels (closer to the CPU)?
  2. Why must cache designs be compared by average memory access time rather than miss rate alone?
  3. Running two programs alternately on the same core can make each slower than running alone. What is the best explanation from a cache perspective?
  4. Which is the best example of temporal locality?
  5. Scanning the 2D C array a[i][j] with j in the inner loop, as above, tends to be faster than with i in the inner loop. Why?