matrix addition is pretty simple; see the program below. However, the given addition function matrix_add_double() does not run at full speed.  On the instructors computer, which has 16GB of RAM, the program below shows that the call to matrix_add_double takes 38571 ms, while another, better implementation achieves the same result in 3794.7ms, which is 10.2 times faster! Your job for this exercise is:          • to explain what in the Operating System and/or CPU and/or other part of the system makes the implementation              below go so slowly.          • to fix the code to achieve full speed. Hint: There are two reasons why the code runs slowly. The one reason is related to how virtual addresses get translated to physical addresses, the other reasons is related to another effect in the hardware. Only the performance for the matrix_add_double function() counts for your exam results. You can leave the other parts of the code untouched, but you may also change them. CODE:

Implementing matrix addition is pretty simple; see the program below. However, the given addition function matrix_add_double() does not run at full speed.  On the instructors computer, which has 16GB of RAM, the program below shows that the call to matrix_add_double takes 38571 ms, while another, better implementation achieves the same result in 3794.7ms, which is 10.2 times faster!

Your job for this exercise is:

         • to explain what in the Operating System and/or CPU and/or other part of the system makes the implementation              below go so slowly.

         • to fix the code to achieve full speed.

Hint: There are two reasons why the code runs slowly. The one reason is related to how virtual addresses get translated to physical addresses, the other reasons is related to another effect in the hardware.

Only the performance for the matrix_add_double function() counts for your exam results. You can leave the other parts of the code untouched, but you may also change them.

CODE:

#include <stdio.h>

#include <stdlib.h>

#include <sys/time.h>

#define ROWS (22500)

#define COLUMNS (29500)

#define LIN(m,n,i,j) ((i) + ((m) * (j)))

double scalar_random_double(double a, double b) {

      return a+(b-a)*(((double)rand()) / ((double) RAND_MAX));

}

double *matrix_alloc_double(unsigned int m, unsigned int n) {

      double *res;

      res = (double *) calloc((size_t) (((unsigned long long int) m) * ((unsigned long long int) n)), sizeof(double));

      if (res == NULL) {

            fprintf(stderr, "No memory left\n"); exit(1);

      }

      return res;

}

void matrix_free_double(double *A) {

      free(A);

}

void matrix_random_double(double *A, unsigned int m, unsigned int n, double a, double b) {

      unsigned int i, j;

      for (i=0u;i<m;i++) {

            for (j=0u;j<n;j++) {

                  A[LIN(m,n,i,j)] = scalar_random_double(a, b);

            }

      }

}

void matrix_add_double(double *C, double *A, double *B, unsigned int m, unsigned int n) {

      unsigned int i, j;

      for (i=0u;i<m;i++) {

            for (j=0u;j<n;j++) {

                  C[LIN(m,n,i,j)] = A[LIN(m,n,i,j)] + B[LIN(m,n,i,j)];

            }

      }

}

void matrix_print_double(FILE *stream, double *A, unsigned int m, unsigned int n) {

      unsigned int i, j;

      for (i=0u;i<m;i++) {

           for (j=0u;j<n;j++) {

                  fprintf(stream, "%1.16e", A[LIN(m,n,i,j)]);

                  if (j<n-1u) {

                        fprintf(stream, "\t");

                  }

            }

            fprintf(stream, "\n");

      }

}

double timeval_diff_ms(struct timeval *before, struct timeval *after) {

      long long int s, us;

      s = ((long long int) after->tv_sec) - ((long long int) before->tv_sec);

      us = ((long long int) after->tv_usec) - ((long long int) before->tv_usec);

      if (us < ((long long int) 0)) {

             us += (long long int) 1000000;

             s--;

      }

      return (((double) s) * 1000.0) + (((double) us) / 1000.0);

}

int main(int argc, char **argv) {

      double *A, *B, *C;

      struct timeval before, after;

      double ms;

      FILE *stream;

      srand(42);

      A = matrix_alloc_double(ROWS, COLUMNS);

      B = matrix_alloc_double(ROWS, COLUMNS);

      matrix_random_double(A, ROWS, COLUMNS, -1.0, 1.0);

      matrix_random_double(B, ROWS, COLUMNS, -2.0, 2.0);

      C = matrix_alloc_double(ROWS, COLUMNS);

      gettimeofday(&before, NULL);

      matrix_add_double(C, A, B, ROWS, COLUMNS);

      gettimeofday(&after, NULL);

      ms = timeval_diff_ms(&before, &after);

      matrix_free_double(A);

      matrix_free_double(B);

      stream = fopen("output.txt", "w");

      matrix_print_double(stream, C, ROWS, COLUMNS);

      fclose(stream);

      printf("Matrix addition of two %d * %d matrices took %fms\n", ROWS, COLUMNS,         ms);

      matrix_free_double(C);

      return 0;

}