Memory Hierarchy

When each row of a 2D array is 4,096 bytes (a power of two), walking down a column can cause many misses even though the cache has spare capacity. Which countermeasure is effective?

  1. APadding each row so its size is not a power of two
  2. BChanging the element type to a different type of the same size
  3. CRelocating the whole array so it starts on a large power-of-two address boundary
Show answer and explanation

Answer: A. Padding each row so its size is not a power of two

With rows exactly 4,096 bytes long, elements down a column are spaced by multiples of 4,096, so their index bits are identical and they all map to the same set. Walking more rows than the associativity causes conflict misses even with capacity to spare. Padding each row by about one line shifts the set for each element and spreads them out. Aligning to a power of two leaves the problem intact, and a same-sized type changes nothing.

  • A. Correct. Shifting the row size spreads elements across different sets.
  • B. A type of the same size leaves the addresses unchanged.
  • C. Aligning to a power of two leaves the concentration in one set.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. Roughly how many times longer is a main-memory DRAM access than an L1 cache hit (for typical PC or server CPUs)?
  2. What is the role of the valid bit attached to each cache line?
  3. What is the main effect of a victim cache, a small fully associative buffer that temporarily holds lines evicted from the L1 cache?
  4. In a multilevel cache with an L2 below the L1, what is the L2's main role?
  5. Which describes an inclusive cache, where a lower level (such as L2) contains everything in the upper level (L1)?