Locality of reference - Temporal locality with loop tiling.

temporal_locality_blocking.c

#include <stdio.h>
#include <time.h>

#define N 1000

#define R 125

int A[N][N], B[N][N], C[N][N];

void init_rand_matrix(int M[N][N])
{
  int i, j;

  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      M[i][j] = rand();
}

int main()
{
  int i, j, k, i1, j1, k1;
  
  clock_t t1;

  init_rand_matrix(A);
  init_rand_matrix(B);

  t1 = clock();
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++)
      for (k = 0; k < N; k++)
        C[i][j] += A[i][k] * B[k][j];

  printf("%f\n", (clock() - t1) / (double) CLOCKS_PER_SEC);

  t1 = clock();

  for (i1 = 0; i1 < N/R; i1++)
    for (j1 = 0; j1 < N/R; j1++)
      for (k1 = 0; k1 < N/R; k1++)
        for (i = R*i1; i < R*(i1+1); i++)
          for (j = R*j1; j < R*(j1+1); j++)
            for (k = R*k1; k < R*(k1+1); k++)
              C[i][j] += A[i][k] * B[k][j];

  printf("%f\n", (clock() - t1) / (double) CLOCKS_PER_SEC);

  return 0;

}