Question

Assume you're using a computer with a 2-way set-associative 32KB cache where writes that miss in the cache are directly written to the next cache hierarchy (write-around policy). Assuming a very large constant n, fill in the loops in a way that minimizes cache misses.

a. for (i = 0; i < n; i++) for (j = 0; j < n; j++)
b. for (j = 0; j < n; j++) for (i = 0; i < n; i++)
c. for (i = 0; i < n; i++) for (j = n-1; j >= 0; j--)
d. for (j = n-1; j >= 0; j--) for (i = 0; i < n; i++)

Answer 1

To minimize cache misses, arrange the loops so that the addresses accessed in each iteration are close to each other. Options b and d would result in a lower number of cache misses.

Step-by-step explanation:

The question is asking how to fill in the loops in a way that minimizes cache misses for a 2-way set-associative 32KB cache with a write-around policy. The answer would be to arrange the loops in such a way that the addresses accessed in each iteration of the loop are close to each other, increasing the likelihood that they will be found in the cache.

a. for (i = 0; i < n; i++) for (j = 0; j < n; j++) - This arrangement will result in a higher number of cache misses because the addresses accessed in each iteration are far apart.

b. for (j = 0; j < n; j++) for (i = 0; i < n; i++) - This arrangement will result in a lower number of cache misses because the addresses accessed in each iteration are closer together.

c. for (i = 0; i < n; i++) for (j = n-1; j >= 0; j--) - This arrangement will result in a higher number of cache misses because the addresses accessed in each iteration are far apart.

d. for (j = n-1; j >= 0; j--) for (i = 0; i < n; i++) - This arrangement will result in a lower number of cache misses because the addresses accessed in each iteration are closer together.