Memory Hierarchy

What is the main purpose of loop blocking (tiling), used for example in matrix multiplication?

  1. ATo compute in small cache-sized blocks and increase data reuse
  2. BTo reduce the number of iterations and hence the branch instructions executed at the end of each iteration
  3. CTo halve total memory usage without changing the order of computation
Show answer and explanation

Answer: A. To compute in small cache-sized blocks and increase data reuse

Computing a large matrix product directly evicts elements before they are reused, forcing repeated reloads from main memory. Loop blocking splits the matrices into small blocks that fit in the cache and finishes the work within each block, reusing loaded data many times and sharply reducing capacity misses. Reducing branches is the goal of loop unrolling, and total memory usage does not change.

  • A. Correct. Computing in cache-sized units increases data reuse.
  • B. Reducing branches is the goal of loop unrolling.
  • C. The order of computation changes, and total memory usage stays the same.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. 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?
  2. What is the main advantage of splitting the L1 cache into an instruction cache (I-cache) and a data cache (D-cache)?
  3. 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?
  4. Why are L1 caches often virtually indexed and physically tagged (VIPT)?
  5. With a cache hit time of 2 cycles, a miss rate of 4% and a miss penalty of 150 cycles, what is the average memory access time in cycles?