Lab #11 - Memory Performance and Cache-Friendly-Code

4/21/2004

All the files for this lab are located on monte in ~hollingd/public/lab11.

#include <stdio.h> 
#define SIZE 100
typedef int mtx[SIZE][SIZE];

/* put the transpose of matrix a in b */

void transpose(mtx a, mtx b ) {
  int i,j,k;

  for (i=0;i<SIZE;i++) {
    for (j=0;j<SIZE;j++) {
      b[j][i] = a[i][j];
    }
  }
}

int main(int argc, char **argv) {
  mtx x,y;

  transpose(x,y);

  return(0);
}

You need to determine what effect changing the loop nesting int he transpose function will have on the memory performance using time or gprof. There are a number of issues you need to consider (and evaluate with some experiments):

• The memory access pattern determined by the order of the loops in transpose will alter the stride used in access to the array a.

• The loop order will also determine the stride used to access the array b!

• Each time in the inner most loop of transpose the array a is read from memory (or the cache), and the array b is written with a new value. Part of what you need to determine is whether the write operations or read operations are more significant given the cache architecture of the machine you are running on. This is to be determined by running experiments!

• Obviously the code in transpose needs to be called many times, once is not enough to get any kind of reliable measurement.

• The size of the arrays (the constant SIZE) can have an effect on memory performance (if the arrays can fit in the cache and we run the function many times we should have a very low miss rate).

 
#define SIZE 100
typedef int mtx[SIZE][SIZE];

/* matrix multiplication. c=ab
   assumes that all of the matrices are the same
   size (and square).
*/
void matrix_mult(mtx a, mtx b, mtx c ) {
  int i,j,k;
  /* initialize c to all zeros */
  for (i=0;i<SIZE;i++) 
    for (j=0;j<SIZE;j++) 
      c[i][j]=0;

  /* do the multiplication */

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


int main(int argc, char **argv) {
  int i;
  mtx x,y,z;

  matrix_mult(x,y,z);

  return(0);
}

You need to play with the order of loops again, determining what effect this has on performance. There are additional complications!:

• The memory access pattern for arrays a, b and c are all effected! Note that c is both read and written each time in the innermost loop!

• This function is much slower than transpose, as the runtime of this function depends on SIZE³, where the run time of the transpose function depends on SIZE².