Memory Hierarchy

Why does fusing the two loops above into one (loop fusion) tend to be faster when N is large?

for (i = 0; i < N; i++) a[i] = b[i] * 2;
for (i = 0; i < N; i++) c[i] = a[i] + 1;
  1. AThe multiply and add merge into one instruction, halving the computation
  2. Ba[i] is used right after being written, so array a need not be reloaded from main memory
  3. CThe iteration count rises from N to 2N, keeping the pipeline full
Show answer and explanation

Answer: B. a[i] is used right after being written, so array a need not be reloaded from main memory

With separate loops, if all of a written by the first loop does not fit in the cache, the second loop misses as it rereads a from the start. Fused, each a[i] is used in the same iteration right after it is written, so it is reused while still in cache or registers and memory traffic drops. The amount of computation is unchanged, and the iteration count falls from 2N to N.

  • A. The number of operations is unchanged; computation is not halved.
  • B. Correct. Reuse right after writing avoids rereading array a.
  • C. The iteration count falls from 2N to N.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. 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?
  2. In a typical computer's memory hierarchy, which property holds more strongly for upper levels (closer to the CPU)?
  3. Why must cache designs be compared by average memory access time rather than miss rate alone?
  4. Running two programs alternately on the same core can make each slower than running alone. What is the best explanation from a cache perspective?
  5. Which is the best example of temporal locality?