Locality

This assignment shows the importance of ordering loops the right way.

We have a matrix A of order at least n = 5000 (n rows and columns) in double precision. You may want to read about large arrays in C first. See the C-intro. under the Diary.

Write the following routines. Make simple minded implementations!

row_sum(A, sum, n)  should compute the row sums of the matrix and return the n sums in the array sum.

col_sum(A, sum, n)  should compute the column sums of the matrix and return the n sums in the array sum.

Write a main program along these lines:

• initialize A, A(i, j) = 1.0d0 / (i + j ) in Fortran and A[i][j] = 1.0 / (i + j + 2) in C for example.
   

• call row_sum forty times and measure the elapsed time
   

• call col_sum forty times and measure the elapsed time

Store the sub-programs in a separate file. One of the routines should be considerable slower than the other. Why? Write another version, fast_sum, of the slower one (you may not use extra memory). Try also with no optimization and full optimization.

When you are finished you should be able to fill in the following table: