Question 5. Consider the following code segment

for (k = 0; k < N; k++) for (i = 0; i < N; i++)

for (j = 0; j < N; j++) z[k] = z[k]+x[i][j]*y[i][j];

You are asked to optimize this code using "Tiling" for a cache of size (C = 10, B = 5, S = 5). Here are some facts:

• Each array element is a 32-bit quantity.

• Assume N = 16 in this question.

• As can be seen above, x,y and z are arrays.

• For this question, assume the element x[i][j] is next to the element x[i+1][j] and the element

  y[i][j] is next to the element y[i+1][j] in memory.

• The arrays z[k] and other contents occupy the first half of the cache while the remaining half is

  shared by x[][] and y[][].

  Here is the code after tiling:

  for (ii = 0; ii < N; ii += TF) for (k = 0; k < N; k++)

  for (i = ii; i < ii+TF; i++) for (j = 0; j < N; j++)

  z[k] = z[k]+x[i][j]*y[i][j];

1. (a) Calculate the number of misses to x[][] and y[][] in the original loop.

2. (b) What is the largest values of TF that will cause the minimum number of misses to x[][] and y[][]. How

   many misses are there now?