Memory Hierarchy

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?

struct P { float x, y, z, mass; };
struct P p[N];
for (i = 0; i < N; i++)
    sx += p[i].x;
  1. AAs an array of structures, the compiler cannot generate instructions that read only the x field
  2. BSeparate arrays make the floating-point computation more precise
  3. CThe x values are contiguous, so fetched lines carry no unneeded fields
Show answer and explanation

Answer: C. The x values are contiguous, so fetched lines carry no unneeded fields

In an array of structures (AoS), x, y, z and mass form a 16-byte group, so even a loop reading only x wastes three quarters of each 64-byte line. With a structure of arrays (SoA), the x values are contiguous, every fetched line is fully used, and memory traffic drops to about a quarter. It also makes SIMD vectorization easier. Compilers can read x from AoS, and changing the layout does not change numerical precision.

  • A. Compilers can read x from an AoS layout just fine.
  • B. Changing the data layout does not change precision.
  • C. Correct. Only the needed x values are contiguous, so lines are used without waste.
Practice this topic Back to topic

More Memory Hierarchy questions

  1. What is the main advantage of splitting the L1 cache into an instruction cache (I-cache) and a data cache (D-cache)?
  2. 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?
  3. Why are L1 caches often virtually indexed and physically tagged (VIPT)?
  4. 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?
  5. A processor has an average CPI of 1.0 with a perfect cache. Each instruction makes 1.3 memory accesses on average, with a 2% miss rate and a 100-cycle miss penalty. What is the actual average CPI?