0
$\begingroup$

I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out.

For ijk iteration, my slides say that there are 2 loads and 0 stores.

for (i=0; i<n; i++) {
  for (j=0; j<n; j++) {
   sum = 0.0;
   for (k=0; k<n; k++)
     sum += a[i][k] * b[k][j];
   c[i][j] = sum;
  } 
}

Similarly, for kij iteration, my slides say that there are 2 loads and 1 store.

for (k=0; k<n; k++) {
 for (i=0; i<n; i++) {
  r = a[i][k];
  for (j=0; j<n; j++)
   c[i][j] += r * b[k][j];
 }
}

And for jki iteration, my slides say that there are 2 loads and 1 store.

for (j=0; j<n; j++) {
 for (k=0; k<n; k++) {
   r = b[k][j];
   for (i=0; i<n; i++)
    c[i][j] += a[i][k] * r;
 }
}

I believe the loads are counted in each case when data is referred to by calling arr[x][x] on the right hand side of the arithmetic evaluation, which would make two in each case. But how are the stores counted?

$\endgroup$
1
$\begingroup$

It appears that the analysis assumes that integer variables are stored in registers, whereas array elements have to be loaded from and stored to memory. The point you've missed is that the statemnt X += Y requires reading X and then writing the new value of X.

sum += a[i][k] * b[k][j];

This loads a[i][k], loads b[k][j], multiplies them, reads sum, adds sum and the product and writes the result to sum. Two loads, no stores.

c[i][j] += r * b[k][j];

This loads b[k][j], reads r, multiplies them, loads c[i][j], adds the product to it and stores the new value of c[i][j]. Two loads, one store.

c[i][j] += a[i][k] * r;

This is essentially the same as the previous case.

$\endgroup$
  • $\begingroup$ Aha! So when when you're writing back to the sum in the first case, you are essentially "storing" it in the registers, and they do not count as "stores" since they are not technically stored in the memory? $\endgroup$ – Jeremy Dec 13 '18 at 21:36
  • $\begingroup$ @Jeremy I think that's what's going on, yes. $\endgroup$ – David Richerby Dec 13 '18 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.